Show code
<think>
Okay, I need to create a self-contained HTML file that animates a traveling salesman problem solution using the 2-opt algorithm on 60 random cities. The user specified it should start with a nearest neighbor tour, then apply 2-opt swaps, highlighting the edges being tested. When a swap improves the tour, it should visually show the "untangling" of the crossing. Also, it needs to display the current tour length and the number of improvements made. The animation should use requestAnimationFrame, no user input, auto-start, and restart when done. All in under 7000 characters.
Hmm, first, the HTML structure. I'll need a canvas and some div elements for the length and improvements. The canvas will handle the drawing. The JavaScript part has to be concise. Let me outline the steps:
1. Initialize the canvas and context.
2. Generate 60 random cities.
3. Create the initial tour using the nearest neighbor algorithm.
4. Implement the 2-opt algorithm with animation.
5. Animate the swapping edges and the tour updates.
6. Keep track of the tour length and improvements.
7. Handle animation frames with requestAnimationFrame.
8. Restart when the improvements stop.
Starting with the random cities: I'll use Math.random() to place points on the canvas. The nearest neighbor starts at a random city, then adds the closest unvisited city each step.
For the 2-opt, I need to loop through all pairs of edges, check if swapping them improves the tour. When a swap is found, animate the reversal. The tricky part is the animation frames. Each step of the 2-opt should wait for a frame to draw the edges being considered, then if swapped, draw the new path with the reversed segment.
I need to structure the code so that each animation frame either processes a step of the 2-opt or restarts. The animation loop will alternate between processing the swaps and rendering the current state.
Variables needed: cities array, tour array (indices of the cities), current tour length, improvements counter, and animation state variables like current indices being tested (i,j), whether a swap is happening, etc.
To animate the swapping, when a swap is made, the segment from i to j is reversed, so during animation frames, we can draw the reversed path step by step? Or maybe just redraw the path once the swap is done. But the user wants to highlight the edges being tested. So during testing, the two edges (between i and i+1, j and j+1) are drawn in a different color, then when swapped, the new edges are drawn.
Wait, the problem says when a swap is done, redraw the reversed segment so the crossing untangles. So perhaps when a swap is found, the reversed segment is animated? Maybe not necessary to animate each step, just show the before and after in quick succession.
Hmm, the animation should be smooth using requestAnimationFrame. So each frame, we can process a small part of the 2-opt steps. Since the 2-opt could take many iterations, we need to structure it so that each animation frame handles a few iterations to prevent blocking the UI.
Alternatively, each frame could handle one swap step. To do that, we can loop through the possible edges incrementally. For example, keep track of the current i and j indices being checked, increment them each frame until done, then reset the problem.
Wait, the problem states to "repeatedly apply 2-opt", so perhaps it's a loop over all possible 2-opt moves until no more improvements. But to animate this, we can't do all steps at once, so we have to process one candidate swap per animation frame, or a few.
Let me think about how to structure the code. The main loop could be inside requestAnimationFrame. The function would do something like:
- If currently testing a swap, highlight the edges, then check if swap improves the tour.
- If improvement, animate the swap by redrawing the path with the reversed segment.
- Keep track of how many improvements have been made.
- Once no more improvements, reset the cities and start over.
But how to handle the timing? Each swap step (testing the edges and deciding to swap) would need to be done at each frame, but spread out so that it doesn't freeze.
Alternatively, each frame processes a single 2-opt move (check one pair of edges, decide swap). Since 60 cities have O(n^2) edges, that might take too long. Maybe it's better to process a small number of steps per frame, then continue until all pairs are checked once, then repeat until no more improvements.
But the total number of iterations could be large. Maybe the 2-opt is applied until no more improvements, but with a maximum number of passes? Not sure. The problem says to "repeatedly apply 2-opt" until finished, so perhaps it stops when a full pass through all possible edges finds no improvements.
So, the algorithm steps would be:
1. Generate cities and initial tour.
2. Compute initial tour length.
3. Until no more improvements:
a. Iterate over all possible pairs of edges (i,j)
b. For each pair, compute the new tour if swapped
c. If shorter, swap the segment and note improvement
d. Repeat until no improvement in a full pass.
But this is computationally intensive. For 60 cities, the number of edge pairs is (60 choose 2) which is 1770, so each full pass is O(n^2). To animate this, each frame would handle a few pairs, so that after many frames, a full pass is done.
So structuring the code to loop through all possible (i,j) pairs, incrementally. Let's say each frame processes one (i,j) pair. We can have variables tracking current i and j. For each frame:
- Get the next i and j (start from 0,0, then go through all combinations)
- Check the current pair.
- If swap improves, update the tour, increment improvements, and redraw.
- Keep going until all pairs have been checked without improvement.
But how to track when to restart? Maybe after a full pass with no improvements, then reset the cities and start again.
Now, to display the improvement count and tour length. We need to update those text elements each frame.
Also, for the animation of the edges being tested, when checking a pair (i,j), the code would highlight the two edges. So, during the frame when that pair is being evaluated, the current edges between i and i+1, and j and j+1 are drawn in a different color (like red). Then, when a swap is done, the new edges (i to j and j+1 to i+1?) need to be drawn to show the untangling.
Wait, in 2-opt, the edges between i and i+1 and between j and j+1 are removed, and replaced with edges between i and j and between i+1 and j+1. So the segment from i to j is reversed.
Therefore, when a swap is made, the path between i and j is reversed, changing the direction from i to j+1. So visually, that would "untangle" any crossing lines.
To show this, when a swap is made, the segment between the two edges should be redrawn with the reversed order. So, the animation code would need to redraw the path with the reversed segment.
Putting this together, here's a rough code outline:
- The canvas is initialized, ctx, etc.
- Variables for cities (array of objects with x,y), tour (indices), length, improvements, etc.
- Functions for calculating distance