選擇貪婪算法找到最低成本路徑

我有一個數字金字塔。每個數字代表關聯的點數。我需要使用貪婪算法來找到從金字塔頂部到底部成本最低的路徑。我讀過關於不知情的&知情搜索算法，但仍然不知道該選什麼。你最適合這種類型的問題是什麼？貪婪的最佳搜索/ A *搜索或其他？這是一個很簡單的問題，但我沒有使用所有這些算法來知道什麼是最佳選擇。正如我所說，它必須是一個貪婪的算法。選擇貪婪算法找到最低成本路徑

來源

2011-03-21 joanna

如果我正確地理解了你，在你的金字塔中，你總是可以選擇向左或向右下降，到底的成本就是你通過的所有節點的總和。

在這種情況下，只需從底部開始工作即可。從底部第二排開始。對於該行中的每個節點，請查看下面一行中的左側和右側兒童。將更便宜的子節點的成本添加到您所在的節點。向上移動並重復，直到你在根/峯。現在每個節點將包含從那裏到最底層的最便宜路徑的成本。通過選擇成本更低的子節點來貪婪地下降。

來源

2011-03-21 12:53:20

這就是我所做的。它看起來太簡單了，但至少我使用了「貪婪」的方法：從金字塔頂部開始，總是選擇三個可能節點中成本最低的下一個節點。我只是想確保我以正確的方式思考。不管怎麼說，還是要謝謝你。 – joanna 2011-03-21 13:41:31

@Joanna：你想要的是糾正你的問題，因爲金字塔在每個級別有4個可能的節點。你想要的是一個四合一者。一個tetraeder在每個級別有3個節點。 – Bytemain 2011-03-21 13:51:03

@joanna只要確保你所看到的成本是從那裏到最底部的最短路徑的成本。如果它只是該節點本身的成本，那麼你的算法是不正確的。 – 2011-03-21 14:26:56

你想要的是Dijkstra算法它比A *搜索更簡單，但我想DFS會這樣做。我不確定你真正想要什麼。

來源

2011-03-21 11:38:26 Bytemain

如果您沒有使用貪婪算法的必要性，這裏不正確。對於這種問題，你自然會使用一種叫做「動態編程」的技術。

你初始化你的金字塔的所有方塊（你做一個備份）與無限 - 除了它自己的價值初始點。

然後你從上到下逐行處理金字塔。您嘗試從第一行開始（只有一行是頂部），並且您更新第二行的節點，併爲它們賦予top +它們的值。然後移動到第二行，並更新下一行中的節點。

您可能以前找到了一個更好的路由到該節點（從節點放置一個位置開始），因此只有在新創建的路由「更快」時纔會更新。（因此你做了無限初始化，這意味着在開始時你不知道是否有實際存在的路線）。當你完成pyradim的處理後，你知道你有最好的路線來放置在級別在下面。

即使它聽起來有點複雜，它很容易實現，我希望它不會讓你成爲一個問題。

來源

2011-03-22 18:49:18 mechu

選擇貪婪算法找到最低成本路徑

回答

相關問題