Методы поиска ИИ для головоломки "Раздвижные 8 плиток"

Введение

Программа принимает на вход начальное состояние головоломки из 8 плиток, затем выбирается один из 4 возможных алгоритмов поиска. Если выбранный алгоритм использует эвристическую функцию, эта функция может быть либо манхэттенским расстоянием, либо количеством неуместных плиток. После завершения поиска программа выводит:

  • План (перечень действий в правильной последовательности).
  • Длина плана.
  • Количество сгенерированных уникальных состояний.
  • Время, затраченное на поиск решения.
  • Доска от начального состояния до целевого состояния после каждого действия.
  • Если план является действительным или недействительным планом.

В следующем разделе будет показано, как всего вышеперечисленного удалось достичь.

Реализация

Во-первых, пустая плитка представлена ​​«0». Доска/состояние представлены массивом из 9 целых чисел. Состояние цели постоянно и сохраняется в переменной targetState = [1,2,3,4,5,6,7,8,0]. Исходное состояние получается от пользователя функцией getInput(). getInput() просит пользователя ввести строку, представляющую начальную поверхность доски. Затем ввод помещается в массив. Пример «8 6 7 2 5 4 3 0 1» будет сохранен как [8,6,7,2,5,4,3,0,1].

Из каждого состояния есть определенные действия, которые применимы. Возможны 4 действия: Влево, Вправо, Вверх, Вниз. Было бы полезно, если бы существовала функция, которая проверяет, какие действия доступны из данного состояния. availableActions(puzzle) делает именно это. Он проверяет, где находится пустая плитка, и предварительные условия каждого действия. Функция возвращает массив из 4 логических значений. Важно отметить, что [0] -> Влево, [1] -> Вправо, [2] -> Вверх и [3] -> Вниз. Функция swap(actual, action) применяет действие, заменяя пустую плитку соседней.

В автоматизированном планировании алгоритм поиска начинается с начального узла (корня) и находит путь к целевому узлу, расширяя ветви от узлов. Следовательно, необходимость реализации объекта типа «дерево» очевидна. В классе StateTree() узел определяется как объект, имеющий:

  • состояние (массив из 9 целых чисел)
  • Список детей
  • Список действий. Эти действия, если их применить из начального состояния, приведут к этому состоянию.
  • Переменная, которая отслеживает, сколько дочерних элементов имеет состояние.

Класс узла имеет функцию addChild(self, state, action). Эта функция добавляет объект типа node в список дочерних элементов текущего узла. Однако в каждой функции поиска addNodes(node) используется для создания возможных дочерних элементов из текущего узла. Эта функция получит доступные действия и применит их одно за другим для создания новых состояний и добавления их в список дочерних элементов текущего узла.

Как были реализованы различные стратегии поиска.

Теперь, когда есть понимание того, как представлены узлы, давайте посмотрим, как строились алгоритмы поиска.

Реализованы 4 алгоритма поиска:

  1. Поиск в ширину
  2. Жадный лучший первый поиск
  3. Поиск
  4. Принудительное восхождение на холм

1. BFS — это простой алгоритм слепого поиска, который расширяет каждый узел слой за слоем (сначала в ширину), пока не будет достигнут целевой узел. Первоначально начальное состояние помещается в очередь/список toVisit. Чтобы избежать циклов или циклов, UniqueStates будет хранить список уникальных посещенных состояний. Создается цикл while, внутри цикла повторяется следующая процедура:

  • Первое значение в списке toVisit выталкивается, и это текущий узел для расширения.
  • Проверьте, является ли узел целевым узлом. Если это конециначе:
  • Разверните узел, добавив дочерние элементы, используя addNodes (узел)
  • Для каждого дочернего узла проверьте, не приводит ли он к необнаруженному состоянию, если да, добавьте в список toVisit и список UniqueStates.

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

Прежде чем описывать остальные 3 алгоритма, сначала необходимо понять эвристику. Эвристика может быть:

  1. Количество неуместных плиток
  2. или, Манхэттенское расстояние

misplacedTiles(puzzle) с учетом функции состояния возвращает количество плиток в неправильном положении. Он делает это, проверяя, находятся ли элементы массива в индексах состояния целей.

Manhatten_Distance(puzzle) дает эвристическое значение, перемещая mhd всех плиток на их правильные позиции и возвращая сумму. mhd() обрабатывает отдельные значения, получая координаты (x,y) плитки и правильное местоположение плитки, а затем вычисляет разницу.

2. Жадный поиск лучшего первого начинается с начального узла и выбирает узел, который имеет наилучшее эвристическое значение, этот узел расширяется, и процесс повторяется. Узлы хранятся в списке под названием «найти», который состоит из словарей типа {«узел»: X, «приоритет»: h}. Таким образом, легко сравнивать эвристические значения различных узлов. Создается цикл while, внутри цикла повторяется следующая процедура:

  • Найдите индекс узла с наименьшим (лучшим) эвристическим значением в поиске. Это будет узел для расширения. Также удалите его из списка.
  • Проверьте, является ли узел целевым узлом. Если это конециначе:
  • Разверните узел, добавив дочерние элементы, используя addNodes (узел)
  • Для каждого дочернего узла проверьте, не приводит ли он к необнаруженному состоянию, если да: проработайте эвристику и добавьте в список поиска и список UniqueStates.

3. A* начинается с начального узла и, аналогично GBFS, выбирает узел с лучшей эвристической функцией, но в A* она состоит из суммы эвристики и стоимости. То есть f(n) = h+c. c - стоимость пребывания в текущем узле. Какие шаги необходимо предпринять, чтобы добраться до текущего узла от root. Это можно легко найти, найдя длину его плана. Остальные функции такие же, как и раньше.

4. Принудительное восхождение на холм начинается с начального узла и расходует узлы в стиле BFS, однако, когда обнаруживается узел с лучшей эвристикой, OpenList отбрасывается и добавляется только этот узел. В реализации управляются три разных списка: лучшие, состояния, посещенные. best отслеживает посещаемые узлы, state отслеживает все уникальные уже просмотренные и посещенные узлы, отслеживает все уже развернутые узлы. Переменная H отслеживает лучшую эвристику, которую когда-либо видели. Если при расширении узла ни один из дочерних узлов не имеет лучшей эвристики, то все они добавляются в лучший список. Однако, если один из них имеет лучшую эвристику, то лучший список отбрасывается, H обновляется и к нему добавляется дочерний узел.

Результаты и оценка

Результаты для следующих двух начальных состояний.

Время, затраченное на поиск

Из этих графиков можно заметить, что наиболее эффективным (с точки зрения скорости) является жадный поиск наилучших результатов, а худшим — поиск в ширину. Это то, что ожидалось, поскольку BFS расширяет все возможные уникальные комбинации от начального узла независимо от их эвристики (слепой/неинформированный поиск) до тех пор, пока не будет достигнуто целевое состояние. Напротив, жадный поиск наилучшего первого поиска начинается с начального узла и всегда расширяет узел, имеющий наилучшее эвристическое значение, до тех пор, пока не будет достигнут целевой узел. Таким образом, решение обычно находится быстро. Важно также отметить, что A* занял больше времени, чем GBFS и Enforced Hill Climb, это также ожидалось, поскольку A* всегда будет сходиться к оптимальному решению, которое обычно найти «труднее», чем любое решение.

Уникальные состояния, изученные поиском

Понимание созданных состояний

Поскольку алгоритмы никогда не застревают в петлях или циклах, существует сильная положительная корреляция между временем, затрачиваемым на выполнение, и генерируемыми состояниями. Поэтому нет необходимости подробно останавливаться на этих результатах. (То же рассуждение, что и при просмотре графиков затраченного времени, которые уже обсуждались выше)

Продолжительность планов

Из приведенного выше графика следует важное наблюдение: никакой другой метод поиска не имеет более короткого (лучшего) плана, чем A*. Так же как и BFS, эти два алгоритма поиска найдут оптимальное решение. (Примечание: BFS не показана на графике, так как для запуска потребовалось более 15 минут). Принудительный поиск Hill Climbing в среднем возвращает самый длинный план. Это неудивительно из-за того, что он попытается расширить лучший эвристически оцененный дочерний элемент узла (следовательно, добавив шаг (действие к шагу)).

Вывод из графиков

Важные выводы о производительности каждой из стратегий поиска. Оптимальными решениями, то есть алгоритмом, который всегда возвращает кратчайший путь, являются BFS и A*. Из этих двух стратегий становится ясно, что A* является лучшим вариантом с точки зрения эффективности. Поскольку, как видно из приведенных выше графиков, A* удается найти план за гораздо меньшее время и путем расширения/исследования значительно меньшего количества состояний. Это в основном связано с тем, что A * является алгоритмом информированного поиска, в то время как BFS не использует функцию эвристики/оценки (следовательно, слепой). Однако может случиться так, что проблема разрешима при любом решаемом плане. Здесь у жадного поиска наилучшего первого поиска и принудительного поиска подъема есть свои преимущества по сравнению с BFS и A*. Эти две стратегии поиска (GBFS и EHCS) значительно быстрее вычисляются и требуют меньше памяти для работы, так как посещают меньше состояний. В ситуациях, когда время имеет решающее значение, эти стратегии могут быть выбраны.

Другой ключевой частью, которая делает алгоритм поиска быстрым и эффективным, является используемая эвристика. Из приведенных выше результатов видно четкое различие между использованием манхэттенского расстояния в качестве эвристики и использованием неуместных плиток в качестве эвристики. Для решения той же проблемы, несмотря на выбранный алгоритм поиска, использование Mhd в качестве эвристики оказалось более эффективным с точки зрения как времени, так и исследуемых состояний. Следовательно, можно сделать вывод, что манхэттенское расстояние является лучшим представлением того, насколько близко / (далеко) текущее состояние от целевого состояния в головоломке из 8 плиток. Другая причина, по которой Mhd является лучшей эвристикой для неуместных плиток, может заключаться в том, что, поскольку алгоритмы поиска пытаются найти лучший узел со значением h, диапазон значений, предлагаемых mhd, больше, чем у неуместных плиток (0–8). Следовательно, при использовании неуместных плиток в качестве эвристики алгоритм сталкивается с гораздо большим количеством случаев, когда ему приходится выбирать между узлами с одинаковыми значениями h.