codesONLY · sohamsshah · Oct 27, 2023 · Oct 2, 2023 · Oct 3, 2023
diff --git a/DSA/Graphs/Maze.js b/DSA/Graphs/Maze.js
@@ -0,0 +1,209 @@
+const maze = [
+    ['S', 0, 1, 0, 1],
+    [0, 1, 0, 0, 0],
+    [0, 0, 1, 1, 0],
+    [1, 0, 0, 0, 'E'],
+];
+
+
+function solveMazeDFS(maze) {
+    const rows = maze.length;
+    const cols = maze[0].length;
+
+    function dfs(x, y) {
+        if (x < 0 || x >= rows || y < 0 || y >= cols || maze[x][y] === 1) {
+            return false;
+        }
+
+        if (maze[x][y] === 'E') {
+            return true; // Reached the end of the maze
+        }
+
+        maze[x][y] = 1; // Mark as visited
+
+        // Explore in all four directions (up, down, left, right)
+        if (dfs(x + 1, y) || dfs(x - 1, y) || dfs(x, y + 1) || dfs(x, y - 1)) {
+            return true;
+        }
+
+        maze[x][y] = 0; // Mark as unvisited if no path was found
+        return false;
+    }
+
+    // Find the start point
+    let startX, startY;
+    for (let i = 0; i < rows; i++) {
+        for (let j = 0; j < cols; j++) {
+            if (maze[i][j] === 'S') {
+                startX = i;
+                startY = j;
+                break;
+            }
+        }
+    }
+
+    // Call DFS from the start point
+    if (dfs(startX, startY)) {
+        return "Maze is solvable.";
+    } else {
+        return "Maze has no solution.";
+    }
+}
+
+console.log(solveMazeDFS(maze));
+
+
+
+
+function solveMazeBFS(maze) {
+    const rows = maze.length;
+    const cols = maze[0].length;
+    const queue = [];
+
+    // Find the start point
+    let startX, startY;
+    for (let i = 0; i < rows; i++) {
+        for (let j = 0; j < cols; j++) {
+            if (maze[i][j] === 'S') {
+                startX = i;
+                startY = j;
+                break;
+            }
+        }
+    }
+
+    // Define possible moves (up, down, left, right)
+    const moves = [[1, 0], [-1, 0], [0, 1], [0, -1]];
+
+    queue.push([startX, startY]);
+
+    while (queue.length > 0) {
+        const [x, y] = queue.shift();
+
+        if (maze[x][y] === 'E') {
+            return "Maze is solvable.";
+        }
+
+        maze[x][y] = 1; // Mark as visited
+
+        for (const [dx, dy] of moves) {
+            const newX = x + dx;
+            const newY = y + dy;
+
+            if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && maze[newX][newY] === 0) {
+                queue.push([newX, newY]);
+            }
+        }
+    }
+
+    return "Maze has no solution.";
+}
+
+console.log(solveMazeBFS(maze));
+
+
+class PriorityQueue {
+    constructor() {
+        this.elements = [];
+    }
+
+    enqueue(element, priority) {
+        this.elements.push({ element, priority });
+        this.elements.sort((a, b) => a.priority - b.priority);
+    }
+
+    dequeue() {
+        return this.elements.shift().element;
+    }
+
+    isEmpty() {
+        return this.elements.length === 0;
+    }
+}
+
+function heuristic(x1, y1, x2, y2) {
+    // A simple heuristic function (Manhattan distance)
+    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
+}
+
+function solveMazeAStar(maze) {
+    const rows = maze.length;
+    const cols = maze[0].length;
+
+    // Find the start and end points
+    let startX, startY, endX, endY;
+    for (let i = 0; i < rows; i++) {
+        for (let j = 0; j < cols; j++) {
+            if (maze[i][j] === 'S') {
+                startX = i;
+                startY = j;
+            } else if (maze[i][j] === 'E') {
+                endX = i;
+                endY = j;
+            }
+        }
+    }
+
+    const openSet = new PriorityQueue();
+    openSet.enqueue({ x: startX, y: startY, cost: 0 }, 0);
+
+    const cameFrom = {};
+    const gScore = {};
+
+    gScore[`${startX}-${startY}`] = 0;
+
+    while (!openSet.isEmpty()) {
+        const current = openSet.dequeue();
+        const { x, y } = current;
+
+        if (x === endX && y === endY) {
+            // Reconstruct the path
+            const path = [];
+            let currentNode = { x: endX, y: endY };
+            while (currentNode) {
+                path.unshift(currentNode);
+                currentNode = cameFrom[`${currentNode.x}-${currentNode.y}`];
+            }
+            return path;
+        }
+
+        for (const [dx, dy] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
+            const newX = x + dx;
+            const newY = y + dy;
+
+            if (
+                newX >= 0 &&
+                newX < rows &&
+                newY >= 0 &&
+                newY < cols &&
+                maze[newX][newY] !== 1
+            ) {
+                const tentativeGScore = gScore[`${x}-${y}`] + 1;
+
+                if (
+                    !gScore[`${newX}-${newY}`] ||
+                    tentativeGScore < gScore[`${newX}-${newY}`]
+                ) {
+                    cameFrom[`${newX}-${newY}`] = { x, y };
+                    gScore[`${newX}-${newY}`] = tentativeGScore;
+                    const fScore =
+                        tentativeGScore + heuristic(newX, newY, endX, endY);
+                    openSet.enqueue({ x: newX, y: newY, cost: fScore }, fScore);
+                }
+            }
+        }
+    }
+
+    return "Maze has no solution.";
+}
+
+const path = solveMazeAStar(maze);
+
+if (path !== "Maze has no solution.") {
+    console.log("Path found:");
+    path.forEach((cell, index) => {
+        console.log(`Step ${index + 1}: (${cell.x}, ${cell.y})`);
+    });
+} else {
+    console.log("Maze has no solution.");
+}
diff --git a/DSA/Graphs/Travelling Salesman Problem/AntColonyOptimization.js b/DSA/Graphs/Travelling Salesman Problem/AntColonyOptimization.js
@@ -0,0 +1,101 @@
+function antColonyOptimizationTSP(cities, distances, numAnts, maxIterations, pheromoneEvaporationRate, alpha, beta) {
+    const numCities = cities.length;
+    const initialPheromoneLevel = 1 / (numCities * numCities);
+    let pheromoneMatrix = Array.from({ length: numCities }, () =>
+        Array(numCities).fill(initialPheromoneLevel)
+    );
+    let bestOrder;
+    let bestDistance = Infinity;
+
+    for (let iteration = 0; iteration < maxIterations; iteration++) {
+        const antPaths = [];
+        for (let ant = 0; ant < numAnts; ant++) {
+            const path = constructAntPath(pheromoneMatrix, distances, alpha, beta);
+            antPaths.push(path);
+            const pathDistance = calculateTotalDistance(path, distances);
+            if (pathDistance < bestDistance) {
+                bestOrder = path;
+                bestDistance = pathDistance;
+            }
+        }
+
+        updatePheromoneMatrix(pheromoneMatrix, antPaths, pheromoneEvaporationRate);
+    }
+
+    return { order: bestOrder, distance: bestDistance };
+}
+
+function constructAntPath(pheromoneMatrix, distances, alpha, beta) {
+    const numCities = pheromoneMatrix.length;
+    const startCity = Math.floor(Math.random() * numCities);
+    let currentCity = startCity;
+    const path = [startCity];
+    const unvisitedCities = new Set([...Array(numCities).keys()].filter((i) => i !== startCity));
+
+    while (unvisitedCities.size > 0) {
+        const nextCity = chooseNextCity(currentCity, unvisitedCities, pheromoneMatrix, distances, alpha, beta);
+        path.push(nextCity);
+        unvisitedCities.delete(nextCity);
+        currentCity = nextCity;
+    }
+
+    return path;
+}
+
+function chooseNextCity(currentCity, unvisitedCities, pheromoneMatrix, distances, alpha, beta) {
+    const pheromoneLevels = [];
+    const totalProbability = [...unvisitedCities].reduce((sum, city) => {
+        const pheromone = pheromoneMatrix[currentCity][city];
+        const distance = distances[currentCity][city];
+        const probability = Math.pow(pheromone, alpha) * Math.pow(1 / distance, beta);
+        pheromoneLevels.push(probability);
+        return sum + probability;
+    }, 0);
+
+    const randomValue = Math.random() * totalProbability;
+    let accumulatedProbability = 0;
+
+    for (let i = 0; i < pheromoneLevels.length; i++) {
+        accumulatedProbability += pheromoneLevels[i];
+        if (accumulatedProbability >= randomValue) {
+            return [...unvisitedCities][i];
+        }
+    }
+
+    return [...unvisitedCities][0]; // Fallback in case of numerical instability
+}
+
+function updatePheromoneMatrix(pheromoneMatrix, antPaths, pheromoneEvaporationRate) {
+    const numCities = pheromoneMatrix.length;
+
+    // Evaporate pheromone
+    for (let i = 0; i < numCities; i++) {
+        for (let j = 0; j < numCities; j++) {
+            pheromoneMatrix[i][j] *= (1 - pheromoneEvaporationRate);
+        }
+    }
+
+    // Deposit pheromone based on ant paths
+    for (const path of antPaths) {
+        const pathDistance = calculateTotalDistance(path, distances);
+        for (let i = 0; i < path.length - 1; i++) {
+            const fromCity = path[i];
+            const toCity = path[i + 1];
+            pheromoneMatrix[fromCity][toCity] += 1 / pathDistance;
+            pheromoneMatrix[toCity][fromCity] += 1 / pathDistance;
+        }
+    }
+}
+
+// Test case
+const cities = ["A", "B", "C", "D"];
+const distances = [
+    [0, 10, 15, 20],
+    [10, 0, 35, 25],
+    [15, 35, 0, 30],
+    [20, 25, 30, 0],
+];
+
+const result = antColonyOptimizationTSP(cities, distances, 10, 100, 0.5, 1.0, 2.0);
+console.log("Ant Colony Optimization Order:", result.order.map((idx) => cities[idx]).join(" -> "));
+console.log("Ant Colony Optimization Distance:", result.distance);
diff --git a/DSA/Graphs/Travelling Salesman Problem/BranchAndBound.js b/DSA/Graphs/Travelling Salesman Problem/BranchAndBound.js
@@ -0,0 +1,50 @@
+function tspBranchAndBound(cities, distances) {
+    const n = cities.length;
+    const visited = new Array(n).fill(false);
+    visited[0] = true;
+    const initialPath = [0];
+    const { order, distance } = branchAndBoundHelper(0, initialPath, 0, Infinity);
+
+    function branchAndBoundHelper(currentCity, path, currentDistance, bestDistance) {
+        if (path.length === n) {
+            return { order: path, distance: currentDistance + distances[currentCity][0] };
+        }
+
+        let minDistance = bestDistance;
+        let minOrder = [];
+
+        for (let nextCity = 0; nextCity < n; nextCity++) {
+            if (!visited[nextCity]) {
+                visited[nextCity] = true;
+                const newPath = [...path, nextCity];
+                const newDistance = currentDistance + distances[currentCity][nextCity];
+
+                if (newDistance < minDistance) {
+                    const result = branchAndBoundHelper(nextCity, newPath, newDistance, minDistance);
+                    if (result.distance < minDistance) {
+                        minDistance = result.distance;
+                        minOrder = result.order;
+                    }
+                }
+
+                visited[nextCity] = false;
+            }
+        }
+
+        return { order: minOrder, distance: minDistance };
+    }
+
+    return { order, distance };
+}
+
+// Test case
+const cities = ["A", "B", "C"];
+const distances = [
+    [0, 10, 15],
+    [10, 0, 20],
+    [15, 20, 0],
+];
+
+const result = tspBranchAndBound(cities, distances);
+console.log("Branch and Bound Optimal Order:", result.order.map((idx) => cities[idx]).join(" -> "));
+console.log("Branch and Bound Optimal Distance:", result.distance);