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

给定一个网格中的3个点，如何找到一个点，使该点与所有3个点的距离之和最小化。这个问题的一个明显的答案是费马三角形。我感兴趣的是知道我们是否可以使用图中的广度优先搜索算法来定位fermat的点。

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;

最佳答案

不需要搜索。
给定“三角形”ABC：
距离之和（P）=距离（A，P）+距离（B，P）+距离（C，P）
其中dist（q，p）=| qx px |+| qy py |（曼哈顿距离）
你可以看到距离之和（p）=距离之和x（p）+距离之和（p）
因此，可以独立地在x轴和y轴上减小距离。
所以，fermat点的x坐标是3个给定x坐标的中值。
fermat点的y坐标是3个给定y坐标的中值。

关于algorithm - 使用BFS在三角形中找到Fermat的点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13023960/