Решающие огни для курса ИИ

Question

Итак, мне была дана следующая задача: Учитывая, что все огни в версии игры 5x5 включены, напишите алгоритм, используя лучший первый поиск UCS/A */BFS/Greedy, который находит решение.

Сначала я понял, что UCS будет ненужным, поскольку стоимость перехода из одного состояния в другое 1 (нажатие кнопки, переворачивающей себя и соседние). Так что я написал BFS вместо этого. Оказалось, что он работает слишком долго и заполняет очередь, хотя я обращал внимание на удаление родительских узлов, когда я закончил с ними, чтобы не переполнять память. Он будет работать около 5-6 минут, а затем сбой из-за памяти. Далее, я написал DFS (хотя он не упоминался как одна из возможностей), и он нашел решение через 123 секунды на глубине 15 (я использовал глубину вначале, потому что я знал, что существует решение на глубина 15).

Что мне сейчас интересно, я что-то упускаю? Есть ли хорошая эвристика, чтобы попытаться решить эту проблему, используя поиск A *? Я ничего не понял, когда речь идет об эвристике, потому что в этой проблеме нет ничего тривиального.

Большое спасибо. Заглядывая вперед к некоторой помощи от вас, ребята

Вот мой исходный код (я думаю, что это довольно просто следовать):

struct state 
{ 
    bool board[25]; 
    bool clicked[25]; 
    int cost; 
    int h; 
    struct state* from; 
}; 

int visited[1<<25]; 
int dx[5] = {0, 5, -5}; 
int MAX_DEPTH = 1<<30; 
bool found=false; 

struct state* MakeStartState() 
{ 
    struct state* noviCvor = new struct state(); 

    for(int i = 0; i < 25; i++) noviCvor->board[i] = false, noviCvor->clicked[i] = false; 
    noviCvor->cost = 0; 
    //h=... 
    noviCvor->from = NULL; 

    return noviCvor; 
}; 

struct state* MakeNextState(struct state* temp, int press_pos) 
{ 
    struct state* noviCvor = new struct state(); 

    for(int i = 0; i < 25; i++) noviCvor->board[i] = temp->board[i], noviCvor->clicked[i] = temp->clicked[i]; 
    noviCvor->clicked[press_pos] = true; 

    noviCvor->cost = temp->cost + 1; 
    //h=... 
    noviCvor->from = temp; 

    int temp_pos; 

    for(int k = 0; k < 3; k++) 
    { 
     temp_pos = press_pos + dx[k]; 

     if(temp_pos >= 0 && temp_pos < 25) 
     { 
      noviCvor->board[temp_pos] = !noviCvor->board[temp_pos]; 
     } 
    } 

    if(((press_pos+1) % 5 != 0) && (press_pos+1) < 25) 
     noviCvor->board[press_pos+1] = !noviCvor->board[press_pos+1]; 

    if((press_pos % 5 != 0) && (press_pos-1) >= 0) 
     noviCvor->board[press_pos-1] = !noviCvor->board[press_pos-1]; 

    return noviCvor; 
}; 

bool CheckFinalState(struct state* temp) 
{ 
    for(int i = 0; i < 25; i++) 
    { 
     if(!temp->board[i]) return false; 
    } 

    return true; 
} 

int bijection_mapping(struct state* temp) 
{ 
    int temp_pow = 1; 
    int mapping = 0; 

    for(int i = 0; i < 25; i++) 
    { 
     if(temp->board[i]) 
      mapping+=temp_pow; 

     temp_pow*=2; 
    } 

    return mapping; 
} 

void BFS() 
{ 
    queue<struct state*> Q; 

    struct state* start = MakeStartState(); 
    Q.push(start); 
    struct state* temp; 
    visited[ bijection_mapping(start) ] = 1; 

    while(!Q.empty()) 
    { 
     temp = Q.front(); 
     Q.pop(); 
     visited[ bijection_mapping(temp) ] = 2; 

     for(int i = 0; i < 25; i++) 
     { 
      if(!temp->clicked[i]) 
      { 
       struct state* next = MakeNextState(temp, i); 
       int mapa = bijection_mapping(next); 

       if(visited[ mapa ] == 0) 
       { 
        if(CheckFinalState(next)) 
        { 
         printf("NADJENO RESENJE\n"); 
         exit(0); 
        } 
        visited[ mapa ] = 1; 
        Q.push(next); 
       } 
      } 
     } 

     delete temp; 
    } 
} 

PS. Поскольку я больше не использую карту (перешел на массив) для посещенных состояний, мое решение DFS улучшилось с 123 секунд до 54 секунд, но BFS все еще сбой.

Answer 1

Прежде всего, вы, возможно, уже знаете, что в Lights Out вам никогда не придется переворачивать один и тот же переключатель более одного раза, и неважно, в каком порядке вы переворачиваете переключатели. Таким образом, вы можете описать текущее состояние двумя различными способами: либо с точки зрения включения огней, либо с точки зрения переключения переключателей. Последний, вместе со стартовой схемой огней, дает вам первый.

Чтобы использовать алгоритм поиска графа для решения проблемы, вам нужно понятие смежности. Это легче следует из второй характеристики: два состояния смежны, если имеется ровно один переключатель, о котором они отличаются. Эта характеристика также напрямую кодирует длину пути к каждому узлу (= количество переключенных переключателей) и уменьшает количество последующих ходов, которые необходимо учитывать для каждого рассматриваемого состояния, поскольку все возможные пути к каждому узлу закодированы в схеме переключателей.

Вы можете использовать это в поиске по ширине относительно легко (и это может быть то, что вы на самом деле пытались). BFS эквивалентен алгоритму Дейкстры в этом случае, даже без использования явной очереди приоритетов, поскольку вы устанавливаете новые узлы для поиска в порядке приоритета (длины пути).

Вы также можете преобразовать это в поиск A * с добавлением подходящей эвристики. Например, поскольку каждый ход отключается не более чем на пять огней, можно принять за эвристику количество огней, которые все еще остаются после каждого хода, разделенные на 5. Хотя это немного грубо, я склонен думать, что это будет некоторая помощь. Однако вам нужна очередь приоритетов для этой альтернативы.

Что касается реализации, то признайте, что вы можете представить как шаблон текущих ламп, так и шаблон переключателей, которые были нажаты как битовые векторы. Каждый шаблон соответствует 32-битовому целому числу, а список посещенных состояний требует 2 бита , что вполне соответствует возможностям современных вычислительных систем.Даже если вы используете это множество байт, вместо этого вы должны быть в состоянии справиться с этим. Кроме того, вы можете выполнять все необходимые операции с помощью побитовых арифметических операторов, особенно XOR. Таким образом, эта задача (при ее заданном размере) должна быть вычислимой относительно быстро.

Update:

Как я уже говорил в комментариях, я решил решить эту проблему для себя, с - мне казалось, - очень хороший успех. Я использовал множество методов для достижения хорошей производительности и минимизации использования памяти, и в этом случае они в основном были взаимодополняющими. Вот некоторые из моих трюков:

• Я представлял каждое состояние всей системы, с одной uint64_t. Верхние 32 бита содержат битовую маску, из которых переключатели были перевернуты, а нижняя 32 содержит битовую маску, из которой в результате включены огни. Я завернул их в struct вместе с одним указателем, чтобы связать их вместе как элементы очереди. Данное состояние может быть проверено как решение с одним побитовым и операционным и одним целым сравнением.

• Я создал предварительно инициализированный массив из 25 uint64_t битмаски, представляющие эффект каждого движения. Один бит, установленный среди верхних 32 каждого, представляет переключатель, который перевернулся, и между 3 и 5 битами, установленными среди нижнего 32, представляют собой огни, которые в результате переключены. Эффект переключения одного коммутатора можно затем вычислить просто как new_state = old_state^move[i].

• Я реализовал простой поиск в ширину вместо А *, отчасти потому, что я пытался поставить что-то вместе быстро, и, в частности, потому, что, как я мог бы использовать регулярные очереди вместо приоритетной очереди.

• Я структурировал свою BFS таким образом, что, естественно, избегал посещать одно и то же состояние дважды, не имея на самом деле трек, в котором государства когда-либо были выставлены в очередь. Это было основано на некотором понимании того, как эффективно генерировать отдельные битовые шаблоны без повторения, причем те, у которых меньше бит, сгенерированных до тех, у кого больше бит. Последний критерий удовлетворительно удовлетворительно соответствовал подходу, основанному на очереди, который требуется в любом случае для BFS.

• Я использовал вторую (обычную) очередь для переустановки динамически распределенных узлов очереди после их удаления из основной очереди, чтобы минимизировать число вызовов до malloc().

Полный код был немного меньше, чем 200 строк, включая пустую и строку комментариев, заявления типа данных, ввод/вывод, реализация очереди (обычный C, без STL) - все.

Обратите внимание, что приоритетная очередь, используемая в стандартном Dijkstra и в A *, составляет в основном около , нахо дия правильный ответ (кратчайший путь) и только второстепенно о том, чтобы делать это эффективно. Запуск и удаление очереди из стандартной очереди могут быть как O(1), тогда как операции с приоритетной очередью - o(log m) в количестве элементов в очереди. A * и BFS имеют наивысшую оценку верхнего предела очереди O(n) в общем числе состояний. Таким образом, BFS будет масштабироваться лучше, чем A * с размером проблемы; вопрос только в том, действительно ли первый надежно дает вам правильный ответ, который в этом случае он делает.