Отслеживание посещенных состояний в поиске в ширину

Поэтому я пытался реализовать BFS для головоломки Sliding Blocks (тип числа). Теперь главное, что я заметил: если у вас есть 4*4доска, количество состояний может быть таким большим, что 16!я не могу заранее перечислить все состояния.

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

Я искал в сети и, по-видимому, они не возвращаются к только что завершенному предыдущему шагу, НО мы можем вернуться к предыдущему шагу и другим маршрутом, а затем снова пересчитать все шаги, которые были ранее посещены. Так как же отслеживать посещенные государства, когда все государства еще не перечислены? (сравнение уже существующих состояний с настоящим шагом будет дорогостоящим).

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

• вставка элементов
• тестирование, если элементы уже там

Практически каждый язык программирования уже должен иметь поддержку структуры данных, которая может выполнять обе эти операции за постоянное ( ) время. Например:$O(1)$

• set в Python
• HashSet на Яве

На первый взгляд может показаться, что добавление всех состояний, которые вы когда-либо видите, к набору, будет дорогим с точки зрения памяти, но это не так уж плохо по сравнению с памятью, которая вам уже нужна для вашей границы; если ваш коэффициент ветвления равен , ваша граница будет расти на элемент на узел, который вы посещаете (удалите узел с границы, чтобы "посетить" его, добавьте новых наследников / потомков), тогда как ваш набор будет расти только на лишний узел на посещаемый узел.б - 1 1 б $b$$b - 1$$1$$b$$1$

В псевдокоде такой набор (назовем его так closed_set, чтобы он соответствовал псевдокоду в википедии), можно использовать в поиске в ширину следующим образом:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(некоторые варианты этого псевдокода тоже могут работать и быть более или менее эффективными в зависимости от ситуации; например, вы можете также взять closed_setвсе узлы, для которых вы уже добавили потомков, и затем полностью избежать generate_children()вызова если currentуже в closed_set.)

То, что я описал выше, будет стандартным способом решения этой проблемы. Интуитивно, я подозреваю, что другое «решение» могло бы состоять в том, чтобы всегда рандомизировать порядок нового списка состояний-преемников перед добавлением их к границе. Таким образом, вы не избежите проблемы случайного добавления состояний, которые вы ранее расширили до границы, но я думаю, что это должно значительно снизить риск застрять в бесконечных циклах.

Будьте осторожны : я не знаю ни одного формального анализа этого решения, которое доказывает, что оно всегда избегает бесконечных циклов. Если я попытаюсь «прогнать» это через мою голову, интуитивно, я подозреваю, что это должно работать, и это не требует дополнительной памяти. Хотя могут быть крайние случаи, о которых я сейчас не думаю, так что это также может просто не сработать, стандартное решение, описанное выше, будет более безопасной ставкой (за счет большего объема памяти).

Ответ Денниса Соемерса правильный: вы должны использовать HashSet или аналогичную структуру для отслеживания посещенных состояний в BFS Graph Search.

Тем не менее, это не совсем отвечает на ваш вопрос. Вы правы, что в худшем случае BFS потребует от вас хранить 16! узлы. Хотя время вставки и проверки в наборе будет равно O (1), вам все равно понадобится абсурдное количество памяти.

Чтобы это исправить, не используйте BFS . Это неразрешимо для всех, кроме самых простых проблем, потому что это требует времени и памяти , которые экспоненциально на расстоянии до ближайшего целевого состояния.

Гораздо более эффективный алгоритм памяти - итеративное углубление . Он обладает всеми желаемыми свойствами BFS, но использует только O (n) памяти, где n - количество ходов для достижения ближайшего решения. Это может занять некоторое время, но вы достигнете пределов памяти задолго до ограничений, связанных с процессором.

Более того, разработайте эвристику для конкретного домена и используйте поиск A * . Это должно потребовать, чтобы вы исследовали только очень небольшое количество узлов и позволили завершить поиск за что-то намного более близкое к линейному времени.

Хотя приведенные ответы, как правило, верны, BFS в 15-головоломке не только вполне выполним, это было сделано в 2005 году! Документ, описывающий подход, можно найти здесь:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Несколько ключевых моментов:

• Для этого требовалась внешняя память - то есть BFS использовала жесткий диск для хранения вместо оперативной памяти.
• На самом деле существует только 15! / 2 состояний, так как пространство состояний имеет два взаимно недоступных компонента.
• Это работает в головоломке со скользящей плиткой, потому что пространства состояний растут очень медленно от уровня к уровню. Это означает, что общий объем памяти, требуемый для любого уровня, намного меньше, чем полный размер пространства состояний. (Это контрастирует с пространством состояний, таким как кубик Рубика, где пространство состояний растет гораздо быстрее.)
• Поскольку головоломка со скользящей плиткой не направлена, вам нужно беспокоиться только о дубликатах в текущем или предыдущем слое. В направленном пространстве вы можете создавать дубликаты на любом предыдущем уровне поиска, что значительно усложняет задачу.
• В оригинальной работе Корфа (ссылка выше) они фактически не сохраняли результат поиска - поиск только вычислял, сколько состояний было на каждом уровне. Если вы хотите сохранить первые результаты, вам нужно что-то вроде WMBFS ( http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf )
• Существует три основных подхода к сравнению состояний из предыдущих уровней, когда состояния хранятся на диске.
  • Первый основан на сортировке. Если вы сортируете два файла наследников, вы можете сканировать их в линейном порядке, чтобы найти дубликаты.
  • Второе основано на хэше. Если вы используете хеш-функцию для группировки наследников в файлы, вы можете загружать файлы, размер которых меньше полного пространства состояний, чтобы проверять наличие дубликатов. (Обратите внимание, что здесь есть две хеш-функции - одна для отправки состояния в файл и одна для разграничения состояний в этом файле.)
  • Третье - структурированное обнаружение дубликатов. Это форма обнаружения на основе хеш-функции, но она выполняется таким образом, что дубликаты могут быть проверены сразу после их создания, а не после того, как все они были сгенерированы.

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

По иронии судьбы ответ «использовать любую систему, которую вы хотите». HashSet - это хорошая идея. Однако оказывается, что ваши опасения по поводу использования памяти необоснованны. BFS настолько плохо справляется с подобными проблемами, что решает эту проблему для вас.

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

Это означает, что при обработке последнего слоя вашей BFS в памяти должно быть не менее 16! / 3 состояний. Какой бы подход вы ни использовали, чтобы убедиться, что он помещается в память, будет достаточно для того, чтобы ваш ранее посещенный список также помещался в память.

Как уже отмечали другие, это не лучший алгоритм для использования. Используйте алгоритм, который лучше подходит для этой проблемы.

Задача с 15 головоломками разыгрывается на доске 4х4. Реализация этого в исходном коде выполняется пошагово. Во-первых, сам игровой движок должен быть запрограммирован. Это позволяет играть в игру человеком-оператором. Игра из 15 головоломок имеет только один свободный элемент, и над этим элементом выполняются действия. Движок игры принимает четыре возможные команды: влево, вправо, вверх и вниз. Другие действия не допускаются, и управлять игрой можно только с помощью этих инструкций.

Следующий слой для игры - GUI. Это очень важно, поскольку позволяет протестировать игровой движок и попытаться решить игру вручную. Кроме того, графический интерфейс важен, потому что мы должны выяснить потенциальную эвристику. И теперь мы можем говорить о самом ИИ. ИИ должен отправлять команды игровому движку (влево, вправо, вверх и вниз). Наивным подходом для решателя будет алгоритм поиска методом грубой силы, что означает, что ИИ посылает случайные команды, пока не будет достигнуто целевое состояние. Более продвинутая идея заключается в реализации некоторой базы данных шаблонов, которая уменьшает пространство состояний. Поиск в ширину - это не эвристика, а начало. Это равносильно созданию графика для проверки возможных движений в хронологическом порядке.

Отслеживание существующих состояний может быть выполнено с помощью графика. Каждое состояние является узлом, имеет идентификатор и родительский идентификатор. ИИ может добавлять и удалять узлы на графике, а планировщик может решать график для нахождения пути к цели. С точки зрения программирования, игровой движок из 15 головоломок является объектом, а список многих объектов - массивом. Они хранятся в графовом классе. Осознать это в исходном коде немного сложно, обычно первая пробная версия заканчивается неудачей, и проект выдаст много ошибок. Чтобы управлять сложностью, такой проект обычно делается в академическом проекте, то есть это тема для написания статьи о нем, которая может иметь 100 страниц и более.

Подходы к игре

$16!$

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

Подпоследовательность Спуск

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

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

Хотя блоки могут временно отойти от своих пунктов назначения, чтобы поддержать стратегию завершения, требующую последовательности ходов, редко бывает, когда такая стратегия превышает восемь ходов, генерируя, в среднем, 5 184 перестановки, для которых можно сравнить конечные состояния используя функцию несоответствия выше.

Если пустое пространство и позиции блоков с 1 по 15 кодируются как массив кусочков, требуются только операции сложения, вычитания и побитового кодирования, что делает алгоритм быстрым. Повторение восьми стратегий перебора грубой силы может повторяться до тех пор, пока неравенство не упадет до нуля.

Резюме

Этот алгоритм не может циклически повторяться, потому что всегда есть хотя бы одна перестановка из восьми ходов, которая уменьшает диспаратность, независимо от начального состояния, за исключением начального состояния, которое уже завершено.