Question

Specification

Start with your Java program "prog340" which implements Deliverables A and B.

This assignment is based on the definition of the Traveling Salesperson Problem (the TSP): Given a set of cities, you want to find the shortest route that visits every city and ends up back at the original starting city. For the purposes of this problem, every city will be directly reachable from every other city (think flying from city to city).

Your goal is to use a non-genetic local search algorithm or algorithms from Chapter 4 of Poole \& Mackworth to find the shortest paths that you can. Note that for any reasonably sized problem, you will not be able to try every possibility, and so you won't ever know when you have the shortest possible path.

You should have two types of output: Summary Mode and Verbose Mode.

Verbose Mode should print to a file every path you try until your program terminates. Summary mode, which prints to the console, should print a path only when that path is better than any path that you have found previously. In all cases, print the single-letter mnemonic of the city (Node), not its full name.

Suggestions

You can start from any city you want, it really doesn't matter which. For example, you can start from the first city in the file, since it is the easiest. Create some tour. You can do this randomly, or you can use a greedy algorithm of some sort, or you can just visit the cities in the order they appear in the file, whatever you prefer. Your choice probably won't affect the goodness of your final tour, but it might affect how long it takes you to get to a good solution.

Selecting and using the techniques of local search, try to find a better tour. Be sure to document what you're trying to do.

The rest of this section assumes you want to create your own algorithm. Here are some thoughts on what is probably the main question: how to step from one possible tour to the next.

- One option would be two swap the order of two cities and see if this shortens the tour Q Mpls. \(\rightarrow\) Seattle \(\rightarrow\) Detroit \(\rightarrow\) Boston \(\rightarrow\) Chicago \(\rightarrow\) Miami \(\rightarrow\) Denver \(\rightarrow\) Mpls.

- Or you could pick one city in the tour, and try removing it and inserting it between every pair of cities to see which gives the shortest tour.

- There are other forms of Iterative Best Improvement, too.

- When deciding what cities to swap or what city to shuffle, you could use either a 1-stage or 2-stage choice algorithm.

With any sort of iterative best improvement, there are various techniques you could use if you wish. One of the big differences among peoples" algorithms will be their choices to use or not use these techniques, and the algorithm they use to decide when to use them (for example, how often to do a random step or restart, temperatures for simulated annealing, etc.)

- You could choose to use Simulated Annealing to decide whether to keep a given tour even if it's longer than the existing tour.

- You could inject randomness by sometimes making random permutations (random walk).

- You could decide after a certain number of iterations that you should just start over from scratch with a random order of cities (random restart).

- You could choose to keep a tabu list or not, and if you do, you could choose its size.

- You could keep multiple tours, and permute them in parallel (beam search).

Since you don't actually know when you have an optimal tour for any reasonably sized problem, you need to decide on a stopping criterion. Some possible suggestions:

- Stop after some number of steps (where the number of steps might be some function of the number \(n\) of cities).

- Stop after you have gone some number \(k\) of steps without improving on your best answer.

- Stop after the program has run for some amount of real-time (measured by something like System.time.millis()).

//Graph Class:
import java.util.ArrayList;
//Graph is a class whose objects represent graphs.
 public class Graph {
    ArrayList nodeList;
    ArrayList edgeList;
   
    public Graph() {
        nodeList = new ArrayList();
        edgeList = new ArrayList();
   
    }
   
    public ArrayList getNodeList() {
        return nodeList;
   }
   public ArrayList 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;
    }
 }

// Node Class:
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 outgoingEdges;
    ArrayList 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();
        incomingEdges = new ArrayList();
    }
   
    public String getAbbrev() {
        return abbrev;
    }
   
    public String getName() {
        return name;
    }
   
    public String getVal() {
        return val;
    }
   
    public ArrayList getOutgoingEdges() {
        return outgoingEdges;
    }
   
    public ArrayList 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;
 }
//Edge Class:
//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;
    }
 }
//NEED HELP ON IMPLEMENT ON DELIVC CLASS
//DelivC Class (DelivC Need to be implemented) :
import java.io.File;
 import java.io.PrintWriter;
// Class DelivC does the work for deliverable DelivC of the Prog340
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();
    }
 }