3

ユークリッド TSP は NP 完全であることが知られています。

私の特別なメトリックでは、A と B の間の距離は次のように定義されます。

  • A から B へ = max(x coordinate of A , y coordinate of B);
  • BからAへ= max(x coordinate of B , y coordinate of A)。

これはまだNP完全ですか？

4

1 に答える 1