興味深いが複雑な問題は次のとおりです。
2 組の点があるとします。1 つのセット A には、通常の 1D または 3D グリッドなどの空間グリッド内のポイントが含まれます。もう 1 つのセット B には、ランダムな間隔で空間グリッドと同じサイズの点が含まれます。数学的には、2 つのセットを並べ替えて、A と B の間の距離に関して対応する行列を作成できます。たとえば、A(i, j) は、A の i と B の j の間の距離を参照できます。
順序付けを行うと、行列が得られます。次に、行列の対角要素 (i,i) は、A の点 i と B の点 i の間の距離です。問題は、最大距離ができるだけ小さくなるように、適切な並べ替え/インデックスを見つける方法です。行列形式で、最大の対角要素ができるだけ小さくなるように、適切な並べ替え/インデックスを見つける方法は?
私からのメモ：
セット A が行列の行に対応し、セット B が行列の列に対応するとします。次に、行列を並べ替えるということは、行/列の置換を行っていることを意味します。したがって、この問題は、最大の対角要素を最小化するための適切な順列を見つけることと同じです。
貪欲なアルゴリズムが選択される場合があります。しかし、最大の対角要素を最小化する理想的に完全な並べ替えを見つけようとしています。