三牛三虎过河问题–图的最短路径dijkstra算法–简单的Python实现

问题：三头牛三只虎要过河，船需要一只动物来划，另外至多还能载一物，而只有一头牛和一只虎会划船，并且当虎的数量多于牛的数量时，虎要吃牛，请设计一个安全渡河方案，并使渡河次数尽量少。

我们用一个数组来表示起点动物的状态，数组中元素为0表示此动物在起点，为1表示此动物不在起点（也就是在终点）

数组描述：[牛一， 牛二， 牛三，虎一，虎二，虎三]

例如：最开始时状态为 000000 （六只动物全部在起点）

结束状态：111111（六只动物全部到达终点）

那么这是一个求无权有向图的最短路径的问题，图的每个节点就是一个状态（此状态必须为有效状态），也就是说我们要从求起始节点（000000）到终点（111111）的路径

思路：

1. 这是一个有向图，首先我们就要把这个图建出来，第一步就是找到所有节点（有效状态），我们定义一个find_all_valid_status函数来实现此功能：穷举法+判断是否合法（写一个judge_status_valid函数来实现），遍历000000->000001->000010->000011-> ··· ->111111，判断每个状态是否合法，如果合法就将此状态加入valid_status

2. 第二，思考如何状态转移，由于只有一头牛和一头虎会划船，我们假设牛一和虎一会划船。于是定义一个状态转移数组translation，里面存储了11个合法转移方式，例如 100000表示牛一过河、 100100表示牛一和虎一过河、 001100表示牛三和虎一过河

   然后如何通过这个状态转移数组来进行状态转移呢？这里使用异或运算，举个例子：

   当前状态为100010，
   起点：牛2，牛3 ，虎1，虎3                                      终点：牛1，虎2      
   我们要进行010100的状态转移（就是让牛2和虎1过河），那么就是 100010 ^ 010100 = 110110
   起点：牛3，虎3                                                           终点：牛1，牛2，虎1，虎2
   这样是不是就成功让牛2和虎1过河了
   

3. 我们知道了这个图的所有节点，并且知道了如何状态转移（就能求出这些节点之间的边），那么就能把这个图建出来。这里调用了Python的Graph库中的dijkstra，掩盖了dijkstra算法和建图的细节，写起来更简便

from dijkstar import Graph, find_path
import numpy as np

names = np.array(['牛一', '牛二', '牛三', '虎一', '虎二', '虎三'])
translation = [[1, 0, 0, 0, 0, 0],
       [1, 1, 0, 0, 0, 0],
       [1, 0, 1, 0, 0, 0],
       [1, 0, 0, 1, 0, 0],
       [1, 0, 0, 0, 1, 0],
       [1, 0, 0, 0, 0, 1],
       [0, 0, 0, 1, 0, 0],
       [0, 1, 0, 1, 0, 0],
       [0, 0, 1, 1, 0, 0],
       [0, 0, 0, 1, 1, 0],
       [0, 0, 0, 1, 0, 1]]
translation = np.array(translation)

graph = Graph()
valid_status = []
def judge_status_valid(status)->bool:   #判断一个状态是否合法
    cattles=0   //用来统计起点牛的数量
    tigers=0  //用来统计起点虎的数量
    for i in range(0, 3):
        if  status[i] == 0:
            cattles += 1
    for i in range(3, 6):
        if status[i] == 0:
            tigers += 1
    if  cattles == 3 or cattles == 0 or cattles == tigers:  //根据起点虎和牛的数量来判断状态是否合法
        return True
    return False

def find_all_valid_status():
    for i in range(0, 64):               #相当于从000000遍历到111111
        status = bin(i)[2:]                        #这里是一个二进制字符串
        status = status.rjust(6, '0')      #控制二进制位数为6位
        status = list(map(int, status))           #将字符串转换为列表
        global valid_status
        if  judge_status_valid(status):
            valid_status.append(status)
    valid_status = np.array(valid_status)    #将有效状态的数组转换为numpy的数组类型
       

def status_transfer(orgin_status, transfer_mode):          #进行状态转移
    arr = []
    for i in range(len(orgin_status)):
        arr.append(orgin_status[i] ^ transfer_mode[i])  #异或运算得到下一个状态
    arr = np.array(arr)
    return arr

def build_graph():
    for status in valid_status:
        for transfer in translation:
            locations_1 = np.argwhere(transfer == 1).squeeze()  #降维处理
            #print(locations_1)
            #print(type(locations_1))
            if  locations_1.size==1 or  status[locations_1[0]] == status[locations_1[1]]:
                next_status = status_transfer(status, transfer)          #进行状态转移之后，下一个状态
                vertex1 = int(np.argwhere((valid_status==status).all(axis=1)))       #查找status在valid_status中的位置，用位置索引作为图的顶点
                vertex2 = np.argwhere((valid_status==next_status).all(axis=1))
                if vertex2.size != 0:
                    vertex2 = int(vertex2)
                    #print("vertex=", vertex2, "   ", vertex2.size)
                    graph.add_edge(vertex1, vertex2, 1)    #建立从顶点vertex1到vertex2的边,边长默认为1（每条边的边长为1，就相当于无权图了）
                
def show_status(status):         #根据当前状态数组打印出状态
    for i in range(status.size):
        if  status[i] == 0:
            print(names[i], end="")
    print("  |  ", end="");
    for i in range(status.size):
        if status[i] == 1:
            print(names[i], end="")

def transfer_object(status1, status2):
    print("           下一步转移对象：", end="");
    flag = 0
    for i in range(status1.size):
        if status1[i] != status2[i]:
            print(names[i], end=' ')
            flag = status1[i]
    if  flag==0:
        print("从起点到终点", end=" ")
    else:
        print("从终点到起点", end=" ")        

def show_how_to_transfer(shortest_path):    #打印转移过程
    for i in range(0, len(shortest_path)-1):
        #print(valid_status[path], type(valid_status[path]), valid_status[path].size)
        #根据当前状态和下一个状态确定转移对象
        path1 = valid_status[shortest_path[i]]         #当前状态
        path2 = valid_status[shortest_path[i+1]]    #下一个状态
        show_status(path1)
        transfer_object(path1, path2)
        print()
    show_status(valid_status[shortest_path[-1]])
    print()

find_all_valid_status()     #找到所有有效状态
build_graph()           #建立图
 #一共有34个有效状态，那么就是求从起点0到终点33的最短路径
shortest_paths = find_path(graph, 0, 33)   #用dijkstar算法求最短路径
print("最短路径：", shortest_paths.nodes)
show_how_to_transfer(shortest_paths.nodes)

今天的文章三牛三虎过河问题–图的最短路径dijkstra算法–简单的Python实现分享到此就结束了，感谢您的阅读。