AI A_star算法野人渡河-实验报告

class Point:
    def __init__(self, a, b, flag):
        self.a = a  # 左岸传教士数量
        self.b = b  # 左岸野人数量
        self.flag = flag  # flag = 1: 船在左岸；flag = 0: 船在右岸
        self.father = None
        self.node = [a, b, flag]
        self.g = 0
        self.f = 0  # f = g+h

import operator

A = 3  # 传教士数量
B = 3  # 野人数量
K = 3  # 最大乘坐人数量
OPEN = []  # open表
CLOSED = []  # closed表


class Point:
    def __init__(self, a, b, flag):
        self.a = a  # 左岸传教士数量
        self.b = b  # 左岸野人数量
        self.flag = flag  # flag = 1: 船在左岸；flag = 0: 船在右岸
        self.father = None
        self.node = [a, b, flag]
        self.g = 0
        self.f = 0  # f = g+h


init = Point(A, B, 1)  # 初始节点
goal = Point(0, 0, 0)  # 目标节点


# 启发函数
def h(s):
    return s.a + s.b - K * s.flag


# 判断传教士是否安全

def safe(s):
    if s.a > A or s.a < 0 or s.b > B or s.b < 0 or (s.a != 0 and s.a < s.b) or (s.a != A and A - s.a < B - s.b):
        return False
    else:
        return True


def equal(a, b):
    if a.node == b.node:
        return True


# 判断当前状态与父状态是否一致
def back(new, s):
    if s.father is None:
        return False
    return equal(new, s.father)


# 将open_list以f值进行排序
def open_sort(l):
    the_key = operator.attrgetter('f')  # 指定属性排序的key
    l.sort(key=the_key)


# 扩展节点时在open表和closed表中找原来是否存在相同mcb属性的节点
def in_list(new, l):
    for item in l:
        if new.node == item.node:
            return True, item
    return False, None


def A_star(s):
    global OPEN, CLOSED
    OPEN = [s]
    CLOSED = []
    while OPEN:  # open表非空
        get = OPEN[0]  # 取出open表第一个元素get
        if get.node == goal.node:  # 判断是否为目标节点
            return get
        OPEN.remove(get)  # 将get从open表移出
        CLOSED.append(get)  # 将get加入closed表

        # 以下得到一个get的新子节点new并考虑是否放入open
        for i in range(A):  # 上船传教士
            for j in range(B):  # 上船野人
                # 船上非法情况
                if i + j == 0 or i + j > K or (i != 0 and i < j):
                    continue
                if get.flag == 1:  # 当前船在左岸，下一状态统计船在右岸的情况
                    new = Point(get.a - i, get.b - j, 0)
                else:  # 当前船在右岸，下一状态统计船在左岸的情况
                    new = Point(get.a + i, get.b + j, 1)

                if not safe(new) or back(new, get):  # 状态非法或new折返了
                    pass
                # 如果要拓展的节点满足以上情况，将它的父亲设为当前节点，计算f，并对open_list排序
                else:
                    new.father = get
                    new.g = get.g + 1  # 与起点的距离
                    new.f = get.g + h(get)  # f = g + h

                    # 如果new在open表中
                    if in_list(new, OPEN)[0]:
                        old = in_list(new, OPEN)[1]
                        if new.f < old.f:  # new的f<open表相同状态的f
                            OPEN.remove(old)
                            OPEN.append(new)
                            open_sort(OPEN)
                        else:
                            pass

                    # 继续，如果new在closed表中
                    elif in_list(new, CLOSED)[0]:
                        old = in_list(new, CLOSED)[1]
                        if new.f < old.f:
                            # 将old从closed删除，并重新加入open
                            CLOSED.remove(old)
                            OPEN.append(new)
                            open_sort(OPEN)
                        else:
                            pass
                    else:
                        OPEN.append(new)
                        open_sort(OPEN)
        print('OPEN表：')
        for o in OPEN:
            print(o.node,o.g,o.f)


# 递归打印路径
def printPath(f):
    if f is None:
        return
    printPath(f.father)
    print(f.node)


if __name__ == '__main__':
    final = A_star(init)
    if final:
        print('有解，解为：')
        printPath(final)
    else:
        print('无解！')