数据结构与算法分析：专题内容——人工智能中的寻路4之A*搜索（代码详解）

一、算法描述

广度优先搜索能够找到一个最优解（如果存在），但是可能需要访问大量的节点，因为我们可以看到，它并没有尝试对候选走法进行排序。相反，深度优先搜索却是尽可能多地向前探测路径，不过，深度优先搜索的搜索深度必须得到限制，要不然它很有可能会在没有任何结果的路径上花费大量的时间。A搜索在搜索时能够利用启发式信息，智能地调整搜索策略。
如下图所示，A搜索是一种迭代的有序搜索，它维护一个棋面状态的开放集合。在每次迭代时，A搜索使用一个评价函数f(n)评价开放集合中的所有棋面状态，选择最小的棋面状态。我们定义f* (n)=g*(n)+h*(n)：

• g*(n)估算从初始状态到状态n的最短走法序列。
• h*(n)估算从状态n到目标状态的最短走法序列。
• f*(n)估算从初始状态开始，经过状态n，到达目标状态的最短走法序列。

星号表示使用了启发式信息（自从1968年开发出此算法后，这个记法被广泛接受），因此f(n)，g*(n)以及h*(n)是对实际开销f(n)，g(n)和h(n)的估算，这些实际开销只能在得到解之后才能够知道。简而言之，f*(n)越低，表示状态n越接近目标状态。
f*(n)最关键的部分是启发式的计算h*(n)，因为g*(n)能够在搜索的过程中，通过记录状态n的深度计算出来。如果h*(n)不能够准确地区分开有继续搜索价值的状态和没有价值的状态，那么A搜索不会表现得比上述任何盲目搜索要好。如果能够准确地估算h(n)，那么使用f*(n)就能够得到一个开销最小的解。

二、复杂度分析

A搜索的行为完全取决于启发函数。最近的研究结果（Russel和Norvig，2003）表明，如果|h(x)-h(x)|≤logh*(x)，那么性能将会是O(d)，d表示解的距离，而不是O(bd)，b表示搜索树的分支因子。但是，这个条件难以满足，在八数码问题表现很好的GoodEvaluator函数也不能满足这个条件。
随着棋面状态变得越来越复杂，启发式函数越来越重要，同时也越来越难以设计。首先启发式函数必须足够高效，或者能够影响整个搜索过程。但是，即使是最差的启发式函数都能够较好地剪枝搜索空间。例如，十五数码问题，八数码问题的一个扩展，使用八数码问题的GoodEvaluator函数扩展时，目标状态如下：

初始状态如下：

A搜索在处理39个棋面状态之后，快速找到了一个15步的解，这个时候开放集合中还有43个棋面状态，如下图所示。

由于有着15步的限制，深度优先搜索在处理22 136个棋面状态之后，仍然没有找到解。而广度优先搜索在处理172 567个状态（85 213在闭合集中，剩余87 354在开放集中）时，已经耗尽了所有的64MB内存。当然你可以加内存或者增大搜索深度限制，但是这些并不是你无法解出这些问题的理由。
不要被A搜索这么容易解出十五数码所迷惑，当初始棋面状态更加复杂时，例如：

A搜索也耗尽了内存。很明显，这个评估函数并不高效，这个例子有超过1025个可能的状态（Korf，2000）。
广度优先搜索能够保证找到步数最少的解，但是它可能需要评价规模相当大的移动序列。深度优先搜索试着在每次搜索时能够前进更多步，它可能能够快速得到一个解，但是它也可能在搜索树的某个部分浪费大量的时间，尽管看起来这个部分不可能得到解。我们认为比较深度优先搜索，广度优先搜索和A搜索是值得的。使用八数码问题作为样例，我们通过随机移动n个方块（n从2、4、8和16开始），注意同样的方块不会在一行中移动两次，因为这就等于什么也没做。当n≥32时，内存耗尽。对于每个棋面状态，我们执行
BREADTH-FIRST SEARCH,DEPTH-FIRST SEARCH(n),DEPTH-FIRST SEARCH(2n)和A搜索。对于每个n：

• 我们将计算开放集合和闭合集中的状态数目，从而可以看出算法得到解的效率如何。标记为#的列表示的是多次运行的平均值。
• 一旦找到解，我们将会计算解的步数，这样能够看出得到的路径的质量。标有s的列表示的是多次运行的结果。括号中的数字技术的是在给定深度限制下，没有能够得到解的次数。
  下表综合了1000次运行的结果，列出了两个统计值：（a）生成的搜索树的平均状态数目，（b）同样的结果的平均步数。
  以下是图中内容转换为表格形式的结果：

表: 比较搜索算法

注意看随着n的增加，盲目搜索的搜索树的规模指数增长，但是A*搜索的搜索树规模还是可控的。更精确地说，这些盲目搜索的增长率如下：
$DFS2(n)\cong 0.2867^{\ast }{n}^{4.0722}$

$\mathrm{DFS}(n)$ $\ll$ $0.2405\ast n^{2.9517}$

$BFS$$(n)$ $\cong$ $0.2585\ast n^{3.4041}$
广度优先搜索一直能够找到解的最短路径，但是注意即使A搜索检查更少的棋面状态，但是得到的解质量也不错（由于GoodEvaluator启发函数）。在达到30步之后，搜索树的增长率达到O（n1.5147），虽然不是线性，但是相比起盲目搜索，这个规模已经相当小了。这些增长率函数的指数部分依赖于问题的分支因子。上表的图形化表示如下图所示。

广度优先搜索能够找到最短路径，而A搜索找到的路径也差不多是最短的。最后，我们看看水平效应是如何阻止深度优先搜索解决问题的（回忆一下那些离目标状态只有两三步远的状态却被加入闭合集）。事实上，在1000次实验中，深度优先搜索使用最大深度限制为13时，60%的实验都失败了。
分析主要关注于搜索状态的数目，这是决定搜索效率的主要因素。当三种搜索都有可能搜索指数级的状态时，由于h*(n)函数计算出的启发式信息，A搜索将搜索最少的状态。
解决滑动n2-1个方块这样的问题不仅仅只是有寻路这种方法。Parberry（1995）提出了一种别出心裁的方法，使用分治思想。也就是说，给定一个n×n数码，n＞3，首先完成最左边的列和最上部的行，然后递归解决(n-1)2-1数码问题。我们得到一个3×3的子问题，这是可以简单地使用穷举法来解决。这个方法保证能在5n3步内找到解。

三、适用情况

我们使用如下的八数码：

上下两图是两棵计算出的搜索树。上图的搜索树使用的是Nilsson（1971）提出的GoodEvaluatorf*(n)函数。下图的搜索树使用的是同样由Nilsson提出的WeakEvaluator f*(n)函数。

浅灰色的棋面状态表示达到目标状态时开放集合的元素。GoodEvaluator和WeakEvaluator都能够得到同样的解，但是使用GoodEvaluator函数在搜索中更加高效。根据两棵树中f*(n)的值，我们希望知道为什么WeakEvaluator需要访问更多的节点。仔细观察在GoodEvaluator产生的搜索树的最初两步，我们可以清楚地看到f*(n)呈递减趋势。而WeakEvaluator的搜索树在走了4步之后才能够减少搜索的候选方向。WeakEvaluator不能很好地差异化棋面状态，事实上，目标状态节点的f*(n)值比初始状态节点以及其子节点的f*(n)都大。
f*(n)函数的h*(n)部分需要非常优秀的设计，这是一门工程而不是一门科学。h*(n)必须非常高效，否则，搜索时间将会非常长。很多A搜索相关的文献都指出，h(n)函数是高度特化的，根据问题的不同而不同。例如在数字地形的寻路（Wichmann和Wuensche，2004）或者是有限资源下的工程排期（Hartmann，1999）。Pearl（1984）写过一篇设计高效启发式函数的文章（很遗憾已经绝版了）。Korf（2000）讨论了设计可行h*(n)函数的高级策略。Michalewicz和Fogel（2004）提出了一种新的解决问题的启发式思路，不仅仅是只能用于A搜索。
在深度优先搜索和广度优先搜索中，棋面状态都会在处理之后放入闭合集中。由于A搜索的启发式信息需要计算g*(n)，所以可能存在一种情况，这种情况下，A搜索需要重新评价已经做出的决定。比如，如果存在一个将要被放入开放集合的棋面状态，其评估分数要比已经访问过的相同棋面状态评估函数低。这样，A搜索会将这个状态
从闭合集中删除，因为我们可能能够得到一个最小耗费的解。
每个棋面状态都存储了一个后链，叫做DepthTransition，记录的是（a）生成此棋面状态的走法，（b）之前的状态以及（c）初始位置开始的深度。在A搜索中，g(n)通常当作深度。算法多次复制一个棋面状态，用来尝试各种走法。
广度优先搜索和深度优先搜索会检查闭合集是否包含某个棋面状态，所以我们可以用散列表来提高效率。但是，对于A搜索来说，我们可能需要重新评估已经访问过的棋面状态。那么，会发生什么呢？回忆一下在深度优先搜索中，一个达到深度限制的棋面状态，尽管只离目标状态只有3步，但是也会被放入闭合集，并且不会再被处理。在A搜索中，如果棋面状态的得分比之前更低，那么它们就需要重新处理。
A*搜索需要在开放集合中快速找到评价值最小的棋面状态。注意，深度优先搜索和广度优先搜索从开放集合中得到下一个棋面状态只需要常数时间，因为它们使用队列或者栈。如果开放集合是一个有序链表，那么插入棋面状态的性能将会是O(n)，我们不能使用二叉堆，因为我们事先不知道有多少棋面状态需要评估。因此我们使用平衡二叉树，插入棋面状态和得到最小开销的棋面状态的性能都是O(log n)。

四、算法实现

• 输入
  算法从一个初始棋面状态开始，寻找一个目标状态。算法假设（a）在给定棋面状态下可以尝试所有的可行走法，以及（b）计算棋面状态n的评估函数f*(n)。
• 输出
  返回一个走法的序列，表示从初始状态到目标状态的近似开销最小的路径（或者只是输出是否存在一个解）。
• 假设
  如果估算得到的结果和实际结果相差不远，那么A*搜索得到的是开销最小的解。

A搜索在开放集合中存储棋面状态，所以能够高效地删除评价值最小的棋面状态。在深度优先搜索和广度优先搜索中，A搜索查看是否已经达到目标状态的方式只是有些许不同。我们回忆一下，深度优先搜索和广度优先搜索会检查棋面状态是什么时候生成的。尤其，A*搜索在从开放集合中删除元素时，会检查是否已经达到目标状态，这样做的目的是确保得到的解是最短路径。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <memory>
#include <list>
#include <iterator>
#include <cmath>


// Forward declarations
class IMove;
class INode;
class Solution;
class DepthTransition;

// Interface for scoring function
class IScoringFunction {
public:
    virtual void score(std::shared_ptr<INode> node) = 0;
    virtual ~IScoringFunction() = default;
};

// Interface for Node
class INode {
public:
    virtual std::shared_ptr<INode> copy() = 0;
    virtual bool equals(std::shared_ptr<INode> other) = 0;
    virtual double score() const = 0;
    virtual void setScore(double score) = 0;
    virtual std::list<std::shared_ptr<IMove>> validMoves() = 0;
    virtual void storedData(std::shared_ptr<DepthTransition> data) = 0;
    virtual std::shared_ptr<DepthTransition> storedData() const = 0;
    virtual ~INode() = default;
};

// Move interface
class IMove {
public:
    virtual void execute(std::shared_ptr<INode> node) = 0;
    virtual ~IMove() = default;
};

// 前置声明
class PuzzleNode;
class PuzzleMove;

class DepthTransition {
public:
    std::shared_ptr<IMove> move;
    std::shared_ptr<INode> previousNode;
    int depth;
    DepthTransition(std::shared_ptr<IMove> m, std::shared_ptr<INode> prev, int d)
        : move(m), previousNode(prev), depth(d) {
    }
};

// 先声明 PuzzleNode，稍后在类外实现 validMoves
class PuzzleNode : public INode {
private:
    std::vector<int> board;
    double scoreValue;
    std::shared_ptr<DepthTransition> transitionData;
public:
    PuzzleNode(std::vector<int> initial) : board(initial), scoreValue(0.0) {}

    std::shared_ptr<INode> copy() override {
        auto newNode = std::make_shared<PuzzleNode>(board);
        newNode->scoreValue = scoreValue;
        newNode->transitionData = transitionData;
        return newNode;
    }

    bool equals(std::shared_ptr<INode> other) override {
        auto o = std::dynamic_pointer_cast<PuzzleNode>(other);
        return o && (board == o->board);
    }

    double score() const override {
        return scoreValue;
    }

    void setScore(double score) override {
        scoreValue = score;
    }

    void storedData(std::shared_ptr<DepthTransition> data) override {
        transitionData = data;
    }

    std::shared_ptr<DepthTransition> storedData() const override {
        return transitionData;
    }

    // 先声明 validMoves
    std::list<std::shared_ptr<IMove>> validMoves() override;

    const std::vector<int>& getBoard() const {
        return board;
    }

    int getEmptyPos() const {
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) return i;
        }
        return -1;
    }
};

// 定义 PuzzleMove
class PuzzleMove : public IMove {
private:
    int fromPos;
    int toPos;
public:
    PuzzleMove(int f, int t) : fromPos(f), toPos(t) {}

    void execute(std::shared_ptr<INode> node) override {
        auto puzzleNode = std::dynamic_pointer_cast<PuzzleNode>(node);
        if (!puzzleNode) return;
        auto& b = const_cast<std::vector<int>&>(puzzleNode->getBoard());
        std::swap(b[fromPos], b[toPos]);
    }
};

// 在类外实现 PuzzleNode::validMoves，使用 PuzzleMove
std::list<std::shared_ptr<IMove>> PuzzleNode::validMoves() {
    std::list<std::shared_ptr<IMove>> moves;
    int emptyPos = getEmptyPos();
    int row = emptyPos / 3;
    int col = emptyPos % 3;

    // 上
    if (row > 0) moves.push_back(std::make_shared<PuzzleMove>(emptyPos, emptyPos - 3));
    // 下
    if (row < 2) moves.push_back(std::make_shared<PuzzleMove>(emptyPos, emptyPos + 3));
    // 左
    if (col > 0) moves.push_back(std::make_shared<PuzzleMove>(emptyPos, emptyPos - 1));
    // 右
    if (col < 2) moves.push_back(std::make_shared<PuzzleMove>(emptyPos, emptyPos + 1));

    return moves;
}




// Manhattan distance heuristic scoring function
class ManhattanScorer : public IScoringFunction {
public:
    void score(std::shared_ptr<INode> node) override {
        auto puzzleNode = std::dynamic_pointer_cast<PuzzleNode>(node);
        if (!puzzleNode) return;

        const auto& board = puzzleNode->getBoard();
        int manhattan = 0;

        // Calculate Manhattan distance for each tile
        for (int i = 0; i < 9; i++) {
            if (board[i] == 0) continue;
            int targetRow = (board[i] - 1) / 3;
            int targetCol = (board[i] - 1) % 3;
            int currentRow = i / 3;
            int currentCol = i % 3;
            manhattan += std::abs(targetRow - currentRow) + std::abs(targetCol - currentCol);
        }

        // Add depth to break ties
        auto trans = puzzleNode->storedData();
        int depth = trans ? trans->depth : 0;

        puzzleNode->setScore(manhattan + depth * 0.001);
    }
};




// Solution class
class Solution {
public:
    Solution(std::shared_ptr<INode> initial, std::shared_ptr<INode> goal, bool success = true)
        : initialNode(initial), goalNode(goal), isSuccess(success) {
    }

    std::shared_ptr<INode> initialNode;
    std::shared_ptr<INode> goalNode;
    bool isSuccess;
};

// Main search function
class SearchSolution {
private:
    std::shared_ptr<IScoringFunction> scoringFunction;

public:
    SearchSolution(std::shared_ptr<IScoringFunction> scorer) : scoringFunction(scorer) {}

    Solution search(std::shared_ptr<INode> initial, std::shared_ptr<INode> goal) {
        // Priority queue for open set
        auto compareNodes = [](std::shared_ptr<INode> a, std::shared_ptr<INode> b) {
            return a->score() > b->score();
            };
        std::priority_queue<std::shared_ptr<INode>,
            std::vector<std::shared_ptr<INode>>,
            decltype(compareNodes)> open(compareNodes);

        // Initialize with initial state
        auto copy = initial->copy();
        scoringFunction->score(copy);
        open.push(copy);

        // Hash set for closed set
        std::unordered_set<std::shared_ptr<INode>> closed;

        while (!open.empty()) {
            // Remove node with lowest score
            auto n = open.top();
            open.pop();
            closed.insert(n);

            // Check if goal state reached
            if (n->equals(goal)) {
                return Solution(initial, n);
            }

            // Calculate successor moves
            auto trans = n->storedData();
            int depth = 1;
            if (trans) {
                depth = trans->depth + 1;
            }

            auto moves = n->validMoves();
            for (auto& move : moves) {
                // Make move and evaluate new state
                auto successor = n->copy();
                move->execute(successor);

                // Store transition data
                successor->storedData(std::make_shared<DepthTransition>(move, n, depth));
                scoringFunction->score(successor);

                // Check if state was previously visited
                auto it = closed.find(successor);
                if (it != closed.end()) {
                    if (successor->score() >= (*it)->score()) {
                        continue;
                    }
                    closed.erase(it);
                }

                // Add to open set
                open.push(successor);
            }
        }

        // No solution found
        return Solution(initial, goal, false);
    }
};

int main() {
    // Create initial state (example: 8-puzzle)
    std::vector<int> initialBoard = { 1, 2, 3, 4, 0, 6, 7, 5, 8 };  // 0 represents empty space
    std::vector<int> goalBoard = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };

    auto initial = std::make_shared<PuzzleNode>(initialBoard);
    auto goal = std::make_shared<PuzzleNode>(goalBoard);

    // Create scorer and search solver
    auto scorer = std::make_shared<ManhattanScorer>();
    auto searchSolver = SearchSolution(scorer);

    // Find solution
    Solution solution = searchSolver.search(initial, goal);

    if (solution.isSuccess) {
        std::cout << "Solution found!\n";

        // Reconstruct path
        std::vector<std::shared_ptr<INode>> path;
        auto current = solution.goalNode;
        while (current) {
            path.push_back(current);
            auto trans = current->storedData();
            if (!trans) break;
            current = trans->previousNode;
        }

        // Print solution path
        std::cout << "Number of moves: " << path.size() - 1 << "\n";
        std::cout << "Path from goal to start:\n";
        for (const auto& node : path) {
            auto puzzleNode = std::dynamic_pointer_cast<PuzzleNode>(node);
            if (!puzzleNode) continue;

            const auto& board = puzzleNode->getBoard();
            for (int i = 0; i < 9; i++) {
                std::cout << board[i] << " ";
                if (i % 3 == 2) std::cout << "\n";
            }
            std::cout << "---\n";
        }
    }
    else {
        std::cout << "No solution exists.\n";
    }

    return 0;
}

五、算法优化

有一些算法使用了双向搜索（Kaindl和Kainz，1997），而不仅仅是从初始状态向前搜索。一开始这种方法由于不能工作，被早期的AI研究人员放弃，Kaindl和Kainz提出了强有力的理由，认为这种方法应该被重新考虑。
一种广为人知的A搜索变种叫做迭代加深A(IDA*)，由Korf（1985）提出。它依赖于一系列逐渐扩展的有限制的深度优先搜索。对于每次后继迭代，搜索深度限制都会在前次的基础上增加。
IDA比单独的深度优先搜索或者广度优先搜索要高效得多，因为每次计算出的开销值都是基于实际的走法序列而不是启发式函数的估计。Korf（2000）描述了高效的启发式信息是如何和IDA结合起来，用于解决十五数码问题，在整个搜索过程中，会对超过4亿个棋面状态进行评估。
Barr和Feigenbaum（1981）提出了一些改进方法，在不能高效地得到一个可接受的h*(n)函数时使用。
虽然A搜索产生了最小耗费的解，但是搜索空间可能会过大以至于无法继续计算。增强A搜索和处理这些巨大规模的问题的改进思想主要包括：

• 迭代加深
  这个策略重复迭代有深度限制的深度优先搜索，每次迭代都会增加深度限制。这种方法能够选择出在下次迭代中优先被处理的节点，因此减少了不必要的搜索，增加了快速收敛到获胜走法的可能性。同时，由于搜索空间被切分成离散的部分，实时算法能够在尽可能多的空间限制下，在时限内寻找到一个较优解。最先应用到A搜索算法的是Korf（1985），他发明了IDA。
• 转移表
  为了避免重复计算，程序员可以对局面状态进行散列，在一个转移表中存储路径长度。如果状态在后面的搜索中会出现，而且当前深度大于先前的深度，那么搜索将会终止。这种方法能够避免搜索一棵低效的子树。
• 层次化
  如果局面状态能够层次化地表示，那么我们可以重新构建一下搜索空间。层次化寻路A*（HPA*）就应用了这种方法（Botea等，2004）。
• 内存限制
  与其在计算时限制搜索空间，程序员可以执行一种“有损”搜索，在搜索的过程中舍弃一些节点，专注于搜索那些被认为和结果相关的区域。简化内存限制A*（SMA*）就是一个例子（Russel，1992）。

Reinefeld和Marsland（1994）总结了一系列的A的有趣的扩展。更多的在AI系统中使用A搜索的信息在教科书和大量的在线资源可以找到相关信息（Barr和Feigenbaum，1981）。
我们现在结束对搜索树的讨论。后面的算法都是基于博弈树的。

六、引用及参考文献

1.《算法设计手册》