2

グリッド内に 3 つのポイントがある場合、3 つのポイントすべてからこのポイントまでの距離の合計が最小になるようなポイントを見つけるにはどうすればよいでしょうか。この問題に対する明白な答えは、フェルマーの三角形です。グラフで幅優先探索アルゴリズムを使用してフェルマーの点を見つけることができるかどうか知りたいです。

struct node{
  int Person1X,Person1Y,Person2X,Person2Y,Person3X,Person3Y; //X and Y coordinates of all 3 persons
  int steps;   //sum of distances covered by all 3 person to reach this state
}

BFS を実行しているときに、steps>min (3 人を頂点とする三角形の任意の 2 つのエッジの合計) が返される場合、制約を設定できます。

if(Person1X=Person2X=Person2X)AND(Person1Y=Person2Y=Person3Y) return steps;
4

1 に答える 1

1

検索は必要ありません。

与えられた「三角形」ABC: SumOfDistances( p ) = dist( A, p ) + dist( B, p ) + dist( C, p )

ここで、dist( q, p ) = |q x -p x | + |q y -p y | (マンハッタン距離)

SumOfDistances( p ) = SumOfDistances x ( p ) + SumOfDistances y ( p )

したがって、x 軸と y 軸の距離を個別に最小化できます。

したがって、フェルマー点の x 座標は、与えられた 3 つの x 座標の中央値です。フェルマー点の y 座標は、与えられた 3 つの y 座標の中央値です。

于 2012-10-25T00:02:50.233 に答える