Tammet – 23. november 2010, kell 03:56

2010-11-23T03:56:24Z

←Vanem redaktsioon		Redaktsioon: 23. november 2010, kell 05:56
1. rida:		1. rida:
			<pre>
	// Travelling Salesman Problem		// Travelling Salesman Problem
	// Depth first search		// Depth first search
90. rida:		91. rida:

	} // end of class		} // end of class
			</pre>

Tammet – 23. november 2010, kell 03:55

2010-11-23T03:55:37Z

Uus lehekülg

// Travelling Salesman Problem
// Depth first search
// Fourth attempt: improved algorithm
// we will not continue searching paths
// which are ALREADY worse than the best one
// found so far

public class Tsp4 {

static int cities=10; // nr of cities
static int nodeslooked=0; // count nodes in search
static int leaveslooked=0; // count leaves in search
static int best=9999999; // global variable recording best distance
// Matrix of distances (cost to travel) between cities
static int dist[][] =
{{0,5,4,3,7,1,3,6,9,2},
{5,0,2,9,4,1,7,2,3,4},
{4,2,0,6,7,2,4,6,8,9},
{3,9,6,0,6,2,5,6,9,9},
{4,2,2,6,0,2,4,5,8,9},
{3,9,6,6,6,0,5,6,9,4},
{1,9,3,2,6,2,0,6,1,5},
{3,2,0,6,2,2,4,0,2,3},
{7,9,6,7,6,1,5,6,0,2},
{1,8,2,7,6,1,3,6,2,0}};

static int passedcities[]; // passed cities on a path
static int bestpath[]; // best path so far

public static void main(String[] args) {
// create helper arrays
passedcities = new int[cities];
bestpath = new int[cities];
// search from city 0, with 0 passed and 0 cost of travel so far
search(0,0,0);
// print out result
System.out.println("examined nodes during search: "+nodeslooked);
System.out.println("examined leaves during search: "+leaveslooked);
System.out.println("best cost: "+best);
System.out.println("best path: ");
for (int i=0; i<cities; i++) System.out.print(bestpath[i] + " ");

}

// The recursive search function
//
// city: nr of city just arrived into
// passed: number of cities passed so far
// passedlen: length (cost) travelled so far

static void search(int city, int passed, int passedlen) {
//System.out.println("city: "+city+" passed: "+passed+
// " passedlen: "+passedlen);
nodeslooked++;
// store the new passed city in the passed array
passedcities[passed]=city;
// maybe we have travelled through all cities - 1?
if (passed==(cities-1)) {
leaveslooked++;
// compute the final length (trip to home is left!)
int length=passedlen+dist[0][city];
// save the length and path if we are back home
// and the length found is best so far
if (length<best) {
best=length;
for (int i=0; i<cities; i++) bestpath[i]=passedcities[i];
}
// if not all cities have been passed, try all cities
// not yet passed
} else {
// loop over all cities
for(int next=0; next<cities; next++) {
// if the distance will be less
// than the best distance so far, ONLY THEN GO!
if (passedlen+dist[city][next] < best) {
// check if next is OK (not passed yet)
boolean okcity=true;
for (int i=0; i<passed+1 && okcity; i++)
if (passedcities[i]==next) okcity=false;
if (okcity) { // if ok, continue search
search(next,
passed+1,
passedlen+dist[city][next]);
}
}
}
}

}

} // end of class

TSP programmi Java lähtekood - Redigeerimiste ajalugu

Tammet – 23. november 2010, kell 03:56

Tammet – 23. november 2010, kell 03:55