鱼C论坛

 找回密码
 立即注册
查看: 9242|回复: 64

[技术交流] python小练习(065):探索法(广度优先搜索)30行代码求解倒酒问题

[复制链接]
发表于 2017-2-4 15:03:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-2-7 11:22 编辑

探索法(“广度搜索”)对于求解不确定性最优路径(状态)问题有非常好的效果,之前的python小练习(064)就是不错的例子。

下面我们再来看一题倒酒问题。

据说有人给酒肆的老板娘出了一个难题:

此人明明知道店里只有两个舀酒的勺子,分别能舀7两和11两酒,却硬要老板娘卖给他2两酒。

聪明的老板娘毫不含糊,用这两个勺子在酒缸里舀酒,并倒来倒去,居然量出了2两酒,聪明的你能做到吗?

这道题目同样可以利用探索法求解最优路径(状态)。

先看解答:(左侧的表示7两勺的状态,右侧的表示11两勺的状态,通过这样的倒酒(状态交换)后,可以得到2两酒)
Found!
[7, 0]
[0, 7]
[7, 7]
[3, 11]
[3, 0]
[0, 3]
[7, 3]
[0, 10]
[7, 10]
[6, 11]
[6, 0]
[0, 6]
[7, 6]
[2, 11]
[Finished in 0.1s]

源代码:
游客,如果您要查看本帖隐藏内容请回复

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-4 17:45:20 | 显示全部楼层
我只是为了看答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-6 11:26:49 | 显示全部楼层
学习下!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-7 11:05:37 | 显示全部楼层
依旧好高深
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-8 17:33:33 | 显示全部楼层
不懂得东西,来学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-8 19:19:44 | 显示全部楼层
代码怎么去实现,思路学习下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-9 14:17:43 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-9 14:31:12 | 显示全部楼层

我只是为了看答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-9 17:26:10 From FishC Mobile | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-2-10 10:02:20 | 显示全部楼层
以前经常玩数独,请问高级数独很有难度的那种带乘法的能不能也通过这种方式进行探索
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-2-10 10:09:39 | 显示全部楼层
知飞科技 发表于 2017-2-10 10:02
以前经常玩数独,请问高级数独很有难度的那种带乘法的能不能也通过这种方式进行探索

python小练习(067):回溯法求解数独问题:
http://bbs.fishc.com/thread-82257-1-3.html
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-22 11:39:17 From FishC Mobile | 显示全部楼层
怎么办,好多要学习的,没时间谈恋爱了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-22 18:40:24 From FishC Mobile | 显示全部楼层
看看怎么写???
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-28 08:47:23 From FishC Mobile | 显示全部楼层
学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-30 09:18:40 | 显示全部楼层
我要看代码。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-30 10:34:37 | 显示全部楼层
看答案
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-15 10:29:26 | 显示全部楼层
棒!!~~~~~~~~~~~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-23 08:08:46 From FishC Mobile | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-5-23 08:56:23 From FishC Mobile | 显示全部楼层
握草,感觉好厉害
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-23 09:57:20 | 显示全部楼层
0.1s 这个速度
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表