A* 算法求解十五数码问题

这是一门小课的课堂作业,计划通的我就用实验报告水一篇吧~

请注意,本文编写于 239 天前,最后修改于 144 天前,其中某些信息可能已经过时。

问题描述

数码问题是一类比较经典的图搜索问题,它给定如下表所示的某个初始状态(这里以 4*4 的十五数码问题为例):

119415
13012
7586
1321014

每次可将 0 上下左右移动一格,要求寻找某个移动策略,使整个局面达到目标状态,例如:

1234
5678
9101112
1314150

算法描述

一般图搜索算法

视每种状态为一个节点。在某节点下,通过移动 0 的位置可以得到新的节点,这称为“扩展一个节点”。理论上讲,整个牌局可能出现的局面数,也就是节点数是有穷的,因此通过暴力搜索肯定能找到解(若有解的话)。但是 15 数码问题局面总数是 16!,这使暴力搜索没有实践价值。

一般的图搜索算法通过维护两个表:OPEN 表与 CLOSE 表,分别存放未被扩展过的节点与已经被扩展过的节点,并通过某种策略来优化搜索过程。其基本过程是:

  1. 将初始状态加入 OPEN 表,清空 CLOSE 表
  2. 若 OPEN 表为空,失败,退出
  3. 移除 OPEN 表中的第一个节点,将其加入 CLOSE 表,该节点记为 n
  4. 若 n 是目标节点,搜索成功,退出
  5. 扩展 n 节点,舍弃扩展出的子节点中与 n 的父节点相同的节点,对剩下的子节点做如下处理:

    • 若该子节点不在 OPEN 表与 CLOSE 表中,则将其加入 OPEN 表
    • 否则,记与该子节点相同的已存在的节点为 P,舍弃该子节点,按照某种原则判断是否应该修改 P 的父节点指向
  6. 按照某种原则重排 OPEN 表
  7. 跳转至第二步

这个过程给出了图搜索算法的一般流程。在进行算法实现时还需要指定重排 OPEN 表的准则:也就是确定哪些节点应该被优先扩展与留在搜索树中。

A 算法

A 算法通过一个估价函数 f 来对节点进行评价,估计出该节点到达目标节点的“希望”,并有限扩展最有希望的节点。其估价函数定义为:

$$ f(n)=g(n)+h(n) $$

其中 n 代表被评价的节点。特别的,定义

$$ g^*(n):从起始节点到n的最优路径的代价 $$

$$ h^*(n):从n到目标节点的最优路径的代价 $$

$$ f^*(n):从起始节点到目标节点的最优路径的代价 $$

因此 $f(n),g(n),h(n)$ 是 $f^*(n),g^*(n),h^*(n)$ 的估计值。一般选择 $g(n)$ 为起始节点到 n 的实际代价,$h(n)$ 为 n 到目标节点的代价估计。$h(n)$ 是基于某准则制定的启发函数,用于描述 n 到目标节点的“难度”。

在一般图搜索算法的第 6 步,A 算法对 OPEN 表中的所有节点使用 $f(n)$ 进行评价并由小到大排序,每次都有限扩展 $f(n)$ 最小的节点。另外在第 5 步,当 P 已存在时,若新生成的子节点的 $f(n)$ 相对 P 的更小,则更新 P 的父节点为当前节点,并递归地更新 P 的所有子节点的估价。

A* 算法

在 A 算法中,若有

$$ h(n)\leq h^*(n) $$

则称为 A* 算法。

算法实现

这里使用 C++ 进行算法实现。设初始与目标状态为问题描述中的两个表。选取 $h(n)$ 为当前节点中所有数码相对目标位置的曼哈顿距离和。

节点类

extern int start[4][4];
extern int target[4][4];
extern int trans[4][2];

class node
{
public:
    int m_State[4][4];
    int m_Zero[2];    
    node* m_Parent;  
    vector<node*> m_Childern;   
    int m_H; // 代价    
    int m_G; // 深度

    node();
    node(int from[4][4]);
    node(int from[4][4], node* parent);

    void init(int from[4][4]);
    void calcH();
    void calcG();
    static void findZero(int state[4][4],int pos[2]);
    void findZero();
    int getPrice();
    void expand();
    bool check(int t[4][4]);

    // 重载操作符,判定节点是否等价
    bool operator==(node b) {
        return this->check(b.m_State);
    }

    bool operator==(int t[4][4]) {
        return this->check(t);
    }
};

void print(int t[4][4]);
int output(node* n);
node* findP(int t[4][4]);
node* get();
void updateAll(node* n);

大部分成员及方法这里只给出声明,实现见附件中的 node.cpp。其中的 expand() 方法值得注意:

int trans[4][2] = { { -1,0 },{ 1,0 },{ 0,1 },{ 0,-1 } };
void node::expand() {
    for (int index = 0; index < 4; index++) {
        int newZP[2] = { m_Zero[0] + trans[index][0],m_Zero[1] + trans[index][1] };
        if (newZP[0] < 0 || newZP[0]>3 || newZP[1] < 0 || newZP[1]>3) continue;

        // 新的数码位置
        int newState[4][4];

        // 初始化为当前状态
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                newState[i][j] = m_State[i][j];
            }
        }

        // 交换 m_Zero 与 newZP 两个位置的数
        int t = newState[m_Zero[0]][m_Zero[1]];
        newState[m_Zero[0]][m_Zero[1]] = newState[newZP[0]][newZP[1]];
        newState[newZP[0]][newZP[1]] = t;

        // 排除与父节点相同的节点
        if (this->m_Parent && *(this->m_Parent) == newState) continue;

        node* P = findP(newState);
        if (!P) {
            // 新建节点并加入 OPEN
            node *newN = new node(newState, this);
            OPEN.push_back(newN);
            m_Childern.push_back(newN);
        }
        else {
            // 已存在,若当前节点代价更小,更改已存在的节点指针及其子节点代价
            node *newN = new node(newState, this);
            if (P->getPrice() > newN->getPrice()) {
                // 修改 P 的父节点为当前节点
                P->m_Parent = this;
                P->calcG();
                updateAll(P);
            }
            else {
                delete newN;
                newN = NULL;
            }
        }
    }
}

其中的 updateAll() 递归地更新了 P 的所有子节点的估价。

OPEN 表与 CLOSE 表

使用 std::vector 作为容器:

extern vector<node*> OPEN;
extern vector<node*> CLOSE;

算法执行

执行函数:

node* execute() {
    // OPEN 为空
    if (OPEN.size() < 1) {
        return NULL;
    }
    
    // 获得估价最小的节点
    node *now = get();
    
    // 删除 OPEN 表中元素
    vector<node*>::iterator it;
    for (it = OPEN.begin(); it != OPEN.end(); it++) {
        if (*it == now) {
            OPEN.erase(it);
            break;
        }
    }

    // 放入 CLOSE 表
    CLOSE.push_back(now);
    // 若抵达目标
    if (*now == target) return now;
    
    // 扩展该节点
    now->expand();
    cout << "OPEN: " << OPEN.size() << "\tCLOSE: " << CLOSE.size() << '\n';

    // 递归调用
    node*n = execute(); 
    
    // 返回目标
    if(n) return n;

    // 查找失败
    return NULL;
}

int main(){
    OPEN.clear();
    CLOSE.clear();
    node *st = new node(start);
    OPEN.push_back(st);
    return output(execute());
}

测试结果

GHOPEN 表大小CLOSE 表大小
410172546188600

最终寻找到的路径步数为 41 步,已扩展节点数 188600 个,待扩展节点数 172546 个,也就是说算法搜索了接近 400000 个节点最终找到了一个路径。路径变换见附件 out.txt(从下到上为转变路径)。

讨论与总结

有解性判断

对 15 数码问题,并非任何两种状态之间都可以相互转换,当前节点 n 相对目标节点 S 的有解性可以用以下准则判断:(n 逆序数奇偶性==S 逆序数奇偶性)==(0到目标位置的行距%2==0)。其中逆序数为将节点排成一列,其中每个数码前方比自己大的数码个数之和。

有解性判断可用在初始节点的判断上,当判断其无解后就无需再进行搜索了。但是该性质不能帮助搜索过程中的剪枝,因为一旦初始节点有解,由初始节点扩展出的节点都有解。

算法不足

影响该算法性能的主要原因是 OPEN 表的排序这一步。实际实现过程中无需对 OPEN 表全局排序,只需要挑出其中估价最小的节点即可,但是这也需要遍历比较。在节点较多时,这是一个瓶颈。

另外估价函数的设计会使算法性能差别很大。当估价函数的启发性不足时,会生成大量的无用节点,延长搜索时间。


附件:main.cpp | node.h | node.cpp | out.txt

添加新评论

已有 17 条评论

惭愧,看不懂

熊猫小A 熊猫小A 回复 @野兔

兔子日常装萌新

虽然看不懂,但是好厉害

[...]熊猫小A又开始写高大上的代码啦!向他学习,我一定要找个时间好好训练一下代码能力(˙ω˙)[...]

门外汉,看不懂,哈哈哈

熊猫小A 熊猫小A 回复 @林海草原

没事,只是一篇水文~

访问两分钟,这风扇转的,呼呼地~

我也发现了,怀疑是数学公式的问题。别的页面似乎没有这种情况……

这……左下角的加载这么炫酷!

熊猫小A 熊猫小A 回复 @mikusa

左下角?广树大佬的看板娘吗?

mikusa mikusa 回复 @熊猫小A

手机端的

熊猫小A 熊猫小A 回复 @mikusa

你说的可能是数学公式解析的信息?

mikusa mikusa 回复 @熊猫小A

我还以为是新的加载特效……

hv3s1 hv3s1 回复 @ohmyga

二级评论测试

ohmyga ohmyga 回复 @hv3s1

咋拿我做测试

枂下 枂下 回复 @ohmyga

评论测试