java - 在TSP问题中还是找不到返回起始城市的方法

Question

问题描述: 旅行商问题(也称为旅行商问题或 TSP)提出以下问题:“给定一个城市列表和每对城市之间的距离，访问每个城市并返回原点城市的最短路线是什么？”

我的解决方案:

我使用回溯法，我使用 Google Guava 库构建图表，唯一的问题是我的代码不返回初始城市，例如，如果我们有 A 、 B 、 C 、 D 城市和最短的trajectory is A ,B , D, C 我们必须返回初始城市 Like A ,B , D, C, A 这是代码(或者您可以查看以下 github 链接以更好地理解问题 https://charlesreid1.github.io/solving-the-traveling-salesperson-problem-with-java-and-guava.html :

    
    package com.Faissal;
    
    import com.google.common.graph.ImmutableNetwork;
    import com.google.common.graph.MutableNetwork;
    import com.google.common.graph.NetworkBuilder;
    
    import java.util.Arrays;
    import java.util.Map;
    import java.util.Set;
    import java.util.TreeMap;
    
    
    class TSP {
        // The actual graph of cities
        ImmutableNetwork<Node, Edge> graph;
        int graphSize;
    
        // Storage variables used when searching for a solution
        String[] route;        // store the route
        double this_distance;   // store the total distance
        double min_distance;    // store the shortest path found so far
    
        /**
         * Defaut constructor generates the graph and initializes storage variables
         */
        public TSP() {
            // Build the graph
            this.graph = buildGraph();
            this.graphSize = this.graph.nodes().size();
    
            // Initialize route variable, shared across recursive method instances
            this.route = new String[this.graphSize];
    
            // Initialize distance variable, shared across recursive method instances
            this.this_distance = 0.0;
            this.min_distance = -1.0; // negative min means uninitialized
        }
    
        /**
         * This method actually constructs the graph.
         */
        public ImmutableNetwork<Node, Edge> buildGraph() {
    
            // MutableNetwork is an interface requiring a type for nodes and a type for edges
            MutableNetwork<Node, Edge> roads = NetworkBuilder.undirected().build();
    
            // Construct Nodes for cities,
            // and add them to a map
            String[] cities = {"Wuhan", "shanghai", "Beijing", "Tianjin", "dalian"};
            Map<String, Node> all_nodes = new TreeMap<String, Node>();
            for (int i = 0; i < cities.length; i++) {
                // Add nodes to map
                Node node = new Node(cities[i]);
                all_nodes.put(cities[i], node);
    
                // Add nodes to network
                roads.addNode(node);
            }
    
            // Construct Edges for roads,
            // and add them to a map
            String[] distances = {"Wuhan:shanghai:839", "Wuhan:Beijing:1153", "Wuhan:Tianjin:1162", "Wuhan:dalian:1423", "shanghai:Beijing:1214", "shanghai:Tianjin:20", "Beijing:Tianjin:4", "shanghai:dalian:1076", "Tianjin:dalian:802"};
            Map<String, Edge> all_edges = new TreeMap<String, Edge>();
            for (int j = 0; j < distances.length; j++) {
                // Parse out (city1):(city2):(distance)
                String[] splitresult = distances[j].split(":");
                String left = splitresult[0];
                String right = splitresult[1];
                String label = left + ":" + right;
                int value = Integer.parseInt(splitresult[2]);
    
                // Add edges to map
                Edge edge = new Edge(left, right, value);
                all_edges.put(label, edge);
    
                // Add edges to network
                roads.addEdge(all_nodes.get(edge.left), all_nodes.get(edge.right), edge);
            }
    
            // Freeze the network
            ImmutableNetwork<Node, Edge> frozen_roads = ImmutableNetwork.copyOf(roads);
    
            return frozen_roads;
        }
    
        /**
         /** Public solve method will call the recursive backtracking method to search for solutions on the graph */
        public void solve() {
            /** To solve the traveling salesman problem:
             * Set up the graph, choose a starting node, then call the recursive backtracking method and pass it the starting node.
             */
    
            // We need to pass a starting node to recursive backtracking method
            Node startNode = null;
    
            // Grab a node, any node...
            for( Node n : graph.nodes() ) {
                startNode = n;
                break;
            }
    
            // Visit the first node
            startNode.visit();
    
            // Add first node to the route
            this.route[0] = startNode.label;
    
            // Pass the number of choices made
            int nchoices = 1;
    
            // Recursive backtracking
            explore(startNode, nchoices);
        }
    
        /** Recursive backtracking method: explore possible solutions starting at this node, having made nchoices */
        /**
         * Recursive backtracking method: explore possible solutions starting at this node, having made nchoices
         * @return
         */
        public void explore(Node node, int nchoices) {
            /**
             * Solution strategy: recursive backtracking.
          */
    
            if (nchoices == graphSize) {
                //
                // BASE CASE
                //
                if (this.this_distance < this.min_distance || this.min_distance < 0) {
                    // if this_distance < min_distance, this is our new minimum distance
                    // if min_distance < 0, this is our first minimium distance
                    this.min_distance = this.this_distance;
    
                    printSolution();
    
    
                } else {
                    printFailure();
                }
    
            } else {
                //
                // RECURSIVE CASE
                //
                Set<Node> neighbors = graph.adjacentNodes(node);
                for (Node neighbor : neighbors) {
                    if (neighbor.visited == false) {
    
                        int distance_btwn = 0;
    
                        for (Edge edge : graph.edgesConnecting(node, neighbor)) {
                            distance_btwn = edge.value;
                        }
    
                        // Make a choice
                        this.route[nchoices] = neighbor.label;
                        neighbor.visit();
                        this.this_distance += distance_btwn;
    
                        // Explore the consequences
                        explore(neighbor, nchoices + 1);
    
                        // Unmake the choice
                        this.route[nchoices] = null;
                        neighbor.unvisit();
                        this.this_distance -= distance_btwn;
                    }
    
                    // Move on to the next choice (continue loop)
                }
    
            } // End base/recursive case
    
    
        }
    
    
        public void printSolution() {
    
            System.out.print("***********\tNEW SOLUTION\t");
            System.out.println("Route: " + Arrays.toString(this.route)
                    + "\tDistance: " + this.min_distance);
        }
    
        /**
         * Do nothing with failed path
         */
        public void printFailure() {
            //
        }
    }

The Node Class is 
``` 

class Node {
    public String label;
    public boolean visited; // Helps us to keep track of where we've been on the graph
    public Node(String name){
        this.label = name;
        this.visited = false;
    }
    public void visit(){
        this.visited = true;
    }
    public void unvisit() {
        this.visited = false;
    }
}

  The Edge Class :
  ``` 
  class Edge {
      public int value;
      public String left, right; // For convenience in construction process. Not necessary.
      public Edge(String left, String right, int value) {
          this.left = left;
          this.right = right;
          this.value = value;
      }
  }

  

主类

``` 


public class Main {

    public static void main(String[] args) {
        
        TSP t = new TSP();
        t.solve();
    }
}

I will be very Thankful if someone helped me with this issue

Answer 1

你快到了，你只需要回到原点。

为此，您必须在 TSP.explore 中引用来源。您可以将它存储在 this.startNode 中的某处，或者使 route 成为节点数组:Node[] route

然后您可以检查 TSP.explore，如果最后一个节点的原点是它的邻居，则将该距离添加到总距离中，然后像往常一样继续。

基本上可以归结为:

// Store Nodes instead of Strings. Edit this everywhere you use it.
Node[] route; 

// ...

if (nchoices == graphSize) {
    //
    // BASE CASE: VISITED EACH NODE
    //
    Set<Node> neighbors = graph.adjacentNodes(node);

    // It's only a solution, if there is a edge to the first node.
    if(neighbors.contains(this.route[0])) {

        // Same computation as in the else-block.
        int distance_btwn = this.getDistanceBetween(node, neighbor);
    
        // Add the distance to the start node.
        int total_distance = this.this_distance + distance_btwn;

        if (total_distance < this.min_distance || this.min_distance < 0) {
            // if this_distance < min_distance, this is our new minimum distance
            // if min_distance < 0, this is our first minimium distance
            this.min_distance = total_distance;

            // You have to tell printSolution to about total_distance somehow.
            printSolution(total_distance);
            return;
        } 
    }
        
    printFailure();
}