给定无限行走的图构建算法

Question

我需要帮助编写弹性映射(图形构建)算法。问题是这样的:

假设您有一个面向文本的虚拟现实(TORG/MUD)，您可以在其中通过 telnet 发送移动命令(n、s、w、e、上、下、进、出...等)来移动您的角色从一个房间到另一个房间。服务器在每个移动步骤后发回相应的房间描述。您的任务是生成一个表示底层 map 结构的图，以便您可以简单地在客户端执行 DFS 来找出如何从一个房间到达另一个房间。您还希望设计系统，以便需要最少的用户输入

以下是假设:

• 服务器上的底层图形拓扑永远不会改变。

• 房间描述并不独特。大多数房间都有不同的描述，但有些房间有完全相同的描述。房间描述偶尔(几天或几周)略有更改

• 你的移动可能会以小概率随机失败，你会收到错误消息而不是新房间描述，例如“你停下来等待马车通过”、“门被锁了” ，并且你的角色仍将在当前房间内。

• 您无法假设每次移动的单位空间距离。例如，您可能有如下所示的拓扑，因此假设每个相邻房间的单位距离并为每个房间分配硬坐标是行不通的。但是，您可以假设相对方向是一致的，即沿 X(西、东)和 Y(南、北)进行拓扑排序时不会出现循环。

• 目标:给定您之前访问过的目的地，算法保证最终将您移动到该位置，并且大多数时候会找到最短路径。错误是允许的，但算法应该能够即时检测并纠正错误。

示例图:

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

我已经实现了一个非常简单的解决方案，可以记录房间描述并构建图表。以下是我的程序以 json 形式生成的图形表示的示例。 “导出”是映射到节点 ID 的移动方向。 -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，但 Mapper 无法确定这是否是它之前见过的 B。

简而言之，我希望能够编写一个弹性图构建算法，该算法在隐藏的目标图中行走(可能是无限的)并生成(并不断更新)一个可以(希望)与目标图相似的图。然后，我们使用生成的图表来帮助在目标图表中导航。是否有针对此类问题的现有算法？

我也想过应用一些机器学习技术来解决这个问题，但我无法写出具体的模型。我正在考虑为我们看到的每个房间定义一个特征列表(房间描述、导出、相邻节点)，每次我们看到一个房间时，我们都会尝试找到最适合特征的图形节点，并基于一些更新规则(例如 Winnow 或 Perceptron)会根据一些错误检测指标更新我们看到的描述。

任何想法/建议将不胜感激!

Answer 1

许多 MU* 将为您提供一种获取房间唯一标识符的方法。 (在 MUSH 及其分支上，这是 think %L。)其他的可能会被设置为以缩写形式描述您已经去过的房间。如果没有，您需要某种方法来确定您之前是否来过某个房间。一种简单的方法是计算每个房间的足够信息的哈希值以获得唯一的 key 。然而，迷宫可能是故意设置的，目的是让您误以为自己处于不同的位置。 Wizardry 特别是为了让老派玩家在绘制地牢 map 时发现自己的 map 有问题而抓狂，而 Zork 系列有一个当你在其他地方时，你扔下的用来标记你在迷宫中位置的物体会被移动。实际上，编写工具来解决这些难题不太值得。

您应该能够记住所有对最短路径的表，并在搜索新导出时更新它以匹配您探索过的子图。这可以实现为 N×N 表，其中行 i、列 j 告诉您下一步从位置i到位置j的最短路径。通常，对于有向图。即使每次运行 Dijkstra 算法也应该足够了，但实际上，每次移动都会在 map 上添加一个房间，并且不会在许多其他房间之间添加更短的路径。您会希望自动映射您已经去过的房间之间的连接(除非它们应该被隐藏)，而不是迫使探索者繁琐地走过每个单独的导出并返回以查看它的去向。

如果您可以设计 map ，您还可以布置区域，以便在它们之间轻松导航，然后您可以保持表格较小:每个表格只需要包含您特意布置的各个区域的 map 像迷宫一样去探索。也就是说，如果你想从一个地下城到另一个地下城，你只需要查找最近的导出，然后在世界地图上查找地下城之间的方向，而不是一张随整个地点数量呈二次方增长的巨大表格游戏。例如，如果您将世界布局为嵌套层次结构，其中一个房间位于某个星球上某个大陆上的某个国家/地区的某个城市附近的街道上的建筑物中，则可以将位置存储为一棵树，从一个区域导航到其他区域只需沿着树向上走，直到到达目的地路径上的 Twig 即可。

我不确定神经网络等机器学习在这里会有什么帮助；如果您正在寻找的技巧是一个看起来与您之前见过的房间相同的房间实际上是重复的，那么处理这种情况的方法是同时维护多个可能的 map 假设表面上相同的房间是或不是重复的，是一个岔路花园。