Выяснение функции оценщика для поиска в первую очередь

Question

Выполняя поиск в первую очередь от 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. В этом случае board == 1288, но как выбрать значение y из test_t tests?

Кроме того, какова структура test_t tests? Мы никогда не видели ничего подобного в C-коде. Это форма многомерного массива?

Answer 1

Кроме того, какова структура test_t tests?

tests определяется как массив struct test_t. Каждый из элементов, содержащихся в массиве, сам по себе содержит массив char s. Да, можно сказать, что это какой-то двумерный массив.

C (и C ++ 11) позволяет инициализировать структуры и массивы структур с помощью вложенных фигурных скобок, как в примере.

но как выбрать значение y из тестов test_t?

Значение y, необходимое в макросе checkPiece, является n-ным значением массива vector, который содержится в текущем struct test_t.

Answer 2

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 поиск Best first - это чисто эвристический алгоритм комбинаторного поиска. Это означает, что в любом данном узле вашего графика вы выберете наиболее подходящего преемника. Оптимальным может быть наименьшая стоимость или большая стоимость. node_t выглядит как общая структура C для поддержки алгоритмов поиска A *, BFS и Dijkstra. Вот почему переменная-член h структуры node_t игнорируется - она ​​не используется в BFS.

valuBoard () оценивает стоимость позиции node_t, просматривая весь список тестов. Значение y не выбрано, вы просто оцениваете стоимость узла, чтобы позже вы могли выбрать наиболее оптимальный ход преемника в алгоритме.