#include "rscommon.h"
+DEBUG_DEFINE_DEBUGF(search);
+
typedef struct Neighbour {
struct Neighbour *next;
int islandid;
return head;
}
-static double bestsofar;
-
-static void process_route(int nports) {
- double value= value_route(nports, ports);
- if (value < bestsofar) return;
+static double best_absolute, best_perleague;
- fprintf(stderr,"value %20f route", value);
+static double process_route(int nports, int totaldist,
+ double overestimate_excepting_tail) {
int i;
+ int leagues_divisor= totaldist + nports;
+
+ debugf("========== ROUTE");
+ for (i=0; i<nports; i++)
+ debugf(" %d",ports[i]);
+ debugf("\n");
+
+ if (nports>=2) {
+ int pair[2], i;
+ pair[1]= ports[nports-1];
+ double guess_absolute= overestimate_excepting_tail;
+
+ for (i=0; i<nports; i++) {
+ pair[0]= ports[i];
+ IslandPair *ip= ipair_get(ports[nports-2], ports[nports-1]);
+ if (ip->route_tail_value < 0)
+ ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
+ guess_absolute += ip->route_tail_value;
+ }
+ double guess_perleague= guess_absolute / leagues_divisor;
+
+ if (guess_absolute <= best_absolute && guess_perleague <= best_perleague) {
+ debugf(" ELIM %f %f\n", guess_absolute, guess_perleague);
+ return guess_absolute;
+ }
+ debugf(" COMPUTE %f %f\n", guess_absolute, guess_perleague);
+ }
+
+ double absolute= value_route(nports, ports, 0);
+ double perleague= absolute / leagues_divisor;
+
+ if (absolute <= best_absolute && perleague <= best_perleague)
+ return absolute;
+
+ debugf(" SOMEHOW BEST\n");
+
+#define CHK(absperl) \
+ fprintf(stderr,#absperl " %15f", absperl); \
+ if (absperl < best_##absperl) fputs(" ",stderr); \
+ else { best_##absperl= absperl; fputs("** ",stderr); }
+
+ CHK(absolute)
+ CHK(perleague)
+
+ fputs(" route",stderr);
+
for (i=0; i<nports; i++)
fprintf(stderr," %d",ports[i]);
putc('\n',stderr);
-
- bestsofar= value;
+
+ return absolute;
}
static void recurse(int last_isle,
int nports, /* excluding last_isle */
- int totaldist /* including last_isle */) {
+ int totaldist /* including last_isle */,
+ double last_estimate) {
ports[nports++]= last_isle;
- process_route(nports);
+ double estimate= process_route(nports, totaldist, last_estimate);
if (nports >= MAX_ROUTELEN) return;
Neighbour *add;
int newdist= totaldist + add->dist;
if (newdist > max_dist) continue;
- recurse(add->islandid, nports, newdist);
+ recurse(add->islandid, nports, newdist, estimate);
}
}
void search(int start_isle) {
- recurse(start_isle,0,0);
+ recurse(start_isle,0,0,1e6);
}
void setup_search(void) {