次の問題を解決する効率的なアルゴリズムを知っている人はいますか?
ある距離空間の 2 つの互いに素な点集合 A、B が与えられたとき、B の最も近い点までの最小距離を最大にする A の点を見つけますか?
質問する
225 次
3 に答える
0
メトリック f が与えられた場合、1/f をメトリックとして使用してから、単純な最近傍検索を実行できるのではないかと思います。私が持っている唯一のハングアップは、1/f が三角形の不等式を満たすかどうかです。
于 2013-05-01T23:36:07.727 に答える
0
特定のアルゴリズムについては知りません。この問題を考えると、バイナリ チョップで問題が解決するかどうかを確認することから始めます。
ただし、進歩させるにはより多くの情報が必要です: B がポイントであるかのように「ポイント A .. from B」と言いますが、B はポイントのセットです。実際、問題の定義から、A と B は同じポイントのセットである可能性があります。または少なくとも重複..
解決策を見つけようとする場合、再帰も役立ちます。つまり、f(n-1) の解が与えられた場合に f(n) の解を見つけます。定義上、A が 1 点で B も 1 点の場合、既知の答えは 1 つあります。
n = 2 の解を一般化できますか?
たとえば、A が 2 点、B が 1 点の場合を解きます。どの A が B から離れているか。
B が 1 点である解が得られたら、B = a セットの解を推測できる場合があります。
HTH
于 2013-05-01T22:42:42.047 に答える