java - 非遗传局部搜索算法

Question

此作业基于旅行销售员问题的定义。我想找到访问每个城市并最终回到原始起始城市的最短路线。目标是使用非遗传局部搜索算法或算法来找到最短路径。

例如：选项将是两个交换两个城市的顺序，看看这是否缩短了行程：

• Mpls。=> 西雅图 => 底特律 => 波士顿 => 芝加哥 => 迈阿密 => 丹佛 => Mpls。

我在基于此算法进行编码时遇到困难。所以，我想知道是否有人可以告诉我如何在我的程序中做到这一点。

文本文件的示例输出

两种类型的输出：摘要模式和详细模式。详细模式应该在您尝试的每个路径都打印到一个文件，直到您的程序终止。打印到控制台的摘要模式应该仅在该路径优于您之前找到的任何路径时打印路径。在所有情况下，打印城市（节点）的单字母助记符。

我正在处理的代码的附加要求

这是我过去几个小时工作的代码。

图表类：

     import java.util.ArrayList;
     //Graph is a class whose objects represent graphs.
public class Graph {
   ArrayList<Node> nodeList;
   ArrayList<Edge> edgeList;
  
   public Graph() {
       nodeList = new ArrayList<Node>();
       edgeList = new ArrayList<Edge>();
  
   }
  
   public ArrayList<Node> getNodeList() {
       return nodeList;
   }
   public ArrayList<Edge> getEdgeList() {
       return edgeList;
   }
   public void addNode(Node n) {
       nodeList.add(n);
   }
   public void addEdge(Edge e) {
       edgeList.add(e);
   }
   public String toString() {
       String s = "Graph g.\n";
       if (nodeList.size() > 0) {
           for (Node n : nodeList) {
       // Print node info
       String t = "\nNode " + n.getName() + ", abbrev " + n.getAbbrev() + ", value " + n.getVal() + "\n";
       s = s.concat(t);
       }
       s = s.concat("\n");
           }
       return s;
   }
}

节点类：

 import java.util.ArrayList;
// Node is a class whose objects represent nodes (a.k.a., vertices) in the graph.
public class Node {
   String name;
   String val; // The value of the Node
   String abbrev; // The abbreviation for the Node
   ArrayList<Edge> outgoingEdges;
   ArrayList<Edge> incomingEdges;
  
  
   String color; //Create the color of the TYPE Node List
   int start; //Create the Starting Time
   int end; //Create the Ending Time
  
  
   public Node( String theAbbrev ) {
       setAbbrev( theAbbrev );
       val = null;
       name = null;
       outgoingEdges = new ArrayList<Edge>();
       incomingEdges = new ArrayList<Edge>();
   }
  
   public String getAbbrev() {
       return abbrev;
   }
  
   public String getName() {
       return name;
   }
  
   public String getVal() {
       return val;
   }
  
   public ArrayList<Edge> getOutgoingEdges() {
       return outgoingEdges;
   }
  
   public ArrayList<Edge> getIncomingEdges() {
       return incomingEdges;
   }
  
   public void setAbbrev( String theAbbrev ) {
       abbrev = theAbbrev;
   }
  
   public void setName( String theName ) {
       name = theName;
   }
  
   public void setVal( String theVal ) {
       val = theVal;
   }
  
   public void addOutgoingEdge( Edge e ) {
       outgoingEdges.add( e );
   }
  
   public void addIncomingEdge( Edge e ) {
       incomingEdges.add( e );
   }
  
  
   //Create the Starting Time of the Node
   public int getStartTime() {
       return start;
   }
   //Create the Finshing Time of the Node
   public int getFinishTime() {
       return end;
   }
   public void setColor(String string) {
       color = string;
   }
   public String getColor() {
       return color;
   }
   //Set Starting-Time
   public void setStartTime(int time) {
       start = time;
      
   }
   //Set Finishing-Time
   public void setFinishTime(int time) {
       end = time;
}

边缘类：

 //import java.util.*;
// Edge between two nodes
// Edge is a class whose objects represent edges (a.k.a., arcs) between nodes of the graph.
public class Edge {
  
   String label;
   int dest;
   int dist;
   Node tail;
   Node head;
  
   //String Type(Forward,Backward,Cross,Tree)
   String name;
  
   public Edge( Node tailNode, Node headNode, String theLabel ) {
       setLabel( theLabel );
       setTail( tailNode );
       setHead( headNode );
   }
  
   public Edge(int dest, int dist,String label,String name)
   {
       //Create the destination Vertex Index
       this.dest = dest;
       this.dist = dist; // Source Vertex index
       this.label=label; // Label of Edge
       this.name= name; // (Locate the Type of Line(F,B,C,T)
       }
  
   public String getLabel() {
       return label;
   }
  
   public Node getTail() {
       return tail;
   }
  
   public Node getHead() {
       return head;
   }
  
   public int getDist() {
       return dist;
   }
  
   public void setLabel( String s ) {
       label = s;
   }
  
   public void setTail( Node n ) {
       tail = n;
   }
  
   public void setHead( Node n ) {
       head = n;
   }
  
   public void setDist( String s ) {
       try {
           dist = Integer.parseInt( s );
       }
       catch ( NumberFormatException nfe ) {
           dist = Integer.MAX_VALUE;
       }
   }
   public String getType() {
       return name;
   }
   public void setType(String string) {
       this.name = string;
   }
}

主驱动：

  import java.io.File;
import java.io.PrintWriter;
public class DelivC {
   File inputFile;
   File outputFile;
   PrintWriter output;
   Graph g;
  
   public DelivC( File in, Graph gr ) {
       inputFile = in;
       g = gr;
      
       // Get output file name.
       String inputFileName = inputFile.toString();
       String baseFileName = inputFileName.substring( 0, inputFileName.length()-4 ); // Strip off ".txt"
       String outputFileName = baseFileName.concat( "_out.txt" );
       outputFile = new File( outputFileName );
       if ( outputFile.exists() ) { // For retests
           outputFile.delete();
       }
      
       try {
           output = new PrintWriter(outputFile);          
       }
       catch (Exception x ) {
           System.err.format("Exception: %s%n", x);
           System.exit(0);
       }
       System.out.println( "DelivC: To be implemented");
       output.println( "DelivC: To be implemented");
       output.flush();
   }
}

标签： javanodesdynamic-programmingcomputer-science