c - 找出最佳优先搜索的评估函数

Question

在运行来自 M Tim Jones 的人工智能:系统方法 的最佳优先搜索时，我们被要求确定下一步行动是如何生成的以及选择解决方案的原因。 p>

为了做到这一点，有两个代码部分难倒了我们:

#define checkPiece( board, y )((board & (1 << (15-y))) ? 1 : 0)

#define MAX_TESTS   14
#define MAX_VECTOR  4

typedef struct {
    unsigned char len;
    unsigned char vector[MAX_VECTOR];
} test_t;

和

const test_t tests[MAX_TESTS]={
                            { 4, { 0,  4, 8,  12 } },
                            { 4, { 1,  5, 9,  13 } },
                            { 4, { 2,  6, 10, 14 } },
                            { 4, { 3,  7, 11, 15 } },
                            { 2, { 8, 13 } },
                            { 3, { 4,  9, 14 } },
                            { 4, { 0,  5, 10, 15 } },
                            { 3, { 1,  6, 11 } },
                            { 2, { 2,  7 } },
                            { 2, { 1,  4 } },
                            { 3, { 2,  5,  8 } },
                            { 4, { 3,  6,  9, 12 } },
                            { 3, { 7, 10, 13 } },
                            { 2, { 11, 14 } } 
                          };

这两个都用在 EvaluateBoard 函数中

void evaluateBoard( node_t *node_p ) {
    int test, i, check;
    int cost = 0;

    for (test = 0 ; test < MAX_TESTS ; test++) {

        check = 0;

        for (i = 0 ; i < tests[test].len ; i++) {
            check += checkPiece( node_p->board, tests[test].vector[i] );
        }

        if (check > 1) cost+= (check-1);
    }

 node_p->g = cost;

  printf(" evaluateBoard %04x = (h %d, g %d)\n", 
       node_p->board, node_p->h, node_p->g);

  return;
}

下一步行动由 Cost int 决定，并且是 checkPiece 结果的结果。在本例中，board== 1288，但是如何从 test_t 测试 中选择 y 值？

另外，test_t tests 的结构是什么？我们从未在 C 代码中看到任何类似的东西。是多维数组的一种形式吗？

Answer 1

test_t 是一个结构体。代码的作者正在用一组初始化结构初始化测试数组。在 C 中，您可以像这样初始化一个结构；

struct t {
     int num1;
     double num2;
};

struct t my_struct = { 123, 3.141 };

如果我想初始化一个 struct t 的数组，那么我可以这样做:

struct t my_array[] = {
    {123, 3.141},
    {3245, 6.2156},
    {912, 5.3},
    {0, 1.0}
};

对于 BFS 的东西，最佳优先搜索是一种纯粹的启发式组合搜索算法。这意味着在图表中的任何给定节点，您将选择最佳的后继节点。最优可能是成本最低或成本最高。 node_t 看起来像是支持 A*、BFS 和 Dijkstra 搜索算法的通用 C 结构。这就是 node_t 结构的 h 成员变量被忽略的原因——它没有在 BFS 中使用。

evaluateBoard() 正在通过整个测试列表评估 node_t 位置的成本。未选择 y 值，您只是评估节点的成本，以便稍后您可以在算法中选择最佳的后继移动。