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

10

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

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

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

DuttaA
источник
1
Примечание: я не мог придумать более подходящий стек для публикации этого вопроса. Я знаю, что детали реализации обычно не приветствуются в этом стеке.
DuttaA
2
imo это отличный вопрос для SE: AI, потому что речь идет не только о реализации, но и о самой концепции. Не говоря уже о том, что вопрос привлек 4 легальных ответа в течение нескольких часов. (Взял на себя смелость редактировать заголовок для поиска и создать тег BFS)
DukeZhou

Ответы:

8

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

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

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

  • set в Python
  • HashSet на Яве

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


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

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

Деннис Соемерс
источник
1
Я смогу это сделать, но время сравнения начнет увеличиваться в геометрической прогрессии
DuttaA
3
SО(1)S
1
@DuttaA Я добавил псевдокод, чтобы точно описать, как будет использоваться набор, надеюсь, это что-то прояснит. Обратите внимание, что мы никогда не перебираем весь цикл closed_set, его размер никогда не должен влиять на наше (асимптотическое) время вычислений.
Деннис Соемерс
1
На самом деле я делал это с использованием C ++. У меня нет ни малейшего представления о хешировании ... Думаю, сейчас я буду использовать python ... Спасибо за ответ
DuttaA
3
@DuttaA В C ++ вы, вероятно, захотите использовать std :: unordered_set
Деннис Соемерс
16

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

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

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

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

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

Джон Дусетт
источник
2
16!
@DennisSoemers правильно .. Вы тоже правильно .. Я просто пытался отточить свои навыки ... Я
перейду
Есть ли случаи, когда BFS может вернуть приемлемые локальные решения? (Я имею дело с более чем 81! * Tbd-value и width-first, кажется оптимальным в том смысле, что есть блокирующие факторы, которые можно легко пропустить без исчерпания. Сейчас мы не беспокоимся о действительно сильной игре, скорее "респектабельно" "слабая" общая производительность по множеству непредсказуемых топологий игровых
плат
2
@DukeZhou BFS обычно используется только тогда, когда ищется полное решение. Чтобы остановить это раньше, вам нужна функция, которая оценивает относительное качество различных частичных решений, но если у вас есть такая функция, вы можете просто использовать вместо нее A *!
Джон Дусетт
Вместо того чтобы говорить «количество ходов в игре», я бы рекомендовал «минимальное количество ходов, чтобы добраться до цели». Я думаю о количестве ходов в игре как о каждом шаге, который забирает вас из одного из 16! состояния к любому другому, что намного больше памяти, чем использует итеративное углубление.
NotThatGuy
7

Хотя приведенные ответы, как правило, верны, 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 )
  • Существует три основных подхода к сравнению состояний из предыдущих уровней, когда состояния хранятся на диске.
    • Первый основан на сортировке. Если вы сортируете два файла наследников, вы можете сканировать их в линейном порядке, чтобы найти дубликаты.
    • Второе основано на хэше. Если вы используете хеш-функцию для группировки наследников в файлы, вы можете загружать файлы, размер которых меньше полного пространства состояний, чтобы проверять наличие дубликатов. (Обратите внимание, что здесь есть две хеш-функции - одна для отправки состояния в файл и одна для разграничения состояний в этом файле.)
    • Третье - структурированное обнаружение дубликатов. Это форма обнаружения на основе хеш-функции, но она выполняется таким образом, что дубликаты могут быть проверены сразу после их создания, а не после того, как все они были сгенерированы.

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

Натан С.
источник
Это отличный ответ .. но не для таких нубов, как я:) ... я не эксперт по программированию ..
DuttaA
Как неориентированный поможет вам избежать дубликатов в других слоях? Конечно, вы сможете вернуться к узлу в другом слое, переместив 3 плитки по кругу. Во всяком случае, направленный поможет вам избежать дубликатов, потому что это более ограничительный. Связанная статья говорит об обнаружении дубликатов, но не упоминает о ненаправленных или направленных вообще, и, кажется, не упоминает об избежании дубликатов на разных уровнях (но я мог бы пропустить это в моем очень кратком сканировании).
NotThatGuy
@NotThatGuy В неориентированном графе родитель и ребенок находятся на расстоянии не более 1 от глубины, в которой они находятся в BFS. Это потому, что как только один из них найден, ненаправленный край гарантирует, что другой будет найден сразу после этого. Но в ориентированном графе состояние на глубине 10 может генерировать дочерние элементы на глубине 2, потому что дочерний элемент на глубине 2 не должен иметь ребра обратно в другое состояние (это сделало бы его глубиной 3 вместо глубины 10) ,
Натан С.
@NotThatGuy Если вы перемещаете 3 плитки по кругу, вы создаете цикл, но BFS будет исследовать это в обоих направлениях одновременно, поэтому на самом деле вы не вернетесь к гораздо меньшей глубине. Полная скользящая плитка 3х2
Натан С.
1
обалденный. Добро пожаловать в SE: AI!
DukeZhou
3

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

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

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

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

Корт Аммон
источник
2

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

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

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

Мануэль Родригес
источник
1

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

16!

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

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

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

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

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

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

Резюме

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

FauChristian
источник