Tammet – 17. november 2008, kell 12:37

2008-11-17T12:37:34Z

Uus lehekülg

<pre>
class Tsp {
static int cities=15;
/*
static int dist[][] =
{{0, 5, 4, 3},
{5, 0, 2, 9},
{4, 2, 0, 6},
{3, 9, 6, 0}};
*/
static int dist[][] = {
{0,92,85,178,206,105,121,223,160,12,183,179,26,220,233,184,151,210,224,231,126,216,161,217,178,156,13,131,271,265,89,107,203,90,146,70,224,185,144,183,166,179,244,69,60,247,196,152,156,111,211,43,94,71,36,144,67,123,94},
{92,0,68,270,298,197,137,213,131,80,250,272,118,245,223,95,243,231,317,323,218,268,72,268,89,147,105,223,261,255,40,171,295,138,57,162,242,206,218,276,77,271,234,161,125,340,265,191,216,84,304,54,159,37,100,237,132,34,158},
{85,68,0,262,290,189,90,167,84,72,204,235,111,199,177,117,236,184,309,315,210,222,103,221,120,100,97,216,215,209,22,136,258,92,61,154,196,160,190,268,94,228,188,153,93,332,219,145,170,37,296,42,141,60,69,229,117,64,135},
{178,270,262,0,31,175,219,265,280,190,138,76,152,233,256,347,84,208,158,56,50,168,339,120,356,255,171,66,312,306,266,153,93,189,293,108,237,199,91,9,312,82,285,123,183,73,99,202,196,249,145,221,141,249,204,78,170,300,149},
{206,298,290,31,0,203,250,296,311,218,170,107,180,264,287,378,118,239,103,25,78,199,367,151,384,286,199,97,343,338,294,185,124,221,325,136,269,231,122,22,344,113,317,151,215,42,130,234,227,280,58,249,172,277,232,106,201,328,181},
{105,197,189,175,203,0,216,302,256,117,222,176,79,270,293,288,148,260,221,228,123,261,266,214,283,248,98,128,349,343,193,153,200,185,234,67,274,235,152,180,265,176,322,66,140,244,193,202,206,209,208,148,140,176,131,141,162,227,106},
{121,137,90,219,250,216,0,104,62,119,120,173,136,136,114,152,237,101,309,275,211,138,162,138,179,37,133,154,152,146,96,74,196,30,102,158,133,76,128,228,116,165,125,148,76,292,150,61,86,53,297,121,78,139,85,230,56,124,107},
{223,213,167,265,296,302,104,0,96,221,149,193,239,32,10,219,310,60,384,322,276,128,239,153,256,71,236,233,48,42,173,149,217,133,179,244,29,67,212,274,183,186,21,234,178,338,165,97,95,130,371,198,162,216,188,304,158,201,196},
{160,131,84,280,311,256,62,96,0,158,181,233,177,128,106,136,297,124,370,336,271,162,156,186,174,29,172,214,144,138,91,134,257,91,96,215,125,100,189,289,100,226,117,206,137,353,198,122,147,47,357,115,139,133,125,290,117,118,167},
{12,80,72,190,218,117,119,221,158,0,181,192,38,218,231,172,163,208,237,243,138,214,149,229,166,154,25,143,269,263,76,105,215,89,133,82,223,183,142,196,154,191,242,81,58,260,208,150,154,99,224,31,92,59,34,157,65,110,92},
{183,250,204,138,170,222,120,149,181,181,0,67,199,117,140,266,183,92,257,195,149,52,276,26,293,156,196,96,196,191,210,80,90,115,216,157,122,84,70,147,229,59,170,170,138,211,38,72,66,167,244,209,94,237,148,177,118,237,128},
{179,272,235,76,107,176,173,193,233,192,67,0,154,161,184,301,125,136,198,132,90,96,307,48,324,208,173,50,240,235,241,108,24,143,247,112,166,128,58,85,266,8,214,125,157,149,26,131,125,202,185,222,108,250,166,118,137,269,119},
{26,118,111,152,180,79,136,239,177,38,199,154,0,236,249,210,125,226,199,205,100,232,187,191,204,172,19,105,287,281,115,123,177,106,172,44,240,201,129,158,192,153,260,43,76,222,170,168,172,130,186,69,110,97,52,119,83,149,82},
{220,245,199,233,264,270,136,32,128,218,117,161,236,0,23,251,278,36,352,289,244,96,270,121,288,103,233,201,79,73,205,117,185,164,211,212,4,35,180,242,215,154,52,202,210,306,133,65,63,162,339,230,130,248,185,272,156,232,164},
{233,223,177,256,287,293,114,10,106,231,140,184,249,23,0,229,301,51,375,313,267,119,249,144,266,81,246,224,57,51,183,140,208,143,189,235,20,58,203,265,193,177,30,225,188,329,156,88,86,140,362,208,153,226,198,295,168,211,187},
{184,95,117,347,378,288,152,219,136,172,266,301,210,251,229,0,335,246,408,403,309,284,95,283,112,153,197,282,267,261,95,202,324,157,54,253,248,222,256,356,36,293,241,252,198,420,285,206,232,100,395,141,206,134,173,328,184,62,232},
{151,243,236,84,118,148,237,310,297,163,183,125,125,278,301,335,0,253,73,121,34,213,312,165,329,272,144,89,357,352,240,176,148,206,281,81,283,245,115,90,311,127,331,96,164,77,144,226,230,255,60,194,163,222,177,7,185,274,130},
{210,231,184,208,239,260,101,60,124,208,92,136,226,36,51,246,253,0,326,264,219,71,256,95,273,99,223,175,107,101,190,107,159,123,196,203,40,24,154,217,210,129,80,193,164,281,107,54,54,147,313,215,121,233,175,246,145,218,155}
};
static int path[] = new int[cities];
static int bestpath[] = new int[cities];
static int calledcount=0;
static int passedcount=0;
static int pathcount=0;
static int bestlen=999999999;

public static void main(String[] args) {
int res;
int i;

System.out.println("tsp starts");
res=searchcities(0,0,0);
System.out.println("----------------------------");
System.out.println("best cost: "+res);
System.out.print("best path:");
for(i=0;i<cities;i++) {
System.out.print(" "+bestpath[i]);
}
System.out.println();
System.out.println("done paths: "+pathcount);
System.out.println("done calls: "+calledcount);
System.out.println("passed cities: "+passedcount);
}

public static int searchcities
(int curcity, int passedcities, int passedlen) {
int j;
int newcity;
int tmpres;
int bestres;
boolean usedcityflag;
boolean nogoflag;
int tmp;

calledcount++;
// just print
/*
System.out.println();
for(j=0;j<passedcities;j++) System.out.print(" ");
System.out.println
("searchcities curcity: "+curcity+
" passedcities:"+passedcities+
" passedlen: "+passedlen);
*/
// maybe reached last city?
if (passedcities>=cities-1) {
pathcount++;
tmp=passedlen+dist[curcity][0];
if (tmp<bestlen) {
bestlen=tmp;
path[passedcities]=curcity;
for(j=0;j<cities;j++) bestpath[j]=path[j];
}
return tmp;
}

passedcount++;
path[passedcities]=curcity;
bestres=99999999;
// loop over all cities
for(newcity=0;newcity<cities;newcity++) {
// search whether we have been in newcity
usedcityflag=false;
for(j=0;j<=passedcities;j++) {
if (path[j]==newcity) {
usedcityflag=true;
break;
}
}
if (!usedcityflag) {
// compute path length
//for(j=0;j<passedcities;j++) System.out.print(" ");
//System.out.print("going to city "+newcity+" ");
nogoflag=false;
if (passedcities==cities-2) {
// last city
if (bestlen<=
(passedlen+dist[curcity][newcity]+
dist[newcity][0]))
nogoflag=true;
} else {
// not last city
if (bestlen<=
(passedlen+dist[curcity][newcity])) nogoflag=true;
}
if (!nogoflag) {
tmpres=
searchcities
(newcity,
passedcities+1,
passedlen+dist[curcity][newcity]);
//System.out.println("giving length "+tmpres);
// store length if shorter than bestres
if (tmpres<bestres) bestres=tmpres;
}
}
}
return bestres;
}

}

</pre>

Travelling salesman - Redigeerimiste ajalugu

Tammet – 17. november 2008, kell 12:37