4 ms·
I'm no expert, but I don't think the "metric" in "Metric TSP problem" means "embeddable in a 2-D space." If you pick random points in a 500-dimensional space,
by yongjik 11y ago
I'm no expert, but I don't think the "metric" in "Metric TSP problem" means "embeddable in a 2-D space." If you pick random points in a 500-dimensional space, the graph is metric.
But how do you define "intersecting paths" there?
- jsprogrammer 11y agoIf any path segments/lines intersect/cross on any plane, then the path is not a solution.
- bmm6o 11y agoI think the point is that random lines in space (dimension > 2) intersect with probability 0, and so that shortcut almost never applies.
- jsprogrammer 11y agoYou should be able to "wrap a hull" around all the points. If there is no hull that can be wrapped without intersecting a path segment, the path is not a solution. Basically you are checking for line-plane intersections. A solution should outline a "non-self-intersecting volume".
- yongjik 11y agoDefining a convex hull in a 100-dimensional space requires 101 points. You can easily have a scenario where the only available "convex hull" is the one that contains the entire graph. In fact, I'm sure that a "randomly chosen" metric graph will be of this variety.
- jsprogrammer 11y agoSounds like something that would be easy to simulate and measure. Also, the hull needn't be convex.