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 email@example.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 firstname.lastname@example.org ================= 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 email@example.com ================= 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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.com ================= 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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ============================================== 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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 email@example.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 firstname.lastname@example.org ================= 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. =================================================================