Алгоритм построения графа, заданный бесконечным ходом

Question

Мне нужна помощь при написании алгоритма упругого преобразования (построения графика). Вот проблема:

Представьте, что у вас есть текстовая виртуальная реальность (TORG/MUD), где вы можете отправлять команды перемещения (n, s, w, e, вверх, вниз, в, из ... и т. Д.), через telnet для перемещения вашего персонажа из комнаты в комнату. И сервер отправляет соответствующее описание комнаты после каждого шага движения. Ваша задача состоит в том, чтобы сгенерировать граф, который представляет основную структуру карты, чтобы вы могли просто сделать DFS на стороне клиента, чтобы выяснить, как добраться из одной комнаты в другую. Кроме того, вы хотите, чтобы спроектировать систему так, чтобы вход минимум пользователя требуется

Вот предположения:

• Основная топология графа на сервере никогда не изменится.

• Описание номеров не уникально. Большинство номеров имеют различные описания, но некоторые номера имеют то же самое описание. Описание комнаты меняются несколько раз в то время (дни или недели)

• Ваше движение может произойти случайным образом с небольшой вероятностью, и вы получите сообщение об ошибке вместо нового описания комнаты, например «Вы остановитесь, чтобы подождать для прохождения вагона »,« Дверь заперта », и ваш персонаж все еще будет в текущей комнате.

• Вы не можете взять единичное расстояние для каждого движения. Например, у вас может быть топология, подобная той, что показана ниже, поэтому, если предположить, что расстояние в одной комнате для каждой соседней комнаты и назначить жесткую координату для каждой комнаты, это не сработает. Однако вы можете предположить, что относительное направление должно быть последовательным, то есть не будет петли в топологическом виде вдоль X (запад, восток) и Y (юг, север).

• Цель: при назначении адресата, который вы посетили ранее, алгоритм гарантирует, что в конечном итоге переместит вас в это место, и в большинстве случаев найдет самый короткий путь. Ошибки допускаются, но алгоритм должен иметь возможность обнаруживать и исправлять ошибки «на лету».

Пример граф:

A--B---B 
|  | <- k 
C--D-E-F 

Я уже реализован очень простое решение, которое было бы записать описание комнаты и построить график. Ниже приведен пример представления графа, который моя программа генерирует в json. «Выходы» - это направление движения, отображаемое на идентификатор узла. -1 представляет собой не отображаемую комнату. Если пользователь идет в направлении и обнаруживает -1 в представлении графика, алгоритм попытается найти узлы, уже находящиеся на графике. Если узлы с тем же описанием будут найдены, он предложит пользователю решить, является ли вновь увиденное помещение одним из старых узлов. Если нет, он добавляет новый узел и связывает его с графиком.

"node": [ 
     { 
      "description": "You are standing in the heart of the Example city. There is a fountain with large marble statue in it...", 
      "exits": { 
       "east": -1, 
       "north": 31, 
       "south": 574, 
       "west": 42 
      }, 
      "id": 0, 
      "name": "cot", 
      "tags": [], 
      "title": "Center of Town", 
      "title_color": "\u001b[1m\u001b[36m Center of Town\u001b[0;37;40m" 
     }, 
     { 
     ... 

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

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

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

Любые мысли/предложения были бы очень признательны!

Answer 1

Многие MU * s предоставят вам возможность получить уникальный идентификатор номеров. (На MUSH и его ответвлениях это think %L.) Другие могут быть настроены для описания комнат, в которых вы уже были, в сокращенной форме. Если нет, вам нужно каким-то образом определить, были ли вы раньше в комнате. Простым способом было бы вычислить хэш достаточной информации о каждой комнате, чтобы получить уникальный ключ. Тем не менее, лабиринт может быть специально настроен, чтобы обмануть вас, думая, что вы находитесь в другом месте. Wizardry, в частности, был предназначен для того, чтобы игроки из старой школы отображали подземелье под рукой, когда они поняли, что их карта должна быть неправильной, и у серии Zork была головоломка, в которой объекты, которые вы сбросили, чтобы отметить свое место в лабиринт будет перемещен, пока вы были где-то еще. На практике кодирование вашего инструмента для решения этих головоломок вряд ли стоит того.

Вы должны иметь возможность запоминать таблицу всех пар-кратчайших путей и обновлять ее в соответствии с подграфом, который вы изучали, всякий раз, когда вы просматриваете новый выход. Это может быть реализовано в виде N × N таблицы, где строка я, колонок J говорит вам следующий шаг на кратчайшем пути от места расположения я к местоположению J. Обычно для ориентированного графа. Даже запустить алгоритм Дейкстры каждый раз должно быть достаточно, но на практике каждый шаг добавляет одну комнату к карте и не добавляет более короткий путь между многими другими комнатами. Вы хотели бы автоматически сопоставлять соединения между комнатами, в которых вы уже были (если они не должны быть скрыты), а не заставлять исследователя утомительно проходить через каждый отдельный выход и обратно, чтобы увидеть, куда он идет.

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

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