S2.9最短路径与最速方案问题 在解决实际问题时,注意观察和善于想象是十分重要的, 观察与想象不仅能发现问题隐含的某些属性,有时还能顺 理成章地找到解决实际问题的钥匙。本节的几个例子说明, 猜测也是一种想象力。没有合理而又大胆的猜测,很难做 出具有创新性的结果。开普勒的三大定律(尤其是后两条) 并非一眼就能看出的,它们隐含在行星运动的轨迹之中 隐含在第谷记录下来的一大堆数据之中。历史上这样的例 子实在太多了。在获得了一定数量的资料数据后,人们常 常会先去猜测某些结果,然后试图去证明它。猜测一经证 明就成了定理,而定理一旦插上想象的翅膀,又常常会被 推广出许多更为广泛的结果。即使猜测被证明是错误的, 结果也决不是一无所获的失败而常常是对问题的更为深入 的了解
在解决实际问题时，注意观察和善于想象是十分重要的， 观察与想象不仅能发现问题隐含的某些属性，有时还能顺 理成章地找到解决实际问题的钥匙。本节的几个例子说明， 猜测也是一种想象力。没有合理而又大胆的猜测，很难做 出具有创新性的结果。开普勒的三大定律（尤其是后两条） 并非一眼就能看出的，它们隐含在行星运动的轨迹之中， 隐含在第谷记录下来的一大堆数据之中。历史上这样的例 子实在太多了。在获得了一定数量的资料数据后，人们常 常会先去猜测某些结果，然后试图去证明它。猜测一经证 明就成了定理，而定理一旦插上想象的翅膀，又常常会被 推广出许多更为广泛的结果。即使猜测被证明是错误的， 结果也决不是一无所获的失败而常常是对问题的更为深入 的了解。 §2.9最短路径与最速方案问题
例5(最短路径问题) 将湖想象成凸出地面的木桩,在AB间拉一根软线,当 设有线被拉紧时将得到最短路径。根据这样的想象,猜测 B付时以如下得到最短路径:过A作圆的切线切圆于E,过 B作圆的切线切圆于F。最短路径为由线段AE、弧EF 现扎和线段FB连接而成的连续曲线(根据对称性,AE,弧 制 E"F′,FB连接而成的连续曲线也是) E F
例5（最短路径问题） 设有一个半径为 r 的圆形湖，圆心为 O。A、 B 位于湖的两侧，AB连线过O，见图。 现拟从A点步行到B点，在不得进入湖中的限 制下，问怎样的路径最近。 A B O r 将湖想象成凸出地面的木桩， 在AB间拉一根软线，当 线被拉紧时将得到最短路径。根据这样的想象，猜测 可以如下得到最短路径： 过A作圆的切线切圆于E，过 B作圆的切线切圆 于F。最短路径为由线 段AE、弧EF 和线段FB连接而成的连续曲线（根据对称性，AE′，弧 E′F′，F′B连接而成的连续曲线也是）。 E F E′ F′
以上只是一种猜测,现在来证明这一猜测是正确的。为此, 先介绍一下凸集与凸集的性质。 定义21(凸集)称集合R为凸集,若x1、x2∈R及λ∈[0, 1],总有x1+(1+4)x2∈R。即若x1、x2∈R,则x1、x2 的连线必整个地落在R中 定理22(分离定理)对平面中的凸集R与R外的一点K, 存在直线l,1分离R与K,即R与K分别位于l的两侧(注: 对一般的凸集R与R外的一点K,则存在超平面分离R与 K),见图。 ③J下面证明猜想 R
以上只是一种猜测，现在来证明这一猜测是正确的。为此， 先介绍一下凸集与凸集的性质。 定义2.1（凸集）称集合 R为凸集，若x1、x2∈R及λ∈[0， 1]，总有λx1+（1+λ）x2∈R。即若x1、x2∈R，则x1、x2 的连线必整个地落 在R中。 定理2.2（分离定理）对平面中的凸 集R与R外的一点K， 存在直线 l , l 分离R与K，即R与K分别位于 l 的两侧（注： 对一般的凸 集R与R外的一点K，则存在超平面分 离R与 K），见图。 k l 下面证明猜想 R
猜测证明如下 (方法一)显然,由AE、EF、FB及AE,E"F,FB围成 的区域R是一凸集。利用分离定理易证最短径不可能经过R 外的点,若不然,设『为最短路径,『过R外的一点M,则 必存在直线离M与R,由于路径『是连续曲线,由A沿 到M,必交/于M1,由M沿「到B又必交厅M2。这样,直线 段MM2的长度必小于路径MMM2的长度,与『是A到B的 最短路径矛盾,至此,我们已证明最短路径必在凸集R内。 不妨设路径经湖的上方到达B点,则弧E必在路径F上,又 直线段AE是由A至E的最短路径,直线FB是由F到B的最短 路径,猜测得证。 A B E
猜测证明如下： （方法一）显然， 由AE、EF、FB及AE′，E′F′，F′B围成 的区域 R是一凸集。利用分离定理易证最短径不可能经过R 外的点，若不然，设 Γ为最短路径，Γ过R外的一点M，则 必存在直 线l分离M与R，由于路径Γ是连续曲线，由A沿Γ 到M，必交l于M1，由M沿Γ到B又必交l于M2。这样，直线 段M1M2的长度必小于路 径M1MM2的长度，与Γ是A到B的 最短路径矛盾，至此，我们已证明最短路径必在凸集R内。 不妨设路径经湖的上方到达B点，则弧EF必在路径F上，又 直线段AE是由A至E的最短路径，直线FB是由F到B的最短 路径，猜测得证。 A B O r E F E′ F′ M1 M2 M Γ l
若可行区域的边界是光滑曲面。则最短路径必由下列弧组 成,它们或者是空间中的自然最短曲线,或者是可行区域 的边界弧。而且,组成最短路径的各段弧在连接点处必定 相切。 到此为止,我们的研讨还只局限于平面之中, 其实上述猜测可十分自然地推广到一般空间 中去。1973年, J.W. Craggs证明了以上结果: oie D B
还可用微积分方法求弧长，根据计算证 明满足限止条件的其他连续曲线必具有 更大的长度；此外，本猜测也可用平面 几何知识加以证明等。 根据猜测不难看出， 例5中的条件可以大大 放松，可以不必 设AB过圆心，甚至可不必设 湖是圆形的。例如对 下图，我们可断定由A 至B的最短路径必 为l1与l2之一，其证明也不 难类似给出。 A B l1 l2 D 到此为止，我们的研讨还只局限于平面之中， 其实上述猜测可十分自然地推广到一般空间 中去。1973年，J.W.Craggs证明了以上结果： 若可行区域的边界是光滑曲面。则最短路径必由下列弧组 成，它们或者是空间中的自然最短曲线，或者是可行区域 的边界弧。而且，组成最短路径的各段弧在连接点处必定 相切