4 Replies - 1446 Views - Last Post: 07 December 2012 - 09:45 PM Rate Topic: -----

#1 itsjimmy91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 77
  • Joined: 19-January 11

Recursive Traveling Salesman Solution

Posted 06 December 2012 - 01:09 PM

Hey guys. I have a project that I am working on where I need to solve a Traveling Salesman program using recursion and backtracking. So far what it does is goes through each path in the following order:

1
12
123
1234
12345

It will then start with two and do the same thing:

2
21
213
2134
21345

This is close, but it isn't correct because it doesn't seem to be visiting every possible path. For instance, after 1-2 it should then be looking for 1-2-3, 1-2-4, 1-2-5, etc, and it is not doing this.

Every point must be visited and can only be visited once.

Here is the code that I currently have. I have a Path class and a Vertice class included.

Main Class
package backtrack;

import java.io.IOException;

public class Backtrack {
    
    public static void main(String[] args) throws IOException {
        BacktrackSimulator backtrack = new BacktrackSimulator();
    }
}



Simulator Class
package backtrack;

import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

public class BacktrackSimulator {
    
    String fileName;
    ArrayList<Vertice> vertices;
    Path bestPath;
    double bestCost;
    Path path;
    
    int count;
    
    
    public BacktrackSimulator() throws IOException
    {
        int size = 0;
        bestCost = Integer.MAX_VALUE;
        vertices = new ArrayList<Vertice>();
        bestPath = new Path();
        path = new Path();
        
        size = GetSize();
        GetVertices();
        
        for(int i=0; i<vertices.size(); i++)
        {
            SetDistances(i);
        }
        
        for(int i=0; i<vertices.size(); i++)
        {
            path.vertices.clear();
            path.totalCost = 0;
            path.vertices.add(vertices.get(i));
            Backtracking(path);
        }
        
        System.out.println("Best cost: " + bestCost);
        System.out.println("Path: ");
        for(int i=0; i<bestPath.vertices.size(); i++)
        {
            System.out.print(bestPath.vertices.get(i).point + " ");
        }
        
    }
    
    // get number of vertices in file
    private int GetSize() throws IOException
    {
        String input; 
        int size = 0;
        
        BufferedReader reader = 
                new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Please enter a filename:");
        fileName = reader.readLine();
        File inputFile = new File(fileName);
        
        Scanner scanFile = new Scanner(inputFile);
        for(int i=0; i<6; i++)
        {
            scanFile.nextLine();
        }
        
        // get the size of the file
        do
        {
            input = scanFile.nextLine();
            if(!input.equals("EOF"))
            {
                size++;
            }
        } while(!input.equals("EOF"));
        
        return size;
    }
    
    // get the vertices from the file
    private void GetVertices() throws IOException
    {
        String input; 
        try
        {
            File inputFile = new File(fileName);
            Scanner scanFile = new Scanner(inputFile);
            
            for(int i=0; i<6; i++)
            {
                scanFile.nextLine();
            }
            
            do
            {
                String[] inputs;
                input = scanFile.nextLine();
                if(!input.equals("EOF"))
                {
                    inputs = input.split(" ");
                    // each line creates a new vertice
                    vertices.add(new Vertice(inputs[0], inputs[1], inputs[2]));
                }
            } while(!input.equals("EOF"));
        }
        catch(IOException e)
        {
            
        }
    }
    
    // set a vertices distances
    private void SetDistances(int i)
    {
        Vertice vertice = vertices.get(i);
        
        for(int j=0; j<vertices.size(); j++)
        {
            Vertice nextVertice = vertices.get(j);
            if(vertice != nextVertice)
            {
                double x1 = vertice.x;
                double y1 = vertice.y;
                double x2 = nextVertice.x;
                double y2 = nextVertice.y;
                double distances = Math.pow((x2-x1), 2) + Math.pow((y2-y1), 2);
                distances = Math.sqrt(distances);
                vertice.distances.put(nextVertice, distances);
            }
        }
    }
    
    public void Backtracking(Path path)
    {
        // check to see if current path cost is greater than bestCost 
        
        System.out.println();
        for(int i = 0; i<path.vertices.size(); i++)
        {
            System.out.print(path.vertices.get(i).point);
        }
        
        if(path.totalCost > bestCost)
        {
            return;
        }
        
        // check to see if the path is complete, will be new best
        else if(path.vertices.size() == vertices.size() 
                && path.totalCost < bestCost)
        {
            bestPath = path;
            bestCost = path.totalCost;
            return;
        }
        
        // recursive call
        else
        {
            for(int i=0; i<vertices.size(); i++)
            {
                if(!path.ContainsVertice(vertices.get(i)))
                {
                    path.AddVertice(vertices.get(i));
                    Backtracking(path);
                }
            }
        }
    }
}



Path Class

package backtrack;

import java.util.ArrayList;

public class Path {
    
    ArrayList<Vertice> vertices;
    double totalCost;
    
    public Path()
    {
        vertices = new ArrayList<Vertice>();
        totalCost = 0;
    }
    
    // add vertice to path
    public void AddVertice(Vertice vertice)
    {
        vertices.add(vertice);
        UpdateTotalCost();
    }
    
    // check if the path already contains the vertice
    public boolean ContainsVertice(Vertice vertice)
    {
        return vertices.contains(vertice);
    }
    
    private void UpdateTotalCost()
    {
        totalCost = 0;
        for(int i=0; i<vertices.size()-1; i++)
        {
            Vertice currentVertice = vertices.get(i);
            Vertice nextVertice = vertices.get(i+1);
            totalCost += currentVertice.distances.get(nextVertice);
        }
    }
}



Vertice Class
package backtrack;

import java.util.ArrayList;
import java.util.HashMap;

public class Vertice {
    
    // properties of a vertice
    int point;
    double x;
    double y;
    HashMap<Vertice, Double> distances;
    
    // constructor w/ x and y coordinates
    public Vertice(String point, String x, String y)
    {
        this.point = Integer.parseInt(point);
        this.x = Double.parseDouble(x);
        this.y = Double.parseDouble(y);
        distances = new HashMap<Vertice, Double>();
    }
}



I know what it needs to be doing, I'm just not sure how to make it do it. Let me know if any of this doesn't make sense. Thanks for the help.

Also, here is the file that is being used to run it.

NAME: hhv15
COMMENT: 
TYPE: TSP	
DIMENSION: 15
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 25 26
2 47 34
3 26 48
4 32 40
5 40 50
EOF



Is This A Good Question/Topic? 0
  • +

Replies To: Recursive Traveling Salesman Solution

#2 itsjimmy91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 77
  • Joined: 19-January 11

Re: Recursive Traveling Salesman Solution

Posted 06 December 2012 - 05:07 PM

Any ideas on this?
Was This Post Helpful? 0
  • +
  • -

#3 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8325
  • View blog
  • Posts: 31,857
  • Joined: 06-March 08

Re: Recursive Traveling Salesman Solution

Posted 06 December 2012 - 09:48 PM

First feeling: over and over complicating for nothing
Why Vertices ? You just like trouble
Was This Post Helpful? 0
  • +
  • -

#4 itsjimmy91  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 77
  • Joined: 19-January 11

Re: Recursive Traveling Salesman Solution

Posted 06 December 2012 - 10:32 PM

Hmmm.. just thought it would be easier to keep track of things.
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10397
  • View blog
  • Posts: 38,465
  • Joined: 27-December 08

Re: Recursive Traveling Salesman Solution

Posted 07 December 2012 - 09:45 PM

A big component of backtracking is undoing a move that doesn't pan out. So add a vertex, run through, then remove the Vertex from the Path. That's why it isn't evaluating all 5! paths.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1