# Recursive Traveling Salesman Solution

Page 1 of 1

## 4 Replies - 6830 Views - Last Post: 07 December 2012 - 09:45 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=303016&amp;s=050ca21dce1eba7671fa9d6207e1a1db&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 itsjimmy91

Reputation: 1
• 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

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;
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;

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
}
} 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)))
{
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;
}

{
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

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

## Re: Recursive Traveling Salesman Solution

Posted 06 December 2012 - 05:07 PM

Any ideas on this?

### #3 pbl

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

Reputation: 8378
• Posts: 31,956
• 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

### #4 itsjimmy91

Reputation: 1
• 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.

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12242
• Posts: 45,328
• 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.