python实现A*和双向A*（启发式搜索）

1. 实验目的 

1） 掌握搜索算法的基本设计思想与方法，  

2） 掌握A*算法的设计思想与方法，  

3） 熟练使用高级编程语言实现搜索算法，  

4） 利用实验测试给出的搜索算法的正确性。  

1. 实验问题 

寻路问题。以图1为例，输入一个方格表示的地图，要求用A*算法找到并输出从起点（在方格中标示字母S）到终点（在方格中标示字母T）的代价最小的路

径。有如下条件及要求：  

1） 每一步都落在方格中，而不是横竖线的交叉点。

2） 灰色格子表示障碍，无法通行。

3） 在每个格子处，若无障碍，下一步可以达到八个相邻的格子，并且只可以到达无障碍的相邻格子。其中，向上、下、左、右四个方向移动的代价为1，向四

个斜角方向移动的代价为 √2。

4） 在一些特殊格子上行走要花费额外的地形代价。比如，黄色格子代表沙

漠，经过它的代价为4；蓝色格子代表溪流，经过它的代价为2；白色格子为普通地形，经过它的代价为0。

5） 经过一条路径总的代价为移动代价 地形代价。其中移动代价是路径上所做的所有移动的代价的总和；地形代价为路径上除起点外所有格子的地形代价的总和。

import numpy as np
import matplotlib.pyplot as plt
import numpy as np; np.random.seed（0）
import seaborn as sns; sns.set（）
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

import numpy as np
import matplotlib.pyplot as plt
import numpy as np;

np.random.seed（0）
import seaborn as sns;

sns.set（）
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

# %%

# 地形

# 通路
road = 0
# 沙漠
caravan = 4
# 路障
barrier = 1
# 河流
river = 2

# 起始点，终止点
st_end = 3
# path
path1 = 5
path2 = 6

# 直线距离
d = 1
# 斜线距离
k = 1.414


def check_pass（terrain）:
    if terrain == road or terrain == caravan or terrain == river:
        return True
    else:
        return False


class Node:
    def __init__（self x y）:
        self.x = x
        self.y = y
        self.F = .0
        self.G = .0
        self.H = .0
        self.parent = None


def least_f（open）:
    res = open[0]
    for node in open:
        if node.F < res.F:
            res = node
    return res


def get_surrounds（node area_map close）:
    res = []
    for i in range（-1 2）:
        for j in range（-1 2）:

            if i == 0 and j == 0:
                continue

            x = node.x + i
            y = node.y + j

            # 超出边界
            if x < 0 or y < 0 or \
                    len（area_map） <= x or len（area_map[0]） <= y:
                continue
                # 判断是否可行
            if not check_pass（area_map[x][y]）:
                continue
            # 未访问过
            node_tmp = Node（x y）
            flag = is_in_list（node_tmp close）
            if flag is None:
                res.append（node_tmp）

    return res


# Calc G
def calc_g（start surround area_map）:
    extra_g = d if （（abs（surround.y - start.y） + abs（surround.x - start.x）） == 1） else k
    extra_g += area_map[surround.x][surround.y]  # 额外的地形代价
    parent_g = 0 if surround.parent is None else surround.parent.G  # 当前点的父节点的起始点到父节点的代价
    surround.G = parent_g + extra_g  # 当前步＋之前的步


def is_in_list（surround1 close）:
    for c in close:
        if surround1.x == c.x and surround1.y == c.y:
            return c
    return None


def calc_h（surround close m_tmp）:  # 计算当前点到终点的距离
# def calc_h（surround end）:  # 计算当前点到终点的距离
    # h_diagonal = min（abs（surround.x - end.x） abs（surround.y - end.y））
    # h_straight = abs（surround.x - end.x） + abs（surround.y - end.y）
    # surround.H = k * h_diagonal + d * （h_straight - 2 * h_diagonal）
    min_h = 99999
    surroundPoints = get_surrounds（surround m_tmp close）
    for target in surroundPoints:
        if is_in_list（target close） is not None:
            if （abs（target.x - surround.x） + abs（target.y - surround.y）） == 1:
                if （d + m_tmp[surround.x][surround.y]） < min_h:
                    min_h = d + m_tmp[surround.x][surround.y]
            else:
                if k + m_tmp[surround.x][surround.y]

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件       10263  2020-12-02 16:07  a_star_bidirection.py
     文件        9389  2020-12-04 09:17  a_star_single.py