 |
| 我的日历 |
|
|
公告
|
| 分类日志 |
页面载入中 |
|
|
最新更新
友情链接
|
|
|
| 最新评论 |
|
|
| 留言 |
|
|
登录
页面载入中 |
|
| Blog信息 |
|
|
|
|
| |
 | |
| |
| 老虎过河 |
|
卡卡·我来自一塌糊涂 发表于 2005-5-26 21:30:00 |
ft. 前天写了，居然没提交成功。现在闲了一会，重新写出来。
在test看到一道题，三只大老虎各带她们的儿子过河，只有一条船，船一次只能载两只老虎。大老虎都会划船，只有一只小老虎会划船。小老虎不在他妈妈身边时可能被其它大老虎吃掉。问如何过河。
比划了一下，没解出来。决定建个模型来解；考虑如下：
将大老虎表示为A，B，C，其子分别为a，b，c，
其中a会划船。
由于河两岸的老虎事实上构成所有老虎集合的一个划分，所以可以只用左岸的老虎集合来表示一个状态。初始状态为 S-start = {A,B,C,a,b,c}，末状态为 S-target = {}。
解题的过程事实上是寻找一个S-start到S-target的一个变换。变换由一系列操作实现，而可行的操作则由状态决定。先列一下可行的状态：
左岸有6只老虎时：S6={A,B,C,a,b,c}
左岸有5只老虎时：S51={A,B,C,a,b} S52={A,B,C,a,c}S53={A,B,C,b,c}
左岸有4只老虎时：S41={A,B,C,a}S42={A,B,C,b}S43={A,B,C,c}S44={A,B,a,b}S45={A,C,a,c}S46={B,C,b,c}
左岸有3只老虎时：S31={A,B,C}S32={a,b,c}
左岸有2只老虎时：S21={a.b}S22={b,c}S23={a,c}S24={A,a}S25={B,b}S26={C,c}
左岸有1只老虎时：S11={a}S12={b}S13={c}
左岸有0只老虎时：S0={}
可行的变换则由可行状态决定。如
S6可行的变换有S6->S53, S6->S43, S6->S42, S6->S46
等等。
画图表示，可行状态为一系列点，而可行变换为点之间的线。形成一个网络图，目标即是在图上寻找S6->S0的通路。
我在图上画了一会，找不到可行的通路。把这题目给小金看了一下，他埋头写了一会，说这题无解。他试图从S0->S6寻找通路，发现不可能。于是我们认定此题无解。
上完课回来，发现sk居然给出了一个解。真ft。仔细观察了他的解，发现其中一个关键的状态即S46={B,C,b,c}。这个状态是由S6一步可达的，他却花了好几步才达到。为什么呢？再仔细看，发现问题所在了。由S6一步可达的S46，船的状态是在右岸；则sk解中的{B,C,b,c}，船却是在左岸。
现在明白了，我建的模型缺少一个变量，即船的位置。一个状态中，船在左岸或在右岸将影响可行的变换个数。
更改模型如下：用+表示船在左岸，用-表示船在右岸
S-start= {A,B,C,a,b,c.+}
S-target={-}
思路同上面的模型。由于多了一个变量，问题的规模增加一倍；但交给计算机算，不管它多复杂了。
另：以上是周二的想法，最初是想使用图与网络中的最大匹配算法。但最后发现成了在一个网络中搜索目标点了。今天上ES课，讲到prolog时，发现不少类似的习题。看来用prolog来解也可。有空再试试
| |
|
|
| 论坛自动发贴机作者qq:525093551 来祝贺 |
|
owwtbd(游客)发表评论于2007-11-25 17:27:00 |
 真不错，非常好。请帮忙推荐我的软件：论坛自动发贴机 自动发贴软件 论坛发贴工具 联系Q:525093551 网站推广软件 论坛群发软件 论坛群发器信息群发软件 免费论坛群发软件联系qq:525093551 论坛自动发帖机 自动发帖软件 论坛发帖工具 论坛发帖机 论坛发帖软件 留言本群发 联系qq:525093551
s9u5w5jt | |
|
|
| 回复:老虎过河 |
|
baoxue发表评论于2005-10-18 14:34:00 |
假设
小老虎abc，且a会划船
1次
ab过河，a回。对岸留b
2次
ac过河，a回。对岸bc
3次
BC过河，Bb回，对岸Cc
4次
Aa过河，Cc回，对岸Aa
5次
BC过河，a回，对岸ABC
6次
ab过河，a回，对岸ABCb
7次
ac过河7
完成 | |
|
|
|
|
|
|
