static double best_absolute, best_perleague;
-static void process_route(int nports, int totaldist) {
+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");
- double absolute= value_route(nports, ports);
- double perleague= absolute / (totaldist + nports);
+ 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;
+ if (absolute <= best_absolute && perleague <= best_perleague)
+ return absolute;
+
+ debugf(" SOMEHOW BEST\n");
#define CHK(absperl) \
fprintf(stderr,#absperl " %15f", absperl); \
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) {
#define TRADES_PER_BLOCK 10
-typedef struct TradesBlock{
+typedef struct TradesBlock {
struct TradesBlock *next;
Trade t[TRADES_PER_BLOCK];
} TradesBlock;
-typedef struct {
- double distance_loss_factor;
- int ntrades;
- TradesBlock *trades;
-} IslandPair;
-
-IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
+static IslandPair ***ipairs; /* ipairs[sislandid][dislandid] */
typedef struct IslandTradeEnd {
struct IslandTradeEnd *next;
add_constraint(startrow+leg, value);
}
-static IslandPair *ipair_get(int si, int di) {
+IslandPair *ipair_get(int si, int di) {
IslandPair *ip, **ipa;
assert(si < islandtablesz);
ipa[di]= ip= mmalloc(sizeof(*ip));
ip->ntrades= 0;
ip->trades= 0;
+ ip->route_tail_value= -1;
int inblock= TRADES_PER_BLOCK;
TradesBlock *block=0, **tail=&ip->trades;
return ip;
}
-double value_route(int nislands, const int *islands) {
+double value_route(int nislands, const int *islands, int exclude_arbitrage) {
int s,d;
/* We need to construct the LP problem. GLPK talks
s++, delay_slot_loss_factor *= LOSS_FACTOR_PER_DELAY_SLOT) {
int si= islands[s];
- for (d=s; d<nislands; d++) {
+ for (d= s + exclude_arbitrage;
+ d < nislands;
+ d++) {
int di= islands[d];
int already_d;
for (already_d=s+1; already_d<d; already_d++)