Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit35476a2

Browse files
committed
Add travelling salesman problem.
1 parent296b20e commit35476a2

File tree

4 files changed

+183
-0
lines changed

4 files changed

+183
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -92,6 +92,7 @@ a set of rules that precisely defines a sequence of operations.
9292
*[Eulerian Path and Eulerian Circuit](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path) - Fleury's algorithm - Visit every edge exactly once
9393
*[Hamiltonian Cycle](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
9494
*[Strongly Connected Components](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/strongly-connected-components) - Kosaraju's algorithm
95+
*[Travelling Salesman Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/travelling-salesman) - brute force algorithm
9596
***Uncategorized**
9697
*[Tower of Hanoi](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/hanoi-tower)
9798
*[N-Queens Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/uncategorized/n-queens)
@@ -105,6 +106,7 @@ algorithm is an abstraction higher than a computer program.
105106

106107
***Brute Force** - look at all the possibilities and selects the best solution
107108
*[Maximum Subarray](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/maximum-subarray)
109+
*[Travelling Salesman Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/travelling-salesman)
108110
***Greedy** - choose the best option at the current time, without any consideration for the future
109111
*[Unbound Knapsack Problem](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/sets/knapsack-problem)
110112
*[Dijkstra Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/dijkstra) - finding shortest path to all graph vertices
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
#Travelling Salesman Problem
2+
3+
The travelling salesman problem (TSP) asks the following question:
4+
"Given a list of cities and the distances between each pair of
5+
cities, what is the shortest possible route that visits each city
6+
and returns to the origin city?"
7+
8+
![Travelling Salesman](https://upload.wikimedia.org/wikipedia/commons/1/11/GLPK_solution_of_a_travelling_salesman_problem.svg)
9+
10+
Solution of a travelling salesman problem: the black line shows
11+
the shortest possible loop that connects every red dot.
12+
13+
![Travelling Salesman Graph](https://upload.wikimedia.org/wikipedia/commons/3/30/Weighted_K4.svg)
14+
15+
TSP can be modelled as an undirected weighted graph, such that
16+
cities are the graph's vertices, paths are the graph's edges,
17+
and a path's distance is the edge's weight. It is a minimization
18+
problem starting and finishing at a specified vertex after having
19+
visited each other vertex exactly once. Often, the model is a
20+
complete graph (i.e. each pair of vertices is connected by an
21+
edge). If no path exists between two cities, adding an arbitrarily
22+
long edge will complete the graph without affecting the optimal tour.
23+
24+
##References
25+
26+
-[Wikipedia](https://en.wikipedia.org/wiki/Travelling_salesman_problem)
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
importGraphVertexfrom'../../../../data-structures/graph/GraphVertex';
2+
importGraphEdgefrom'../../../../data-structures/graph/GraphEdge';
3+
importGraphfrom'../../../../data-structures/graph/Graph';
4+
importbfTravellingSalesmanfrom'../bfTravellingSalesman';
5+
6+
describe('bfTravellingSalesman',()=>{
7+
it('should solve problem for simple graph',()=>{
8+
constvertexA=newGraphVertex('A');
9+
constvertexB=newGraphVertex('B');
10+
constvertexC=newGraphVertex('C');
11+
constvertexD=newGraphVertex('D');
12+
13+
constedgeAB=newGraphEdge(vertexA,vertexB,1);
14+
constedgeBD=newGraphEdge(vertexB,vertexD,1);
15+
constedgeDC=newGraphEdge(vertexD,vertexC,1);
16+
constedgeCA=newGraphEdge(vertexC,vertexA,1);
17+
18+
constedgeBA=newGraphEdge(vertexB,vertexA,5);
19+
constedgeDB=newGraphEdge(vertexD,vertexB,8);
20+
constedgeCD=newGraphEdge(vertexC,vertexD,7);
21+
constedgeAC=newGraphEdge(vertexA,vertexC,4);
22+
constedgeAD=newGraphEdge(vertexA,vertexD,2);
23+
constedgeDA=newGraphEdge(vertexD,vertexA,3);
24+
constedgeBC=newGraphEdge(vertexB,vertexC,3);
25+
constedgeCB=newGraphEdge(vertexC,vertexB,9);
26+
27+
constgraph=newGraph(true);
28+
graph
29+
.addEdge(edgeAB)
30+
.addEdge(edgeBD)
31+
.addEdge(edgeDC)
32+
.addEdge(edgeCA)
33+
.addEdge(edgeBA)
34+
.addEdge(edgeDB)
35+
.addEdge(edgeCD)
36+
.addEdge(edgeAC)
37+
.addEdge(edgeAD)
38+
.addEdge(edgeDA)
39+
.addEdge(edgeBC)
40+
.addEdge(edgeCB);
41+
42+
constsalesmanPath=bfTravellingSalesman(graph);
43+
44+
expect(salesmanPath.length).toBe(4);
45+
46+
expect(salesmanPath[0].getKey()).toEqual(vertexA.getKey());
47+
expect(salesmanPath[1].getKey()).toEqual(vertexB.getKey());
48+
expect(salesmanPath[2].getKey()).toEqual(vertexD.getKey());
49+
expect(salesmanPath[3].getKey()).toEqual(vertexC.getKey());
50+
});
51+
});
Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,104 @@
1+
/**
2+
* Get all possible paths
3+
*@param {GraphVertex} startVertex
4+
*@param {GraphVertex[][]} [paths]
5+
*@param {GraphVertex[]} [path]
6+
*/
7+
functionfindAllPaths(startVertex,paths=[],path=[]){
8+
// Clone path.
9+
constcurrentPath=[...path];
10+
11+
// Add startVertex to the path.
12+
currentPath.push(startVertex);
13+
14+
// Generate visited set from path.
15+
constvisitedSet=currentPath.reduce((accumulator,vertex)=>{
16+
constupdatedAccumulator={ ...accumulator};
17+
updatedAccumulator[vertex.getKey()]=vertex;
18+
19+
returnupdatedAccumulator;
20+
},{});
21+
22+
// Get all unvisited neighbors of startVertex.
23+
constunvisitedNeighbors=startVertex.getNeighbors().filter((neighbor)=>{
24+
return!visitedSet[neighbor.getKey()];
25+
});
26+
27+
// If there no unvisited neighbors then treat current path as complete and save it.
28+
if(!unvisitedNeighbors.length){
29+
paths.push(currentPath);
30+
31+
returnpaths;
32+
}
33+
34+
// Go through all the neighbors.
35+
for(letneighborIndex=0;neighborIndex<unvisitedNeighbors.length;neighborIndex+=1){
36+
constcurrentUnvisitedNeighbor=unvisitedNeighbors[neighborIndex];
37+
findAllPaths(currentUnvisitedNeighbor,paths,currentPath);
38+
}
39+
40+
returnpaths;
41+
}
42+
43+
/**
44+
*@param {number[][]} adjacencyMatrix
45+
*@param {object} verticesIndices
46+
*@param {GraphVertex[]} cycle
47+
*@return {number}
48+
*/
49+
functiongetCycleWeight(adjacencyMatrix,verticesIndices,cycle){
50+
letweight=0;
51+
52+
for(letcycleIndex=1;cycleIndex<cycle.length;cycleIndex+=1){
53+
constfromVertex=cycle[cycleIndex-1];
54+
consttoVertex=cycle[cycleIndex];
55+
constfromVertexIndex=verticesIndices[fromVertex.getKey()];
56+
consttoVertexIndex=verticesIndices[toVertex.getKey()];
57+
weight+=adjacencyMatrix[fromVertexIndex][toVertexIndex];
58+
}
59+
60+
returnweight;
61+
}
62+
63+
/**
64+
* BRUTE FORCE approach to solve Traveling Salesman Problem.
65+
*
66+
*@param {Graph} graph
67+
*@return {GraphVertex[]}
68+
*/
69+
exportdefaultfunctionbfTravellingSalesman(graph){
70+
// Pick starting point from where we will traverse the graph.
71+
conststartVertex=graph.getAllVertices()[0];
72+
73+
// BRUTE FORCE.
74+
// Generate all possible paths from startVertex.
75+
constallPossiblePaths=findAllPaths(startVertex);
76+
77+
// Filter out paths that are not cycles.
78+
constallPossibleCycles=allPossiblePaths.filter((path)=>{
79+
/**@var {GraphVertex} */
80+
constlastVertex=path[path.length-1];
81+
constlastVertexNeighbors=lastVertex.getNeighbors();
82+
83+
returnlastVertexNeighbors.includes(startVertex);
84+
});
85+
86+
// Go through all possible cycles and pick the one with minimum overall tour weight.
87+
constadjacencyMatrix=graph.getAdjacencyMatrix();
88+
constverticesIndices=graph.getVerticesIndices();
89+
letsalesmanPath=[];
90+
letsalesmanPathWeight=null;
91+
for(letcycleIndex=0;cycleIndex<allPossibleCycles.length;cycleIndex+=1){
92+
constcurrentCycle=allPossibleCycles[cycleIndex];
93+
constcurrentCycleWeight=getCycleWeight(adjacencyMatrix,verticesIndices,currentCycle);
94+
95+
// If current cycle weight is smaller then previous ones treat current cycle as most optimal.
96+
if(salesmanPathWeight===null||currentCycleWeight<salesmanPathWeight){
97+
salesmanPath=currentCycle;
98+
salesmanPathWeight=currentCycleWeight;
99+
}
100+
}
101+
102+
// Return the solution.
103+
returnsalesmanPath;
104+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp