kdtree.w,v

Lin-Kernighan heuristic for the TSP and minimum weight perfect matching

head	1.165;
access
	david
	neto;
symbols
	zero-five-zero:1.165
	zero-four-seventeen:1.165
	zero-four-ten:1.159
	zero-four-nine:1.159
	zero-four-eight:1.159
	zero-four-five:1.159
	zero-four-zero:1.159;
locks
	neto:1.165;


1.165
date	98.10.10.19.25.16;	author neto;	state Exp;
branches;
next	1.164;

1.164
date	98.10.09.21.34.29;	author neto;	state Exp;
branches;
next	1.163;

1.163
date	98.10.09.21.19.30;	author neto;	state Exp;
branches;
next	1.162;

1.162
date	98.10.09.19.19.24;	author neto;	state Exp;
branches;
next	1.161;

1.161
date	98.10.09.16.47.34;	author neto;	state Exp;
branches;
next	1.160;

1.160
date	98.10.08.20.01.35;	author neto;	state Exp;
branches;
next	1.159;

1.159
date	98.07.16.21.58.55;	author neto;	state Exp;
branches;
next	1.158;

1.158
date	98.02.13.21.16.55;	author neto;	state Exp;
branches;
next	1.157;

1.157
date	97.10.25.21.44.06;	author neto;	state Exp;
branches;
next	1.156;

1.156
date	97.10.25.19.49.11;	author neto;	state Exp;
branches;
next	1.155;

1.155
date	97.10.18.15.23.37;	author neto;	state Exp;
branches;
next	1.154;

1.154
date	97.10.18.14.40.25;	author neto;	state Exp;
branches;
next	1.153;

1.153
date	97.10.18.14.31.05;	author neto;	state Exp;
branches;
next	1.152;

1.152
date	97.10.17.21.48.51;	author neto;	state Exp;
branches;
next	1.151;

1.151
date	97.10.17.20.47.35;	author neto;	state Exp;
branches;
next	1.150;

1.150
date	97.09.27.18.06.44;	author neto;	state Exp;
branches;
next	1.149;

1.149
date	97.08.15.20.18.25;	author neto;	state Exp;
branches;
next	1.148;

1.148
date	97.05.16.18.11.41;	author neto;	state Exp;
branches;
next	1.147;

1.147
date	97.01.21.21.55.55;	author david;	state Exp;
branches;
next	1.146;

1.146
date	97.01.21.17.42.14;	author david;	state Exp;
branches;
next	1.145;

1.145
date	97.01.17.21.15.44;	author neto;	state Exp;
branches;
next	1.144;

1.144
date	96.12.13.15.08.17;	author neto;	state Exp;
branches;
next	1.143;

1.143
date	96.12.02.15.26.06;	author neto;	state Exp;
branches;
next	1.142;

1.142
date	96.11.11.16.36.44;	author neto;	state Exp;
branches;
next	1.141;

1.141
date	96.09.03.15.14.03;	author neto;	state Exp;
branches;
next	1.140;

1.140
date	96.08.16.13.04.53;	author neto;	state Exp;
branches;
next	1.139;

1.139
date	96.08.16.12.42.26;	author neto;	state Exp;
branches;
next	1.138;

1.138
date	96.08.15.14.20.27;	author neto;	state Exp;
branches;
next	1.137;

1.137
date	96.08.15.12.54.30;	author neto;	state Exp;
branches;
next	1.136;

1.136
date	96.07.30.17.15.34;	author neto;	state Exp;
branches;
next	1.135;

1.135
date	96.07.30.13.03.33;	author neto;	state Exp;
branches;
next	1.134;

1.134
date	96.07.30.12.59.52;	author neto;	state Exp;
branches;
next	1.133;

1.133
date	96.07.29.17.08.56;	author neto;	state Exp;
branches;
next	1.132;

1.132
date	96.07.29.16.19.56;	author neto;	state Exp;
branches;
next	1.131;

1.131
date	96.07.26.16.19.54;	author neto;	state Exp;
branches;
next	1.130;

1.130
date	96.07.26.15.41.44;	author neto;	state Exp;
branches;
next	1.129;

1.129
date	96.07.26.13.44.55;	author neto;	state Exp;
branches;
next	1.128;

1.128
date	96.07.26.13.21.36;	author neto;	state Exp;
branches;
next	1.127;

1.127
date	96.07.26.12.45.03;	author neto;	state Exp;
branches;
next	1.126;

1.126
date	96.07.25.14.02.54;	author neto;	state Exp;
branches;
next	1.125;

1.125
date	96.07.25.12.09.27;	author neto;	state Exp;
branches;
next	1.124;

1.124
date	96.07.24.15.57.27;	author neto;	state Exp;
branches;
next	1.123;

1.123
date	96.07.24.15.48.46;	author neto;	state Exp;
branches;
next	1.122;

1.122
date	96.07.24.13.51.38;	author neto;	state Exp;
branches;
next	1.121;

1.121
date	96.07.15.22.28.48;	author david;	state Exp;
branches;
next	1.120;

1.120
date	96.07.15.21.18.21;	author david;	state Exp;
branches;
next	1.119;

1.119
date	96.07.15.18.33.24;	author david;	state Exp;
branches;
next	1.118;

1.118
date	96.07.15.16.00.08;	author david;	state Exp;
branches;
next	1.117;

1.117
date	96.07.15.15.23.55;	author david;	state Exp;
branches;
next	1.116;

1.116
date	96.07.05.21.02.33;	author david;	state Exp;
branches;
next	1.115;

1.115
date	96.07.05.20.34.02;	author david;	state Exp;
branches;
next	1.114;

1.114
date	96.07.05.20.31.31;	author david;	state Exp;
branches;
next	1.113;

1.113
date	96.07.05.17.13.32;	author david;	state Exp;
branches;
next	1.112;

1.112
date	96.07.04.20.07.38;	author david;	state Exp;
branches;
next	1.111;

1.111
date	96.06.28.14.00.54;	author neto;	state Exp;
branches;
next	1.110;

1.110
date	96.06.28.12.58.29;	author neto;	state Exp;
branches;
next	1.109;

1.109
date	96.06.26.12.15.42;	author neto;	state Exp;
branches;
next	1.108;

1.108
date	96.06.26.12.08.19;	author neto;	state Exp;
branches;
next	1.107;

1.107
date	96.06.26.12.05.44;	author neto;	state Exp;
branches;
next	1.6;

1.6
date	96.06.26.12.02.28;	author neto;	state Exp;
branches;
next	1.5;

1.5
date	96.06.26.11.38.41;	author neto;	state Exp;
branches;
next	1.4;

1.4
date	96.06.26.11.36.29;	author neto;	state Exp;
branches;
next	1.3;

1.3
date	96.06.25.17.10.15;	author neto;	state Exp;
branches;
next	1.2;

1.2
date	96.06.25.16.41.37;	author neto;	state Exp;
branches;
next	1.1;

1.1
date	96.06.24.17.16.26;	author neto;	state Exp;
branches;
next	;


desc
@K-d search structure.  See Bentley's work.
@


1.165
log
@Support ATT as well.
If only quadrant 0 then use very tight search bounds.
The kd bin comparison functions needed to be fixed: they now bring
equal cities together.  (This was a bug within the last couple of
revisions)
@
text
@


\noindent Copyright \copyright 1994, 1995, 1996, 1997, 1998 David Neto
\smallskip

\noindent 
   This library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public
   License as published by the Free Software Foundation; either
   version 2 of the License, or (at your option) any later version.
\smallskip

\noindent 
   This library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.
\smallskip

\noindent   
   You should have received a copy of the GNU Library General Public
   License along with this library; if not, write to the
   Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA  02111-1307, USA.
\smallskip

\noindent   
   You may contact David Neto via email at {\tt netod@@@@acm.org}, or with
   greater latency at
\smallskip
\noindent{\obeylines
     Department of Computer Science
     University of Toronto
     10 King's College Rd.
     Toronto, Ontario
     M5S 3G4
     Canada
}
\medskip


\noindent\hbox{}\hrule\hbox{}\penalty-1000
\vskip0.5cm\relax



@@i webdefs.w
@@i types.w



{\obeylines
$Log: kdtree.w,v $
Revision 1.164  1998/10/09 21:34:29  neto
Better cutoff value

Revision 1.163  1998/10/09 21:19:30  neto
Fixed case where only one quadrant neighbour in each direction.

Revision 1.162  1998/10/09 19:19:24  neto
Added test driver for bulk searches.
This appears to work.

Revision 1.161  1998/10/09 16:47:34  neto
Added changes need for bulk neighbour searches.

Revision 1.160  1998/10/08 20:01:35  neto
Make quadrant mask really a module (static) variable.
Will now do bulk builds.

Revision 1.159  1998/07/16 21:58:55  neto
Added the LGPL notice in each file.