X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~yarrgweb/git?a=blobdiff_plain;f=yarrg%2Frssearch.c;h=646c796196d69a364034eed7f302a216fe31d040;hb=d66f27768708df0b8ce256e2d868ff4f7060ef3f;hp=0286584dddaa5f5045ce392a2b3e2350f119b0f8;hpb=39c06791f9cefbedf3438c2a661716142c889bee;p=ypp-sc-tools.main.git diff --git a/yarrg/rssearch.c b/yarrg/rssearch.c index 0286584..646c796 100644 --- a/yarrg/rssearch.c +++ b/yarrg/rssearch.c @@ -15,6 +15,7 @@ static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */ static sqlite3_stmt *ss_neigh; static int ports[MAX_ROUTELEN]; +static int final_isle; static Neighbour *get_neighbours(int isle) { Neighbour **np= &neighbours[isle]; @@ -23,7 +24,8 @@ static Neighbour *get_neighbours(int isle) { SQL_BIND(ss_neigh, 1, isle); while (SQL_STEP(ss_neigh)) { - Neighbour *add= mmalloc(sizeof(*add)); + Neighbour *add; + NEW(add); add->islandid= sqlite3_column_int(ss_neigh, 0); add->dist= sqlite3_column_int(ss_neigh, 1); add->next= head; @@ -39,35 +41,26 @@ static Neighbour *get_neighbours(int isle) { static PotentialResult ***strat_base; -static inline int isle2arch(int isle) { - int arch= islandid2arch[isle]; - assert(arch>=0); - return arch; -} - static double process_route(int nports, int totaldist, double overestimate_excepting_tail) { - int i; + int i, ap; int leagues_divisor= totaldist + nports; ctr_routes_considered++; + int wrong_final= final_isle && ports[nports-1] != final_isle; + debugf("========== ROUTE"); for (i=0; i=2) { int pair[2], i; pair[1]= ports[nports-1]; - double guess_absolute= overestimate_excepting_tail; - + guess[A]= overestimate_excepting_tail; + for (i=0; iroute_tail_value= value_route(2, pair, pair[0]!=pair[1]); } - guess_absolute += ip->route_tail_value; + guess[A] += ip->route_tail_value; + } + guess[P]= guess[A] / leagues_divisor; + + if (wrong_final) { + ctr_routes_wrongfinalelim++; + debugf(" WFELIM\n"); + return guess[A]; } - double guess_perleague= guess_absolute / leagues_divisor; - if (guess_absolute <= strat->absolute && - guess_perleague <= strat->perleague) { - ctr_routes_eliminated++; - debugf(" ELIM %f %f\n", guess_absolute, guess_perleague); - return guess_absolute; + if (guess[A] <= highscores[A][0].value && + guess[P] <= highscores[P][0].value) { + ctr_routes_quickelim++; + debugf(" QELIM %f %f\n", guess[A], guess[P]); + return guess[A]; } - debugf(" COMPUTE %f %f\n", guess_absolute, guess_perleague); } - ctr_routes_valued++; + int finisle= ports[nports-1]; int finarch= isle2arch(finisle); + int midarch= route2midarch(ports,nports); - double absolute= value_route(nports, ports, 0); - double perleague= absolute / leagues_divisor; + PotentialResult **strat_fin= ONDEMAND(strat_base[finarch], narches); + PotentialResult *strat= ONDEMAND(strat_fin[midarch], 1); - if (absolute <= strat->absolute && - perleague <= strat->perleague) - return absolute; + if (nports>=2) { + if (guess[A] <= strat->value[A] && + guess[P] <= strat->value[P]) { + ctr_routes_stratelim++; + debugf(" ELIM %f %f\n", guess[A], guess[P]); + return guess[A]; + } + debugf(" COMPUTE %f %f\n", guess[A], guess[P]); + } - debugf(" SOMEHOW BEST\n"); + ctr_routes_valued++; - fildebugf("final %d:%3d mid %d:%3d ",finarch,finisle,midarch,midisle); + double value[AP]; + value[A]= value_route(nports, ports, 0); + value[P]= value[A] / leagues_divisor; -#define CHK(absperl) \ - fildebugf(#absperl " %15f", absperl); \ - if (absperl < strat->absperl) { \ - debugf(" "); \ - } else { \ - strat->absperl= absperl; \ - memcpy(strat->absperl##_ports, ports, sizeof(*ports) * nports); \ - fildebugf("** "); \ + if (wrong_final) { + ctr_routes_wrongfinal++; + return value[0]; } - CHK(absolute) - CHK(perleague) + if (value[A] <= strat->value[A] && + value[P] <= strat->value[P]) + return value[A]; + + debugf(" SOMEHOW BEST\n"); + + fildebugf("final %d:%3d mid %d ",finarch,finisle,midarch); + + for (ap=0; apvalue[ap]) { + debugf(" "); + } else { + int pos; + ctr_newbests_strat[ap]++; + strat->value[ap]= value[ap]; + memcpy(strat->ports[ap], ports, sizeof(*ports) * nports); + if (nports < MAX_ROUTELEN-1) strat->ports[ap][nports]= -1; + fildebugf("** "); + for (pos=0; pos < nhighscores[ap]; pos++) + if (highscores[ap][pos].pr == strat) goto found; + /* not found */ + pos= -1; + found: + for (;;) { + pos++; + if (pos >= nhighscores[ap]-1) break; /* new top */ + if (highscores[ap][pos].value >= value[ap]) break; /* found spot */ + if (pos>0) + highscores[ap][pos-1]= highscores[ap][pos]; + } + pos--; + if (pos>0) { + highscores[ap][pos].value= value[ap]; + highscores[ap][pos].pr= strat; + } + fildebugf("@%2d", pos); + } + } fildebugf(" route"); @@ -121,7 +160,7 @@ static double process_route(int nports, int totaldist, fildebugf(" %d",ports[i]); fildebugf("\n"); - return absolute; + return value[0]; } static void recurse(int last_isle, @@ -141,18 +180,22 @@ static void recurse(int last_isle, } } -void search(int start_isle, PotentialResult ****strat_base_io) { +void search(int start_isle, int final_isle_spec, + PotentialResult ****strat_base_io) { strat_base= ONDEMAND(*strat_base_io, narches); + final_isle= final_isle_spec <= 0 ? 0 : final_isle_spec; recurse(start_isle,0,0,1e6); } +int nhighscores[AP]; +HighScoreEntry *highscores[AP]; int narches; char **archnames; int *islandid2arch; void setup_search(void) { - neighbours= mcalloc(sizeof(*neighbours) * islandtablesz); + MCALLOC(neighbours, islandtablesz); SQL_PREPARE(ss_neigh, "SELECT biid, dist FROM routes WHERE aiid=?"); @@ -162,10 +205,8 @@ void setup_search(void) { " SELECT DISTINCT archipelago\n" " FROM islands\n" " )"); - archnames= mcalloc(sizeof(*archnames) * max_narches); - islandid2arch= mmalloc(sizeof(*islandid2arch) * islandtablesz); - int i; - for (i=0; i