algorithm - 使用 BFS 在三角形中定位费马点

Question

给定网格中的 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 个人为顶点的三角形任意两条边的总和）返回；

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

Answer 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 坐标的中值。