graph-theory - 初斩术是什么意思？

Question

M H Alsuwaiyel 撰写的“Algorithms Design Techniques and Analysis”的第 3 部分名为“First-Cut Techniques”，包括贪婪方法和图遍历。而我想知道“初剪术”的含义，google了没找到，所以在这里求助。

Answer 1

先入为主的技巧是指您在遇到问题时第一时间想到的方法。例如，在此图中，边表示从一个节点到另一个节点的路径，值表示采用该路径的成本。比方说，你把一个婴儿放在节点 1 上，并告诉它使用成本最低的路径去节点 3。它会带来什么？

它需要 1-4 优势，因为它的成本最低。那么到节点 3 需要 4-3 边。但是你可以清楚地看到，如果婴儿会采取 1-2 然后是 2 -3 边缘，它会花费更少。第一刀技术是婴儿会做的。也就是说，在不考虑 future 路径的情况下，它会选择它能找到的成本最低的路径。为那个瞬间做出最好的决定被称为贪心法。看起来，贪心法行不通，但有时您会发现，贪心法可以为您提供最佳解决方案。大多数图遍历和最短路径算法都是贪心的。

希望这对您有所帮助。祝你好运!