グリッド内に 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;