Quote:
Originally posted by dcann1222@Aug 19 2003, 04:08 AM
Quote:
It takes my script 0.53 seconds to solve and I get the path:
D I G E H L K J F C B A 65
|
Wow, that's great. Are you checking all possible routes? My script solves the 5-destination route in 0.02 seconds, but it grows exponentially from there.
For example:
5 points = 120 possible routes (0.02 sec)
6 points = 720 possible routes (0.1 sec)
...
12 points = 479,001,600 possible routes (hours)
...
26 points = 403,291,461,126,606,000,000,000,000 possible routes (years!)
When calculating all of the possible permutations of the points, processing time quickly becomes unreasonable. I'd like to see how you guys solved this problem.
|
You can use pruning to get the result space down. For instance if you know you have a solution that's 56, and you've got A B C D E F 60, then you don't have to worry about the permutations of G H I J K L (saving 5! or 120 permutations). If you catch the "error" earlier, then you save even more.
Yesterday I thought of an even better solution which goes along the lines of:
PHP Code:
// $bestdisttable[$a][$b] is the shortest path from $a to $b, calculated by using dijikstra in my case
$moves = explode(" ", $moves);
if (count($moves) == 2) {
// assume that there is a path at least.
if ($bestdisttable[$moves[0]] < $bestdisttable[$moves[1]]) {
echo $moves[0]." ".$moves[1]." "($bestdisttable[$moves[0]] < $bestdisttable[$moves[1]]);
} else {
die($moves[0]." ".$moves[1]." "($bestdisttable[$moves[0]] < $bestdisttable[$moves[1]]));
}
} else if (count($moves) == 1) {
die($moves[0]." 0");
}
// we have 3 or more elements. Have fun with them!
$movesleft = heap(); // theoretical function. I didn't make this yet
foreach ($bestdisttable as $from=>$bestdist) {
foreach ($bestdist as $to=>$dist) {
$movesleft->insert = array("score" => $dist, "path" => array($from, $to));
}
while ($work = $movesleft->lowest()) {
if (count($work["path"]) == count($moves) {
// if this is the first complete path, then it's a winner since you can't get lower than this by having a longer distance incomplete path added to some value.
die (implode(" ", $work["path"])." ".$work["score"]);
} else {
// otherwise put all the permutations from here on the heap
foreach ($moves as $move) {
if (in_array($move, $work["path"])) continue;
$copy = $work;
$last = $copy["path"][count($copy["path"])-1];
$copy["path"][] = $move;
$copy["score"] += $bestdisttable[$last][$move];
$movesleft->insert($copy);
}
}
}
}
There's still lots of optimizations to be done, but it's too late for the contest anyways, so I didn't worry about it (I actually wrote it in this box). I haven't done any complexity tests, but I think it's still along the lines of n! worst-case, and much faster in the average-case