人工智能导论实验

A-star algorithm

传送：看懂A*的网站

源码

"""
实验内容：假设在一个 n * m 的迷宫里，入口坐标和出口坐标分别为（1，1）和（5，5），
每一个坐标点有两种可能：0 或 1，其中 0 表示该位置允许通过，1 表示该位置不允许通过
如地图：
    0 0 0 0 0
    1 0 1 0 1
    0 0 1 1 1
    0 1 0 0 0
    0 0 0 1 0

最短路径应该是：
    A B 0 0 0
    1 C 1 0 1
    E D 1 1 1
    F 1 J K L
    G H 1 1 M

估价函数
估价函数 Evaluation Function
 f(n) = g(n) + h(n)
 估价 = 代价 + 启发
代价即 移动到该点的耗费
启发即 该点移动到终点的预计耗费
Open 表根据 f 排序，取 open 表首元素为下一步

"""


# def increase(dot, n, m):
def increase(dot):
    flag = 0
    n = int(dot[0])
    m = int(dot[1])
    print('n, m:', n, m)
    increase_open_list = []     # 先排序，再放入 open 表
    if m - 1 > 0 and list_map[n][m - 1] != 1:
        point = (n, m - 1)
        print(point)
        point = (n, m - 1, f(point))
        print(point)
        if point not in close_list and point not in wrong_list:
            increase_open_list.append(point)
            flag = 1
    if n - 1 > 0 and list_map[n - 1][m] != 1:
        point = (n - 1, m)
        print(point)
        point = (n - 1, m, f(point))
        if point not in close_list and point not in wrong_list:
            increase_open_list.append(point)
            flag = 1
    if m + 1 <= 5 and list_map[n][m + 1] != 1:
        point = (n, m + 1)
        print(point)
        point = (n, m + 1, f(point))
        if point not in close_list and point not in wrong_list:
            increase_open_list.append(point)
            flag = 1
    if n + 1 <= 5 and list_map[n + 1][m] != 1:
        point = (n + 1, m)
        print(point)
        point = (n + 1, m, f(point))
        if point not in close_list and point not in wrong_list:
            increase_open_list.append(point)
            flag = 1
    if flag:
        global open_list
        increase_open_list.sort(key=lambda x: x[2], reverse=False)
        open_list = increase_open_list + open_list
        return True
    return False


def f(dot):
    valuation = g(dot) + h(dot, (5, 5))
    return valuation


def g(dot):
    cost = 1
    return cost


def h(dot, end):
    # 这个启发式算法仅仅是上下左右计算到终点的耗费
    inspire = abs(end[0] - dot[0]) + abs(end[1] - dot[1])
    return inspire


open_list = []
close_list = []
wrong_list = []

d0 = [1, 1, 1, 1, 1, 1]
d1 = [1, 0, 0, 0, 0, 0]
d2 = [1, 1, 0, 1, 0, 1]
d3 = [1, 0, 0, 1, 1, 1]
d4 = [1, 0, 1, 0, 0, 0]
d5 = [1, 0, 0, 0, 1, 0]

list_map = [d0, d1, d2, d3, d4, d5]


# list_map = []
# m = int(input('m:'))
# for i in range(int(input('n:'))):
#     list_n = []
#     for j in range(m):
#         list_n.append(int(input()))
#     list_map.append(list_n)

# start = (1, 1)
# end = (5, 5)
# spot = tuple()

i = 1
j = 1
spot = (i, j)
spot = (i, j, f(spot))
stop = 0
while 1 <= i <= 5 and 1 <= j <= 5:
    # if increase(spot, 5, 5):
    if increase(spot):
        close_list.append(spot)
        print('cl:', close_list)
        # open_list.sort(key=lambda x: x[2], reverse=False)
        print('ol:', open_list)
        spot = open_list[0]
        print('spot:', spot)
        i = int(spot[0])
        y = int(spot[1])
        if i == 5 and y == 5:
            print('arrival terminal.')
            break
    else:
        wrong_way = open_list.pop(0)
        print('wrong_way:', wrong_way)
        wrong_list.append(wrong_way)
        spot = open_list[0]
    stop += 1
    if stop == 20:
        break

传送：加深理解启发函数

$$ 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离（Manhattan distance）\\

如果图形中允许朝八个方向移动，则可以使用对角距离\

如果图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）
$$

• 好吧其实我的启发函数就是最佳优先搜索

---

$$End.$$

md地址.