algorithm - 使用 BFS 找到三角形中的 Fermat 点

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 时，我们可以设置一个约束， if steps>min(以3人为顶点的三角形任意两条边之和) return;

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