我有一些正在编写伪代码的示例问题,我注意到贪婪技术和穷举搜索之间的惊人模式。
Job 1, Job 2, Job 3, Job 4, Job 5
Person: 1 9 2 7 8
Person: 2 6 4 3 7
Person: 3 5 8 1 8
Person: 4 7 6 9 4
以上是一个赋值问题的表例。基本上,您有 n 份工作要做,这里有五份,您需要完成其中最少的工作,时间由表中每个人及其工作的附加值显示。
似乎穷举搜索和贪心技术的唯一区别是两者用于解决问题的数据结构。贪婪使用加权图,而穷举使用数组。这种情况在我们的算法中经常发生吗?许多算法是否彼此紧密模仿,但只是使用更高效的数据结构来解决我们的问题?
最佳答案
穷举搜索探索所有可能的解决方案,然后它能够选择最好的解决方案。
贪心搜索从一些(部分)解决方案开始。然后以一种总是变得更好的方式改进/完成此解决方案。然而,这并不一定会导致所有问题的最佳解决方案。
示例
想象一个 super 简单的问题:你有这个数字序列:
index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
numbers: 1 6 5 4 5 6 7 8 9 5 2 1 0 1 5 4 5 6 4 1
你要找到最小的数字。如果你进行穷举搜索,你会遍历整个序列并只返回遇到的最小数字。如果你进行贪婪搜索,你会选择一些数字,例如索引为 7 的那个,即 8。然后您尝试贪婪地改进解决方案:您看对了 - 有 9,而且更糟。你向左看 - 有 7 个更好,所以移到那里。你再看看两边,右边有 8 个,左边有 6 个,所以向左走。你再这样做两次,你就会得到索引 3,其中数字 4 就是这个贪心搜索的最终解决方案——你不能通过向左或向右移动来进一步改进它,但显然不是最好的解决方案。但与穷举搜索相比,您获得它的步骤也少得多。
关于algorithm - 贪心技术与穷举搜索有何不同?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31234521/