算法学习 -- 枚举

在学习枚举算法之前,首先问有关枚举的几个问题

1. 为什么要进行枚举?

2. 需要对哪些对象进行枚举?

3. 如何进行枚举?

4. 枚举的结束条件是什么?

现在针对两个使用枚举算法的实例对以上问题进行分析.

实例一:熄灯问题

给定一个5×6的棋盘,上面有灯,每个灯都有各自的按钮,每个按钮按下去都会使其自己和周围的上下左右四盏灯改变(原来熄灭的变亮,原来亮的变灭),如何操作按钮使这个棋盘上所有灯都熄灭。

实例二:青蛙问题

一个5000×5000的稻田,有很多青蛙从这个稻田上跳过,每只青蛙跳过的步长不一样,青蛙每次总是沿着一条直线跳跃稻田(至少3个稻子),农民早上起来看到被踩踏的稻子,希望找到造成最大损害的那只青蛙经过的路径。

第一个问题:为神马要枚举?

因为解决这个问题可能不止一个方案,然而目前我并不知道哪个方案可以,仅仅知道如果按照这个方案操作造成的结果,这个结果是否符合最后的要求并不清楚。需要进一步实验验证。

实例一,总共有5×6个按钮可以操作,但并不知道按下哪些按钮会导致所有灯都熄灭。实例二,总共有5000×5000个稻子,被踩踏的稻子也很多,但是并不知道哪些稻子是被某只青蛙踩踏的,而且是最多的。

第二个问题:需要对哪些对象进行枚举?

接着上个问题所述,假定一个假设,接着进行这个假设,通过这个假设来进行推理,推理出一个结果,这个结果会接着推理下一个结果,顺序下去,最后可以推导出最终的结果,最终的结果是不是题目要求的结果。而这而的假设就是我们需要枚举的对象。这个假设要求可以推得最后的唯一结果,同时它必须不是很多,否则复杂度很大。

实例一,因为下一行的按钮负责将上一行的灯熄灭,一行一行的熄灭,只要第一行的按钮被按下去了,第一行的灯状态就可以确定,第二行的按钮只需要将第一行的熄灭就行,那么第二行的按钮状态也是确定的,依次类推,到最后第五行时,第五行的按钮负责熄灭了第四行的灯,但是不一定使第五行的灯熄灭。所以需要枚举的对象是第一行的按钮状态。

实例二,因为被踩踏的稻子数至少为3个,所以可以将这些被踩踏的任意两个稻子作为一只青蛙经过的路径。任意两个稻子就决定了这只青蛙的步长,根据步长就可以判断下这只青蛙的下一步的位置,依次可以推断出最后一个稻子的位置,就可以知道这只青蛙是不是踩踏最多的那只了。

第三个问题:如何进行枚举?

通过对第二个问题的分析,我们知道了需要对哪些对象进行枚举,接下来需要知道如何对这些对象进行枚举。具体如何枚举需要看所要枚举的对象。

实例一,需要枚举的对象是第一行的按钮状态,因为按下用1表示,不按用0表示,在枚举的过程中,实际是对第一行的6个按钮进行枚举,因为这六个按钮都是0和1,可以看作二进制数,枚举就是二进制不断加一的过程。

实例二,需要枚举的对象是踩踏稻子中任意两个稻子,实际是对n个数中任意两个数进行遍历,外层循环遍历 i 从1到n - 1, 内层循环遍历 j 从 i 到 n。

第四个问题:枚举的结束条件是什么?

通过问题二的分析知道,在某个假设,经过一步一步的推导,看最后的结果是否符合问题给出的条件或约束,如何符合,那枚举就可以结束,说明这个枚举就是最后的答案。

实例一, 第五行的按钮熄灭了第五行的灯,则符合将灯全部熄灭这一要求,所以枚举结束,获得正确的按钮。

实例二,最后一个稻子位置在被毁稻子列表中,而且这个枚举情况下的被毁稻子数最多,则枚举结束,可以判定这条路径就是被毁最多路径。

原文地址:https://www.cnblogs.com/jinee/p/4596320.html