<iframe align="top" marginwidth="0" marginheight="0" src="http://www.zealware.com/csdnblog01.html" frameborder="0" width="728" scrolling="no" height="90"></iframe>
微软过桥问题的图论解法
微软的过桥问题说的是4个人在晚上过一座小桥,过桥时必须要用到手电筒,只有一枚手电筒,每次最多只可以有两人通过, 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟,试问最少需要多长时间4人才可以全部通过小桥?
这个问题如果用图论来建模的话,就可以以4个人在桥两端的状态来作为节点来构造一个有向图,如下图所示,以已经过桥了的人的状态作为图的节点,初始时没有人过桥,所以以空表示,第一轮有两个人过桥,有6种可能的组合,(1,2)(1,5)(1,10)(2,5)(2,10)(5,10),从空的状态转换到这些状态的需要的时间分别为2,5,10,5,10,10分钟,时间就作为有向边的权值。当有两个人过桥后,需要一个人拿手电筒回去接其他人,这时有四种可能的情况,分别是1,2,5,10中的一人留在了河的对岸,(1,2)这种状态只能转换到(1)(2)两种状态,对应的边的权值分别为2,1分钟,(1,2)转换到(1)时也就是2返回了,返回需要耗时2分钟,以此类推可以建立以下的图论模型。
要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出(空)节点到(1,2,5,10)节点间的最短路径。
<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><span lang="EN-US" style="FONT-SIZE: 10.5pt; FONT-FAMILY: " times new roman mso-bidi-font-size: mso-fareast-font-family: mso-font-kerning: mso-ansi-language: en-us mso-fareast-language: zh-cn mso-bidi-language: ar-sa><shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 366pt; HEIGHT: 393.75pt" type="#_x0000_t75"><imagedata o:title="" src="file:///C:/DOCUME~1/rose/LOCALS~1/Temp/msohtml1/01/clip_image001.png"></imagedata></shape></span><div><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/drzhouweiming/81d293f5fda54f0e86c66754149fc97e.png"></div>
<stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 366pt; HEIGHT: 393.75pt" type="#_x0000_t75"><imagedata o:title="" src="file:///C:/DOCUME~1/rose/LOCALS~1/Temp/msohtml1/01/clip_image001.png"></imagedata></shape>
根据Dijkstra最短路径算法很容易求出其最短路径,如图中的粗线所示。
这样总时间为2+1+10+2+2=17分钟
所以能够活学图论的话,这类智力问题就变成了图论的入门级的问题。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1340741
分享到:
相关推荐
火车过桥问题.pdf
包括生产者消费者问题和猴子过桥问题的源代码实现,用C#实现的,带可视化界面,并且包含一个猴子过桥问题exe的安装包生产工程。
本文给出了过桥用时最少的一种方法。并不保证采用其他方法仍然可以达到该值。可以肯定,采用其他方法所用时间不能小于采用本文方法所用时间。
这个题目是求N个人(N由自己输入)过桥的最少时间,规则是晚上过桥,只有一个火把,每次最多两个人一起过桥,每个人的过桥时间不一样(每个人过桥的时间由用户输入),两个人一起过去的时候以过桥时间最大的那个人...
在两个城市南北方向之间存在一条铁路,多列火车可以分别从两个城市的车站排队等待进入车道向对方城市行驶,该铁路在同一时间,只能允许在同一方向上行车,如果同时有相向的火车行驶将会撞车。请模拟实现两个方向行车...
过桥问题是一个数学难题,其中一组N人必须在晚上过一座桥。 天很黑,他们只有提着灯才能过桥。 只提供一盏灯,最多两个人可以同时穿过。 如果灯不在一侧,则不可能从一侧穿过。 过马路的时间是最慢的人过马路的时间...
这个题目是求N个人(N由自己输入)过桥的最少时间,规则是晚上过桥,只有一个火把,每次最多两个人一起过桥,每个人的过桥时间不一样(每个人过桥的时间由用户输入),两个人一起过去的时候以过桥时间最大的那个人...
过桥问题课设报告.doc
描述一个场景:在悬崖两边有一大堆猴子,猴子大小不一,中间有一个独木桥,每次只能单方向通过一定量的猴子,要使用一种调度算法,要使猴子序列能安全通过独木桥到达对岸!
小升初行程问题专项训练之火车过桥问题流水行船问题.doc
火车过桥问题讲义可用.pdf
火车过桥问题教案参考.pdf
这个问题如果用图论来建模的话,就可以以4个人在桥两端的状态来作为节点来构造一个有向图,如下图所示,以已经过桥了的人的状态作为图的节点,初始时没有人过桥,所以以空
火车过桥问题说课稿分享.pdf
过桥问题(含答案).doc
火车过桥问题解说与精练归纳.pdf
过桥问题(含答案)-.doc
行程问题-火车过桥与错车超车问题.pdf行程问题-火车过桥与错车超车问题.pdf行程问题-火车过桥与错车超车问题.pdf行程问题-火车过桥与错车超车问题.pdf行程问题-火车过桥与错车超车问题.pdf行程问题-火车过桥与错车...
火车过桥问题四年级PPT学习教案.pptx
小升初火车过桥问题专项训练.doc