Skip to content

Commit 3ce847d

Browse files
Sarthak950Sarthak950
authored
Implement Travelling Salesman Problem codesONLY#32 (codesONLY#89)
* Traveling Salesman Problem Solution * solution for maze in DFS BFS and A* search
1 parent 0db5af8 commit 3ce847d

15 files changed

Lines changed: 1045 additions & 0 deletions

‎DSA/Graphs/Maze.js‎

Lines changed: 209 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,209 @@
1+
const maze = [
2+
['S', 0, 1, 0, 1],
3+
[0, 1, 0, 0, 0],
4+
[0, 0, 1, 1, 0],
5+
[1, 0, 0, 0, 'E'],
6+
];
7+
8+
9+
function solveMazeDFS(maze) {
10+
const rows = maze.length;
11+
const cols = maze[0].length;
12+
13+
function dfs(x, y) {
14+
if (x < 0 || x >= rows || y < 0 || y >= cols || maze[x][y] === 1) {
15+
return false;
16+
}
17+
18+
if (maze[x][y] === 'E') {
19+
return true; // Reached the end of the maze
20+
}
21+
22+
maze[x][y] = 1; // Mark as visited
23+
24+
// Explore in all four directions (up, down, left, right)
25+
if (dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1)) {
26+
return true;
27+
}
28+
29+
maze[x][y] = 0; // Mark as unvisited if no path was found
30+
return false;
31+
}
32+
33+
// Find the start point
34+
let startX, startY;
35+
for (let i = 0; i < rows; i++) {
36+
for (let j = 0; j < cols; j++) {
37+
if (maze[i][j] === 'S') {
38+
startX = i;
39+
startY = j;
40+
break;
41+
}
42+
}
43+
}
44+
45+
// Call DFS from the start point
46+
if (dfs(startX, startY)) {
47+
return "Maze is solvable.";
48+
} else {
49+
return "Maze has no solution.";
50+
}
51+
}
52+
53+
console.log(solveMazeDFS(maze));
54+
55+
56+
57+
58+
function solveMazeBFS(maze) {
59+
const rows = maze.length;
60+
const cols = maze[0].length;
61+
const queue = [];
62+
63+
// Find the start point
64+
let startX, startY;
65+
for (let i = 0; i < rows; i++) {
66+
for (let j = 0; j < cols; j++) {
67+
if (maze[i][j] === 'S') {
68+
startX = i;
69+
startY = j;
70+
break;
71+
}
72+
}
73+
}
74+
75+
// Define possible moves (up, down, left, right)
76+
const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
77+
78+
queue.push([startX, startY]);
79+
80+
while (queue.length > 0) {
81+
const [x, y] = queue.shift();
82+
83+
if (maze[x][y] === 'E') {
84+
return "Maze is solvable.";
85+
}
86+
87+
maze[x][y] = 1; // Mark as visited
88+
89+
for (const [dx, dy] of moves) {
90+
const newX = x + dx;
91+
const newY = y + dy;
92+
93+
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && maze[newX][newY] === 0) {
94+
queue.push([newX, newY]);
95+
}
96+
}
97+
}
98+
99+
return "Maze has no solution.";
100+
}
101+
102+
console.log(solveMazeBFS(maze));
103+
104+
105+
class PriorityQueue {
106+
constructor() {
107+
this.elements = [];
108+
}
109+
110+
enqueue(element, priority) {
111+
this.elements.push({ element, priority });
112+
this.elements.sort((a, b) => a.priority - b.priority);
113+
}
114+
115+
dequeue() {
116+
return this.elements.shift().element;
117+
}
118+
119+
isEmpty() {
120+
return this.elements.length === 0;
121+
}
122+
}
123+
124+
function heuristic(x1, y1, x2, y2) {
125+
// A simple heuristic function (Manhattan distance)
126+
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
127+
}
128+
129+
function solveMazeAStar(maze) {
130+
const rows = maze.length;
131+
const cols = maze[0].length;
132+
133+
// Find the start and end points
134+
let startX, startY, endX, endY;
135+
for (let i = 0; i < rows; i++) {
136+
for (let j = 0; j < cols; j++) {
137+
if (maze[i][j] === 'S') {
138+
startX = i;
139+
startY = j;
140+
} else if (maze[i][j] === 'E') {
141+
endX = i;
142+
endY = j;
143+
}
144+
}
145+
}
146+
147+
const openSet = new PriorityQueue();
148+
openSet.enqueue({ x: startX, y: startY, cost: 0 }, 0);
149+
150+
const cameFrom = {};
151+
const gScore = {};
152+
153+
gScore[`${startX}-${startY}`] = 0;
154+
155+
while (!openSet.isEmpty()) {
156+
const current = openSet.dequeue();
157+
const { x, y } = current;
158+
159+
if (x === endX && y === endY) {
160+
// Reconstruct the path
161+
const path = [];
162+
let currentNode = { x: endX, y: endY };
163+
while (currentNode) {
164+
path.unshift(currentNode);
165+
currentNode = cameFrom[`${currentNode.x}-${currentNode.y}`];
166+
}
167+
return path;
168+
}
169+
170+
for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
171+
const newX = x + dx;
172+
const newY = y + dy;
173+
174+
if (
175+
newX >= 0 &&
176+
newX < rows &&
177+
newY >= 0 &&
178+
newY < cols &&
179+
maze[newX][newY] !== 1
180+
) {
181+
const tentativeGScore = gScore[`${x}-${y}`] + 1;
182+
183+
if (
184+
!gScore[`${newX}-${newY}`] ||
185+
tentativeGScore < gScore[`${newX}-${newY}`]
186+
) {
187+
cameFrom[`${newX}-${newY}`] = { x, y };
188+
gScore[`${newX}-${newY}`] = tentativeGScore;
189+
const fScore =
190+
tentativeGScore + heuristic(newX, newY, endX, endY);
191+
openSet.enqueue({ x: newX, y: newY, cost: fScore }, fScore);
192+
}
193+
}
194+
}
195+
}
196+
197+
return "Maze has no solution.";
198+
}
199+
200+
const path = solveMazeAStar(maze);
201+
202+
if (path !== "Maze has no solution.") {
203+
console.log("Path found:");
204+
path.forEach((cell, index) => {
205+
console.log(`Step ${index + 1}: (${cell.x}, ${cell.y})`);
206+
});
207+
} else {
208+
console.log("Maze has no solution.");
209+
}

‎DSA/Graphs/Travelling Salesman Problem/AntColonyOptimization.js‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
function antColonyOptimizationTSP(cities, distances, numAnts, maxIterations, pheromoneEvaporationRate, alpha, beta) {
2+
const numCities = cities.length;
3+
const initialPheromoneLevel = 1 / (numCities * numCities);
4+
let pheromoneMatrix = Array.from({ length: numCities }, () =>
5+
Array(numCities).fill(initialPheromoneLevel)
6+
);
7+
let bestOrder;
8+
let bestDistance = Infinity;
9+
10+
for (let iteration = 0; iteration < maxIterations; iteration++) {
11+
const antPaths = [];
12+
for (let ant = 0; ant < numAnts; ant++) {
13+
const path = constructAntPath(pheromoneMatrix, distances, alpha, beta);
14+
antPaths.push(path);
15+
const pathDistance = calculateTotalDistance(path, distances);
16+
if (pathDistance < bestDistance) {
17+
bestOrder = path;
18+
bestDistance = pathDistance;
19+
}
20+
}
21+
22+
updatePheromoneMatrix(pheromoneMatrix, antPaths, pheromoneEvaporationRate);
23+
}
24+
25+
return { order: bestOrder, distance: bestDistance };
26+
}
27+
28+
function constructAntPath(pheromoneMatrix, distances, alpha, beta) {
29+
const numCities = pheromoneMatrix.length;
30+
const startCity = Math.floor(Math.random() * numCities);
31+
let currentCity = startCity;
32+
const path = [startCity];
33+
const unvisitedCities = new Set([...Array(numCities).keys()].filter((i) => i !== startCity));
34+
35+
while (unvisitedCities.size > 0) {
36+
const nextCity = chooseNextCity(currentCity, unvisitedCities, pheromoneMatrix, distances, alpha, beta);
37+
path.push(nextCity);
38+
unvisitedCities.delete(nextCity);
39+
currentCity = nextCity;
40+
}
41+
42+
return path;
43+
}
44+
45+
function chooseNextCity(currentCity, unvisitedCities, pheromoneMatrix, distances, alpha, beta) {
46+
const pheromoneLevels = [];
47+
const totalProbability = [...unvisitedCities].reduce((sum, city) => {
48+
const pheromone = pheromoneMatrix[currentCity][city];
49+
const distance = distances[currentCity][city];
50+
const probability = Math.pow(pheromone, alpha) * Math.pow(1 / distance, beta);
51+
pheromoneLevels.push(probability);
52+
return sum + probability;
53+
}, 0);
54+
55+
const randomValue = Math.random() * totalProbability;
56+
let accumulatedProbability = 0;
57+
58+
for (let i = 0; i < pheromoneLevels.length; i++) {
59+
accumulatedProbability += pheromoneLevels[i];
60+
if (accumulatedProbability >= randomValue) {
61+
return [...unvisitedCities][i];
62+
}
63+
}
64+
65+
return [...unvisitedCities][0]; // Fallback in case of numerical instability
66+
}
67+
68+
function updatePheromoneMatrix(pheromoneMatrix, antPaths, pheromoneEvaporationRate) {
69+
const numCities = pheromoneMatrix.length;
70+
71+
// Evaporate pheromone
72+
for (let i = 0; i < numCities; i++) {
73+
for (let j = 0; j < numCities; j++) {
74+
pheromoneMatrix[i][j] *= (1 - pheromoneEvaporationRate);
75+
}
76+
}
77+
78+
// Deposit pheromone based on ant paths
79+
for (const path of antPaths) {
80+
const pathDistance = calculateTotalDistance(path, distances);
81+
for (let i = 0; i < path.length - 1; i++) {
82+
const fromCity = path[i];
83+
const toCity = path[i + 1];
84+
pheromoneMatrix[fromCity][toCity] += 1 / pathDistance;
85+
pheromoneMatrix[toCity][fromCity] += 1 / pathDistance;
86+
}
87+
}
88+
}
89+
90+
// Test case
91+
const cities = ["A", "B", "C", "D"];
92+
const distances = [
93+
[0, 10, 15, 20],
94+
[10, 0, 35, 25],
95+
[15, 35, 0, 30],
96+
[20, 25, 30, 0],
97+
];
98+
99+
const result = antColonyOptimizationTSP(cities, distances, 10, 100, 0.5, 1.0, 2.0);
100+
console.log("Ant Colony Optimization Order:", result.order.map((idx) => cities[idx]).join(" -> "));
101+
console.log("Ant Colony Optimization Distance:", result.distance);

‎DSA/Graphs/Travelling Salesman Problem/BranchAndBound.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
function tspBranchAndBound(cities, distances) {
2+
const n = cities.length;
3+
const visited = new Array(n).fill(false);
4+
visited[0] = true;
5+
const initialPath = [0];
6+
const { order, distance } = branchAndBoundHelper(0, initialPath, 0, Infinity);
7+
8+
function branchAndBoundHelper(currentCity, path, currentDistance, bestDistance) {
9+
if (path.length === n) {
10+
return { order: path, distance: currentDistance + distances[currentCity][0] };
11+
}
12+
13+
let minDistance = bestDistance;
14+
let minOrder = [];
15+
16+
for (let nextCity = 0; nextCity < n; nextCity++) {
17+
if (!visited[nextCity]) {
18+
visited[nextCity] = true;
19+
const newPath = [...path, nextCity];
20+
const newDistance = currentDistance + distances[currentCity][nextCity];
21+
22+
if (newDistance < minDistance) {
23+
const result = branchAndBoundHelper(nextCity, newPath, newDistance, minDistance);
24+
if (result.distance < minDistance) {
25+
minDistance = result.distance;
26+
minOrder = result.order;
27+
}
28+
}
29+
30+
visited[nextCity] = false;
31+
}
32+
}
33+
34+
return { order: minOrder, distance: minDistance };
35+
}
36+
37+
return { order, distance };
38+
}
39+
40+
// Test case
41+
const cities = ["A", "B", "C"];
42+
const distances = [
43+
[0, 10, 15],
44+
[10, 0, 20],
45+
[15, 20, 0],
46+
];
47+
48+
const result = tspBranchAndBound(cities, distances);
49+
console.log("Branch and Bound Optimal Order:", result.order.map((idx) => cities[idx]).join(" -> "));
50+
console.log("Branch and Bound Optimal Distance:", result.distance);

0 commit comments

Comments
 (0)