1 | boolean tsp_seed_rjm(population *pop, entity *adam) |
---|
2 | { |
---|
3 | int i,s,tmp,j,k; |
---|
4 | int *data; |
---|
5 | int Assigned[MAX_TOWNS] ; |
---|
6 | int closest2,marker1; |
---|
7 | |
---|
8 | DBG("*** In tsp_seed_rjm, pop-<len_chromosomes = %i \n",pop->len_chromosomes); |
---|
9 | data = (int *)adam->chromosome[0]; |
---|
10 | |
---|
11 | for (i=0; i < pop->len_chromosomes; i++) Assigned[i] = -1; // these are the nodes assigned to the path |
---|
12 | |
---|
13 | for (i=0; i<pop->len_chromosomes; i++) |
---|
14 | { |
---|
15 | Assigned[i] = -1; |
---|
16 | if(ids[i] == source_id) // ie find the index where index of source_id is initially stored |
---|
17 | s = i; |
---|
18 | DBG("ids[%i] = %i, \n",i,ids[i]); |
---|
19 | } |
---|
20 | Assigned[s] = 1; // mark this vertex's index as assigned |
---|
21 | data[0] = s; // place it in the first position |
---|
22 | DBG("Postion 0 , index = %i, data[0] = %i\n",s,s); |
---|
23 | marker1 = 0; |
---|
24 | for ( k=1; k < pop->len_chromosomes; k++){ // loop through every sequential position in path not yet filled |
---|
25 | closest2 = -1; |
---|
26 | for ( i=0; i < k ; i++){ // now scan every vertex in the path which could precede a new vertex eg. 0...k |
---|
27 | for (j=0; j < pop->len_chromosomes; j++) // loop through the vertices not yet in the path eg. where Assigned[j] < 0 |
---|
28 | if ( Assigned[j] < 0 ){ // this vertex j not yet included in the path |
---|
29 | // find the unassigned vertex closest to vertex i already in the path |
---|
30 | if ( closest2 < 0 || marker1 < 0 || DISTANCE[i][j] < DISTANCE[marker1][closest2] ){ |
---|
31 | closest2 = j; // j is current index of the vertex not yet in path |
---|
32 | marker1 = i; // i is current index of vertex in path |
---|
33 | DBG("closest1 = %i,marker1 = %i\n",closest2,marker1); |
---|
34 | } |
---|
35 | } |
---|
36 | |
---|
37 | // closest1 now contains index of vertex closest to member marker1 of the assigned path |
---|
38 | DBG("marker1 = %i, closest2 = %i\n , distance between = %f",marker1,closest2,DISTANCE[data[marker1]][closest2]); |
---|
39 | } |
---|
40 | |
---|
41 | DBG("Finished second loop, closest2 = %i, marker1 = %i, index k = %i\n",closest2,marker1,k); |
---|
42 | // now closest2 contains the index of a vertex closer to a vertex in path than any other vertex not |
---|
43 | // already in the path is to any vertex in the path |
---|
44 | // shuffle the existing following entries back down the path |
---|
45 | for ( j = k -1; j > marker1; j-- ){ |
---|
46 | if ( Assigned[data[j]] ){ |
---|
47 | DBG("Shuffling data[%i] = data[%i] = %i\n",j+1,j,data[j]); |
---|
48 | data[j+1] = data[j]; |
---|
49 | } |
---|
50 | } |
---|
51 | Assigned[closest2] = 1; // mark the vertex as in the path |
---|
52 | data[k] = closest2; // add the vertex into path as successor to vertex it's closest to |
---|
53 | DBG("data[%i] = %i\n",k,closest2); |
---|
54 | |
---|
55 | } // this loop fills consecutive positions in the path |
---|
56 | |
---|
57 | return TRUE; |
---|
58 | } |
---|
59 | |
---|