chiark / gitweb /
routesearch: correct elim algorithms
authorIan Jackson <ian@liberator.relativity.greenend.org.uk>
Sat, 17 Oct 2009 11:55:13 +0000 (12:55 +0100)
committerIan Jackson <ian@liberator.relativity.greenend.org.uk>
Sat, 17 Oct 2009 11:55:13 +0000 (12:55 +0100)
yarrg/rssearch.c
yarrg/x.gdb

index 881d5de..b05a275 100644 (file)
@@ -43,7 +43,7 @@ static Bucket ***buckets_base[GRANUS];
 
 static double process_route(int nports, int totaldist,
                            double overestimate_excepting_tail) {
-  int i, ap;
+  int i, ap, granui;
   int leagues_divisor= totaldist + nports;
 
   ctr_routes_considered++;
@@ -79,12 +79,15 @@ static double process_route(int nports, int totaldist,
       return guess[A];
     }
 
-    if (guess[A] <= highscores[granus-1][A][0].value &&
-       guess[P] <= highscores[granus-1][P][0].value) {
-      ctr_routes_quickelim++;
-      debugf(" QELIM %f %f\n", guess[A], guess[P]);
-      return guess[A];
+    for (granui=0; granui<granus; granui++) {
+      if (guess[A] > highscores[granui][A][0].value ||
+         guess[P] > highscores[granui][P][0].value)
+       goto not_quickelim;
     }
+    ctr_routes_quickelim++;
+    debugf(" QELIM %f %f\n", guess[A], guess[P]);
+    return guess[A];
+  not_quickelim:;
   }
 
   int finisle= ports[nports-1];
@@ -94,7 +97,6 @@ static double process_route(int nports, int totaldist,
   int midarch= route2midarch(ports,nports);
 
   Bucket *buckets[GRANUS];
-  int granui;
   for (granui=0; granui<granus; granui++) {
     Bucket **buckets_fin;
     int mid, fin;
@@ -109,12 +111,15 @@ static double process_route(int nports, int totaldist,
   }
 
   if (nports>=2) {
-    if (guess[A] <= buckets[0]->prs[A].value[A] &&
-       guess[P] <= buckets[0]->prs[P].value[P]) {
-      ctr_routes_bucketelim++;
-      debugf(" ELIM %f %f\n", guess[A], guess[P]);
-      return guess[A];
+    for (granui=0; granui<granus; granui++) {
+      if (guess[A] > buckets[granui]->prs[A].value[A] ||
+         guess[P] > buckets[granui]->prs[P].value[P])
+       goto not_bucketelim;
     }
+    ctr_routes_bucketelim++;
+    debugf(" ELIM %f %f\n", guess[A], guess[P]);
+    return guess[A];
+  not_bucketelim:
     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
   }
 
index 32daa5f..3bb9ef6 100644 (file)
@@ -1,4 +1,4 @@
 file ./routesearch
-set args OCEAN-Midnight.db 13470 20220 -1 0.0005 search 10 10 30 any 34 7 5 10 35 24 2 2>u
+set args -d OCEAN-Midnight.db -g 3 -D1 13470 20220 -1 0.0005 search 10 10 30 any 34 7 5 10 35 24 2 2>u
 #break rssearch.c:179 if ports[0]==24 && ports[1]==21
 run