找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 302|回复: 5

[求助] 求python解决摆渡问题

1

主题

4

帖子

4

积分

贫民

积分
4
wd3355 发表于 2018-1-13 21:51:49 来自手机 | 显示全部楼层 |阅读模式
       有一名猎人带着一只狼,一个妇女带着两个孩子,一个老人也带着两个孩子,一同要过河。河上有只有一条小船每次只能搭乘2人(不论大人小孩或者是狼都算占一个单位)。
       且狼如果不和猎人在一起就会咬人,如果老人离开妇女就会打他的孩子,如果妇女离开老人也会打他的孩子。
       其中只有猎人和妇女会划船。
       求,如何大家才能安全过河。
       网易公开课上看到的问题,本人初学python,请各位大神帮忙看这个问题如何用python语言解决。
回复

使用道具 举报

1

主题

4

帖子

4

积分

贫民

积分
4
wd3355  楼主| 发表于 2018-1-13 22:10:43 来自手机 | 显示全部楼层
这两张图是老师给的思路
Screenshot_2018-01-13-22-05-23.jpeg
Screenshot_2018-01-13-22-05-09.jpeg
回复 支持 反对

使用道具 举报

1

主题

4

帖子

4

积分

贫民

积分
4
wd3355  楼主| 发表于 2018-1-14 02:18:27 来自手机 | 显示全部楼层
    想了许久,不要说用语言解决,逻辑都没弄通顺,我怎么觉得这辈子他们都过不去河了呢?
回复 支持 反对

使用道具 举报

2

主题

219

帖子

219

积分

版主

Rank: 7Rank: 7Rank: 7

积分
219

热心会员默默耕耘优秀版主

剑心无痕 发表于 2018-1-15 11:09:51 | 显示全部楼层
本帖最后由 剑心无痕 于 2018-1-15 11:12 编辑
wd3355 发表于 2018-1-14 02:18
想了许久,不要说用语言解决,逻辑都没弄通顺,我怎么觉得这辈子他们都过不去河了呢? ...
  1. import copy
  2. here, there = 0, 1
  3. s = [here] * 8  # hunter, wolf, female, child1, child2, older, child3, child4
  4. state = []
  5. for i in range(256):
  6.     k = i
  7.     for j in range(8):
  8.         s[7 - j] = k % 2
  9.         k >>= 1
  10.     # 狼吃人
  11.     if s[0] != s[1] and (s[1] == s[2] or s[1] == s[3] or s[1] == s[4] or s[1] == s[5] or s[1] == s[6] or s[1] == s[7]):
  12.         continue
  13.     # 女人老人不在一起,孩子被打
  14.     if s[2] != s[5] and (s[2] == s[6] or s[2] == s[7] or s[5] == s[3] or s[5] == s[4]):
  15.         continue
  16.     state.append(copy.copy(s))
复制代码
把所有的可能状态都打印出来才70种,其中还是对称,看一半就可以了,再用排除法。反正我找不到有效路径,除非老人也会划船
回复 支持 反对

使用道具 举报

2

主题

219

帖子

219

积分

版主

Rank: 7Rank: 7Rank: 7

积分
219

热心会员默默耕耘优秀版主

剑心无痕 发表于 2018-1-15 13:10:22 | 显示全部楼层
wd3355 发表于 2018-1-14 02:18
想了许久,不要说用语言解决,逻辑都没弄通顺,我怎么觉得这辈子他们都过不去河了呢? ...
  1. here, there = 0, 1
  2. s = [here] * 8  # hunter, wolf, female, child1, child2, older, child3, child4
  3. state = []
  4. for i in range(256):
  5.     k = i
  6.     for j in range(8):
  7.         s[7 - j] = k % 2
  8.         k >>= 1
  9.     # 狼吃人
  10.     if s[0] != s[1] and (s[1] == s[2] or s[1] == s[3] or s[1] == s[4] or s[1] == s[5] or s[1] == s[6] or s[1] == s[7]):
  11.         continue
  12.     # 女人老人不在一起,孩子被打
  13.     if s[2] != s[5] and (s[2] == s[6] or s[2] == s[7] or s[5] == s[3] or s[5] == s[4]):
  14.         continue
  15.     state.append((tuple(s), i))

  16. action = {}
  17. for i in range(len(state)):
  18.     for j in range(i + 1, len(state)):
  19.         if state[i][0][0] != state[j][0][0] or state[i][0][2] != state[j][0][2]:
  20.             if bin(state[i][1] ^ state[j][1]).count('1') <= 2 and bin(state[i][1]).count('1') != bin(state[j][1]).count('1'):
  21.                 action[state[i][0]] = action.get(state[i][0], []) + [state[j][0]]
  22.                 action[state[j][0]] = action.get(state[j][0], []) + [state[i][0]]

  23. path = []
  24. def find(state):
  25.     if state == (1, 1, 1, 1, 1, 1, 1, 1):
  26.         return True
  27.     for i in action[state]:
  28.         if i in path:
  29.             continue
  30.         path.append(i)
  31.         if find(i):
  32.             return True
  33.         path.pop()
  34.     return False

  35. find(tuple([here] * 8))   # False找不到
复制代码
状态转移的图搜索算法, 反正就是找不到路径,过不去
回复 支持 反对

使用道具 举报

1

主题

4

帖子

4

积分

贫民

积分
4
wd3355  楼主| 发表于 2018-1-15 14:32:54 来自手机 | 显示全部楼层
学习中,非常感谢
回复 支持 反对

使用道具 举报

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

本版积分规则

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