4 ms·
Try all 12 possibilities for reconnecting those three chains... I'm only coming up with 8 possibilities. Pick one chain and designate it Aa. That may be follow
by jessaustin 12y ago
Try all 12 possibilities for reconnecting those three chains...
I'm only coming up with 8 possibilities. Pick one chain and designate it Aa. That may be followed by:
Bb, Cc
Bb, cC
bB, Cc
bB, cC
Cc, Bb
Cc, bB
cC, Bb
cC, bB
If distance depends on direction, multiply by 2 (for aA in addition to Aa), but that still isn't 12.
- Animats 12y agoAa can be in the middle.
- jessaustin 12y agoAa Bb Cc is identical to Cc Aa Bb (or bB aA cC). That's why we fixed one chain, to simplify the rest of the calculation. EDIT: on reading TFA I find Norvig does essentially the same thing: "So let's arbitrarily say that all tours must start with the first city in the set of cities. We'll just pull the first city out, and then tack it back on to all the permutations of the rest of the cities." Interestingly he doesn't also eliminate the Aa-aA redundancy, because "First, it would mean we can never handle maps where the distance from A to B is different from B to A. Second, it would complicate the code (if only by a line or two) while not saving much run time."
- Animats 12y agoOK, non-standard problem definition. Sorry. Usually it's an interconnection problem without specified ends.