生成与测试范式

[luobengseng1]

解决问题的直接方法是提出可能的解，然后检查每个提议，看是否有提议构成了解。人们称之为生成与测试范式。
本文用n皇后问题阐释这种方法，n皇后问题涉及将n个皇后放在n×n的棋盘上，任何两个皇后都不互相攻击。也就是说，任何两个皇后都不应该占据相同的行、列或对角线。这些条件被称为问题的约束条件。
在这个问题中，4个皇后需要放置在4×4棋盘上。总共有 或1820种方法来实现这个目标。这些提议的解中，有许多提议的解违反了问题的一个或多个约束条件。但是，如果为了不丢失解，一个可靠的生成器必须提出满足问题约束的、大小为4的任何子集。更一般地说，如果这个生成器提出了每个可能的解，那么这个生成器就是完备的。此外，如果提出的解被拒绝了，那么这个方案就不会再次被提议（事实上，每个成功的提议都只能提出一次）。换句话说，一个好的生成器应该是非冗余（noredundant）的。最后，回想一下，将4个皇后放置在一个4×4棋盘上有1820种方法。如果生成器没有提出明显不可行的解，那么这个生成器会相对有效。可以说，如果生成器拥有一些信息，允许其对提案做出一些限制，那么这个生成器就是知情的（informed）。
求解4皇后问题的第一种方法是采用生成器，在最坏的情况下，这个生成器检查1820种将4个皇后放在4×4棋盘上的每一种方式。
完全枚举法是一种搜索方法，它将查看所有位置，寻找问题的解。甚至在已经发现了这组位置不可能成功得到解的情况下，完全枚举法还是进一步得到了部分解。我们可以使用带有生成与测试范式的回溯。在推进过程中，允许测试模块查看一个可能的解。