changes to TSP
authorYanhuaSun <sun51@illinois.edu>
Fri, 6 May 2011 06:09:33 +0000 (01:09 -0500)
committerYanhuaSun <sun51@illinois.edu>
Fri, 6 May 2011 06:09:33 +0000 (01:09 -0500)
examples/charm++/state_space_searchengine/TSP_SE/Makefile
examples/charm++/state_space_searchengine/TSP_SE/main.C
examples/charm++/state_space_searchengine/TSP_SE/searchEngineAPI.C

index c3120c7e27c51343ee0061028f939589e76d5121..4665963c7cab0766a78bbe6a27bdbf11b33dc5f8 100644 (file)
@@ -1,6 +1,6 @@
 OPTS =  -DBRANCHBOUND -DUSEINTPRIORITY #-DSTATISTIC#  -DOPTIMIZE #-DUSEPRIORITY -DOPTIMIZE #-DADPATIVE
 
-OPTS += -I../template -L../template
+OPTS += -I../searchengineLib -L../searchengineLib
 
 include ../Makefile.common
 
index 9d57918aa8316d04ac0638a0a0061d5d320e8113..9ee10759d4d6956dfec9344e7317f37077976108 100644 (file)
@@ -14,7 +14,7 @@ int  N, maxD;
 
 #undef M_PI
 #define M_PI 3.14159265358979323846264
-
+/*
 int geom_edgelen (int i, int j, CCdatagroup *dat)
 {
      double lati, latj, longi, longj;
@@ -33,7 +33,7 @@ int geom_edgelen (int i, int j, CCdatagroup *dat)
      q5 = cos(lati - latj) * q4 * q4 - cos(lati + latj) * q3 * q3;
      return (int) (6378388.0 * atan2(sqrt(q1*q1 + q2*q2), q5) + 1.0);
 }
-
+*/
 void readinput(char* filename)
 {
     FILE *file;
index b1582f571d402644ec0af04b87a2197ffb30db2d..9fda109b3707f07bc62eb3cacd38474da737ef86 100644 (file)
@@ -25,10 +25,12 @@ public:
        int length; // length
        double cost;
     int *tour;
+    int *intour;
 
     void initialize()
     {
         tour = (int*) ( (char*)this+sizeof(TspBase));
+        intour = (int*) ((char*) this+sizeof(TspBase)+sizeof(int)*N);
     }
     void copy(TspBase *parent)
     {
@@ -39,7 +41,10 @@ public:
         {
             tour[i] = parent->tour[i];
         }
-
+        for(int i=0; i<N; i++)
+        {
+            intour[i] = parent->intour[i];
+        }
     }
 
     double lowerbound()
@@ -48,21 +53,24 @@ public:
         temp_graph.resize(N*N);
         for(int i=0; i<N*N; i++)
             temp_graph[i] = graph[i];
-
-        if(length >= 2)
+        if(length == 1)
         {
-            int v1 = tour[0];
-            int v2 = tour[1];
-            temp_graph[v1*N+v2] = maxD;
-            temp_graph[v2*N+v1] = maxD;
+            int v0=tour[0];
+            int v1=tour[1];
+            temp_graph[v0*N+v1]=maxD;
+            temp_graph[v1*N+v0]=maxD;
+        }
+        else if(length >= 2)
+        {
+            int v1;
             for(int i=1; i<length-1; i++)
             {
                 v1=tour[i];
-                v2 = tour[i+1];
-
                 for(int j=0; j<N; j++)
-                    temp_graph[v1*N+j] = maxD;
-                temp_graph[v2*N+v1]= maxD;
+                {
+                    temp_graph[v1*N+j] = maxD; //whole row
+                    temp_graph[j*N+v1]= maxD;  //whole column
+                }
             }
         }
         double lower_sum = 0;
@@ -73,20 +81,23 @@ public:
                 lower_sum += *min_element(temp_graph.begin()+i*N, temp_graph.begin()+(i+1)*N);
             }else
             {
-                int j;
-                for( j=1; j<length-1; j++)
+                if(intour[i])
+                    continue;
+                //find the minimum and second minimum element
+                int m_min, m2_min;
+                m_min = m2_min=temp_graph[i*N];
+                for(int j=1; j<N; j++)
                 {
-                    if(i == tour[j])
-                        break;
+                    if(temp_graph[j]<m_min)
+                    {
+                        m2_min=m_min;
+                        m_min=temp_graph[j];
+                    }
                 }
-                if(j < length-1)
-                    continue;
-                sort(temp_graph.begin()+i*N, temp_graph.begin()+(i+1)*N-1);
-
-                lower_sum += temp_graph[i*N] + temp_graph[i*N+1];
+                lower_sum += m_min+m2_min;
             }
         }
-        return (cost + lower_sum); 
+        return (cost + 0.5*lower_sum); 
     }
 
     void printInfo()
@@ -119,6 +130,9 @@ inline void createInitialChildren(Solver *solver)
     state->tour[0]=0;
     state->length=1;
     state->cost = 0;
+    for(int i=1; i<N; i++)
+        state->intour[i]=0;
+    state->intour[0] = 1;
 #ifdef USEINTPRIORITY
     solver->setPriority(state, (int)lowerBound(state));
 #endif
@@ -134,38 +148,16 @@ inline void createChildren( StateBase *_base , Solver* solver, bool parallel)
     int childIndex = 0;
     int last = s->tour[s->length-1];
     /* construct the current graph, remove all the edges already in the path */
-    vector< int > temp_graph;
-    temp_graph.resize(N*N);
-    for(int i=0; i<N*N; i++)
-        temp_graph[i] = graph[i];
-
-    if(s->length >= 2)
-    {
-        int v1 = s->tour[0];
-        int v2 = s->tour[1];
-        temp_graph[v1*N+v2] = maxD;
-        temp_graph[v2*N+v1] = maxD;
-        for(int i=1; i<s->length-1; i++)
-        {
-            v1=s->tour[i];
-            v2 = s->tour[i+1];
-
-            for(int j=0; j<N; j++)
-                temp_graph[v1*N+j] = maxD;
-            temp_graph[v2*N+v1]= maxD;
-        }
-    }
-    
     for(int j=0; j<N; j++)
     {
-        if(last == j || temp_graph[last*N+j] == maxD)
+        if(last == j || s->intour[j])
             continue;
         if(s->length == N)
         {
             if(j == 0)
             {
                 //s->printInfo();
-                solver->updateCost(s->cost+temp_graph[last*N+j]);
+                solver->updateCost(s->cost+graph[last*N+j]);
                 //solver->reportSolution(); 
             }
         }else
@@ -174,9 +166,9 @@ inline void createChildren( StateBase *_base , Solver* solver, bool parallel)
             NewTour->initialize();
             NewTour->copy(s);
             NewTour->tour[s->length] = j;
+            NewTour->intour[j]=1;
             NewTour->length = s->length + 1;
-            
-            NewTour->cost = s->cost + temp_graph[last*N+j];
+            NewTour->cost = s->cost + graph[last*N+j];
 #ifdef USEINTPRIORITY
             solver->setPriority(NewTour, (int)lowerBound(NewTour));
 #endif