Question

最短路径 数学建模

公园计划有8个入口（已确定，只是图未给出），现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的1.4倍。请说明原理或模型

Answer 1

关于问题2的求解方法如下：先不谈优化。

假设正常坐标。矩形分别为(0,0),(0,w),(w,h),(h,0), y在前，x在后，假设 w >= h。

1、外层循环是枚举起点，顺时针。

2、内层循环是枚举终点，逆时针。

如果发现两点当前所拥有路径大于两点距离1.4则需要新增边的方式实现。新增边，雷同上述循环方式，（实际可以在对应点遍例时，对中间量进一步存储下来），选择最短边实现。同时，如果存已新增边，则要判断是否可以删除。

以上循环仅针对起点和终点分别在两条相临边的情况。

随后，开始循环检测起点和终点分别在两条不相临边的情况。算法雷同。

对于优化方式，可以采用跳跃判断的方法。如果直角三角形两条直角边差异过大，则不给予考虑。因此对上述第一阶段的扫描，固定的起点假设到直角的距离是X，则终点到直角的距离大于X‘的都不需要考虑了。 (X’ ^ 2 + x^2 ) * 1.4*1.4 > (x + x')^2

主要重点在于，相临边上的起点终点，就是第一阶段，如果出现新增边，他的存在，是不可被第二阶段的计算所替代的。而这种直角三角形，随着直角的改变，相互之间的边的存在也有不可替代性。既然是不可替代的，所以一定要参与到最后的总最短距离计算。

还好这个问题不是个比较复杂的问题。如果想不同，可以分析一下，正方形上，非离散，而是连续的点，在任意两点之间空间距离和可新增边的实际距离的关系。就可以了。

但这个问题绝对不是最短路径问题。因为不同起点和终点，空间距离是随着顶点的不同而变化的。所以是否需要新增边，需要根据三角形来判断。而不是一群具体距离值进行最小路径判断。
用的模型是：任意状态下的分析，不转移到无限点的情况。