先切技術的含義是什麼？

Question

M H Alsuwaiyel寫的「算法設計技術與分析」第3部分被命名爲「First-Cut Techniques」，其中包括貪心法和圖遍歷。 我想知道「先切技術」的含義。我無法通過Google搜索找到它，所以我在此尋求幫助。

Answer 1

先切技術意味着您第一次看到問題時想到的方法。例如，在此圖中，邊表示從一個節點到另一個節點的路徑，這些值表示獲取路徑的成本。假設您在節點1上放置一個嬰兒，並使用最低成本的路徑告訴它到節點3。它會想出什麼？

它將採取1-4邊緣，因爲它具有最低的成本。然後，將需要4-3邊緣去節點3.但你可以清楚地看到，如果寶寶已經採取了1-2然後2-3邊緣，它會花費更少。先切技術是嬰兒會做的事。也就是說，如果不考慮未來路徑，它會花費最低的成本路徑。在當下時刻做出最佳決定稱爲貪婪方法。看起來，貪婪的方法行不通，但有時你會看到貪婪的方法爲你提供最好的解決方案。大部分圖遍歷和最短路徑算法都是貪婪的。

希望這會有所幫助。祝你好運！