寻找迷宫中的最短路径

我是业余程序员，学习如何编程。我从未有过任何的计算机科学课程，所以我有困难的时候与这个简单的问题：寻找迷宫中的最短路径

class Room { 
    String name; 
    ArrayList<Room> neighbors = new ArrayList<Room>(); 

    // constructor with name 
    // getters 
    void addNeighbor(Room room) { 
     neighbors.add(room); 
    } 
} 

class Finder { 
    void findShortestPath(Room start, Room end) { 
     // ? 
    } 
}

每个房间都有一些邻居。超过4个，所以它不像矩阵导向问题。你被给予最后的房间，你必须从起始房间找到最短的路径（比较房间的名字）。结果应该是“道”，如：

开始：厨房

结束：卫生间

路径：厨房，客厅，走廊，卧室，卫生间

我想我必须使用一些递归房间和我想我应该保存在我已经在一些堆栈的地方。但我真的不知道该如何开始。

你们中的一些人可以帮我吗？谢谢

来源

2012-03-24 Nancy

http://en.wikipedia.org/wiki/A*_search_algorithm – jonmorgan 2012-03-24 21:29:59

每个房间都需要可以花费的路线。然后你可以遍历路线。 – 2012-03-24 21:30:28

@JakobBowyer只取1成本:) – 2012-03-24 21:34:44

您正在寻找BFS。

在你的情况下，图G = (V,E)实际上是V= { all rooms }和E = {(u,v), (v,u) | u and v are neighboring rooms }

请注意，你不关心你没有所有边缘[邻居]算法开始之前 - 你知道如何计算相关集使用neighbors字段，可以在飞行中边缘[和房间]。
这是事实，因为您需要为您的路径使用每个“边缘” - 当您发现靠近源的路径更近时，“发现”了这个边缘。

您可以看看this post - 运行BFS后如何找到实际路径。

来源

2012-03-24 21:30:43 amit

有了这些知识，我能够完成这一点。谢谢！ – Nancy 2012-03-24 22:29:21

欢迎@Nancy。如果您发现一个有用的答案，请不要忘记[接受]（http://meta.stackexchange.com/q/5234/161469）答案。 – amit 2012-03-24 23:00:34

你想写一个广度优先搜索。这个主题有很多可用的资源。

来源

2012-03-24 21:31:10 ShiggityShiggityShwa

寻找迷宫中的最短路径

回答

相关问题