3 ms·
Only in the worst case and large N. For practical problems, it’s solvable for tens of thousands of nodes.
by domoritz 3y ago
Only in the worst case and large N. For practical problems, it’s solvable for tens of thousands of nodes.
- Sai_ 3y agoA cab service with unknown, frequently updated nodes where edge weights - driving distance from last drop to next pickup- can vary, would qualify as pretty bad version of TSP. You can come up with a good enough solution but it’s not “solved”. This “good enough” solution starts to break down whenever there is a huge concentration of drivers in a location. If this weren’t the case, ride shares wouldn’t have had to add a cancellation fee and hidden destinations from drivers.