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

在运行M Tim Jones'人工智能：系统方法的最佳优先搜索时，我们被要求确定下一步如何生成以及解决方案的原因采摘。找出最佳优先搜索的评估函数

为了做到这一点，两个代码段绊倒我们：

#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结果的结果。在这种情况下，电路板== 1288，但是如何从test_t tests中选择y值？

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

来源

2011-09-08 Jason

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

struct t { 
    int num1; 
    double num2; 
}; 

struct t my_struct = { 123, 3.141 };

如果我想初始化结构T的数组，然后我可以做这样的事情：

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

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

evaluateBoard（）正在通过整个测试列表来评估node_t位置的成本。没有选择y值，您只是评估节点的成本，以便稍后您可以选择算法中最优化的后继移动。

来源

2011-09-08 15:30:15

顺便说一下，当我在游戏行业工作时，我对这个东西的工作非常熟悉。虽然，我还没有读过你正在使用的书。最好的第一个搜索是一个非常容易理解的算法。如果您有任何问题，如果您的书不适合您，我可以帮助您。 –

谢谢，这个解释帮了很大忙。 – Jason

另外，什么是结构test_t测试？

tests被定义为struct test_t的数组。阵列中包含的每个元素本身都包含一个数组char s。所以，你可以说它是某种二维数组。（和C++ 11）允许使用嵌套花括号初始化结构和结构数组，如同在示例中一样。

但是如何从test_t测试中选择y值？

在checkPiece万客隆所需的y值是vector阵列是本身包含在当前struct test_t的第n值。

来源

2011-09-08 15:33:24 Constantinius

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

回答

相关问题