找到一個最小化兩組最大距離的算法，比貪婪算法更好

Question

這裏有趣但很複雜的問題：

假設我們有兩組點。一組A包括一些空間網格中的點，如常規的一維或三維網格。另一組B包括隨機間隔並且與空間網格大小相同的點。在數學上，我們可以對這兩個集合進行排序，並且關於A與B之間的距離構造對應的矩陣。例如，A（i，j）可以指A的i與i之間的距離B.

給定一些排序，我們有一個矩陣。然後，矩陣中的對角元素（i，i）是A的點i和B的點i之間的距離。問題是如何找到一個好的重新排序/索引，使得最大距離儘可能小？在矩陣形式中，如何找到一個好的重新排序/索引，使盡可能小的最大對角元素？從自己

注：

1. 假設集合A是對應於矩陣的行，並設置B是向矩陣的列。然後重新排序矩陣意味着我們正在做行/列置換。因此，我們的問題相當於找到一個很好的排列來最小化最大的對角元素。

2. 貪婪算法可能是一種選擇。但我試圖找到一個理想完美的重新排序，以儘量減少最大的對角元素。

Answer 1

您所指的重新排序本質上是一個對應性問題，即您正在嘗試爲另一個集合中的每個點找到最接近的匹配。貪婪算法會正常工作。你正在尋找的距離通常被稱爲Hausdorff distance。