我正在为一些示例问题编写伪代码,并且我注意到贪婪技术和详尽搜索之间存在令人担忧的模式。
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 份工作要做,这里有 5 份,您需要以最少的数量完成这些工作,时间由表中每个人和他们的工作所附加的值显示。
穷举搜索和贪婪技术的唯一区别似乎是两者用于解决问题的数据结构。贪婪使用加权图,而详尽使用数组。这种情况在我们的算法中经常发生吗?许多算法是否彼此紧密模仿,但只是使用更有效的数据结构来解决我们的问题?
详尽的搜索探索all可能的解决方案,然后它就能够选择最好的解决方案。
贪婪搜索从一些(部分)解决方案开始。然后以一种总是变得更好的方式改进/完成该解决方案。然而,这并不一定会产生所有这些问题的最佳解决方案。
Example
想象一个超级简单的问题:您有以下数字序列:
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 所在。这就是这个贪婪搜索的最终解决方案 - 你无法通过向左或向右来改进它,但显然不是最好的。但与详尽的搜索相比,您获得它的步骤要少得多。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)