Алгоритм построения графа с учетом бесконечного блуждания

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, но картограф не может определить, был ли это B, который он видел раньше.

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

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

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

Answer 1

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

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

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

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