生成与测试范式
-
解决问题的直接方法是提出可能的解,然后检查每个提议,看是否有提议构成了解。人们称之为生成与测试范式。
本文用n皇后问题阐释这种方法,n皇后问题涉及将n个皇后放在n×n的棋盘上,任何两个皇后都不互相攻击。也就是说,任何两个皇后都不应该占据相同的行、列或对角线。这些条件被称为问题的约束条件。
在这个问题中,4个皇后需要放置在4×4棋盘上。总共有 或1820种方法来实现这个目标。这些提议的解中,有许多提议的解违反了问题的一个或多个约束条件。但是,如果为了不丢失解,一个可靠的生成器必须提出满足问题约束的、大小为4的任何子集。更一般地说,如果这个生成器提出了每个可能的解,那么这个生成器就是完备的。此外,如果提出的解被拒绝了,那么这个方案就不会再次被提议(事实上,每个成功的提议都只能提出一次)。换句话说,一个好的生成器应该是非冗余(noredundant)的。最后,回想一下,将4个皇后放置在一个4×4棋盘上有1820种方法。如果生成器没有提出明显不可行的解,那么这个生成器会相对有效。可以说,如果生成器拥有一些信息,允许其对提案做出一些限制,那么这个生成器就是知情的(informed)。
求解4皇后问题的第一种方法是采用生成器,在最坏的情况下,这个生成器检查1820种将4个皇后放在4×4棋盘上的每一种方式。
完全枚举法是一种搜索方法,它将查看所有位置,寻找问题的解。甚至在已经发现了这组位置不可能成功得到解的情况下,完全枚举法还是进一步得到了部分解。我们可以使用带有生成与测试范式的回溯。在推进过程中,允许测试模块查看一个可能的解。
西南地区IT社群(QQ)
- 云南
- 【昆明网页设计交流吧】243627302
- 【昆明nodejs交流吧】 243626749
- 【VUE】838405306
- 【云南程序员总群】343606807
- 【昆明UI设计】104031254
- 【云南软件外包】15547313
- 贵州
- 【PHP/java源码/站长交流群】55692114
- 四川
- 【成都Java/JavaWeb交流】86669225
- 【vaScript+PHP+MySql】116270060
- 【UI设计/设计交流学习群】135794928
- 重庆
- 【诺基亚 JAVA游戏博物馆】 559479780
- 【PHP,Java,Python,C++接单】 442103442
- 西藏