Мне нужно написать программу, которая решит лабиринт. Лабиринт имеет графическую структуру, где каждый узел - какая-то комната, а ребра - выходит в другие комнаты:
Технические характеристики:
- Начнем со случайной комнаты.
- Лабиринт имеет тупики, 0 или несколько выходов.
- Мы ничего не знаем обо всем лабиринте, только номер текущей комнаты и список дверей из него.
- Когда мы входим в новую комнату, мы не знаем, откуда мы пришли (какая дверь из текущей комнаты ведет нас обратно в предыдущую комнату).
- Мы можем узнать, когда мы достигнем выхода.
- Каждый шаг мы перемещаемся из текущей комнаты в какую-то доступную дверь из нее.
- Например, если мы находимся в комнате 6, мы не можем просто начать прыгать. Это как движение робота.
- Мы точно знаем идентификатор текущей комнаты. Мы знаем ID каждой двери в текущей комнате (не во всех лабиринтах).
- Мы контролируем робот.
Я посмотрел все известные алгоритмы, но все они требуют, по крайней мере, дополнительные возможности, чтобы вернуться в предыдущую комнату. Согласно спецификации, мы не можем использовать любые алгоритмы, которые ищут кратчайший путь (на самом деле, мне не нужен кратчайший путь), потому что мы знаем только о текущей комнате. Мы не можем использовать левый (правый) алгоритм следования, потому что не знаем направления выхода. Вероятно, единственное решение, которое соответствует спецификации, - это выбор случайного выхода в каждой комнате в надежде, что будет найден какой-то временной выход ...
Любое предложение, как решить такой лабиринт в более умном способе?
Ответы:
Хм, вы знаете номер фактической комнаты. Таким образом, вы можете построить структуру данных. Я полагаю, что к списку выходов не привязаны номера комнат. Но, выбрав случайным образом, вы знаете, по крайней мере, что есть связь.
Допустим, вы находитесь в комнате 4 и выберите один из трех случайных выходов. Теперь система сообщает вам, что вы находитесь в комнате 6 и у вас остался только один выход. Вы выбираете это и возвращаетесь в комнату 4. На данный момент вы собрали некоторую информацию о структуре лабиринта. Теперь вы выбираете другой выход и заканчиваете в комнате 5. Моя информация о комнате 4 (один выход в 6, один выход в 5)
Можете ли вы выбрать конкретный выход? они пронумерованы, скажем, если в комнате 4 вы выбираете выход, который всегда заканчивается 6? В противном случае вы по крайней мере можете узнать о возможных маршрутах.
Хорошо, просто прочитайте ваш комментарий. Поэтому, если у выходов есть идентификаторы, и они статически связаны с комнатой (даже если вы не знаете, какой из них для начала), вы просто выбираете новый и запоминаете соединения выхода / комнаты и помните, какой выход уже был опробован. Попробуйте не проверенные выходы, пока не обыщите каждую комнату.
Таким образом, это на самом деле просто. После нескольких шагов у вас должен быть более или менее полный список соединений. Только когда вы входите в новую комнату, вы можете (на несколько шагов) бегать вокруг случайно. Но с каждым шагом вы получаете больше информации, и всякий раз, когда вы заходите в ранее посещенную комнату, вы можете принять более разумное решение (не проверять тупиковую комнату 6 снова, например, когда вы возвращаетесь к 4, поскольку у нее нет выходов, которые не проверялись).
Редактировать Идея состоит в том, чтобы сначала сделать случайные шаги и записать информацию, которую вы найдете, как я описал (описание Дэна более сжато). Если вы оказались в комнате без неизвестных выходов, вы можете использовать любой известный указатель пути, чтобы найти кратчайший путь к комнате, у которой есть выходы, которые вы еще не исследовали.
Не уверен на 100%, но я думаю, что Питер Норвиг написал о подобной проблеме (лабиринт Wumpus) в своей книге «Искусственный интеллект: современный подход». Хотя, если я правильно помню, речь шла не столько о поиске пути, сколько о принятии решений относительно некоторой информации, которую система могла получить о соседних комнатах.
Редактировать:
Нет, это не только случайно. Отслеживая уже проверенные выходы, вы удаляете ненужную избыточность. На самом деле вам даже не нужно выбирать случайно.
Предположим, вы начинаете в комнате 4. Информация, которую вы получаете: 3 выхода A, B, C. Вы всегда выбираете первый, который теперь не используется, выход. Итак, начните с A. Вы заканчиваете в комнате 6. Теперь вы помните 4A => 6 (и использовали) в комнате 6, вы получаете информацию 1, выход A. Снова вы выбираете первый неиспользованный (и в данном случае только выход) Назад в комнату. для знания 6A => 4 (и больше никаких выходов в комнате 6) Теперь вы выбираете следующий выход B и достигаете комнату 5 ...
Рано или поздно вы обыщите все комнаты таким образом. Но в систематическом вопросе.
Единственная причина, по которой вам понадобится найти путь, - это когда вы оказались в комнате, где все выходы уже исследованы. Тогда вы захотите найти прямой путь к следующей комнате с неисследованными выходами, чтобы продолжить поиск. Таким образом, основная хитрость заключается не в том, чтобы узнать, какой выход ведет в какую комнату (хотя это может быть полезно), а в том, чтобы отслеживать еще не опробованные выходы.
Таким образом, например, вы можете избежать постоянного бега по кругу, что может привести к риску чисто случайного подхода.
В вашем примере лабиринт это, скорее всего, не имеет большого значения. Но в большом лабиринте с множеством комнат и подключений и, возможно, хитроумными комнатами с круглой структурой эта система гарантирует, что вы найдете выход с как можно меньшим количеством испытаний.
(Я думаю, что это та же система, что и Byte56 в Gamers)
источник
Я понимаю, что вы, вероятно, получили суть из других ответов, но это был забавный вопрос, и я захотел немного поработать над Python. Это мой объектно-ориентированный подход. Отступ определяет область видимости.
Графическое представление
Граф может быть легко хранится в виде ключа, значение словаря, где ключ является идентификатором номера, а значение представляет собой массив номеров это приводит к.
Интерфейс агента
Сначала мы должны подумать, какую информацию агент должен уметь извлекать из среды, и какие операции он должен уметь выполнять. Это позволит упростить мышление об алгоритме.
В этом случае агент должен иметь возможность запрашивать у среды идентификатор комнаты, в которой он находится, он должен иметь возможность получить количество дверей в комнате, в которой он находится ( обратите внимание, что это не идентификаторы комнат, в которых он находится). двери ведут к! ) и он должен быть в состоянии пройти через дверь, указав указатель двери. Все, что знает агент, должно быть выяснено самим агентом.
Знание Агент
Когда агент впервые входит в карту, он знает только количество дверей в комнате и идентификатор комнаты, в которой он находится в настоящее время. Мне нужно было создать структуру, которая будет хранить информацию, которую агент узнал, например, какие двери у него не было. через, и где двери, ведущие к тому, был через.
Этот класс представляет информацию об одной комнате. Я решил хранить не посещенные двери как a
set
и посещенные двери как adictionary
, где ключ - это идентификатор двери, а значение - это идентификатор комнаты, в которую он ведет.Агентный алгоритм
Каждый раз, когда агент входит в комнату, он ищет в своем словаре знаний информацию о комнате. Если для этой комнаты нет записей, она создает новую
RoomKnowledge
и добавляет ее в свой словарь знаний.Он проверяет, является ли текущая комната целевой комнатой, и если да, то возвращается.
Если в этой комнате есть двери, которые мы не посещали, мы проходим через дверь и храним там, куда она ведет. Затем мы продолжим цикл.
Если не было не посещенных дверей, мы возвращаемся в комнаты, которые посетили, чтобы найти дверь с не посещенными дверями.
В
Agent
класс наследует отAgentInterface
класса.Вспомогательные функции
Мне пришлось написать функцию, которая бы находила ключ в словаре с заданным значением, поскольку при возврате мы знаем идентификатор комнаты, в которую мы пытаемся попасть, а не какую дверь использовать для доступа к ней.
тестирование
Я проверил все комбинации начальной / конечной позиции на карте, приведенной выше. Для каждой комбинации распечатывает посещенные комнаты.
Заметки
Возврат не очень эффективен - в худшем случае он может пройти через каждую комнату, чтобы попасть в соседнюю комнату, но откат довольно редко - в приведенных выше тестах откат только три раза. Я избегал включать обработку исключений, чтобы сохранить код кратким. Любые комментарии по моему Python приветствуются :)
источник
По сути, у вас есть диаграмма направленности, где каждая связанная комната соединена двумя неизвестными проходами - по одному в любом направлении. Допустим , вы начинаете в узле
1
, а двериA
иB
вывести. Вы не знаете , что лежит за каждой дверью, так что вы просто выбрать дверьA
. Вы получаете в комнату2
, которая имеет двериC
,D
иE
. Теперь вы знаете , что дверьA
ведет из комнаты1
в комнату2
, но вы не знаете , как получить обратно, так что вы случайно выбрать дверьC
. Вы получаете обратно в комнату1
! Теперь вы знаете , как получить от комнаты1
и2
. Продолжайте исследовать через ближайшую неизвестную дверь, пока не найдете выход!источник
Так как комнаты всегда находятся в одном и том же порядке в списках выхода, мы можем быстро составить карту комнат, ища выход.
Мой псевдокод несколько Javaish, извините, я использую его много в последнее время.
Unvisited_Rooms - это хэш-карта, содержащая идентификатор комнаты и список индексов неотображаемых комнат или массива 2d, что бы ни работало.
Я предполагаю, что алгоритм может пойти что-то вроде этого:
Вам нужно будет использовать один из общих искателей пути узлов к комнатам PathTo () через «карту». Надеюсь, это достаточно ясно, чтобы вы могли начать с чего-то.
источник
Я не слишком ясно понимаю ваши требования, но если разрешено следующее, это может быть простой алгоритм. Вероятно, ошибка там, тем более что он использует рекурсивную функцию. Кроме того, он проверяет, ведет ли дверь в комнату, из которой вы пришли, но я не знаю, как будет обрабатываться круговая дорожка из трех комнат, она может просто продолжать вращаться вечно в этих трех комнатах. Возможно, вам придется добавить историю, чтобы убедиться, что номер не проверен дважды. Но, прочитав ваше описание, это может быть запрещено.
[Edit] Добавлен 'id' к предыдущей проверке и обновлен, чтобы сделать объект более ориентированным.
источник
curRoom.doors <= 1
, Поэтому функция возвращает немедленно, зная , что он находится в тупике, но думая , что он уже исследовал полноту лабиринта.Короткий ответ - поиск в глубину с возвратом. Вы можете сделать ширину, если хотите, но ваш маленький робот будет намного больше ходить туда-сюда.
Конкретнее, предположим, что мы получили:
Чтобы найти выход, нам просто нужно:
Позвоните
escape()
с идентификатором стартовой комнаты, и робот переместится к выходу (по телефонуmoveTo()
).источник
escape(int startingRoom)
следует позвонитьescape(Stack<int> path)
if (path.contains(door)) continue;
нарушает его требования - агент на самом деле не знает, ведет ли дверь обратно в комнату, в которой он уже находился, если он не проходит через дверь.