traveling-salesman - 澄清旅行推销员的制定

Question

我一直在研究旅行商问题，我有一个关于它是如何制定的问题。或者这可能是关于分类或子问题名称或问题变体的问题。

在旅行商问题中，城市在空间中的位置以及城市之间的距离被测量以形成具有加权连接的图，或者可以任意选择边缘上的权重，即使它们可能使城市无法布局在地图上？

如果其中一个被认为是标准的旅行推销员问题，那么另一个有名称吗？

Answer 1

在公制 tsp 中，它满足三角形不等式，但如果您有单向街道或山脉、峡谷等障碍物，则不是公制 tsp。

Answer 2

TSP 可以通过多种方式定义。您正在描述对称的欧几里得 TSP，其中权重对应于节点之间的实际距离，并且在节点之间的巡回中顺时针行驶会给出。正如 Phpdna 所建议的，三角不等式得到满足。

但是，这不是 TSP 的标准定义。事实上，这是子问题或特例。一般问题可以在每对节点之间具有任何权重，并且不必是欧几里得距离。

例如，如果您试图通过旅行成本而不是距离来制定最短旅行，那么您会将城市之间的旅行成本作为顶点之间的权重......这可以是任何东西。在欧几里得地图上，城市 A 可能最接近城市 B，但无论出于何种原因，从 A 到 B 的旅行成本可能远高于从 A 到 C 到 B 的成本。这是一般情况。但无论哪种方式，它们都是 NP 难的。