• 定义状态：人、狼、羊、菜表示为四维向量 \([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]\) 需要满足下列条件：

  • \(I_1 \neq I2\)。即人必须在船上，即转移前后人处于岸的不同侧
  • 一次之多运送两样
  • 运送的物品都是从\(A\)侧到\(B\)侧，不能是一个从\(A\)到\(B\)，一个从\(B\)到A

  获取全部合法状态转移的函数：

  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
  

[状态转移]人、狼、羊、菜过河问题