尋找迷宮中的最短路徑

我是業餘程序員，學習如何編程。我從未有過任何的計算機科學課程，所以我有困難的時候與這個簡單的問題：尋找迷宮中的最短路徑

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

尋找迷宮中的最短路徑

回答

相關問題