向量维度置换后近邻曼哈顿距离和最小化问题的NP难性问询

Great question! The problem you've outlined is absolutely NP-hard. We can confirm this by reducing a classic NP-hard problem—the Traveling Salesman Problem (TSP)—directly to your problem, which shows that solving your problem is at least as hard as solving TSP.

Reduction Proof Walkthrough #

Let's break down how to map a TSP instance to your vector permutation problem:

1. Start with a TSP Instance
   Suppose we have a standard TSP problem with n cities. Let d(i,j) represent the distance between city i and city j. Our goal in TSP is to find a cycle that visits every city exactly once with the minimal total travel distance.

2. Build the Vector Permutation Instance
   For each city i, create an m=n-dimensional vector V_i. The j-th element of V_i is exactly d(i,j)—so each vector is just the row of the TSP distance matrix corresponding to city i.
   Now, each vector can have its elements permuted freely (reordering the distance values in any way), and we need to choose permutations such that the sum of each vector's Manhattan distance to its nearest neighbor is minimized.

3. Link the Two Problems

   • If we have an optimal TSP cycle: i₁ → i₂ → ... → iₙ → i₁ with total distance sum(d(i_k, i_{k+1})) (where i_{n+1} = i₁), we can permute each vector V_{i_k} to follow the cycle order: [d(i_k, i_{k+1}), d(i_k, i_{k+2}), ..., d(i_k, i₁)].
   • In this setup, the nearest neighbor of V_{i_k} will be V_{i_{k+1}}, and their Manhattan distance is sum_{t=1 to n} |d(i_k, i_{k+t}) - d(i_{k+1}, i_{k+t})|. Minimizing the total sum of these distances directly corresponds to minimizing the total length of the TSP cycle—since only the optimal TSP cycle will yield the minimal possible sum here.

   Conversely, any optimal solution to your vector permutation problem will correspond to an optimal TSP cycle. This means solving your problem is equivalent to solving TSP, which is proven NP-hard.

A Quick Note on Simplified Cases #

Even if you restrict the problem to smaller dimensions (like m=2, where each vector only has two elements to swap), it's still NP-hard. We can use similar reduction techniques, mapping to problems like minimum weight perfect matching instead of TSP, to confirm this. In short, unless P=NP, there's no known polynomial-time algorithm to solve this problem for arbitrary n and m ≥ 2.

内容的提问来源于stack exchange，提问作者yu sun