LAST MINUTE NOTE: Both Lord_Bitish and Sir_Sot have reported solutions which are 380 long and touch 380 unique points ... both programs are randomized in some way and if you run them enough times, they turn up with different solutions. It just so happens that neither of these programs found the perfect solution in the SINGLE finals run I made. I suspect that some of the other entries were "capable" of finding better solutions had they been run frequently enough.
======================================= Lord_Bitish =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Lord_Bitish 100 380 379 442.05 C Chad Hurritz
=================
Lord_Bitish was submitted by Chad Hurritz at churritz@cts.com
=================
HOW DID Lord_Bitish attack the traveling salesman aspect of the problem?
Because of the 20K source limitation, I decided to start with a large set
of random tours that were improved by two quick functions. FYI, this method
is non-deterministic, but it did not use any AI/GA schemes save chaos.
Usually I'd end up with a multiple of lowest costing tours from this operation,
to which each I would apply the unique move finder.
HOW DID Lord_Bitish deal with the knight's moves? the unique move measure?
Since there is a shortest path in knights moves from every city to every
other city on the grid, that path was the cost used as the TSP cost from city
i to j. Also, since there were at least one path with this shortest cost in
knights moves, there was an opportunity to find more unique moves and avoid
revisitation conflicts. Revisitations were then iterativley isolated out.
(Thus, if there was a revisitation, I would redraw the two, three, or
four edges around the conflict trying not to take the same path twice.)
To help resolve conflicts I also ran each best tour backwards to see if
going the other way would help reduce any revisited moves.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
I hope the final solution is bleedingly difficult.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
(1)program.
(2)program, when i'm not programming i'm mountain climbing at 10K+.
(3)huh?
(4)you wouldn't want to know.
(5)my potm idea would be chessers, a board game you play with chess pieces
and their moves but utilizing checkers piece capturing techniques, so
you wouldn't land on another players space to capture them, you'd have
to jump over the other player's piece.
=================================================================
======================================= Sir_Sot =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Sir_Sot 100 380 378 275.07 C Bob Ashenfelter
=================
Sir_Sot was submitted by Bob Ashenfelter at ash@hotsoup.att.com
=================
HOW DID Sir_Sot attack the traveling salesman aspect of the problem?
As indicated by the questions in this questionnaire, this problem is
basically the standard traveling salesman problem: Given a complete
matrix of distances between a set of target points, find the shortest
path that visits all of them. The requirements of only making knight's
moves and not straying out of the first quadrant are but trifles, as is
the desire to not revisit any point. Sir_Sot's strategy is to first
generate a fairly good solution to the traveling salesman problem, then
improve this solution by various modifications, and finally generate
knight's moves to visit all the target points in the order that has been
determined.
The target points are read in and the "home" point is added to them and
is subsequently treated the same as all the rest. A table of all the
distances between the target points is computed. Distance, of course,
is the minimum number of knight's moves connecting two points. I have
a simple routine for computing distances, but a table look-up is faster.
Also, two values are computed for each target point, the shortest distance
to another point and the sum of the distances to the two closest points.
These are used to truncate searches that are going the wrong way.
To solve the traveling salesman problem Sir_Sot has two "solvers" and
four "improvers". A "solver" starts from scratch and generates a
solution while an "improver" takes a previously generated solution and
tries to make it better. A solution consists of a circular array of
indices to the target points.
The first solver starts from a random point, then goes to one of the
nearest points, then goes to one of the nearest unvisited points, etc.,
until there are no points left. If there are more than one closest
point, then the point farthest from the initial point is chosen. This
minimizes having the last point end up a long way from the first.
The second solver starts with two random points and computes the distance
from one to the other and back. It then adds whatever point increases
the total distance the least. It continues adding points one at a time,
each time choosing the point and the path to insert it in so as to
minimize the total distance added, until there are no points left.
The first improver takes a string of n consecutive points and tries all
rearrangements of these points to get the minimum total distance. It is
implemented by a recursive function and uses the precomputed shortest-
distance values to trim fruitless branches from the search tree. This
procedure can potentially compute the optimum solution, but, as is well
known, the CPU time increases fiendishly with the size of n and this is
what makes the traveling salesman problem famous. In practice, n gets
up to about 15 in the time allowed.
The second improver takes a given point and tries to move it to another
place in the tour so that the total distance is reduced. It is motivated
by the observation that the solvers can bypass one or more points, leaving
them stranded to be picked up at the end regardless of the cost.
The third improver takes a given path (between two consecutive points)
and tries to find another path such that the connections between them
can be interchanged to give a shorter total distance. It is motivated
by the observation that whenever the tour crosses over itself, it can
often be improved by uncrossing it.
There is a fourth improver which is similar to the second except it cuts
out a string of n points and inserts it elsewhere. This has been a
disappointment. While it improves the solution by itself, when in the
presence of the other improvers it never seems to do anything because the
others do it first. It is still in the code, but it is not being used.
There is one more routine which swaps two of three points in a straight
line. It is intended for use in generating moves and will be described
later. However, it very occasionally improves the total distance of the
solution and so it is used as an improver.
So how are these tools used by Sir_Sot? One of the solvers is run a
number of times, the best solution is chosen, and the improvers are run
until there is no more improvement. The same is done with the other
solver. This is repeated with an increasing number of solutions and
with increasingly long strings for the first improver. This continues,
usually until the time limit is half used up. The best solution found
so far is recalled and the improvers continue on alone, again with longer
and longer strings optimized until just before the time limit. At this
point Sir_Sot has usually found its best solution to the traveling
salesman problem.
HOW DID Sir_Sot deal with the knight's moves? the unique move measure?
Now it is time to compute the actual moves that will be used to visit
the target points in the order specified by the solution. This is rela-
tively straightforward so only 2 seconds are reserved for it. A target
point is chosen and a move is chosen randomly from the possible knight's
moves to points that are closer to the next target point in the solution.
This continues until that target point is reached and is then repeated
for each succeeding point in the solution until it gets back to the
first target point. Of course moves out of the first quadrant must
not be chosen and points that have already been visited should not be
revisited unless there are no suitable unvisited points available.
Maximizing the number of unique points hit is the final difficulty. It
may be that a previously chosen move forces a point to be revisited. To
get around this the moves are computed a number of times with random
starting points and both directions around the solution. But it may be
that the solution itself forces revisits. It appears that in most cases
the solution can be reordered to avoid the revisit with no increase in
total distance (i.e. moves). These cases usually seem to arise from a
sequence of three successive target points which are all in a straight
line in the direction of a knight's move. When the solution enters or
leaves the triad at the middle point, that point will have to be re-
visited. But this can be avoided if that point is swapped with one of
the end points and it can be done with no increase in distance. And so
there is a routine, alluded to above, that modifies the solution by
recognizing this condition and swapping the points. This and also the
second and third improvers are run each time the moves are recomputed.
Before seeing the final set, I knew of no case in which this procedure
did not result in the maximum number of unique hits. In most cases no
points are revisited, but there are some configurations in which the
boundary of the territory causes non-unique hits. (I had expected that
Fred would throw in a couple of these. He didn't, actually, but he came
close enough to trip me up!)
All that remains is to print out the moves. The only hitch here is that
"home" has been treated as just another target point and so may have
ended up anywhere in the solution and thus in the list of move points.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
There are some cases (e.g. regular arrays, including the 99-point system
test) in which Sir_Sot can "prove" that it has found an optimum solution
and if so it makes a quick exit. There are other cases that are so simple
(e.g. the 9- and 24-point system tests) that it finds itself repeatedly
generating the same optimum distance and these also cause an early termin-
ation. In most other cases it usually finds its best solution rather
early but it keeps on trying until the time limit runs out, hoping to
find something better.
There are a number of places where Sir_Sot chooses randomly between two
or more seemingly equal choices. In order to make the choice more nearly
random, the random-number generator is seeded with the time of day. Thus
it seldom repeats the same solution with the same input. This allows me
to run it repeatedly and get some idea of what its best performance is and
how likely it is to achieve it.
Sir_Sot has been tested with as many fiendish input sets as I can think
of and it solves most of them handily. The only cases in which it fails
to consistently produce its best solution are those with close to 100
points scattered about randomly. In these cases it usually makes 2 or 4
moves more than it should, with perhaps a 20% chance of finding the best
solution. Exasperatingly, it seems to do almost as well with a short time
limit as with a long one. I anticipated that in this contest there would
be up to a half dozen contestants finding an optimum solution and it would
come down to fastest execution time. It would take some luck, but Sir_Sot
could be among them. Therefore, its time limit was set at between 4 and 5
minutes rather than 10 minutes.
As it turned out, the final set did not include enough random points to
defeat Sir_Sot's ability to solve the traveling salesman problem. But I
obviously underestimated the difficulty of maximizing the number of unique
points visited and didn't give it enough CPU time or, more importantly,
thought. With the final set of target points the traveling salesman
problem is solved in an average of only 5 seconds, seldom more than 10.
However, in 20 runs, the number of unique hits varied from 375 to 380.
The number 379 came up 5 times out of 20 (25%) and would have won because
of my shortened time limit. One run (5%) produced a (presumably) optimum
answer with 380 unique hits which would have won outright. Thus Sir_Sot's
probability of winning was approximately 30 percent. Fred's run produced
the most likely (50%) result, 378, only good enough for second place. It
could have been worse.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Circuit design.
Bicycling, sailing, grow orchids, travel.
DMTS
No way...
See questionnaire for previous POTM.
=================================================================
======================================= veni,vedi,jumpi =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
veni,vedi,jumpi 100 380 378 610.08 C P.Frants S.Pieterse
=================
veni,vidi,jumpi was submitted by P.Frants S.Pieterse at pfrants@cs.vu.nl
=================
HOW DID veni,vidi,jumpi attack the traveling salesman aspect of the problem?
We constructed initial tours using 'nearest neighbour' with different
starting points. The next step was to improve the tour by applying 2-opt until
the tour did not improve anymore. The final step was to apply 3-opt.
This algorithm was applied repeatedly during ten minutes (multistart). After we
ran out of initial tours generated with 'nearest neighbour' we started
generating 100% random tours as initial tours.
HOW DID veni,vidi,jumpi deal with the knight's moves? the unique move measure?
We first reduced the problem to a pure TSP by calculating the shortest
distance between each pair of cities. This was done using dynamic programming
to speed up the process.
The unique move measure was NOT done with backtracking, because we were
afraid Fred would have a testcase where simple backtracking would take too
long. Therefore we simply generated a couple of hundred tours using our
jump-table (If you want to know what that is look at our code) and looking
only one step ahead. From these tours we then chose the best.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
The algorithm is much more important than efficient code. The combination of
2-opt, 3-opt and multistart was quite effective in solving the TSP. Because of
the small number of cities (<= 100) an optimal tour was found quite easily.
Maybe it would have been more fun with more cities...
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
We are both students at the Vrije Universiteit Amsterdam. Who the hell likes to
spend so many nights and days thinking, programming and trying to solve a
problem which is known to be NP-complete... But somehow we managed to have
fun anyway. Next time we'll try to improve our ranking by 2 places. We'll be
back!
Pop-corn accelerates the mind as do AC/DC and Amorphis!
We think the POTM problems are very good. We like search-problems. Keep up the
excellent work, Fred!
=================================================================
======================================= knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
knight 100 380 377 452.96 GCC Staffan Ulfberg
=================
knight was submitted by Staffan Ulfberg
=================
HOW DID knight attack the traveling salesman aspect of the problem?
The program generates random paths which are passed to a Lin-Kernighan
optimization procedure. For 100 random input points, one such pass
takes around .4 seconds on a Sparcstation 10 when the program is
compiled with gcc and no optimization.
HOW DID knight deal with the knight's moves? the unique move measure?
After finding what it thinks is the best route, the knight jumps
around to each location in turn. If there are two possible jumps that
moves the knight equally close to his destination, the one that has
not been visited gets preference. If more than one place to which the
knight considers jumping has not been visited before, the knight makes
a random choice. This is repeated until all moves is to a unique
point, or until it gives up... Well, it's not especially efficient,
but still only takes a fraction of the total running time of the
program. Very easy to implement.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Well, this was all made in a hurry and the code is a mess.
Especially, I hard-coded a table that was first computed at run-time,
and the way this was done was optimized for editing speed:-) The
benefit is only marginal for tough problems, but for the first tests
it made a great difference. I think the hardest thing to decide was
when to stop computing. (How many random path/Lin-Kernighan rounds
should the program compute?) And, hmmm, I'd probably not understand
the Lin-Kernighan part myself anymore:-), but I think it's quite
efficient for small problems, though (n<=100).
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm a graduate student in Theoretical Computer Science at the Royal
Institute of Technology in Stockholm. I thought that was for fun:)
=================================================================
======================================= Knight_Errant =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Knight_Errant 100 380 359 575.43 GCC =Andre Wilhelmus
=================
Knight_Errant was submitted by Andre Wilhelmus at awilhelm@hvscg01.ns-nl.att.com
=================
HOW DID Knight_Errant attack the traveling salesman aspect of the problem?
First the savings method is used.
Then it repeatedly uses 2-opt moves followed by randomizing the
15 points closest to another point until 570 seconds passed.
Then the best solution is printed.
HOW DID Knight_Errant deal with the knight's moves? the unique move measure?
When connecting two points, it tried to evade already occupied points.
It did not try to rearrange two already connected points.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Nope.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Application programmer.
I play adventures at home on a Mac.
Rank?
:-)
No.
=================================================================
======================================= knight_b4_xmas =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
knight_b4_xmas 100 382 378 450.18 C++ Jim Hahn
Sorry ... no description available for knight_b4_xmas
=================================================================
======================================= FeudalExpress =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
FeudalExpress 100 382 377 549.21 C =Vincent Goffin
=================
FeudalExpress was submitted by Vincent Goffin at vjg@mozart.att.com
=================
HOW DID FeudalExpress attack the traveling salesman aspect of the problem?
I reluctantly concluded I'd have to use the full 10 minutes.
I use the first 7 minutes to generate as many random independent solutions
as possible and keep the 10 best.
I generate a random solution by starting with a random minimum spanning tree,
adding a random perfect matching of the odd nodes, finding a random Eulerian
tour, then a Hamiltonian tour (i.e. a solution). This approach is a watered
down Christofides algorithm.
These solutions are not that good but they are relatively fast to generate
and are much better than purely random tours. To improve them I apply some
heuristic optimizations (of random type!) chosen from so called node and edge
insertions and edge reconnections. I apply as many as needed to reach a local
minimum. I chose not to use more sophisticated optimizations because they get
too expensive quickly. Instead I store the solution if it's one of the 10
best so far and go generate another, until 7 minutes are up.
I use the last 3 minutes to try to "breed" the 10 best solutions into improved
solutions. Often this does yield improvements. Something like this is a
nice way to conclude and possibly extend the random search.
HOW DID FeudalExpress deal with the knight's moves? the unique move measure?
The trick here was to calculate the distance matrix (between any 2 sites).
this took me nearly 200 lines of code with umpteen special cases that gave
all the right distances, in one pass. Frustrating, but fast.
My method to avoid revisiting the same sites twice is an approximation.
I have a method that will find a minimum path with a minimum number of
overlaps, but of course this doesn't mean the number is zero. So I iterate.
Once initial paths are selected, I erase them one by one, replacing the with
one of these minimum paths. I continue this for all path segments in a tour
as long as the total number of overlaps decreases.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Thanks Fred, for running this show.
Nearly every potm (including this one) has been an opportunity to read
up on some interesting topic and get some first hand experience with it.
It looks like a game, but you can't get to the finishing line without
some serious work!
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Living: I'm a programmer in Bell Labs Company 2 (at least until Jan 16).
Fun: I enjoy fixing up my old house (90+ years)
Rank: MTS
Innermost secret: huh?
POTM ideas: Remember Rubik's cube? maybe a minimal move cube descrambler.
I think that is still an open question, but it's also close to the previous
cut-shuffle-flip potm.
=================================================================
======================================= gimpy =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
gimpy 100 382 377 600.49 C Don Shugard
=================
gimpy was submitted by Don Shugard at dds@research.att.com
=================
HOW DID gimpy attack the traveling salesman aspect of the problem?
Early on I went with a greedy Kruskal's algorithm. This produced acceptable
results on the small test cases. For the finals I went with an
iterative Lin Kernighan. I couldn't find a good stopping method so
I let it timeout with the hope that it will find a better solution.
HOW DID gimpy deal with the knight's moves?
Precalculated a distance grid. The only distance that had to change was
the distance from (0,0) to (1,1) could not get there in 2 without going out
of bounds. This then gives an absolute distance between points by looking
up their positional differences in the array.
the unique move measure?
I used a breadth first branch and bound approach to move from 1 point to the
next. Cost for each move was based on whether it was a customer, not visited
square or a visited square. Squares outside the 100 x 100 were weighted
more to encourage visitation. I used the distance array to see if the
move progressed 1 closer to the end.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
WHAT DO YOU DO FOR A LIVING?
VLSI designer.
FOR FUN?
Fly radio controlled airplanes.
RANK?
Still trying
INNERMOST SECRET?
Constants aren't. Variables won't.
=================================================================
======================================= muddle_of_the_knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
muddle_of_the_knight 100 382 371 51.47 C Brace Stout
=================
muddle_of_the_knight was submitted by Brace Stout at brace@stoutware.com
=================
HOW DID muddle_of_the_knight attack the traveling salesman aspect
I knew right away that the brute force approach was out of the
question due to the factorial nature of the problem.
My first thought was to find a means for determining the number
of hops to get from one spot to another. I took a brute force
approach to this at first, but later refined it to a function,
which improved the speed of the overall algorithm by about a
factor of three.
There were two phases to my approach. First, I hacked together
a quick and dirty entry, which simply created a cycle using the
first destination, and repeatedly added the destination which
increased the total hops required by the least amount until all
destinations were used. This entry remained in the lists until
the last week of December, doing better than I expected. I
planned on being a 'sleeper', submitting my final 'killer'
version at the end of the contest.
(I'm writing this December 29, and from what I've seen in the
weekly status, I'm afraid my final version will be in the top ten,
but probably won't take first. If I'd only found more time to
work on it...)
Anyway, the final version uses a similar approach, except that
each destination starts out as a cycle having one destination,
((0,0) is automatically a destination), and combining the cycles
until only one cycle remains. A variety of heuristic measures
are used when determining which cycles to combine, and at what
point. These heuristics including the number of hops added by
combining the cycles, the total number of destinations in the
cycles to be combined, and a 'moment', calculated as the sum
of all destination distances from a point.
HOW DID muddle_of_the_knight deal with the knight's moves? unique move measure?
The eight possible moves are represented in a table. A function
determines the minimum number of knight hops between destinations.
Once the path must be generated, a very simple attempt to avoid
stepping on another paths is made. I concentrated on the
traveling salesman portion of the problem, intending to tackle
the unique move measure once I pegged the other, which I never
felt I did.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
I used a 'chessboard' layout as a test vector, since there is
a way to move a knight on a chessboard such that each square is
visited only once. In its various incarnations, my program was
at best able to visit all points with two visited points twice.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm a software systems engineering consultant in Phoenix, AZ.
I graduated in 1983 from Rose-Hulman Institued of Technology in
Terre Haute, IN. I have enjoyed programming since I first used
a computer in college. My latest hobbies include R/C cars,
soprano saxophone, and video/computer games.
My innermost secret will stay that way.
I would like to see Ada / Ada 95 allowed as an implementation
language.
=================================================================
======================================= pendragone =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
pendragone 100 384 379 3.83 C Andrew Gauld
=================
pendragone was submitted by Andrew Gauld at andrew.gauld@att.com
=================
HOW DID pendragone attack the traveling salesman aspect of the problem?
Generated an initial solution by starting at 0,0 and forming a chain by
appending the cheapest next point. Then optimized by reversing a path segment,
moving a path segment, or both - segments found by brute force search.
Far from guaranteed optimal, but it is frequently optimal, and its fast.
HOW DID pendragone deal with the knight's moves? the unique move measure?
Precomputed costs between all pairs of points and stored in a table. Used
formulas for most pairs, special cased (0,0) to (1,1) (cost 4), horizontal or
vertical move by 1 (cost 3), and move diagonal by 2 (cost 4). Moves generated
by most direct move with special case steering for last few steps of the path.
Used a post-processing step to avoid duplicate hits on a single point - only
check moves differing by 2 steps for duplicates.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
=================================================================
======================================= KnightMare =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
KnightMare 100 386 377 501.68 GCC Andreas Eisele
=================
KnightMare submitted by Andreas Eisele at Andreas.Eisele@ims.uni-stuttgart.de
=================
HOW DID KnightMare attack the traveling salesman aspect of the problem?
KnightMare performs a brute force beam search for a good tour. Given N
points P1... PN and a beam width of W, it computes, for increasing i,
up to W distinct partial tours connecting the points P1..Pi. From this
set, all of the i*W possible extensions that include point Pi+1 are
considered and a selection of up to W shortest ones are kept.
This approach has a number of problems. It is rather sensitive to the
order in which the points are presented. Also, a larger beam width
occasionally leads to worse results. Therefore, KnightMare applies
the search using increasing beam widths to a set of presentations of
the point set in various orders, including original order, sorted
according to various directions, and random order. If the search
detects a new shortest tour, this tour is also fed back into the
algorithm in the hope to find even better variations. The search with
increasing beam widths is iterated as long as time is available.
HOW DID KnightMare deal with the knight's moves? the unique move measure?
The distance function d that gives the minimal number of steps needed
to get from point A to B was determined empirically. Given d, planning
actual move sequences is not too difficult: in order to get from A to
B, perform one legal move that decreases the remaining distance, and
iterate.
Optimizing the unique move measure turned out to be pretty difficult
in general, so KnightMare applies only some weak heuristics to avoid
moves to fields which are known to be used in other parts of the
solution.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
JOB: Research, programming work and teaching on natural language
grammar formalisms and processing strategies at the "Institut für
maschinelle Sprachverarbeitung", Universität Stuttgart.
FUN: Talking with my wife, playing with my daughters (2 and 4),
working in our vineyard (not always fun), things like the POTM.
INNERMOST SECRET: When will I finally start writing up my PhD thesis?
I don't know myself, though...
=================================================================
======================================= sellsalot =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
sellsalot 100 392 386 294.12 C Warren Montgomery
=================
sellsalot was submitted by Warren Montgomery at w.a.montgomery@att.com
=================
HOW DID sellsalot attack the traveling salesman aspect of the problem?
The program computes the knights move distance between all required
points in initialization to reduce this to a simple traveling
salesman problem. The points are sorted so that the first N points
are maximally mutually distant (i.e. the first point is furthest
from 0,0, the next further than the rest from 0,0 and the first
point, etc.). With less than 30 points, a pruned exhaustive search
is done for the shortest path. Given a tour for the first N
points, the N+1st point is added at each location to get a tour of
N+1 points, and any tour that already exceeds the shortest tour of
the complete set is discarded. The ordering causes all the distant
points to be considered early and keeps the search reasonably
narrow on most point sets. A simply computed tour visiting the
nearest unvisited point each time is used to provide a reasonable
initial pruning limit. The exhaustive search is limited to 10
seconds, and if it does not complete or more than 30 points are
given, a more limited search is done.
In the limited search, the program computes a "quasi optim" tour of
the first X points, then inserts the remaining points in the tour
inserting each one where it causes the least possible increase in
tour distance. The quasi optimum is computed as above, except that
when deciding whether or not to prune a partially completed tour, a
factor M times the number of points remaining to be added to the
partial tour is added to the distance, on the theory that any
possible extension of this tour will add at least M moves per point
added. The values of X and M are adjusted dynamically, starting
with X=10 and M=0, increasing X after each minimum tour is computed
and increasing M if the previous tour required more than an
certain amount of time (limit dependent on M). (M>2 generally goes
very fast but produces poor results, X<15 generally goes very
fast). If after stepping X from 10 to the number of points 5
minutes has not yet expired, the program picks the best tour with
M>0 and attempts to find a better tour at that X value and lower M.
The algorithm seems to run well on random data, but Fred's diagonal test
case turned up a weakness where a precise pattern must be followed.
HOW DID sellsalot deal with the knight's moves? the unique move measure?
The knights moves were done brute force, by computing the knights
moves distance for every square from 0,0 in initialization, and
using it to quickly look up inter-square distances. Moves between
0,0 and 1,1 were treated as an ugly special case because of the
rule against moving into negative grid positions. Once an optimal
(number of moves) tour was computed, it followed the tour
attempting not to visit a previously visited square. Each leg was
laid out in sequence, using backtracking to try all possible paths
of the minimum length, if necessary, to find one with all
unoccupied squares. If every path crosses occupied squares, one
was selected and the paths crossed would be marked for
reconsideration. After a complete set of paths was computed, any
marked for reconsideration were tried again, trying to avoid all
squares occupied in other paths. This produced repetition free
tours most of the time.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
A good problem. I would probalby have done better spending more
time in the library and less at the keyboard, but I had more fun
that way.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm a Tech Manager in network systems processor/controller
development, and spend more recreation time outside than at the
keyboard. This was a good problem, tough enough not to have
trivial solutions but manageable enough not to require lots of
programming. My number one suggestion is to shorten the contest
period. (I always preferred speed chess to the real thing as
well. I guess I just have a short attention span for things like this).
=================================================================
======================================= hopalong =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
hopalong 100 394 393 125.78 C Dick Bradley
Sorry ... no description available for hopalong
=================================================================
======================================= late_knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
late_knight 100 398 395 342.22 C =Stan Peijffers
=================
late_knight was submitted by Stan Peijffers at speijffe@hvssa01.ns-nl.att.com
=================
HOW DID late_knight attack the traveling salesman aspect of the problem?
It is a branch-and-bound algorithm.
Starting from an initial tour (the "convex hull") cities are included
such that the tour length is minimally increased (greedy strategy).
At each iteration only the best 3 new nodes are examined.
In order to avoid examining the same tours over and over again,
the algorithm requires a check for duplicates. This requires
the tours to be stored in hash tables. Either the algorithm
stops when the whole search tree is examined, or when the hashtables
become full.
This algorithm seems to converge very rapidly to reasonably
good solutions. Normally the algorithm works "from the outside in".
However it cannot be avoided that some cities are "left behind"
(consequence of the greedy strategy). This leads to suboptimal
solutions when these cities have to be included in the tour
very late. Typically what happens is that "crossing edges"
occur which are likely to be not optimal.
To remedy this, once the TSP algorithm has found a solution, an
optimization algorithm is called to fix the crossing edges.
Advantages of this approach (compared to other b&b approaches) :
- the algorithm always finds a solution
- there is no need to worry about ending up with subloops
- algorithm works equally well when cities are clustered
- no need to calculate a lowerbound; lowerbound = length
of the current tour.
Disadvantages :
- requires duplicates checking
- greedy strategy may lead to suboptimal solutions
HOW DID late_knight deal with the knight's moves? the unique move measure?
The knight's moves did not really present a problem : the program
uses a preconstructed table of (relative) distances.
The second algorithm takes as input the result of the TSP algorithm
(after optimization) and determines the optimal path
between cities (pth_search). An
attempt is made to visit as many different squares as possible.
This is done as follows :
Every edge in the tour is given a value which indicates the degree
of flexibility there is in assigning specific sequences of knigth moves
between the 2 nodes (with a maximum value of 9). There are cases where
an edge is broken down in 2 edges by inserting a "virtual city" when
it is discovered that part of the sequence of knight moves is a forced one.
Once virtual cities added and each edge (virtual or real) is given
a "flexibility factor", the final tour is then constructed by building
the knight sequences first for edges with low flexibility and
gradually moving up to edges with higher flexibility.
(So the order is not the order of the edges as they appear in the tour).
For every edge the sequence of knight moves with a maximum of
different (unvisited) squares is selected. This selection is done
by means of a breadth-first search method where the value to be
minimized == 100 * length of the sequence - number of unvisited squares.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Did quite a bit of research. Here are some of the books that were
useful :
- Reinelt - The traveling salesman
- Lawler, Lenstra, etc : The traveling salesman problem.
- Papadimitriou, Steiglitz : Combinatorial Optimization,
- etc.
In the end I decided to pursue my own idea.
Around Christmas time I started investigating solutions based on linear
programming (simplex, branch-and-cut). The first attempts looked very
promising. Unfortunately I didn't have enough time to convert this idea
into a full-fledged working program.
To anyone new to the field of linear programming, I can recommend :
- Hillier, Lieberman : Introduction to Operations Research
(6th edition just appeared).
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Still working on intl 5ESS.
=================================================================
======================================= Neee =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Neee 100 398 391 0.95 C Stuart McDonald
=================
Neee was submitted by Stuart McDonald at smd@hpsqf.sqf.hp.com
=================
HOW DID Neee attack the traveling salesman aspect of the problem?
First it "draws" the smallest convex polygon that joins the outer most
cities. It then draws another polygon around the cities which are enclosed
by that polygon, and so on until all the cities have been visitied. E.g.
Given the following cities (h = home)
h A Then the enclosing polygons would be
B C h A G E h
D B C F B
E F D
G
It then starts with the center polygon, and for each city making up the
polygon it calculates the length of the routes for each of the positions in
the outer polygon that the city can be placed and inserts it in the shortest.
E.g.
Starting with D it would calculate the length of the routes for putting D
between h and A, A and G, G and E, E and h.
So D would be placed between G and E, making the outermost polygon now
h A G D E h
This continues for each of the cities in the center polygon and once they
have been done it proceeds to the next polygon up (e.g. B C F B). Once this
has been done for all the polygons (except the outer one) then the outer
polygon then contains all the cities and forms the route to take.
HOW DID Neee deal with the knight's moves? the unique move measure?
A 2D array holding the number of moves to get to a location was created by
recursively moving from 0,0. This array was 100x100 but also had a 4x4 border
around it which could be visitied (so -3,-3 was a valid location to access
in this array).
The array was used thus: Given two locations (x1,y1) (x2,y2) calculate the
location ABS(x1-x2),ABS(y1-y2). This location in the array gives you the
number of moves to get between those to cities. To calculate the route to take
you simply look at the array entries for the 8 possible moves around this
locations and pick one which has a number of moves one less than the one you
are on just now. So basically you are heading towards the 0,0 location which
has 0 moves.
The array has a border around it which allows you to go negative for the
following reason. Say the locations are horizontally inline with each other,
(50,50) and (90,50) The starting array location would be 40,0, but without
the border then the route taken would never use any of the locations with a
Y less than 50.
One problem with the above is whenever you use the array with the home city
you have to change the entry at 1,1 to be 4 moves instead of 2 (another reason
for the border), bit of a bodge that.....
I duffed up on the unique move measure...What I did was set the top bit of
values in the array when I used that location for a move, and when
calculating the route I would check the 8 locations for one without the top
bit set and if there was one I would use it, otherwise I would use one with
the top bit set. But this doesn't work, because the 100x100 array is not an
array of _absolute_ locations, it doesn't cause any problems though and I
didn't have time to fix it.....
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
My first entry was actually a Genetic Algorthim approach called geKNIGHTic,
but I don't really know anything about genetic algorithmns and it actually
turned out better to start with a "good" path (e.g. closest-first approach)
and randomly change it, keeping the best one.
The main problem was given two routes, how do you "breed" them to produce a
new route which is at least reasonable? I tried just taking a random section
of one route and inserting it into the other, but the new route turns out to
be too far removed from the orignal routes and is almost always longer.
So when that failed I hacked up Neee in 2 days using the route code from
geKNIGHTic. Ironically enough the "polygon" approach of Neee could be used to
solve the problem with the GA, if I have time I may try it......
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Living: Breath, move, you know the usual stuff.
Rank: Graduate Engineer for HP.
Fun: Sex, Cakes, Programming, Hang-Gliding, The Jam.
Secret: I cheated on a class arithmetic test when I was 7 and won a packet
of fruit polos.....
Ideas: Hmmmmmmm, Pass.
=================================================================
======================================= spunky =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
spunky 100 400 392 320.98 C =Neil Weinstock
Sorry ... no description available for spunky
=================================================================
======================================= Horsey =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Horsey 100 402 388 37.08 C Randy Saint
=================
Horsey was submitted by Randy Saint at saint@phoenix.phoenix.net
=================
HOW DID Horsey attack the traveling salesman aspect of the problem?
It found a greedy tour based on an estimate of the number of moves
between the cities. It then tried to improve that by selecting
a group of cities and trying to insert that group elsewhere in the
tour. The size of the group goes from (num_cities-2) down to 1.
HOW DID Horsey deal with the knight's moves? the unique move measure?
Once the tour is selected, Horsey uses an A* branch and bound search
to find the moves between each city.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm a Systems Analyst working in the Advanced Technology Section with Loral
Space Information Systems, Houston TX.
I have a Web page devoted to programming contests. I try to keep it current
with the contests that I know about. It's at:
http://www.phoenix.net/~saint/contests/contests.html
=================================================================
======================================= symphony =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
symphony 100 408 393 136.11 GCC Gerie Alards
Sorry ... no description available for symphony
=================================================================
======================================= up_all_knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
up_all_knight 100 410 382 0.30 GCC Jim Curran
=================
up_all_knight was submitted by Jim Curran at jimc@hercules.cb.att.com
=================
HOW DID up_all_knight attack the traveling salesman aspect of the problem?
First, I divided up all the points into 4 equal-sized triangular quadrants.
If you imagine the letter 'X' inside a box that gives you the layout of the 4
quadrants. Next, I sorted the points to allow a counter-clockwise motion from
quadrant to quadrant. Then, I ran these points (counter-clockwise visits)
through a routine which looked ahead at the cost of a path from
x-a-b-c, x-b-a-c, x-c-b-a
where x is the current location and a,b and c are the next points in the
sorted path. After choosing the best path I moved to the first point in that
"best" path and looked ahead again. This was repeated for each point in
each quadrant. Finally I took the resulting path and ran it through the same
algorithim but clockwise hoping that this would improve the path.
Then I repeated the above two steps except I started out clockwise instead of
counter-clockwise. Of the 4 paths, I chose the least expensive.
My algorithm had a nasty habit of taking undesirable points
"along for the ride". That is, it would decide it couldn't visit a point
but it would continue to compare the cost of visiting that point even though
the knight had exited the vicinity of that point.
HOW DID up_all_knight deal with the knight's moves? the unique move measure?
Basically the knight would look at its position relative to the target point
and choose a move which would get it closest to the target. This was
implemented with a recursive algorithm, one move at a time. When the knight
came within 4 squares of the target it went to a table solution. I developed
4 table solutions for the approaches to a target point. Imagine a 5x5 grid
with one of the corner points on the target point and the knight occupying one
of the remaining 24 positions. I found that I could go from any point in the
5x5 grid to the target in 4 moves or less. I had to develop 4 different
tables (nw,sw,se,ne) because of the constraints that we couldn't move into the
negative areas. I struggled with this at first coming up with this so I'd
like to see how others did it.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
I concentrated on making the move cost calculation code speedy (because that's
what I like to do) with the expectation that I could call it lots and lots
in an effort to find a short path without losing out in the timing category.
I never got around to writing a decent path optimization which really needed
the calculation speed. But I had a good time anyway.
I also avoided stdio in favor of mmap and write but I'm not sure how much time
that bought me.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Software developer for the total network management (TNM) project here at AT&T
in Columbus.
I guess I write programs for fun...
It would be cool to work on POTM problems (like this one) which can be depicted
graphically. I used gnuplot to view my results which gave me near-instant
gratification in seeing my progress.
=================================================================
======================================= Day_Tripper =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Day_Tripper 100 432 418 6.51 C Tommy Six
Sorry ... no description available for Day_Tripper
=================================================================
======================================= HardDaysKnight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
HardDaysKnight 100 436 427 320.77 C Joe Eccles
=================
HardDaysKnight was submitted by Joe Eccles at joe@mink.mt.att.com
=================
HOW DID HardDaysKnight attack the traveling salesman aspect of the problem?
KNIGHT'S DISTANCE METRIC
Essential to the methods used was to know the knight's distance between any
two points. This can be done by recursively generating a matrix of distances
from (0,0). Simple mark all legal moves from 0,0 with '1', then all legal moves
from those spaces with '2', etc., until all spaces of interest are filled.
(You need to fill a couple of rows and columns beyond 99 to allow since some
paths may lead you beyond those limits.) The resulting matrix gives you the
proper distance between any two points except for a change of 1 diagonally.
Such a move has a knight's distance of 2 except when the move is between
(0,0) and (1,1), where the distance is 4 due to the prohibition against moving
into negative corrdinates. With this matrix, the total tour length can be
calculated for any given ordering of points. Thus the problem becomes one of
finding the proper order in which to visit the 'cities', and the actual set
of moves is never generated until the `optimal` order is found.
BACKGROUND
Just to be different, I decided to approach this problem as though it were
a molecular dynamics problem, similar to the problem of how to determine the
way a protein folds itself in space. There are rough equivalences in the
problems. For a protein it is relativly easy these days to determine the list
of thecomponent acids that make up the chain and their order (primary structure)
The problem is to determine to way these chains fold on themselves (secondary
structure) and the way groups of chains aggregate (teritary structure) to
minimize total energy. With the traveling knight problem, we know the list of
cities to be visited (primary structure) and need to determine the order to
visit them in to minimize the number of moves (secondary structure) and the
steps taken between cities to maximize the number of spaces visited in that
total number of moves (tertiary structure).
To accomplish this I used analogies to some standard methods from molecular
dynamics.
- Local minimization using the method of steepest decent.
- Searching using Metropolis (Monte Carlo) methods.
- Global minimizaton using simulated annealing.
LOCAL MINIMIZATION
A number of methods were used to generate guesses to the optimal ordering, and
then in each case, 'speepest decent' was used for 'local optimization.' The
steepest decent procedure was to sort by making a swap of the pair that
resulted in the greatest decrease in the tour length, and then repeating the
process until to single swap would decrease the length. This doesn't give a
'global minimum' since it is easy to get into configurations where all single
swaps increase the distance, but some swap of three or more `cities` would
decrease the length. The `steepest decent' approach generally did better than
a simple sort strategy of swapping any pair found if that decreased the length.
SPECIAL CASES
Some special cases were identified and specific solutions applied. For instance,
a specific solution was identified for the 'all on the diagonal' case.
INITIAL GUESS
An initial guess of the optimal order was generated by picking from the
remaining input set the closest (knight's distance) point to the last one
picked, followed by the 'steepest decent' sort.
SEARCH
Random generation of the order of visits to cities, followed by local
optimization is an effective way of searching for an optimal solution.
The procedure is simply to use a random number generator to determine to
choose the order, perform the 'steepest decent' sort on the result, and
keep it if this is the shortest length found so far. This is repeated
for some number of random guesses.
SIMULATED ANNEALING
In molecular dynamics, one standard method of dealing with the problem of local
minima is to model heating the material to a point that it has enough energy to
get over any local barrier, and then cool it to trap it in another (hopefully
lower) local minimum, repeating the procedure to try to identify the optimal
minimum. Heating implies providing additional velocity to the components using
a gaussian (bell curve) distribution. A random gaussian is easily computed
by taking the average of a number of uniform random numbers - in my case,
averaging six values returned by 'rand()'. The more numbers averaged, the
narrower the distribution.
For a given 'temperature', generate a (gaussian) random number in the
range of (-temp, +temp), and for each 'city' exchange it with the 'city' that
far down the array. A narrow gaussian maximizes the probability of no exchange
or exchange with adjacent 'cities', so as not to totally randomize the
array. The order is then 'cooled' by using the 'steepest decent' sort. This
is done for some set of 'temperatures' ranging from 2 to (number of cities)/4.
HOW DID HardDaysKnight deal with the knight's moves? the unique move measure?
The knight's moves were only generated after the "optimal" order of "cities"
had been determined. At each point, the list of all legal knights moves
[(delta x, delta y) = (-1, -2), (-1, +2), ... ]
was generated, and those that did not decrease the knight's distance to the
next target were discarded. Out of the remaining list, a space was selected
that had not yet been visited (if such a space existed). This scheme can be
extended to avoid travelling to unvisited spaces that force future moves to
visited spaces - most easily by backtracking if a such an unwanted move is
the only one available, but this was not implemented due to lack of time.
This scheme does not deal with the possibility that two equally short tours
exist, one of which cannot be made without revisiting a space more than once.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
The methods used will never deterministically find the true optimal solution.
Since I can never tell if the best solution I have found is optimal or not,
deciding when to terminate the random search or the annealling search is
based on empirical experience.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Obviously I'm a frustrated physicist.
=================================================================
======================================= red_eye =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
red_eye 100 436 415 1.49 C Davor Slamnig
=================
red_eye was submitted by Davor Slamnig at slama.pub.hr!slama@ig2.att.att.com
=================
HOW DID red_eye attack the traveling salesman aspect of the problem?
1. All the distances between all the points are determined
using the "jump-table" described in the next section, and
stored in an array (the elements contain the distance between two
particular locations and the location's indexes).
2. The array is sorted in respect to distance (shortest connnection
first).
3. A solution path is built by adding the connections from the
array (sequentially, starting from the shortest connection).
Before actually adding the connection to the path, a check is made
whether the connection is valid (e.g. the connection is not valid if
one of the points is already connected to two other locations, or the
resulting path connects start and end locations without visiting all
the locations, or if it closes a loop).
4. The actual moves connecting the points in the solution path
are calculated.
HOW DID red_eye deal with the knight's moves? the unique move measure?
A "jump-table" is calculated at program start. It's a 2D integer array,
sized 201 x 201. The location 100,100 is marked as 0. All the possible
knight jumps from that position hold the value 1, all possible jumps
from these locations are marked as 2 (if not already marked), and so
on. It looks like this (the center portion):
7 6 7 6 5 6 5 6 5 6 5 6 5 6 5 6 5 6 7 6
6 7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 6 5 6 7
7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 4 5 6 5 6
6 5 6 5 4 5 4 3 4 3 4 3 4 3 4 5 4 5 6 5
5 6 5 4 5 4 3 4 3 4 3 4 3 4 3 4 5 4 5 6
6 5 4 5 4 3 4 3 2 3 2 3 2 3 4 3 4 5 4 5
5 6 5 4 3 4 3 2 3 2 3 2 3 2 3 4 3 4 5 6
6 5 4 5 4 3 2 3 4 1 2 1 4 3 2 3 4 5 4 5
5 6 5 4 3 4 3 2 1 2 3 2 1 2 3 4 3 4 5 6
6 5 4 5 4 3 2 3 2 3 0 3 2 3 2 3 4 5 4 5
5 6 5 4 3 4 3 2 1 2 3 2 1 2 3 4 3 4 5 6
6 5 4 5 4 3 2 3 4 1 2 1 4 3 2 3 4 5 4 5
5 6 5 4 3 4 3 2 3 2 3 2 3 2 3 4 3 4 5 6
6 5 4 5 4 3 4 3 2 3 2 3 2 3 4 3 4 5 4 5
5 6 5 4 5 4 3 4 3 4 3 4 3 4 3 4 5 4 5 6
6 5 6 5 4 5 4 3 4 3 4 3 4 3 4 5 4 5 6 5
7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 4 5 6 5 6
6 7 6 5 6 5 4 5 4 5 4 5 4 5 4 5 6 5 6 7
7 6 7 6 5 6 5 6 5 6 5 6 5 6 5 6 5 6 7 6
The moves that connect two locations are calculated in reverse.
Translate the two points so that one of the points ends up
at 100,100 (marked as 0). The other point's value (N) represents the
distance between the two points (in knight jumps). Jump from this
point (marked as N) to any other point marked as N-1. Then decrement N
by 1 and jump again until you arrive at zero.
This guarantees the shortest path between the two points (and is quite
fast). The rule that forbids visiting negative locations neccessitates
some special case processing.
The table calculation takes up a significant portion of red_eye's
processing time. In normal circumstances I'd have a precalculated table
file and load it on program start - but that was a POTM no-no.
Red_eye does some unique-location optimization using another 2D table,
which marks used locations and avoids them in subsequent moves if
possible.
WHAT DO YOU DO FOR A LIVING? FOR FUN?
I'm a C/C++ UNIX/MS-Windows/MS-DOS programmer, doing contract work for
local companies here in Zagreb (Croatia), and for a few UK-based firms.
Also, I'm a professional composer, guitar player and writer (lit).
What I do for fun is in mostly in these areas, too.
=================================================================
======================================= lancelot =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
lancelot 100 438 436 0.73 C Matt Cross
=================
lancelot was submitted by Matt Cross at mcross@sw.stratus.com
=================
HOW DID lancelot attack the traveling salesman aspect of the problem?
In the simplest possible manner - find the next closest 'goal' (next
customer or home if no more customers), then go there.
HOW DID lancelot deal with the knight's moves? the unique move measure?
I made a small set of structures to easily identify the locations that
could be reached via 1, 2, or 3 knights moves, which included the
final destination and all the possible moves to get there. When
deciding on which path to take, I first found the shortest way to get
where I wanted to go, then I scored all the possible paths using a
similar method to your scoring method, and took the path with the
highest score. If the space could not be reached within 3 moves, I
would move one knight's move in the direction that came closest to the
current goal.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
This plan works well for dense configurations, but the lack of long
distance planning shows with some of the more spread out
configurations (notably the (1,1) to (99,99) test points).
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
For a living, I port, maintain, and improve VOS, Stratus's proprietary
operating system.
For fun, I program in contests, [try] to build small robots, fight in
the SCA, and hang out with my wonderful wife.
POTM idea: Ever seen the game 'freecell' for Windows? A program to
solve that game would be neat. Or, a program to play 'minesweeper'.
Something along the lines of 'corewars' would also be interesting.
=================================================================
======================================= k-thing =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
k-thing 100 444 431 1.36 C Martin Kealey
=================
k-thing was submitted by Martin Kealey at martin@kurahaupo.gen.nz
=================
HOW DID k-thing attack the traveling salesman aspect of the problem?
Kthing keeps a table of "chains", where a point may be a
singleton (not connected to any chain) or a end or intermediate
member of a chain. To end or singleton points are selected to be
joined together on the basis of being in the greatest degree
nearer to a point than the third nearest to that point.
This methodology is suitable to an annealing type process, where
noise is intially added and the progressively removed over many
iterations, to find global minima; however this implementation
makes only a single attempt to find a solution (I ran out of time
to include this aspect).
One advantage of a single-shot method: it is quite fast - running
on my i486 DX33 here got run times of 1 - 2 seconds for sets of
100 random points, with one or two fewer unique hits than the
optimum. I think that puts it in the top half dozen scorers at
least.
HOW DID k-thing deal with the knight's moves? the unique move measure?
The route finding and move generation are two completely separate
phases (although it is possible for certain critical combinations that it
might be better to allow feedback).
The unique move measure is only half-heartedly supported,
basically by attempting to travel down the leftmost path
available, which tends to produce differentiating paths back and
forwards. This isn't perfect, so some randomizing is added,
which seems to improve the hit rates on average.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
I explored using an ordered heap, except that the overhead of
maintaining it sorted was more than gained when extracting
entries, mainly because the data structures to cope with
double-indexed entries were several times the size of this
program. Actually, I started by working on this, and eventually
gave up as it was clear that MANY points would have to be removed
& reinserted into the heaps each join, which would defeat the
point of having them there to start with. So, I just reverted to
brute force.
My function to calculate the number of moves between two points
was contructed by checking against a table-generating function
(which ran a LOT more slowly). The basic algorithm for this is
to check first for moves in the vacinity of 0,0, which differ
from the expected results from the rest of the calculation. Then
to normalise the vector between the two points into the +,+
quadrant, then to normalise further to one half of the quadrant
(so that y>0, y>x>0), then to select either orthogonal or
diagonal measurement depending on whether x>x*2.
The code assumes 2-s complement integers, since it uses "x&1" for
"x%2" and "x&~1" for "x-x%2". A decent optimiser ought to be
able to do this for me, but I don't trust it.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
* Programming.
* Designing programs.
* Hacker in the original sense of the word, or Guru depending
on your point of view.
* I used to write z80 programs directly in octal
* (1) The Pentominoes puzzle (12 pieces each 5 squares to be
fitted in 5x12 rectangle)
(2) Maybe I'll think of something next week?
=================================================================
======================================= lurch =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
lurch 100 450 446 0.54 C Phong Vo
Sorry ... no description available for lurch
=================================================================
======================================= K =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
K 100 450 433 0.16 C David Wales
=================
K was submitted by David Wales at david.wales@waii.com
=================
HOW DID K attack the traveling salesman aspect of the problem?
In general look for 'nearest' that hadn't been visited so far. Of
course 'nearest' in cartesian space is not the same in knight space,
which caused most of the problems.
This was my first stab, assuming that I was going to do more. In fact
apart from some little heuristics this was my final stab too - time
just slipped away before Christmas!
HOW DID K deal with the knight's moves? the unique move measure?
Choose the knight move that most reduces the distance to the point. If
there is a choice of moves choose one that visits an unvisited
square. Continue until within 3 squares of the destination, then use a
lookup table to determine the moves necessary to end at the
point. There might be a number of possible final routes, so use a
scoring system to choose which one to take i.e. an unvisited square
was worth one, an unvisited sales point was worth 999. These values
were preset in a matrix representing the whole surface.
At each move mark off the visited square from the matrix.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Had been meaning to add a simulated annealing wrap around all of
this. (honest! :-). Starting from an intial path, new paths would be
generated randomly and tested for performance against the original. I
had intended to do this by exchanging adjacent points on the path, or
by swapping sections of the path. ( ref. Numerical Recipes in C ).
Looking at the final run times I guess others, including the winners,
did something along these lines.
Apart from that - lookup tables are important in reducing run times.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Software Engineer, Western Geophysical, programming geophysical
interpretation tools for the seismic industry. For fun I'm trying to
improve my Chinese and teach my 11 year old son C.
=================================================================
======================================= cagey_knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
cagey_knight 100 456 434 372.19 C Kunal Ghosh
Sorry ... no description available for cagey_knight
=================================================================
======================================= NightMother =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
NightMother 100 456 432 0.38 G++ Emery Lapinski
Sorry ... no description available for NightMother
=================================================================
======================================= horseplay =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
horseplay 100 484 468 562.05 C++ Stu Rowland
=================
horseplay was submitted by Stu Rowland at swr@mtatm.att.com
=================
HOW DID horseplay attack the traveling salesman aspect of the problem?
Horseplay uses a two pronged approach. The first part is a steepest
descent approximation arrived at by simply interchanged pairs of
cities. This is used as a threshold for the second step which is a
breadth first search which keeps the first N smallest sequences at each
step in the search. N was empirically determined such that a 100 city
list could be solved in just a little under 10 minutes.
HOW DID horseplay deal with the knight's moves? the unique move measure?
A 100x100 knights distance matrix is precomputed. By putting one city
at the origin and using the positive difference of the x and y
coordinates, the distance to the other city is a simple looked up.
The only exception, which is handled separately, is when the cities
have a positive difference of (1,1) and neither is the origin. In that
case, the distance is 2, not 4. The same matrix is used to move from
one city to another just by following the sequence of decreasing
distances. Flips and rotates are used to keep away from negative
coordinates.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Unlike the usual POTM contest, I found this one rather uninteresting.
It is just a time bounded traveling salesman problem, a problem that is
known to be NP complete. The knights move aspect is a trivial twist on
the problem.
=================================================================
======================================= ig-knighted =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
ig-knighted 100 488 464 320.91 C Alfredo Machuca
Sorry ... no description available for ig-knighted
=================================================================
======================================= oyster_knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
oyster_knight 100 562 561 34.41 PERL Gary Gressel
==============================================
oyster_knight was submitted bu Gary Gressel at gressel@onac02.attmail.com
==============================================
HOW DID oyster_knight attack the traveling salesman aspect of the problem?
Basically brute force. I look for the nearest point and go for it and
continue doing such until I run out of points. Then I go back to home.
No fancy sorts, trees, or other algorithms. Basically I wanted to see PERL
in the list of entries this time. Next time I'll devote some time to the
task.
HOW DID oyster_knight deal with the knight's moves? the unique move measure?
A routine checks validity of movement (above negatives basically) and
determines distance to points. Points within (+/-8,+/-8) matrix are
pre-determined by a matrix, after that I just do a straight line
distance calculation.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
Nothing this time.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm a system admin/programmer for AT&T. For fun I've started model training--
figured that should get me away from the computer tubes for a few years.
=================================================================
======================================= knightshift =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
knightshift 99 386 371 63.71 GCC Ag Primatic
=================
knightshift was submitted by Ag Primatic at ag@emailbox.att.com
=================
HOW DID knightshift attack the traveling salesman aspect of the problem?
knightshift used simulated annealing (adapted from Numerical Recipies
in C) to find the best path. After the best city order was
calculated, the path was traced using a pre-computed set of optimal
directions from one position to another.
HOW DID knightshift deal with the knight's moves? the unique move measure?
The knight's moves were pre-computed into an array. The only special
case was the move between 0,0 and 1,1. This was hard-coded in the
distance function.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
I realized that the move array only had to include one quadrant. The
other three quadrants were mirror images of the first.
I had an idea of how to maximize the number of unique cities visited
by keeping all possible move paths in a linked list, and running the
annealer one more time over the universe of possible paths, but I
didn't have time to implement it.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
MTS HW Engineer for QUEST in AT&T Bell Labs.
New POTM idea--natural language processing. How about a program that
accepts a restricted set of english statements and converts them to a
C program?
=================================================================
======================================= hop_skip_and_jump =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
hop_skip_and_jump 99 416 402 478.63 C Alex Popiel
=================
hop_skip_and_jump was submitted by Alex Popiel at popiel@nag.cs.colorado.edu
=================
HOW DID hop_skip_and_jump attack the traveling salesman aspect of the problem?
I used two methods to attack the travelling salesman problem:
1) In early versions, hop_skip_and_jump built a table of all of the
sites and the distances to others sites (and the other sites themselves,
listed in cheapest to most expensive order). It would then start at 0,0
and generate a path using the cheapest segments to unused sites. This
would result in a fairly good initial guess for a path, which was then
improved by changing the order of site traversal (by removing and re-adding
sites on the end of the path in a depth-first search with pruning).
2) In later versions, hop_skip_and_jump replaced the initial guess with
a method that used the shortest segments overall, piecing them together
to form a path over the entire set. This resulted in a much better
initial guess. The segments were then traded out in a depth-first
search with pruning.
HOW DID hop_skip_and_jump deal with the knight's moves?
Given the sequence of sites for the above, I then did a simple depth-first
search for the path with the fewest duplications; I dealt with the knight-
moves in the routine that generated possible children of any particular
state.
the unique move measure?
I dealt with the move measure by reducing it to a set of table lookups
(which table (of four) determined by a very few simple tests). The
tables were as follows:
dx = abs(x1-x2)
dy = abs(y1-y2)
table 1: dx < 6 && dy < 6 && (x1 == y1 == 0 || x2 == y2 == 0)
table 2: dx < 6 && dy < 6 && !(x1 == y1 == 0 || x2 == y2 == 0)
table 3: dx > 2 * dy || dy > 2 * dx
table 4: everything else
Note that the first two tables differed only in one value (the value
at 1,1) and were indexed by [dx,dy]. The third and fourth tables were
each reduced to two rows; the third table was indexed by [major axis,
minor axis &1]; the fourth table was indexed by [dx+dy, (dx+dy) &1].
Note also that the tables took up just over 1K of space, and choosing
between them and computing the indicies took between 8 and 9 operations.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
If reasonable, segregate the problem into smaller parts to reduce
search time. Since I searched on each of the order of sites to visit
and the actual steps to visit those sites independantly, my search
times were significantly reduced.
Use a good algorithm. Algorithms will help more than tight code.
Use a profiler. Optimize only the code which is taking lots of time.
Multiplying by a power of two is faster than multiplying by other
numbers. Many compilers translate this to a shift even with
optimization off. Remember this when sizing your multidimensional
arrays.
Make no assumptions about the input unless it is specifically stated
in the problem or the clarifications. If handling a wierd special
case complicates your code, ask a leading question which might get
the special case outlawed. (I tried to get an input set of only one
site outlawed, but wasn't able to. I have a special test for that
case.)
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm an undergraduate university student (soon to graduate, I hope!)
majoring in computer science. I also do various consulting and
programming on the side.
My free time (what's that?) is spent socializing (with humans, even!),
playing games (with a large section of RPGs, mostly 2nd edition Ars
Magica), and programming. I've been known to dance and climb wimpy
mountains, too.
My rank is (depending on which context you ask) student, member of
the PennMUSH Development Team, Joint Venturer with Chaco Communications,
husband, or friend.
Secrets? If I had secrets, I probably wouldn't mention them in a
public forum. ;-)
Ideas? Sorry, I used them all up on the ACM locals.
=================================================================
======================================= to_B_or_to_A =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
to_B_or_to_A 0 -1 0 4412.67 G++ David Roe
Sorry ... no description available for to_B_or_to_A
=================================================================
======================================= gareth =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
gareth 0 0 0 0.00 GCC Andrew Shaw
=================
gareth was submitted by Andrew Shaw at shaw@kauai.lc.att.com.
=================
HOW DID gareth attack the traveling salesman aspect of the problem?
Found the shortest distance between each pair of customers and
then applied greedy algorithm. If total tour was more than
optimal tour (sum of internode 2-shortest-distances over 2),
then permute tour looking for shorter one. Never implemented
this permutation, though, as the time was excessive without.
HOW DID gareth deal with the knight's moves? the unique move measure?
Used A* to find shortest path between each pair of nodes. This
was not the best approach, obviously. For unique moves, once I
had a shortest tour, I would have depth-first searched along the
tour applying different moves from the set for each leg, back-
tracking the case of a conflict. Didn't get to do this, either.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
=================================================================
======================================= Good_Knight =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
Good_Knight 0 0 0 0.00 C Scott Everett
Good_Knight was submitted by Scott Everett at severett@intgp1.att.com
=================
HOW DID Good_Knight attack the traveling salesman aspect of the problem?
My first attempt was to construct all possible minimum routes. Thus,
if there were three points that were all distance of 6 from the 0,0
start point the program tried all three points as possible start moves.
This was not sufficient, so I allowed for some non-locally optimum moves.
This worked for few numbers of points, but the
program dumped core on large numbers of points because it ran out of memory.
I had several good ideas to improve this part of the program, but
I never had time to implement them.
Anyway, the program generated a list of paths it thought would work
and then they were each examined to find which yielded the BEST route.
I timed the execution of each aspect of the program, such as table
generation, etc. to find where most time was being spent and only
worked at optimizing the algorithms in those locations. This
provided the best improvements in execution time for the least effort.
HOW DID Good_Knight deal with the knight's moves? the unique move measure?
The program constructed a table of all possible knight moves within a distance
of 5 spaces from a central point. This table was extremely useful for choosing
a unique path among equally long paths. I used a simple algorithm to get within
a distance of 5 moves. It was very easy for the program to choose unique paths
to get within range, since there were so many possible routes.
I created a 105x105 table and initialized it to zero using memset(). When the
program generated a move, it marked the location in the table where it had been.
This allowed the router to ignore paths that had already been used UNLESS that
path resulted in a minimum path, since shortest path was more critical than
unique points hit.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
The important point to get started on this problem was to have the
program understand how a knight moves, and for it to be able to
calculate distances between two points using such moves. Once this
part of the program was generated, the rest of the problem
could be visualized as how to move in a straight line between points
and find the best route. It was not necessary to be concerned with
the details of the knight moves, since the program to handle this was
already created. Distance measurements were in terms of moves. The table
of possible moves from a central point was critical to this design, since
I did not have to constantly re-generate this information. I was able
to plug in a modified co-ordinate set and the table kicked out a
distance between the points.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I am a software developer for the ATM GlobeView-2000 project.
=================================================================
======================================= SaintGeorge =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
SaintGeorge 0 0 0 0.00 C George Newsome
=================
SaintGeorge was submitted by George Newsome at gnewsom@hotair.att.com
=================
HOW DID SaintGeorge attack the traveling salesman aspect of the problem?
Borrowed a public domain TSP solver and provided a new cost function which
calculated the a -> B cost based on knoghts move.
HOW DID SaintGeorge deal with the knight's moves? the unique move measure?
Brute force. Starting at a point A, select the legal move going in the
right direction and chain from there. This had some problems ar ther
board edge, and I wonder wether that problem caused the illegal move
failure you found.
I forced unique moves by recognising that there are very many equal cost
paths between almost any two points. The last step, printing the actual
route, disallowed points already used. If no new path could be found, then
the collision was accepted as I judged lower cost as higher priority that
no collisions.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
I learned a lot from this dabble with graph theory including some stuff I
might even be able to use! Because I pinched a solver (and fixed a bug
in it!) I haven't any strategy to offer anyone else. I'm very interested
in seeing how the very fast solvers went about it!
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
I'm involved in forward looking software engineering activities. mainly
interested in infrastructures for distributed systesm and environments
for composition and software construction.
Fun? Enjoy walking with the outing club, doing trail clean ups, writing
to senators, the president on environmental issues. Try to keep
tropical fish, fix up the house, yard etc. Read alot (at times). Try
to pay for Tim to get through CMU! Innnermost secret - I must have
been an idiot to move to the USA with a pre college family!
I liked that TSP problem alot. Pehaps a network flow problem could be equally
enjoyable.
=================================================================
======================================= knightcrawler =============
=================================================================
ENTRY CITIES PTS U-PTS secs. Code Author
knightcrawler 0 0 0 0.00 G++ Rob Creager
=================
knightcrawler was submitted by Rob Creager at robc@bigb.stortek.com
=================
HOW DID knightcrawler attack the traveling salesman aspect of the problem?
1) Build a matrix of distances between all cities.
2) From where we currently are, find the closest city and go there,
saving the move made. Loop until all cities visited.
HOW DID knightcrawler deal with the knight's moves? the unique move measure?
1) From the list of 8 possible moves from current position to
destination, chose the one with the most moves left. If move produces
a valid position, mark it, else go to next one in the list. (Note the
checking for a valid wasn't in the prog sent in - But I thought it
was. The tour generated by a working program is (on a sparc 5):
best path is 456 moves
Cities not hit 0
Cities visited 451
Brute tour 2147483647
10.640u 0.200s 0:12.56 86.3% 0+727k 0+0io 0pf+0w
2) Check a grid which keeps the cities visited. If the move marked
above produces a move to an unvisited city use it, otherwise check
another move. If no moves get us to an unvisited city, use the move
from above.
ANY OTHER COMMENTS, TRICKS, HELP FOR THE UNWASHED, WHATEVER?
1) I was really happy with the algorithm to choose an unvisited city,
and couldn't come up with a good (and quick/easy to implement)
algorithm to choose the city tour.
WHAT DO YOU DO FOR A LIVING? FOR FUN? RANK? INNERMOST SECRET? POTM IDEAS?
Embeded system programmer. Whatever it takes (R/C Sailplanes & cars,
program, read, volleyball, ski, marine fish...). Software developement
engineer. I have no secrets... I had one once, but forgot it.
=================================================================