数学建模大赛答辩草稿.
数模答辩草稿
第一题
已知条件：
- 各
收发点位置 运送路径- 每条
运送路径的包裹数
假设：
- 无视高度
定义：
空飞: 不携带包裹的一次飞行有效飞行：携带包裹，跟随运送路径从一收发点飞行至另一收发点
目标：
- 最小
空飞数 - 最小
空飞数的完整路径
因为假设无视高度，所有我们可以将这个问题简化为二维问题。
已知各收发点位置和运送路径，很容易地联想到图论这个工具。
将收发点作为节点，运送路径作为有向边。
进一步想到每条运送路径的包裹数可作为权，由此构造出一个有向正权图。
我们现在有了图，可以将问题转变为：
已知条件:
- 各
节点 有向边有向边的权
假设：
- 无视高度
定义：
空移：从一节点沿有向边的 反方向 移动 到另一节点有效移动：从一节点沿有向边的 正方向 移动 到另一节点。
目标：
- 最小
空移数 - 最小
空移数的完整路径
试求解该图论问题，我们联想到求解单源最短路径常用的算法：dijkstra。
基于该算法的思想，我们可以确定以下三点因素：
权的含义：包裹数量- 终止条件：当
图中每一条边的权的和等于 0 时终止 - 每一步的局部最优解：对于当前
节点， 若出度不为 0，则存在有效移动的可能，则经过头为当前节点且权最大的有向边进行一次有效飞行，该有向边的权减一； 若出度为 0，则必空移一次，回到上一个节点即可。
此外，为了记录路径序列S 和空飞数n，
我们规定只要移动，就记录一次当前节点到序列 S 中；仅当空移时，数 n 自增 1。
假设一起始节点，重复上述的步骤，直到终止条件。
终止后得到的 S 和 n 即为目标，求解完毕。