tsp bb

 import java.util.Arrays;

import java.util.PriorityQueue;

class TravellingSalesman {

    static class Node implements Comparable<Node> {
        int level;
        int[] path;
        int bound;
        int cost;

        Node(int level, int[] path, int bound, int cost) {
            this.level = level;
            this.path = Arrays.copyOf(path, path.length);
            this.bound = bound;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.bound, o.bound);
        }
    }

   
    static int calculateBound(Node node, int[][] graph, int n) {
        int bound = 0;

       
        for (int i = 0; i < node.level - 1; i++) {
            bound += graph[node.path[i]][node.path[i + 1]];
        }

       
        boolean[] visited = new boolean[n];
        for (int i = 0; i < node.level; i++) {
            visited[node.path[i]] = true;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                int minCost = Integer.MAX_VALUE;
                for (int j = 0; j < n; j++) {
                    if (!visited[j] && i != j && graph[i][j] < minCost) {
                        minCost = graph[i][j];
                    }
                }
                bound += (minCost == Integer.MAX_VALUE) ? 0 : minCost;
            }
        }

        return bound;
    }

   
    public static int solveTSP(int[][] graph) {
        int n = graph.length;
        PriorityQueue<Node> pq = new PriorityQueue<>();

       
        int[] initialPath = new int[n + 1];
        initialPath[0] = 0;
        Node root = new Node(1, initialPath, calculateBound(new Node(1, initialPath, 0, 0), graph, n), 0);
        pq.add(root);

        int minCost = Integer.MAX_VALUE;
        int[] bestPath = null;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();

           
            if (currentNode.bound < minCost) {
                for (int i = 1; i < n; i++) {
                    if (!isVisited(i, currentNode.path, currentNode.level)) {
                        Node childNode = new Node(currentNode.level + 1, currentNode.path, 0, currentNode.cost);

                        // Update path and cost
                        childNode.path[currentNode.level] = i;
                        childNode.cost = currentNode.cost + graph[currentNode.path[currentNode.level - 1]][i];

                       
                        childNode.bound = calculateBound(childNode, graph, n);

                       
                        if (childNode.level == n) {
                            childNode.cost += graph[i][0];
                            if (childNode.cost < minCost) {
                                minCost = childNode.cost;
                                bestPath = Arrays.copyOf(childNode.path, n + 1);
                                bestPath[n] = 0;
                            }
                        } else if (childNode.bound < minCost) {
                            pq.add(childNode);
                        }
                    }
                }
            }
        }

        System.out.println("Optimal Path: " + Arrays.toString(bestPath));
        return minCost;
    }

   
    static boolean isVisited(int city, int[] path, int level) {
        for (int i = 0; i < level; i++) {
            if (path[i] == city) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
       
        int[][] graph = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        System.out.println("Minimum cost: " + solveTSP(graph));
    }
}

Comments

Post a Comment

Popular posts from this blog

q3part b

  import java . util . Random ; public class TSPMutation {     public static void main( String [] args ) {         // Example cities (0, 1, 2, 3, 4)         int [] chromosome = { 0 , 1 , 2 , 3 , 4 }; // A possible solution (tour)                 System .out.println( "Original Chromosome:" );         printChromosome(chromosome);                 // Apply Mutation (Swap two cities in the path)         mutate(chromosome);                 System .out.println( "Mutated Chromosome:" );         printChromosome(chromosome);     }     // Mutation function: Swap two cities' positions     public static void mutate( int [] chromosome ) {         Random rand = new Random();           ...
Read more

Literal table

 #code import java.util.*; class Literal {     String value;     int address;     public Literal(String value) {         this.value = value;         this.address = -1; // not assigned yet     } } public class Ass2{     // Check if a literal already exists in the list     public static boolean literalExists(List<Literal> list, String value) {         for (Literal l : list) {             if (l.value.equals(value)) return true;         }         return false;     }     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         List<String> code = new ArrayList<>();         List<Literal> literalTable = new ArrayList<>();         Lis...
Read more

quicksort 1

 import java.util.Random; public class QuicksortExample {     public static void main(String[] args) {         int N = 500; // Number of elements to sort         // Initialize an array of random integers         int[] arr = new int[N];         Random rand = new Random();         for (int i = 0; i < N; i++) {             arr[i] = rand.nextInt(1000); // Random integers between 0 and 999         }         // Displaying the unsorted array (optional)         System.out.println("Unsorted array:");         printArray(arr);         // Start measuring time         long startTime = System.nanoTime();         // Call the quicksort method         quicksort(arr, 0, N - 1);       ...
Read more