扫雪问题 地图中的实线表示马里兰州威考密科县中扫雪区域 中的二车道马路,虚线表示州属高速公路。一场雪 后,从位于地图*标记地点以西4英里的二处车库派 出二辆扫雪车。求用两辆扫雪车扫清马路上的雪的 有效的方法,扫雪车可以利用高速公路进出扫雪区 假设扫雪车既不会发生故障也不会停顿,在交叉 路口不需特别的扫雪方法
扫雪问题 ❖ 地图中的实线表示马里兰州威考密科县中扫雪区域 中的二车道马路，虚线表示州属高速公路。一场雪 后，从位于地图*标记地点以西4英里的二处车库派 出二辆扫雪车。求用两辆扫雪车扫清马路上的雪的 有效的方法，扫雪车可以利用高速公路进出扫雪区。 ❖ 假设扫雪车既不会发生故障也不会停顿，在交叉 路口不需特别的扫雪方法
不妨假定 令1.铲雪车不会抛锚或受阻停滞; 令2.在交叉路口或一头不通的路底不需要特别 的除雪技术; 3.铲雪车右行驶; 4.铲雪车在地图上星号位置进入指定地区;
不妨假定： ❖ １.铲雪车不会抛锚或受阻停滞； ❖ ２.在交叉路口或一头不通的路底不需要特别 的除雪技术； ❖ ３.铲雪车右行驶； ❖ ４.铲雪车在地图上星号位置进入指定地区；
5该地区被大雪均匀覆盖; 6.两车的除雪功率相同; 7.两车作业时速度相同; 今8 行驶即完成一个单向行车道的作业
❖ ５.该地区被大雪均匀覆盖； ❖ ６.两车的除雪功率相同； ❖ ７.两车作业时速度相同； ❖ ８.一次行驶即完成一个单向行车道的作业
模型的分析与假设 令问题是为两车完成作业寻找最短路径。该模 型以铲雪车在规定时间内清除的雪量作为测 定其效率的标准。这时间会受空驶影响,若 空驶时间多,效率就低。因模型不限制车速, 当作业时间与完成整个地区作业花费的时间 总量之比获最大值时,效率最高。因此该椟 型可取的高效率的条件是,两车所花费的时 间均为作业时间
模型的分析与假设 ❖ 问题是为两车完成作业寻找最短路径。该模 型以铲雪车在规定时间内清除的雪量作为测 定其效率的标准。这时间会受空驶影响，若 空驶时间多，效率就低。因模型不限制车速， 当作业时间与完成整个地区作业花费的时间 总量之比获最大值时，效率最高。因此该模 型可取的高效率的条件是，两车所花费的时 间均为作业时间
令为达到这一理想状态,我们决定,若发现前 面路面已作业完毕,则调头返回到出发点。 这样做可行是因为,一方面若降雪未停,可 开始第二遍作业,另一方面若降雪已停,则 需返回停车场,即地图上星号位置以西4英里 处
❖ 为达到这一理想状态，我们决定，若发现前 面路面已作业完毕，则调头返回到出发点。 这样做可行是因为，一方面若降雪未停，可 开始第二遍作业，另一方面若降雪已停，则 需返回停车场，即地图上星号位置以西4英里 处
令为建立模型,需把该城市分为两部分,分派 给两车,两部分道路的总长应该相等,否则 车先于另一车完成作业,与两车同时完成 作业相比,会增加完成整个地区的作业时间。 此外,两部分区域应该明确,且各区域保持 连通,不然的话,指定在一区域内作业的车 会驶上另一车正在作业的路面
❖ 为建立模型，需把该城市分为两部分，分派 给两车，两部分道路的总长应该相等，否则 一车先于另一车完成作业，与两车同时完成 作业相比，会增加完成整个地区的作业时间。 此外，两部分区域应该明确，且各区域保持 连通，不然的话，指定在一区域内作业的车 会驶上另一车正在作业的路面
令为平均划分这一城市,需测量所有街道的长 度。方法是:用影印机放大地图,用一软绳 模拟路段的弯曲形状,然后绷紧,再以其长 度按比例扩大,就是路段的实际长度。用此 法确定所有路段的长度后,就可将该城市分 为相通的两部分,两区路段总和之差为0.06 英里(见图1),与总长12529英里相比则可 忽略不计的差额
❖ 为平均划分这一城市，需测量所有街道的长 度。方法是：用影印机放大地图，用一软绳 模拟路段的弯曲形状，然后绷紧，再以其长 度按比例扩大，就是路段的实际长度。用此 法确定所有路段的长度后，就可将该城市分 为相通的两部分，两区路段总和之差为0.06 英里（见图1），与总长125.29英里相比则可 忽略不计的差额
现在问题已简化到寻找一最短路径,使车子行驶遍 及所指定区域的所有街道。用图论的观点来看,每 个指定地区的街道网可以先看如下的一个无向图, 它的顶点是街道的交叉路口或街道的尽头,边是街 道。进一步,这些边还可以被分成连接两顶点的方 向相反的两条有向边,这个图因而成为有向图。因 为这个街道网是连通的,所以得到的图夜市连通的, 因而最短路径的问题就归结为求该有向图的一个欧 拉有向闭路径
❖ 现在问题已简化到寻找一最短路径，使车子行驶遍 及所指定区域的所有街道。用图论的观点来看，每 个指定地区的街道网可以先看如下的一个无向图， 它的顶点是街道的交叉路口或街道的尽头，边是街 道。进一步，这些边还可以被分成连接两顶点的方 向相反的两条有向边，这个图因而成为有向图。因 为这个街道网是连通的，所以得到的图夜市连通的， 因而最短路径的问题就归结为求该有向图的一个欧 拉有向闭路径
G ￥T c