TSP problem fixed
[charm.git] / examples / charm++ / state_space_searchengine / TSP_SE / searchEngineAPI.C
1 /*
2  * exampleTsp.C
3  *
4  *  Created on: Mar 4, 2010
5  */
6
7 #include "searchEngine.h"
8 #include "exampleTsp.h"
9
10 #include <vector>
11 #include <string>
12 #include <iostream>
13 #include <cstdlib>
14 #include <algorithm>
15 using namespace std;
16
17 extern int se_statesize;
18
19 /*readonly*/ extern int initial_grainsize;
20 #define MAX 100000
21 extern CkVec< double > graph; 
22 class TspBase: public StateBase
23 {
24 public:
25         int length; // length
26         double cost;
27     double lowerBoundValue;
28     int *tour;
29     int *intour; //whether a node is in tour or not
30
31     void initialize()
32     {
33         tour = (int*) ( (char*)this+sizeof(TspBase));
34         intour = (int*) ((char*) this+sizeof(TspBase)+sizeof(int)*N);
35     }
36     void copy(TspBase *parent)
37     {
38         length = parent->length;
39         cost = parent->cost;
40         lowerBoundValue = parent->lowerBoundValue;
41         for(int i=0;i<length; i++)
42         {
43             tour[i] = parent->tour[i];
44         }
45         for(int i=0; i<N; i++)
46         {
47             intour[i] = parent->intour[i];
48         }
49     }
50
51     double lowerbound()
52     {
53         
54         double lower_sum = 0;
55         for(int i=0; i<N; i++)
56         {
57             if(intour[i] == 2)
58                 continue;
59             if(intour[i] == 1 && i!=0)
60             {
61                 double m_min=MAX;
62                 for(int j=0; j<N; j++)
63                 {
64                     if((intour[j] ==0 && graph[j]<m_min) || (length==N && intour[j]==1))
65                         m_min= graph[j];
66                 }
67                 lower_sum += m_min;
68             }else
69             {
70                 double m_min, m2_min;
71                 m_min = m2_min=graph[i*N];
72                 for(int j=i*N+1; j<i*N+N; j++)
73                 {
74                     if(graph[j]<m_min)
75                     {
76                         m2_min=m_min;
77                         m_min=graph[j];
78                     }
79                 }
80                 lower_sum += m_min+m2_min;
81             }
82         }
83         lowerBoundValue = (cost + 0.5*lower_sum);
84         return lowerBoundValue; 
85     }
86
87     double getLowerBound()
88     {
89         return lowerBoundValue;
90     }
91
92     void printInfo()
93     {
94         CkPrintf("\n length=%d, lowerBound=%f", length, lowerBoundValue);
95         for(int i=0; i<length; i++)
96         {
97             CkPrintf("(%d, value=%f", tour[i], graph[tour[i]*N+tour[(i+1)%N]]);
98             CkPrintf("%d)", intour[tour[i]]);
99         }
100     }
101 };
102
103
104 inline double cost( StateBase *s )
105 {
106     return ( ((TspBase*)s)->cost);                                      // cost of given node
107 }
108
109 inline double lowerBound( StateBase *s)
110 {
111     return ((TspBase*)s)->getLowerBound();
112 }
113
114 inline void createInitialChildren(Solver *solver)
115 {
116
117     se_statesize = sizeof(TspBase)+2*sizeof(int)*N;
118     TspBase *state = (TspBase*)solver->registerRootState(sizeof(TspBase)+2*sizeof(int)*N, 0, 1);
119     state->initialize();
120     state->tour[0]=0;
121     state->length=1;
122     state->cost = 0;
123     for(int i=0; i<N; i++)
124         state->intour[i]=0;
125     state->lowerbound();
126 #ifdef USEINTPRIORITY
127     solver->setPriority(state, (int)lowerBound(state));
128 #endif
129     solver->process(state);
130 }
131
132 inline void createChildren( StateBase *_base , Solver* solver, bool parallel)
133 {
134
135     TspBase *s = (TspBase*)alloca(sizeof(TspBase)+2*sizeof(int)*N);
136     s->initialize();
137     ((TspBase*)_base)->initialize();
138     s->copy((TspBase*)_base);
139     int childIndex = 0;
140     int last = s->tour[s->length-1];
141     int childNum = 0;
142     //CkPrintf("lower bound=%f\n", s->getLowerBound());
143     /* construct the current graph, remove all the edges already in the path */
144     //s->printInfo();
145     for(int j=0; j<N; j++)
146     {
147         //CkPrintf("last=%d,j=%d, intour=%d\n", last, j, s->intour[j]);
148         if(last == j || s->intour[j]==2 || (j==0&&s->length<N))
149             continue;
150         if(s->length == N)
151         {
152             if(j == 0)
153             {
154                 //s->printInfo();
155                 //CkPrintf(" cost=%f\n", s->cost+graph[last*N+j]);
156                 solver->updateCost(s->cost+graph[last*N+j]);
157                 //solver->reportSolution(); 
158             }
159         }else
160         {
161             childNum++;
162             TspBase *NewTour  = (TspBase*)solver->registerState(sizeof(TspBase)+2*sizeof(int)*N, childIndex, N);
163             NewTour->initialize();
164             NewTour->copy(s);
165             NewTour->tour[s->length] = j;
166             NewTour->intour[j]=1;
167             NewTour->intour[last] = NewTour->intour[last]+1;
168             NewTour->length = s->length + 1;
169             NewTour->cost = s->cost + graph[last*N+j];
170             NewTour->lowerbound();
171             //NewTour->printInfo();
172 #ifdef USEINTPRIORITY
173             solver->setPriority(NewTour, (int)lowerBound(NewTour));
174 #endif
175             solver->process(NewTour);
176         }
177     }
178     //CkPrintf(" %d children created\n", childNum);
179 }
180 int parallelLevel()
181 {
182     return initial_grainsize;
183 }
184
185 int searchDepthLimit()
186 {
187     return 1;
188 }
189
190     SE_Register(TspBase, createInitialChildren, createChildren, parallelLevel, searchDepthLimit, lowerBound);
191
192