4 ms·
It reduces to a special case called the metric TSP. If going through node C is shorter than going from A to B directly, then just replace the A-to-B distance wi
by DerekL 10y ago
It reduces to a special case called the metric TSP. If going through node C is shorter than going from A to B directly, then just replace the A-to-B distance with the length of A-to-C-to-B. It's just as hard to solve as regular TSP, but easier to approximate.
- lorenzhs 10y agoWell yeah it's clearly still NP-complete. But the TSP (or variant thereof) isn't related to the routing engine at all, as the routing engine only defines the edge weights. They're fairly orthogonal problems. Logistics software needs to solve both, but consumer satnav doesn't.