暴力搜索算法
3.97/5 (13投票s)
一个通用的类，实现了穷举搜索算法，用于解决各种谜题和谜语。
引言
一种使用计算系统解决困难问题的方法是应用穷举搜索。这意味着要穷尽所有可能的组合，直到找到解决方案。在本文中，我将介绍一个穷举搜索算法的实现，该算法可应用于各种问题。本文的创意来源于CodeProject上的一篇文章，该文章介绍了一个解决爱因斯坦谜题的C++程序。本文的功能得到了扩展，以利用面向对象编程的优势，并生成一个通用的求解器类，该类可以作为许多特定于问题的求解器类的基类。将介绍许多问题求解器类的示例，包括一个解决爱因斯坦谜题的示例。
注意：实现所使用的语言是C++。尽管使用了一些高级语言特性（如模板类、STL），但本文中的技术细节尽量保持简洁，以便即使是经验较少的程序员也能理解穷举算法的逻辑，并从示例谜题中获得乐趣。
八皇后问题
我将从八皇后问题开始介绍穷举搜索算法的思想。这是一个著名的在棋盘上放置8个互不攻击的皇后的问题。解决这个谜题的源代码可以在许多软件书中找到。在下载区，您可以找到一个实现了该谜题的Java Applet（java_applets_src.zip）。
计算系统可以帮助我们快速解决这个谜题。此外，它还可以帮助我们找到所有可能的解决方案。为此，我们必须指示程序搜索8个皇后在棋盘上的所有可能的位置。总共有 64!63!62!61!60!59!58!57! 种不同的排列。尝试搜索所有这些不同的组合效率极低。通过归纳法解决问题要好得多。也就是说，首先解决在1x8棋盘上放置一个皇后的问题，然后解决在2x8棋盘上放置两个皇后的问题，以此类推，直到找到完整的解决方案。通过这种方式，可以及早发现大量明显错误的组合，而无需进行测试。如果在棋盘的前n列中有两枚皇后互相攻击，那么无论其余8-n枚皇后如何放置，该组合都无法构成解决方案。
归纳搜索算法的工作方式如下。我们开始将第一个皇后放在a1。第二个皇后放在b3（因为b1和b2被第一个皇后攻击）。然后我们在第三列寻找一个未被攻击的格子。我们以同样的方式继续，直到到达一列没有未被攻击的格子。在这种情况下，我们回到前一列，并尝试将放在那里的皇后移动到另一个未被攻击的格子。我们只检查行号比前一个高的格子。如果这也无法实现，我们会回退一列，并尝试做同样的事情。如果在前一列找到了一个新的未被攻击的格子，我们就准备再次向前推进。每当我们能够在第八行放置一个皇后时，就找到一个新的解决方案。我们递增一个变量，将皇后的位置存储在一个表中，然后返回到第7列寻找一个新的未被攻击的格子。当我们需要从第2列返回到第1列，并且皇后被放置在a8时，搜索就完成了。可以通过单击前面Applet中的“Solve”按钮来可视化该算法。
泛化
归纳搜索算法的概念可以用于更一般的情况。为了能够重用算法的功能，我们将定义一个“抽象”谜题。这个“抽象”谜题由一个n个单元格的表表示，必须用来自有序列表的元素填充（参见图1）。
图 1：通用谜题
为了以归纳方式解决谜题，我们首先填充单元格1，然后是单元格2，依此类推，直到所有单元格都被填充。算法的流程图如下所示。
图 2：流程图
要使此技术生效，我们必须定义两个函数：
- check_placement(m)：检查前m个单元格的子谜题是否已解决
- get_next_element(e)：给定一个元素e，返回其在有序列表中的下一个元素。
C++类riddle_solver<move_t>实现了“抽象”谜题。
template <class move_t> class riddle_solver { public: /** Constructor. */ riddle_solver<move_t>(); /** Destructor. */ ~riddle_solver<move_t>(); /** Solves the riddle using inductive searching algorithm. If not instructed otherwise (by restricting the number of solutions to search for), all possible combinations are searched. @result Returns true if one or more solutions have been found. */ bool solve(); /** Prints all solutions found. */ void print_all(); /** Sets the maximum number of solutions to search for. If 0 is given, solve function will scan all possible combinations. @param n Maximum number of solutions to search for. */ void set_solutions_count(int n); /** Sets the size of the riddle, that is the size of the table it must be filled to solve the riddle. @param s Riddle's size. */ void set_size(int s); /** Sets null element. When null element is given as input to get_next_element function, the first element in the ordered element list will be returned. Null element cannot be used to fill a cell. @param mn Null element. */ void set_null_element(move_t mn); private: /** tries to fill the next cell in the table. If this is impossible it will return false. The algorithm must then return to a previous cell. It must not be overridden. @result Returns true if it was possible to make a new move. */ bool make_next_move(); /** It tries to find another valid element in a previous cell. It will go back as many cells as required. If this impossible, false will be returned and the searching will stop. It must not be overridden. @result Returns true if a new valid element in a previous cell has been found. */ bool go_back(); protected: // virtual functions /** Checks if the subriddle of size moves_count is solved. It may be overridden. It is declared virtual, because it is called from solve function of the base class. When called in the context of a subclass, solve function must call check_placement of the subclass and not this version. @result Returns moves_count if the subriddle is solved, 0 otherwise. */ virtual int check_placement(); /** Gets next element from the elements ordered list. @param pos Position of cell that contains the element to be replaced by the next one found. A new cell will contain null element, so that we start the searching from the first element in the list. It must be overridden. @result Returns next element. */ virtual move_t get_next_element(int pos); /** Registers move at specified position. In its simplest form, it just inserts element move at cell pos. It may be overridden. @param pos Position of cell to place the element. @param move Element to be placed. */ virtual void register_move(int pos, move_t move); /** Undoes last move (at position moves_count - 1). In its simplest form, it just removes the element placed at the last cell and fills it with null element. It may be overridden. */ virtual void unregister_last_move(); /** Prints solution in the standard output. @param sol Vector containing the solution. */ virtual void print_solution(vector<move_t> sol) {;}; protected: // Data members /// Table storing the moves made. vector<move_t> moves_array; /// Riddle's size (moves_array size). int size; /// Number of moves made so far. int moves_count; private: /// Null element. move_t move_null; /// Maximum number of solutions to look for. int sol_number_max; /// Vector for storing all solutions found. vector<vector<move_t> > sol_v; };
注意：riddle_solver<move_t>是一个模板类。move_t类型定义了填充表单元格的元素的类型。在本文的所有示例中，riddle_solver将使用int作为move_t进行实例化。但是，该类可以与任何其他原生类型（如float或double）或重载=运算符的用户定义类一起使用。
使用riddle_solver<int>作为基类，可以使用一个简单的类来解决八皇后谜题。
q8_riddle_solver::q8_riddle_solver()
{
set_null_element(-1);
set_size(8);
}
q8_riddle_solver::~q8_riddle_solver() {}
int
q8_riddle_solver::get_next_element(int pos)
{
if (moves_array[pos] == 7)
return(-1);
else
return(moves_array[pos]+1);
return(-1);
}
int
q8_riddle_solver::check_placement()
{
int i, j;
for(i=0;i<moves_count;i++)
{
for(j=i+1;j<moves_count;j++)
{
if (moves_array[i] == moves_array[j])
return(0);
if (i + moves_array[i] == j + moves_array[j])
return(0);
if (i - moves_array[i] == j - moves_array[j])
return(0);
}
}
return(moves_count);
}
void
q8_riddle_solver::print_solution(vector<int> sol)
{
char str[4];
str[2] = ' ';
str[3] = '\0';
for(char i = 0; i < 8; i ++)
{
str[0] = 'a' + i;
str[1] = '1' + sol[i];
cout << str;
}
cout << endl;
};
在接下来的段落中，riddle_solver类将用于解决更多谜题。
爱因斯坦谜题
这是最初促使我写这篇文章的谜题。如下所示：
- 有5栋不同颜色的房子。
- 每栋房子里住着一个不同国籍的人。
- 这五位主人喝一种特定的饮料，抽一种特定的香烟品牌，养一种特定的宠物。
- 所有主人都不拥有相同的宠物，不抽相同的香烟品牌，也不喝相同的饮料。
对于这个奇特的社区，我们知道以下信息：
- 英国人住红房子。
- 瑞典人养狗。
- 丹麦人喝茶。
- 绿房子在白房子左边。
- 绿房子主人喝咖啡。
- 抽Pall Mall的人养鸟。
- 黄房子主人抽Dunhill。
- 住在中间房子的人喝牛奶。
- 挪威人住第一栋房子。
- 抽Blends的人住在养猫的人旁边。
- 养马的人住在抽Dunhill的人旁边。
- 抽BlueMaster的人喝啤酒。
- 德国人抽Prince。
- 挪威人住在蓝房子旁边。
- 抽Blends的人的邻居喝水。
问题是：谁养鱼？要回答这个问题，必须找出所有房子对应的国籍、颜色、宠物、饮料和香烟品牌。
图 3：爱因斯坦谜题社区
为了将谜题改编成我们的抽象谜题的形式，我们定义一个大小为25的表。前5个单元格包含主人的国籍，接下来的五个是房子的颜色，然后是宠物、饮料和香烟品牌。这意味着在构建解决方案时，我们将首先找到所有主人的国籍，然后移动到房子的颜色，依此类推。元素列表由1到5的数字组成，并按自然顺序排列。我们有5种属性类型（国籍、颜色、宠物、饮料和香烟品牌），每种属性有5种值。我们将每种属性值映射为1到5的数字。表中的单元格用1到5的数字填充，但有一个限制，即两个房子不能包含相同的属性值。实现的详细信息出现在文件eisteins_riddle.cpp和einsteins_riddle.hpp中。
幻方
阶数为n的幻方是一个nxn的表，其中包含从1到n²的所有数字，使得所有行、列和主对角线的总和都相同。构造任意阶幻方的算法存在[1]。CodeProject上还有一篇文章可以完成这项工作。枚举特定阶数的所有幻方的问题听起来更具挑战性（[2]）。我们将尝试使用riddle_solver类来枚举3阶、4阶和5阶的幻方。
在上面介绍的抽象谜题概念中，我们将按照下图所示的顺序，逐个单元格地构造幻方。
图 4：幻方的访问顺序
以下列表展示了check_placement 例程的实现。每当一个单元格被填入一个数字时，该例程就会检查一行、一列或一个主对角线是否已完成。如果已完成，则计算总和并测试其是否正确。阶数为nxn的幻方所有行、列和主对角线的总和应为 n[n²+1]/2。
int magic_square_solver::check_placement() { int r, c; if (moves_count == 0) return(0); r = (moves_count-1) / square_size; c = (moves_count-1) % square_size; // A row has just been completed if (c == square_size-1) { if (!test_row(r)) return(0); } if (r == square_size - 1) { // Reverse diagonal has been completed if (c == 0) { if (!test_reverse_diagonal()) return(0); } // Diagonal has been completed if (c == square_size - 1) { if (!test_diagonal()) return(0); } // A column has just been completed if (!test_column(c)) return(0); } return(moves_count); }
尽管此代码对3x3的方块效果很好，但您会发现对于4x4的方块来说，它太慢了，几乎没有用。为了加快速度，我们必须增强check_placement例程，以便更早地检测出错误的组合。我们通过修改check_placement来实现这一点，使其对每个新填入的单元格进行测试，而不仅仅是对完成行、列或主对角线的单元格进行测试。对于每个新填入的单元格，我们计算其所属的行和列的部分总和。如果它是主对角线的一部分，我们还计算到目前为止对角线的总和。然后我们检查，这些部分总和是否已经大于所需总和，或者是否小于其应有的最小值。如果是这种情况，我们就返回前一个单元格。部分填充的行/列/对角线的最小总和计算如下。如果n-m个单元格已填，则部分总和应等于或大于n[n²+1]/2- n² - (n²-1) - ... - (n²-m+1)。
int magic_square_solver::check_placement() { int r, c; if (moves_count == 0) return(0); r = (moves_count-1) / square_size; c = (moves_count-1) % square_size; // A row has just been completed if (c == square_size-1) { if (!test_row(r)) return(0); } if (r == square_size - 1) { // Reverse diagonal has been completed if (c == 0) { if (!test_reverse_diagonal()) return(0); } // Diagonal has been completed if (c == square_size - 1) { if (!test_diagonal()) return(0); } // A column has just been completed if (!test_column(c)) return(0); } else { // Test partial row, column, diagonal if (c != square_size-1 && !test_partial_row(r, c)) return(0); if (!test_partial_column(c, r)) return(0); if (c == r && !test_partial_diagonal(r)) return(0); if ((c == square_size - r - 1) && !test_partial_reverse_diagonal(r)) return(0); } return(moves_count); }
通过增强的check_placement例程，您将能够在一两分钟内枚举4x4的方块。将得到的结果与[2]中呈现的结果进行比较。请注意，如果我们有一个解决方案，我们可以很容易地找到另外7个通过反射和旋转。如果不计算同一解决方案的这些变体，我们必须将结果除以8。
当我们转向5x5的方块时，我们发现即使是增强版本效率也很低。实际上，有 275305224*8 个5阶幻方。如果算法每毫秒能找到一个解决方案，那么枚举所有解决方案仍然需要25天半！不过不必气馁。通过一个简单的技巧，我们可以提高算法的速度。我们所要做的就是改变我们访问单元格的顺序。
图 5：5x5幻方的访问顺序
magic_square_5类按照上图的访问顺序解决了5x5幻方的问题。该类在行、单元格或主对角线完成时执行基本测试。在我的机器上，它每秒能找到大约一到两个解决方案。它仍然很慢，但我相信通过一些优化，可以在合理的时间内枚举所有5阶幻方。
从这个例子可以得出结论，尽早捕获无效组合非常重要，即使这意味着check_placement例程必须更复杂，因此花费更多时间。限制必须测试的组合数量所带来的好处可能远远超过在check_placement中花费的时间。通过改变填充表的顺序也可以达到同样的效果（限制组合的数量）。
跳棋
这是一个经典的棋盘游戏。要赢得游戏，您必须从棋盘上移除所有棋子，只留下最后一个。棋子可以移动到左、右、上或下两个位置，越过另一个棋子。被越过的棋子将被移除。您可以在下载区找到一个Java Applet来玩这个游戏。
要使用riddle_solver类来解决这个谜题，必须定义谜题表和元素列表。当完成31步移动时，谜题就被解决，因此谜题表的大小应该是31，并且包含赢得游戏所需的所有移动。我们还必须找到一种表示移动的方法。这是基于棋子移动的位置和移动方向（参见图4）。
图 6：移动的表示
移动根据其数值进行排序，即数值较大的移动在数值较小的移动之后进行尝试。实现的详细信息可以在solo.cpp和solo.hpp文件中找到。
链接
历史
- 2004年6月3日。初次发布