A*算法与八数码问题(numpy)

努力是为了不平庸~

学习的最大理由是想摆脱平庸,早一天就多一份人生的精彩;迟一天就多一天平庸的困扰。

目录


一、引言 

    A*算法是一种启发式图搜索算法,其特点在于对估价函数的定义上。对于一般的启发式图搜索,总是选择估价函数f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的实际代价以及从节点n到达目标节点的估价代价。

 以8数码问题为例实现A*算法的求解程序。

 估价函数f(n) = g(n) + h(n)

g(n)=d(n)——结点n在搜索树中的深度

h(n)可选择h1(n)——结点n中“不在位”的数码个数 或 h2(n) =p(n)= 将牌“不在位”的距离和

二、思路

1. 确定问题和目标:

   八数码问题,即通过移动数字将初始状态转变为目标状态。目标是编写能够自动求解八数码问题的程序。

2. 确定算法和数据结构:

   选择A*算法,然后确定所需的数据结构,如节点类、状态表示方法等。

3. 编写代码框架

   ①定义必要的变量和数据结构,如open表、close表、初始状态和目标状态等。

   ②创建节点类,并定义节点类的属性和方法。

4. 实现辅助函数:

   根据代码中的需要,实现辅助函数,如find_pos函数用于找到数字在状态中的位置。

5. 实现主函数:

   ①编写主函数,处理用户输入和输出。

   ②获取用户输入的初始状态和目标状态。

   ③检查可行解的存在性,判断是否可以通过移动数字从初始状态到达目标状态。

   ④如果可行解存在,开始启发式搜索过程。

6. 实现搜索算法:

   ①在主函数中编写启发式搜索的逻辑。

   ②创建open表和close表,并初始化。

   ③使用循环迭代进行搜索,直到找到可行解或无解。

   ④在每次迭代中,根据算法规则进行状态扩展和判断,并更新open表和close表。

7. 实现状态操作函数:

   根据算法需求,实现状态操作函数,如移动空白格、判断状态是否在表中等。

8. 进行测试和调试:

   ①编写测试用例,包括不同的初始状态和目标状态。

   ②运行代码,并观察输出结果是否符合预期。

   ③根据需要进行调试和修正代码错误。

 三、代码与函数

A、代码步骤的方法、目的及意义

①导入必要的库:

   这里使用了NumPy库,它提供了Python中对多维数组进行高效操作的功能。

②定义open表与close表以及初始状态和目标状态:

   open表用于存放待扩展的节点,close表用于存放已扩展的节点。start_state和target_state分别表示初始状态和目标状态,都是3×3的二维数组。

③定义节点类:

   这里定义了一个名为Node的类,表示搜索过程中的节点。该类具有一些属性和方法,用于存储节点状态、计算代价等信息。

④定义辅助函数,实现节点类:

   find_pos(self, state, num):在状态state中查找值为num的元素的位置。

   __init__(self, state, prt=[]):节点类的构造函数,初始化节点的状态、父节点、代价等信息。

   moveto(self, x, y):将空白格移动到指定位置(x, y),生成新的状态。

⑤定义函数get_reverse_num(state)用于计算逆序数,判断解的存在性。

   意义:逆序数用于判断八数码问题是否有可行解。

⑥定义函数display(cur_node)用于输出状态及深度信息。

   意义:用于展示搜索过程中每个节点的状态、搜索深度、代价等信息。

⑦定义函数is_in_list(alist, state)用于检查状态是否在列表中。

   意义:用于判断一个状态是否已经在open表或close表中。

⑧定义排序的权值函数delta(node)。

意义:用于指定节点的排序权值,这里使用节点的F值作为排序依据。

⑨输入初始状态和目标状态:

   意义:使用输入函数逐个获取用户输入的初始状态和目标状态。

⑩判断是否存在可行解:

    使用逆序数判断八数码问题是否有可行解。如果逆序数的奇偶性不同,则不存在可行解。

⑪启发式搜索的实现:

    在启发式搜索中,使用open表存放待扩展的节点,close表存放已扩展的节点。通过不断扩展节点,并将其加入open表和close表,最终找到可行解。搜索过程中,使用delta函数对open表中的节点按照F值进行排序

以上是对代码的关键步骤的分析。

B、函数构造和作用

1. 函数get_reverse_num(state):

   构成:

          ①参数:state,表示一个状态的二维数组。

          ②返回值:逆序数,表示状态中元素的逆序对数量。

   作用:该函数用于计算逆序数,判断八数码问题是否有可行解。通过将非空元素按顺序拼接成字符串s,然后统计在s中出现的逆序对数量,最终得到逆序数。

2. 函数display(cur_node):

   构成:

          ①参数:cur_node,表示当前节点对象。

          ②作用:该函数用于展示搜索过程中每个节点的状态、搜索深度、代价等信息。首先,它通过跟踪节点的父节点,将搜索路径中的所有节点存储在列表alist中。然后,它按照搜索路径的顺序遍历alist,打印每个节点的搜索深度G、状态state、代价信息G、H、F。

3. 函数is_in_list(alist, state):

   构成:

           ①参数:alist,表示一个节点列表;state,表示一个状态的二维数组。

           ②返回值:如果状态state在列表alist中存在,则返回对应的节点对象;否则返回-1。

   作用:该函数用于判断一个状态是否已经在open表或close表中。它遍历列表alist中的节点对象,将每个节点的状态与输入的state进行比较。如果找到匹配的状态,则返回对应的节点对象;否则返回-1,表示状态不在列表中。

4. 函数delta(node):

   构成:

            ①参数:node,表示一个节点对象。

            ②返回值:节点的代价F。

   作用:该函数用于作为排序的权值函数。在启发式搜索中,根据节点的代价F值对open表中的节点进行排序。

四、state和parent的属性和作用

state和parent是节点类中的两个重要属性

1.state属性:

   构成:state是一个二维数组,表示节点对应的状态。

   作用:state记录当前节点状态,即一个具体的排列。通过不同的状态组合,可以表示不同的八数码棋盘布局。

   例:在代码中的使用:通过current_node.state可以获取当前节点的状态。

2. parent属性:

   构成:parent是一个列表,存储指向父节点的引用。

   作用:parent记录了当前节点的父节点,即在搜索树中指向当前节点的上一层节点。

   例:在代码中的使用:通过current_node.parent可以获取当前节点的父节点。这对于回溯搜索路径和展示解决方案非常有用,因为可以通过跟踪父节点,从目标节点一直追溯到初始节点,形成搜索路径。

在启发式搜索中,每个节点都通过移动空白格生成新的状态,并将其作为子节点添加到搜索树中。通过state和parent属性的设置和更新,可以构建搜索树,跟踪搜索路径,并最终找到解决八数码问题的路径。

五、解题代码

import numpy as np

# 定义open表与close表
open_list = []  # 存放待扩展的节点
close_list = []  # 存放已扩展的节点
start_state = np.zeros((3, 3), dtype=int)  # 初始状态,3×3矩阵,先全设为零
target_state = np.zeros((3, 3), dtype=int)  # 目标状态,3×3矩阵,先全设为零

# 定义节点类
# 定义了一个名为Node的类,表示搜索过程中的节点。该类具有一些属性和方法,用于存储节点状态、计算代价等信息。
class Node:
    G = 0  # 起点到当前节点的最短路径代价值
    H = 0  # 当前节点到目标节点的最短路径代价值
    F = 0  # F = G + H,起点经过当前节点到目标节点的最短路径的总代价值
    state = np.zeros((3, 3), dtype=int)  # 一个二维数组,记录了当前节点的状态,即八数码问题中的一个具体排列。通过不同的状态组合,可以表示不同的八数码棋盘布局。
    parent = []  # 一个列表,记录了当前节点的父节点,即在搜索树中指向当前节点的上一层节点。


    #find_pos(self, state, num)是节点类中的一个方法,用于找到指定数字在状态中的位置
    # self:表示节点对象自身。  state:表示一个状态的二维数组。  num:表示要查找的数字。  返回一个包含两个元素的元组(i, j),表示数字num在状态state中的行索引和列索引。
    def find_pos(self, state, num):             # 在状态state中查找值为num的元素的位置x,y
        for i in range(len(state)):
            for j in range(len(state[i])):
                if state[i][j] == num:
                    return i, j

    # 节点类的构造函数,初始化节点的状态、父节点、代价等信息。
    def __init__(self, state, prt=[]):
        self.state = state
        if prt:
            self.parent = prt
            self.G = prt.G + 1
        for i in range(len(state)):
            for j in range(len(state[i])):
                x, y = self.find_pos(target_state, state[i][j])
                self.H = self.H + abs(x - i) + abs(y - j)
        self.F = self.G * 1 + self.H * 10

    # 将空白格移动到指定位置(x, y),生成新的状态。
    def moveto(self, x, y):
        x0, y0 = self.find_pos(self.state, 0)
        newstate = self.state.copy()
        tmp = newstate[x0][y0]
        newstate[x0][y0] = newstate[x][y]
        newstate[x][y] = tmp
        return newstate

# 得到逆序数,用于判断解的存在性
# 逆序数用于判断八数码问题是否有可行解
def get_reverse_num(state):
    ans = 0
    s = ""
    for i in range(len(state)):
        for j in range(len(state[i])):
            if not state[i][j] == 0:
                s += str(state[i][j])

    for i in range(len(s)):
        for j in range(i):
            if s[j] > s[i]:
                ans += 1
    return ans

# 输出状态及深度信息
# 用于展示搜索过程中每个节点的状态、搜索深度、代价等信息
def display(cur_node):
    alist = []
    tmp = cur_node
    while tmp:
        alist.append(tmp)
        tmp = tmp.parent
    alist.reverse()
    for node in alist:
        print("搜索深度%d" % node.G)
        print(node.state)
        print("G={0},H={1},F={2}".format(node.G, node.H, node.F))
        print()
    print("总共探索了%d次" % int(node.G + 1))

# 检查state状态是否在list中(可能是open或close表)
# 用于判断一个状态是否已经在open表或close表中
def is_in_list(alist, state):
    for stat in alist:
        if (stat.state == state).all():
            return stat
    return -1

# 排序的权值函数
# 用于指定节点的排序权值,这里使用节点的F值作为排序依据
def delta(node):
    return node.F

# 输入初始与目标状态
# 使用输入函数逐个获取用户输入的初始状态和目标状态
for i in range(len(start_state)):
    for j in range(len(start_state[i])):
        start_state[i][j] = input("start_state" + "(" + str(i + 1) + "," + str(j + 1) + "):")

print("the start state is:")
print(start_state)

for i in range(len(target_state)):
    for j in range(len(target_state)):
        target_state[i][j] = input("target_state" + "(" + str(i + 1) + "," + str(j + 1) + "):")

print("the target state is:")
print(target_state)

# 可行解判断
# 使用逆序数判断八数码问题是否有可行解。如果逆序数的奇偶性不同,则不存在可行解
if get_reverse_num(target_state) % 2 != get_reverse_num(start_state) % 2:
    print(get_reverse_num(target_state))
    print(get_reverse_num(start_state))
    print("找不到可行解!")
    exit(-1)

# 可行解存在时,开始启发搜索
# 在启发式搜索中,使用open表存放待扩展的节点,close表存放已扩展的节点。
# 通过不断扩展节点,并将其加入open表和close表,最终找到可行解。搜索过程中,使用delta函数对open表中的节点按照F值进行排序
open_list.append(Node(start_state))
while open_list:
    current_node = open_list.pop(0)  # 从open表中取出F值最小的节点进行扩展
    close_list.append(current_node)  # 将扩展的节点加入close表
    # 当open表中取出的恰好为目标状态时,找到可行解
    if (current_node.state == target_state).all():
        print("可行解已找到!")
        display(current_node)
        exit(0)
    # 否则对当前节点进行拓展
    x, y = current_node.find_pos(current_node.state, 0)  # 找到空白格的位置
    for [x_, y_] in [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]]:
        if 0 <= x_ < len(start_state) and 0 <= y_ < len(start_state):
            new_state = current_node.moveto(x_, y_)  # 移动空白格得到新状态
            # 判断新状态是否在close表
            if is_in_list(close_list, new_state) == -1:
                # 如果不在close表
                if is_in_list(open_list, new_state) == -1:
                    # 如果也不在open表,则将其加入open表
                    open_list.append(Node(new_state, current_node))
                else:
                    # 如果open表中已存在这种状态,则选取G值较小的
                    index = is_in_list(open_list, new_state)
                    if current_node.G + 1 < open_list[index].G:
                        # 如果新路线更好,则放弃旧路线而选择新路线
                        open_list.pop(index)
                        open_list.append(Node(new_state, current_node))
                    # 否则忽略
    # 对open表按F值从小到大进行排序
    open_list.sort(key=delta)

版权声明:本文为博主作者:醉蕤原创文章,版权归属原作者,如果侵权,请联系我们删除!

原文链接:https://blog.csdn.net/m0_63794226/article/details/131191603

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
乘风的头像乘风管理团队
上一篇 2024年1月3日
下一篇 2024年1月3日

相关推荐

此站出售,如需请站内私信或者邮箱!