#include "rscommon.h"
+DEBUG_DEFINE_DEBUGF(search);
+
typedef struct Neighbour {
struct Neighbour *next;
int islandid;
static double best_absolute, best_perleague;
-static void process_route(int nports, int totaldist) {
- double absolute= value_route(nports, ports);
- double perleague= absolute / (totaldist + nports);
+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);
+ }
- if (absolute < best_absolute && perleague < best_perleague) return;
+ 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); \
fputs(" route",stderr);
- int i;
for (i=0; i<nports; i++)
fprintf(stderr," %d",ports[i]);
putc('\n',stderr);
+
+ 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, totaldist);
+ 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) {