定义状态：人、狼、羊、菜表示为四维向量 \([i,j,k,w]\) 。\(0\) 表示在左岸，\(1\) 表示在右岸。最终需要从 \([0,0,0,0]\) 转移到 \([1,1,1,1]\)
不合法状态：由于人不在时，狼会吃羊，羊会吃菜，故这些状态不合法：
i != j and j == k # 狼吃羊
i != k and k == w # 羊吃菜
获取全部合法状态的函数：
def get_state():
cnt = 0
state = {}
for i in range(2):
for j in range(2):
for k in range(2):
for w in range(2):
if (i != j and j == k) or (i != k and k == w):
continue
else:
state[cnt] = [i,j,k,w]
cnt += 1
return cnt, state
状态转移：
船每一次需从左岸到右岸，或从右岸到左岸，运送至多两样，且人必须在船上。故对于某一个状态转移\([I_1, J_1, K_1, W_1]\to [I_2, J_2, K_2, W_2]\) 需要满足下列条件：
获取全部合法状态转移的函数：
def get_trans(cnt, state):
trans = []
for i in range(cnt):
for j in range(i+1, cnt):
m = state[i]
n = state[j]
# count diff
diff = sum([m[x]^n[x] for x in range(4)])
sub = sum([m[x]-n[x] for x in range(4)])
if diff > 2 or m[0] == n[0] or sub == 0:
continue
else:
# print(str(m) + " => " + str(n))
trans.append((i,j))
return trans
转化问无向图最短路问题，求解\([0,0,0,0] \to [1,1,1,1]\) 的最短路
import networkx as nx
import numpy as np
# [ human, wolf, sheep, veg]
def get_state():
cnt = 0
state = {}
for i in range(2):
for j in range(2):
for k in range(2):
for w in range(2):
if (i != j and j == k) or (i != k and k == w):
continue
else:
state[cnt] = [i,j,k,w]
cnt += 1
return cnt, state
def get_trans(cnt, state):
trans = []
for i in range(cnt):
for j in range(i+1, cnt):
m = state[i]
n = state[j]
# count diff
diff = sum([m[x]^n[x] for x in range(4)])
sub = sum([m[x]-n[x] for x in range(4)])
if diff > 2 or m[0] == n[0] or sub == 0:
continue
else:
# print(str(m) + " => " + str(n))
trans.append((i,j))
return trans
if __name__ == ‘__main__‘:
num_node, tot_state = get_state()
tot_trans = get_trans(num_node, tot_state)
G = nx.Graph()
for node in range(num_node):
G.add_node(node)
for edge in tot_trans:
G.add_edge(edge[0], edge[1])
tot_shortest_path = nx.all_shortest_paths(G=G, source=0, target=num_node-1)
dic = {0:"人", 1:"狼", 2:"羊", 3:"菜"}
cnt = 0
for shortest_path in tot_shortest_path:
for i in range(len(shortest_path)):
cur = tot_state[shortest_path[i]]
print(‘[‘ + str(i+1) + ‘] ‘, end=‘‘)
print("左岸: ", end=‘‘)
for j in range(4):
if cur[j] == 0:
print(dic[j], end=‘‘)
print(" | ",end=‘‘)
print("右岸: ", end=‘‘)
for j in range(4):
if cur[j] == 1:
print(dic[j], end=‘‘)
print(‘\n‘)
print(‘------------------------‘)
cnt += 1
print(‘总方案数‘ + str(cnt))
结果
[1] 左岸: 人狼羊菜 | 右岸:
[2] 左岸: 狼菜 | 右岸: 人羊
[3] 左岸: 人狼菜 | 右岸: 羊
[4] 左岸: 狼 | 右岸: 人羊菜
[5] 左岸: 人狼羊 | 右岸: 菜
[6] 左岸: 羊 | 右岸: 人狼菜
[7] 左岸: 人羊 | 右岸: 狼菜
[8] 左岸: | 右岸: 人狼羊菜
------------------------
[1] 左岸: 人狼羊菜 | 右岸:
[2] 左岸: 狼菜 | 右岸: 人羊
[3] 左岸: 人狼菜 | 右岸: 羊
[4] 左岸: 菜 | 右岸: 人狼羊
[5] 左岸: 人羊菜 | 右岸: 狼
[6] 左岸: 羊 | 右岸: 人狼菜
[7] 左岸: 人羊 | 右岸: 狼菜
[8] 左岸: | 右岸: 人狼羊菜
------------------------
总方案数2
原文：https://www.cnblogs.com/popodynasty/p/14968497.html