《算法的乐趣》6.妖怪和和尚过河问题------python

本文主要是介绍《算法的乐趣》6.妖怪和和尚过河问题------python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

有三个和尚和三个妖怪要利用唯一一条小船过河，这条小船一次最多载两个人。同时，无论在河两岸还是在船上，只要妖怪的数量大于和尚的数量，妖怪就会将和尚吃掉。安排一下，保证和尚和妖怪都能过河并且和尚不能被妖怪吃掉。

方法类似于第五章的内容：遍历所有由妖怪、和尚和小船的位置构成的状态空间，寻找一条或多条从初始状态到最终状态的转换路径。结果一颗状态搜索树。

状态和动作

状态模型：不仅能描述静止状态，还能够描述并记录状态转换动作，尤其是对状态转换的描述。
初始状态：[3, 3, 0, 0 ,0]表示河左岸和尚和妖怪的数目，河右岸和尚和妖怪的数目，小船的位置0：左岸，1：右岸
最终状态：[0, 0, 3, 3, 1]

动作模型：小船位置的变化引起河两岸和尚和妖怪数目的变化。动作引起船的变化一起此动作移动的和尚和妖怪的数量。
一共有十种动作：两个妖怪过河，一个和尚过河，两个和尚过河，一个妖怪和一个和尚过河，一个妖怪返回，两个妖怪返回，一个和尚返回，两个和尚返回，一个妖怪和一个和尚返回。
用一个抽象的记录进行一致性处理：[0, -1, 0]第一个是河左岸和尚数目的变化；第二个参数是河左岸妖怪数目的变化；第三个参数是船的动作0：过河，1：返回

搜索算法：深度优先遍历算法

递归实现：

关键

关键在于排除所有重复的状态：首先对于下一个满足要求的动作的选择；
然后看此动作造成的状态是否满足条件，进行挑选；
避免重复：当前状态下的下一个状态是否已经出现过。

from collections import dequeinitial_state = [3, 3, 0, 0, 0]    # 初始状态
final_state = [0, 0, 3, 3, 1]     # 最终状态action = [[0, -1, 0], [0, -2, 0], [-1, 0, 0], [-2, 0, 0], [-1, -1, 0], [0, 1, 1], [0, 2, 1], [1, 0, 1], [2, 0, 1], [1, 1, 1]]# 利用python的deque队列记录状态转移情况，初始化时加入初始状态。deque是可以从头尾插入和删除的队列，在不指定大小时，为一个无边界的队列
record = deque()
record.append(initial_state)def next_state_lawful(current_state):# 下一个动作判定next_action = []for state in action:if current_state[4] == state[2] and (current_state[1] + state[1]) >= 0 and (current_state[1] + state[1]) <= 3 \and (current_state[0] + state[0]) >= 0 and (current_state[0] + state[0]) <= 3 :next_action.append(state)# 下一个状态for state in next_action:left_monk = current_state[0] + state[0]left_monster = current_state[1] + state[1]right_monk = current_state[2] - state[0]right_monster = current_state[3] - state[1]next_state = list(current_state)if (left_monk==0 or (left_monk>0 and left_monk>=left_monster)) and \(right_monk==0 or (right_monk>0 and right_monk>=right_monster)):next_state[0] = left_monknext_state[1] = left_monsternext_state[2] = right_monknext_state[3] = right_monsternext_state[4] = int(not (current_state[4]))yield next_state # 记录调试的变量：num表示总共实现方法数，record_list记录所有实现路径
num = 0
record_list = []def searchResult(record):global num, record_list# 由record的末尾元素得到当前状态current_state = record[-1]# 得到关于当前状态的下一状态的可迭代生成器，供下一步循环使用next_state = next_state_lawful(current_state)#遍历所有可能的下一状态for state in next_state:if state not in record:#保证当前状态没在以前出现过。如果状态已经出现还进行搜索就会形成状态环路，陷入死循环。record.append(state)#添加新的状态到列表中if state == final_state:print(record)#打印出可行方案#record_list.append(record)这样使用错误，导致加入列表的是record的引用，应该使用下面的式子来进行深复制，得到一个新的队列再加入列表。record_list.append(deque(record))num += 1else:# 递归搜索searchResult(record)# 去除当前循环中添加的状态，进入下一个循环，关键步，第一次实现的时候遗漏了   record.pop()

searchResult(record)
print("总共实现方式的种类数目：", num)
print("实现方式的最少步骤为：%d 步" % (min([len(i) for i in record_list])-1))

deque([[3, 3, 0, 0, 0], [3, 1, 0, 2, 1], [3, 2, 0, 1, 0], [3, 0, 0, 3, 1], [3, 1, 0, 2, 0], [1, 1, 2, 2, 1], [2, 2, 1, 1, 0], [0, 2, 3, 1, 1], [0, 3, 3, 0, 0], [0, 1, 3, 2, 1], [0, 2, 3, 1, 0], [0, 0, 3, 3, 1]])
deque([[3, 3, 0, 0, 0], [3, 1, 0, 2, 1], [3, 2, 0, 1, 0], [3, 0, 0, 3, 1], [3, 1, 0, 2, 0], [1, 1, 2, 2, 1], [2, 2, 1, 1, 0], [0, 2, 3, 1, 1], [0, 3, 3, 0, 0], [0, 1, 3, 2, 1], [1, 1, 2, 2, 0], [0, 0, 3, 3, 1]])
deque([[3, 3, 0, 0, 0], [2, 2, 1, 1, 1], [3, 2, 0, 1, 0], [3, 0, 0, 3, 1], [3, 1, 0, 2, 0], [1, 1, 2, 2, 1], [2, 2, 1, 1, 0], [0, 2, 3, 1, 1], [0, 3, 3, 0, 0], [0, 1, 3, 2, 1], [0, 2, 3, 1, 0], [0, 0, 3, 3, 1]])
deque([[3, 3, 0, 0, 0], [2, 2, 1, 1, 1], [3, 2, 0, 1, 0], [3, 0, 0, 3, 1], [3, 1, 0, 2, 0], [1, 1, 2, 2, 1], [2, 2, 1, 1, 0], [0, 2, 3, 1, 1], [0, 3, 3, 0, 0], [0, 1, 3, 2, 1], [1, 1, 2, 2, 0], [0, 0, 3, 3, 1]])
总共实现方式的种类数目： 4
实现方式的最少步骤为：11 步

这篇关于《算法的乐趣》6.妖怪和和尚过河问题------python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---