穷举法

来自计算思维百科
跳转至: 导航搜索

穷举法(Exhaustive Algorithm),也称蛮力法,是一种简单直接地解决问题的方法,是指在问题的解空间范围内逐一测试,找出问题的解。

基本概念 

穷举法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下:

(1)对于一种可能的情况,计算其结果。

(2)判断结果是否符合要求,如果不满足则执行第(1)步来搜索下一个可能的情况;如果符合要求,则表示寻找到一个正确答案。

在使用穷举法时,需要明确问题的答案的范围,这样才可以在指定的范围内搜索答案。指定范围之后,就可以使用循环语句和条件语句逐步验证候选答案的正确性,从而得到需要的正确答案。

应用

四色定理

地图上为区分相邻国家、省、市等区域,会给其着不同的颜色。一张地图最少需要几种颜色着色?解决这一问题的答案是数学史上的著名难题—“四色定理”,它的证明是也用穷举法实现的。

四色定理('Four-Color Theorem),又称四色问题、四色猜想,是世界近代三大数学难题之一。四色定理最早是由一位叫古德里(Francis Guthrie)的英国大学生提出的,其内容是:“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”。用数学语言表示,即“将平面任意地细分为不相重叠的区域,每一个区域总可以用1、2、3、4这四个数字之一来标记,而不会使相邻的有公共边界的两个区域得到相同的数字。”。

著名数学家德·摩尔根(Augustus De Morgan)在1852年10月23日致哈密顿的一封信中首次提到了四色问题的来源,并在信中简述了自己证明四色定理的设想与感受。之后的一个多世纪,四色定理都未得到证明。最终在1976年,美国数学家阿佩尔(K.Appel)与哈肯(W.Haken)用穷举法借助电子计算机获得了四色定理的证明。他们在两台不同的电子计算机上,用了1200个小时,作了100亿判断,完成了四色定理的证明。证明由两部分组成,第一部分,利用以前确立的结果,加上一些数学推理,证明一般问题可以归约到证明有限个特例上;第二部分,用计算机程序产生了所有的特例(大约1700个例子),通过穷举,发现所有特例都是四着色的。

百钱买百鸡问题

穷举法还可以用于解决中国古代著名趣题、进行逻辑推理判定,求解百钱百鸡、五家共井、谁做的好事、四大湖等问题。排序中的冒泡排序、选择排序也是穷举法。

公元5世纪末,中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡,问翁、母、雏各几何?意思是公鸡每只5元、母鸡每只3元、小鸡3只1元,用100元钱买100只鸡,求公鸡、母鸡、小鸡的只数。

百钱百鸡问题在很多书籍中都作为穷举法的一个典型案例。设鸡翁、鸡母、鸡雏的个数分别为x、y、z,根据题意,可得如下方程:

5x+3y+z/3 = 100                                               

x+y+z = 100                                                  

1≤x<20, 1≤y<33, 3≤z<100, z mod 3 = 0                               

用穷举法求解,即在有限集合:1≤x<20, 1≤y<33,3≤z<100中,对每组x、y、z的值,计算x+y+z=100,5x+3y+z/3=100,z mod 3=0三个条件是否成立,从而找出百鸡问题的解。

国王的婚姻

从前,有一个酷爱数学的年轻国王想邻国一位聪明美丽的公主求婚。公主出了这样一道题:求出48770428433377171的一个真因子。若国王能在一天之内求出答案,公主便接受他的求婚。 国王回去后立即开始逐个数地进行计算,他从早到晚,共算了3万多个数,最终还是没有结果。国王向公主求请,公主将答案告之:223092827是它的一个真因子。国王很快就验证了这个数能除尽48770428433377171。公主说:“我再给你一次机会,如果还求不出,将来你只好做我的证婚人了。” 国王立即回国,并向时任宰相的大数学家求教,大数学家在仔细地思考后认为这个数为17位,则最小的一个真因子不会超过9位,于是他给国王出了一个主意:按自然数的顺序给全国的老百姓每人编一个号发下去,等公主给出数目后,立即将它通报全国,让每个老百姓用自己的编号去除这个数,除尽了立即上报并赏金万两。最后,国王用这种方法求婚成功。 宰相在这里用的方法就是穷举法,将问题逐一分解,在解空间范围内,即每个老百姓的编号(不超过9位的自然数,)把每个可能的解分给每个老百姓进行计算。这是一种并行算法。

详见:国王的婚姻

密码破译

穷举法是一种用穷举法实现的密码破译方法,它对密码进行逐个测试直到找到真正的密码。例如一个已知是六位并且全部由数字组成的密码,共有10^6种组合,最多尝试10^6-1次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码,但如果密码比较复杂的话,破译密码的时间会很长,因此需要结合其他方法缩短试误时间。

评价

巧妙和高效的算法很少来自于穷举法,但基于以下因素,它仍是一种重要的算法设计策略。

  1. 穷举法是一种几乎什么问题都能解决的一般性方法;
  2. 即使效率低下,仍可用穷举法求解一些小规模的问题实例;
  3. 如果解决的问题实例不多,而穷举法可用一种可接受的速度对问题求解,那么花时间去设计一个更高效地算法是得不偿失的。


可以体现的计算思维

穷举法是最简单的一种算法,其依赖于计算机的强大计算能力来穷尽每一种可能性,从而达到求解问题的目的,提现了计算思维的机械化特点。