扫雪问题 地图中的实线表示马里兰州威考密科县中扫雪区域 中的二车道马路,虚线表示州属高速公路。一场雪 后,从位于地图*标记地点以西4英里的二处车库派 出二辆扫雪车。求用两辆扫雪车扫清马路上的雪的 有效的方法,扫雪车可以利用高速公路进出扫雪区 假设扫雪车既不会发生故障也不会停顿,在交叉 路口不需特别的扫雪方法
扫雪问题 ❖ 地图中的实线表示马里兰州威考密科县中扫雪区域 中的二车道马路，虚线表示州属高速公路。一场雪 后，从位于地图*标记地点以西4英里的二处车库派 出二辆扫雪车。求用两辆扫雪车扫清马路上的雪的 有效的方法，扫雪车可以利用高速公路进出扫雪区。 ❖ 假设扫雪车既不会发生故障也不会停顿，在交叉 路口不需特别的扫雪方法
不妨假定 令1.铲雪车不会抛锚或受阻停滞; 令2.在交叉路口或一头不通的路底不需要特别 的除雪技术; 3.铲雪车右行驶; 4.铲雪车在地图上星号位置进入指定地区;
不妨假定： ❖ １.铲雪车不会抛锚或受阻停滞； ❖ ２.在交叉路口或一头不通的路底不需要特别 的除雪技术； ❖ ３.铲雪车右行驶； ❖ ４.铲雪车在地图上星号位置进入指定地区；
5该地区被大雪均匀覆盖; 6.两车的除雪功率相同; 7.两车作业时速度相同; 今8 行驶即完成一个单向行车道的作业
❖ ５.该地区被大雪均匀覆盖； ❖ ６.两车的除雪功率相同； ❖ ７.两车作业时速度相同； ❖ ８.一次行驶即完成一个单向行车道的作业
模型的分析与假设 令问题是为两车完成作业寻找最短路径。该模 型以铲雪车在规定时间内清除的雪量作为测 定其效率的标准。这时间会受空驶影响,若 空驶时间多,效率就低。因模型不限制车速, 当作业时间与完成整个地区作业花费的时间 总量之比获最大值时,效率最高。因此该椟 型可取的高效率的条件是,两车所花费的时 间均为作业时间
模型的分析与假设 ❖ 问题是为两车完成作业寻找最短路径。该模 型以铲雪车在规定时间内清除的雪量作为测 定其效率的标准。这时间会受空驶影响，若 空驶时间多，效率就低。因模型不限制车速， 当作业时间与完成整个地区作业花费的时间 总量之比获最大值时，效率最高。因此该模 型可取的高效率的条件是，两车所花费的时 间均为作业时间
令为达到这一理想状态,我们决定,若发现前 面路面已作业完毕,则调头返回到出发点。 这样做可行是因为,一方面若降雪未停,可 开始第二遍作业,另一方面若降雪已停,则 需返回停车场,即地图上星号位置以西4英里 处
❖ 为达到这一理想状态，我们决定，若发现前 面路面已作业完毕，则调头返回到出发点。 这样做可行是因为，一方面若降雪未停，可 开始第二遍作业，另一方面若降雪已停，则 需返回停车场，即地图上星号位置以西4英里 处