0

我在接受一家大公司的采访时被问到这个问题：

假设我们有这个接口：

interface ILabyrinth
{

   // create a labyrinth of size 100*100 max.  Rabbit and carrot are positioned at random locations within the maze.
   void Init();

   // try to move the rabbit in one direction.  return true if the move was successful, returns false otherwise (there was a wall) 
   bool tryMove(Direction d);

   // return true if carrot and rabbit are at the same place.
   bool isSuccess();

}

为了找到胡萝卜，你会如何移动兔子？一旦我们到达它，我们只需要停下来。

我的解决方案是应用经典的 DFS 搜索，但我们需要使用 tryMove() 函数回溯鼠标，因为我们自己无法做到这一点（因为数据仅由 ILabzrinth 接口包含和修改。

我通过在大小为 198*198 (= (100-1)*2) 的新地图中跟踪兔子的运动来做到这一点。在这张地图中，我保存了我们过去在那个位置的方向。所以我可以很容易地回溯。

你知道如何改进吗？

4

2 回答 2

2

就启发式方法而言，您没有太多可以改进的地方，因为在您处于胡萝卜之上之前，您不知道胡萝卜在哪里。因此，在没有任何启发式的情况下，有必要做一个 DFS。

在您来自的方向的地图中，您还可以将存储用作您去过的地方的标志，以避免重新探索您已经去过的地方。您没有表明是否检查了这一点，但如果您没有，那么这是一个可能的改进领域。

为了最小化内存使用，可以将方向的回溯存储在堆栈中。这样可以避免在大地图中存储额外的数据。由于您可能想要保留标志图，因此您仍然需要一个布尔图。但是，这仅花费每个单元格 1 位（而不是 1 字节的方向）。

于 2013-04-29T11:15:47.127 回答
0

如果这是一次采访，我希望你提到“老鼠和奶酪”变成了“兔子和胡萝卜”，这可能看起来像一个细节，但可能是故意的......（如果我们只移动，isSuccess() 将永远不会返回 true老鼠而不是兔子！）

除此之外，我不会使用 DFS，但在深入 (BFS) 之前为每个可用分支移动了 1 个案例，因为您不知道 POI 在哪里。禁止访问节点，除非新距离小于前一个距离（但它不应该经常发生！）。不向后退（当我向右移动时向左走）是一个加号，但包含在前面的规则中。

希望它无论如何都对你有用...... GL！

编辑：我发现了这个：http ://www.astrolog.org/labyrnth/algrithm.htm#solve 。我在这里尴尬地提出的建议对应于非人类最适合的路径，在该路径中，您使用具有距离的 *n 网格在本地重新创建一个迷宫（我猜是描述的第二条最短路径......）

顺便说一句，这里的问题是什么：找到胡萝卜？找到一条最短路径？还是不回溯路径？？？

重新编辑：消歧后，此答案的部分内容不适合问题：目标不是找到最短路径而是胡萝卜，兔子当时只能在一个方格内。

于 2013-04-29T11:22:53.507 回答