2 点之间的最短路线也通过其他几个预定义点中的 1 个
Shortest route between 2 points that also passes through 1 of a few other pre defined points
我正在努力寻找我的问题的确切答案。我有一个 20 x 20 的网格。我正在寻找 PHP 代码示例、公式或算法的正确名称，以找出以下内容：
- 两点之间同时经过其他几个预定义点中的一个的最短路线
- 路线不必return到终点
- 允许路线在单元格之间斜向通过
- 出发地和目的地已设置
假设我的网格水平方向从 A 到 T，垂直方向从 1 到 20。我想计算从起点 A5 到目的地 G12 的最短路线，同时根据最短路线经过 C7、D9、E5 或 J8。
此外，知道如何扩展它会很方便，这样它在到达目的地 (G12) 的途中不仅会经过一个点，而且可能会经过 2 个点。
我已经搜索了 2 天，现在我的脑子里满是 Dijkstra、TSP、BFS 和其他东西！
谢谢！
如果你可以直接跳到中间点而忽略整个网格，那么基本几何建议从点 S(tart) 到点 E(nd) 通过所需点的最短路径A 只是两条线段 SA + AE 并且计算它的总距离实际上非常快（它只是标准的欧氏距离）。因此，除非您有数千个可能的中间点，否则只需检查所有路径 SA+AE、SB+BE，...并比较距离将非常快。即使有两个中间点并且池有十几个大小，也只有几百个组合，所以蛮力仍然很快。
我正在努力寻找我的问题的确切答案。我有一个 20 x 20 的网格。我正在寻找 PHP 代码示例、公式或算法的正确名称，以找出以下内容：
- 两点之间同时经过其他几个预定义点中的一个的最短路线
- 路线不必return到终点
- 允许路线在单元格之间斜向通过
- 出发地和目的地已设置
假设我的网格水平方向从 A 到 T，垂直方向从 1 到 20。我想计算从起点 A5 到目的地 G12 的最短路线，同时根据最短路线经过 C7、D9、E5 或 J8。
此外，知道如何扩展它会很方便，这样它在到达目的地 (G12) 的途中不仅会经过一个点，而且可能会经过 2 个点。
我已经搜索了 2 天，现在我的脑子里满是 Dijkstra、TSP、BFS 和其他东西！
谢谢！
如果你可以直接跳到中间点而忽略整个网格，那么基本几何建议从点 S(tart) 到点 E(nd) 通过所需点的最短路径A 只是两条线段 SA + AE 并且计算它的总距离实际上非常快（它只是标准的欧氏距离）。因此，除非您有数千个可能的中间点，否则只需检查所有路径 SA+AE、SB+BE，...并比较距离将非常快。即使有两个中间点并且池有十几个大小，也只有几百个组合，所以蛮力仍然很快。