先切技术的含义是什么？

Question

M H Alsuwaiyel写的“算法设计技术与分析”第3部分被命名为“First-Cut Techniques”，其中包括贪心法和图遍历。 我想知道“先切技术”的含义。我无法通过Google搜索找到它，所以我在此寻求帮助。

Answer 1

先切技术意味着您第一次看到问题时想到的方法。例如，在此图中，边表示从一个节点到另一个节点的路径，这些值表示获取路径的成本。假设您在节点1上放置一个婴儿，并使用最低成本的路径告诉它到节点3。它会想出什么？

它将采取1-4边缘，因为它具有最低的成本。然后，将需要4-3边缘去节点3.但你可以清楚地看到，如果宝宝已经采取了1-2然后2-3边缘，它会花费更少。先切技术是婴儿会做的事。也就是说，如果不考虑未来路径，它会花费最低的成本路径。在当下时刻做出最佳决定称为贪婪方法。看起来，贪婪的方法行不通，但有时你会看到贪婪的方法为你提供最好的解决方案。大部分图遍历和最短路径算法都是贪婪的。

希望这会有所帮助。祝你好运！