Animated Travelling Salesman Problem Solver written in TS generators
HTML 2.93%JavaScript 0.30%TypeScript 94.31%SCSS 2.46%typescript
tspsolver's Introduction
Travelling Salesman Problem Solver
Introduction
This project provides a visual overview of several graph algorithms, namely: Depth-First Search, Dijkstra algorithm, Minimum Spanning Tree solver, and Travelling Salesman Problem solver
Random Seed: random seed for the map generator (should be a prime number)
Start City: city number where the salesman starts (range 1 - #number of cities)
Visual Speed: speed of the visual window
Cities Density: density of cities (maximum number is 22)
Walls Density: density of walls (maximum amount is 80% of all blocks)
Start button will run the simulation
Visual Speed can be adjusted at any time
The webpage is responsive and should work on mobile phones too
Known Limitations
the canvas always re-renders the full map, no matter what has or hasn't changed - if we'd only re-rendered the changed tiles (would need some kind of memorizer), it would speed up the visual part especially for bigger maps
the problem, however, is the scaling -> for instance, the size of each block can be 23.13 x 23.13 (instead of 23x23) - it's better for blurring when the browser window is scaled, but it makes impossible to re-render only changed tiles (as the tiles might have shared borders)
Flow
A generator will generate a random map
The Salesman (a white circle) will explore the map
Dijkstra algorithm will find the best path to the first city
The Salesman will walk to the first city
MST algorithm will generate a minimum spanning tree
TSP algorithm will find an optimal solution on how to visit the cities
The Salesman will endlessly travel between cities in an optimal way
Canvas
each cell has a label with its coordinates and cities have numbers (this feature is disabled for maps where at least one size is greater than 20 cells)
for some phases, the algorithm displays backtrace that leads to the previous milestone
milestones are used by DFS algorithm whenever the Salesman arrives at a cell from which there are more paths
node-ts for running TypeScript from NodeJS (used only for the performance test)
parcelJS for bundling (it parses the index.html and compiles everything that is attached to it, including SASS and TS files)
Project Structure
project
│
└───docs // screenshots
│
└───src // source code
│ │
│ └───algorithms // implementation of all algorithms
│ │
│ └───renderers // graphical part (canvas and UI renderer)
│ │
│ └───structs // data structures and interfaces
│ │
│ └───tests // automated tests
│ │
│ │ index.ts // main entry for the web app
| | runner.ts // state machine that handles the whole flow
|
| index.html // html layout
| jest.config // config for jest tests
| package.json // npm scripts and dependencies
│ README.md // readme
│ styles.scss // SASS styles
│ README.md // README file
│ tsconfig.json // typescript config
Architecture
architecture-wise, the project follows a hybrid object-oriented approach with functional programming where it came in handy
all algorithms are implemented as generators, so that they can be easily interrupted
the whole flow is implemented as a state machine (runner.ts) that can run either inside an EventLoop (implemented by CanvasRenderer) or during a single loop (implemented by PerformanceLooper for performance tests)
every single state represents one part of the flow
for instance, ExploreState will initialize the algorithm, repeatedly call its generator, and return back reporting data that will be used by the CanvasRenderer
CanvasRenderer uses a simple endless loop where it calls the state machine and collects data for rendering
when any of those states returns null, the state machine will move on to the next state
Algorithmic Details
Helping Structures and Algorithms
Coord
2D coordinates
note that some parts use indices and some parts 2D coordinates
all arrays are one-dimensional. Therefore, the algorithms need to recalculate 2D to 1D and vice- ersa
Random Number Generator
in algorithms/random-generator.ts
a simple Multiply-with-carry random generator. Implemented for the ability to use a random seed repeatedly
Priority Queue
a simple FIFO queue with priorities for Dijsktra search
Stack
a simple LIFO stack for DFS
State Machine
a state machine with the possibility to be notified when a transition has taken place
Random Map Generator
in algorithms/map-generator.ts
a simple map generator that tries to generate a random map with a given number of cities and walls
it guarantees that there is a path between each two cities. However, it doesn't guarantee that all cells can be visited
walls are more likely put nearby other walls (e.g. 78% chance if there are 3 walls nearby)
Known Issues
the generator is not very good for maps with a dense amount of walls, as it spends a lot of time trying to remove some of them to make all cities visitable
the distribution of walls still looks too random. A more natural solution would be a simplex noise, voronoi cells, and the like.
Map Exploration
in algorithms/map-explorer.ts
uses a variation of a Depth-First Search algorithm. It basically simulates the movement of ants.
whenever there is a cell from which there are more cells to visit, we create a "milestone" and put it onto a stack
to speed things up, when we are going back, the milestones around which all walls have already been visited, are discarded
works quite well for any map
the algorithm uses two sets: visited nodes and explored nodes. If we enter a cell, all surrounding cells will be marked explored
for exploration, we can use even diagonal cells. For movement, however, we can only go up, down, left, and right
the order in which the neighbors are taken into consideration is important, as it dictates how the algorithm will search the map
note: the fact that we consider even diagonal cells when exploring the neighbourhood, saves us some revisiting, yet it doesn't have very significant impact - you can try yourself in map-explorer.ts, instead of currentTile.neighborsArr, choose the directionalNeighbors attribute
Known Issues
in some instances, when the map has almost been explored, there may remain a few unexplored "islands". The problem is that the algorithm doesn't know how to get to these islands, and starts backtracking until it explores the map completely
this results in weird "dizzy" movement. A solution could be to perfrom Dijkstra or AStar on a partially explored map
Dijkstra Search
in algorithms/path-finder
a basic implementation of Dijkstra pathfinding algorithm with a priority queue
a heuristic function is the number of steps - to make one step, it takes cost = 1
Known Issues
as it is a standard implementation, it always explores the full map, even if there can't be any better solution - it doesn't take into consideration the Euclidean topology of the map
a solution would be to stop the algorithm when the current cost-so-far is the same as the Manhattan distance between both points - this could save a few iterations on very sparse maps
Minimum Spanning Tree
in algorithms/mst-finder.ts
this algorithm uses Dijkstra to calculate the closest path from each city to all other cities
the output of this algorithm is a list of spanning trees for all cities that can be further used by TSP Solver
Travelling Salesman Problem Solver
in algorithms/tsp-solver.ts
an NP-complete problem solver that consumes an enormous amount of memory and takes ages to complete
we used dynamic programming with some recursive relation of sub-problems
for n cities, there are O(n * 2^n) subproblems
the total complexity is O(n^2 * 2^n) which is really terrible, but still better than O(n!)
to make the implementation as fast as possible, the algorithm uses bit masks and sparse arrays to memorize the subproblems. There are no 2D coordinates, only an array of permutations stored in bit masks
Known Limitations
even with dynamic programming, it is insanely slow (see the performance test below)
since it uses a bit array, the theoretical maximum number of cities is 64, yet with a common setup (2GB memory and i7 CPU), you will hardly go past 25 cities
the current algorithm expects that a minimal path from city A to city B can be different than the path from B to A, which is not our case. Therefore, it could have run a bit faster if this was taken out
note: the visual part can be sped up significantly, if you move the yield operator in tsp-solver.ts to the parent loop. It won't look that visually pleasing, but for cities > 15, it will speed up the run by 50%!
Tests
Automated tests
all algorithms and data structures have a few tests in the tests folder
Performance Testing
there are two main bottlenecks: map generator (rationale are described above) and TSP (of course)
all tests were conducted without the visual layout, on Intel Core i7-6800K 3.40 GHz, 6 Cores
note that the visual part runs significantly slower, as it has to render the data
Common Variations
Dijkstra that searches for the way back and the MST generator didn't have any significant contributions to the total time
the following table displays the runs for various configurations of the map size, cities and walls
map generator seems to take the most time, yet since its complexity is not exponential, TSP takes over when the number of cities exceeds 15
a reasonable configuration seems to be mapSize ~ 20 x 20 with up to 50% walls and 15 cities - here the report shows varying results, probably due to certain bias that was introduced by randomness
Map Size
Cities (num)
Walls
Generator / explore / TSP / total (ms)
5x5
2
0
5 / 1 / 1 / 10
5x5
2
10
2 / 1 / 1 / 5
5x5
2
20
5 / 1 / 1 / 10
5x5
3
0
0 / 3 / 1 / 5
5x5
3
10
1 / 3 / 5 / 10
5x5
3
20
0 / 0 / 1 / 1
5x5
4
0
0 / 0 / 2 / 3
5x5
4
10
0 / 0 / 1 / 1
5x5
4
20
1 / 0 / 1 / 3
10x10
3
0
1 / 1 / 0 / 3
10x10
3
40
2 / 0 / 0 / 3
10x10
3
80
10 / 0 / 0 / 12
10x10
5
0
1 / 0 / 0 / 3
10x10
5
40
2 / 0 / 0 / 4
10x10
5
80
7 / 0 / 0 / 8
10x10
7
0
1 / 1 / 0 / 3
10x10
7
40
2 / 2 / 1 / 5
10x10
7
80
8 / 0 / 2 / 10
20x20
5
0
4 / 2 / 1 / 10
20x20
5
160
27 / 1 / 1 / 30
20x20
5
320
145 / 1 / 2 / 157
20x20
9
0
2 / 3 / 2 / 10
20x20
9
160
27 / 1 / 3 / 32
20x20
9
320
72 / 0 / 1 / 75
20x20
13
0
2 / 5 / 26 / 50
20x20
13
160
27 / 1 / 14 / 43
20x20
13
320
105 / 1 / 17 / 125
30x30
7
0
6 / 12 / 3 / 27
30x30
7
360
104 / 5 / 2 / 127
30x30
7
720
484 / 4 / 2 / 492
30x30
13
0
7 / 10 / 19 / 43
30x30
13
360
107 / 1 / 17 / 131
30x30
13
720
488 / 1 / 19 / 513
30x30
19
0
8 / 10 / 2587 / 2615
30x30
19
360
120 / 4 / 2501 / 2630
30x30
19
720
535 / 2 / 2520 / 3061
TSP test
there seems to be a boundary after which the complexity explodes - in this case it's around 18 cities
note that TSP doesn't work with the whole map, only with cities. Therefore, the number of walls doesn't have any significancy to the test.