强力搜索算法

下载演示应用程序 - 86 KB下载Java小程序源 - 67 KB简介
技术，解决困难的问题，使用一个计算系统之一， 是运用蛮力搜索。这意味着穷举搜索 所有可能的组合，直到找到一个解决方案。在本文中，我 将目前实施蛮力搜索算法，可以 适用于各种各样的问题。对这篇文章的想法是采取 由   ; 在CodeProject上的文章，其中提出，解决了一个C程序 爱因斯坦的谜。这篇文章的功能扩展， 为了利用面向对象编程的好处，并& #160; 产生一个通用的求解器类，可以从多个基类 特定问题的求解器类。许多问题的求解器类的例子 将提交​​，其中包括解决爱因斯坦的里德尔。
注意:执行的语言是C。虽然有些 销售先进的语言功能的使用（模板类，STL），。 在这篇文章中的技术细节都保持在最低限度，使连 经验不足的程序员可以按照蛮力的逻辑 算法，例如拼图的乐趣。
八皇后之谜
我将介绍蛮力搜索开始算法的思想 从八皇后之谜。这是众所周知的配售8问题 非攻击棋盘上的皇后。为解决这一难题的源代码 可以发现在许多软件书籍。在下载一节中，你会发现， 一个Java applet（）实现了这个谜团。
计算系统可以帮助我们迅速解决这个谜团。此外，它   ; 可以帮助我们找到所有可能的解决方案。为了这样做，我们必须指示我​​们 8皇后棋盘上的所有可能的展示位置的程序来搜索。 有一个共64！63！62！61！60！59！58！57！不同 配售。尝试搜索所有这些，这将是非常低效 不同的组合。它要解决的问题要好得多 电感。这是首先要解决的问题放置一个皇后在的 一个的1x8的棋盘上，然后放置在一个2X8的两位皇后的问题 棋盘和完整的解决方案继续下去，直到找到。在这种方式 大集团显然是错误的组合的早期发现在 过程不需要进行测试。如果有一对攻击 皇后在棋盘的第n列，则无论身在何处 其余8 - N皇后放置，组合不能构成 解决方案。   ;
感性的搜索算法的工作原理如下。我们开始放置
60; 在A1的第一个皇后。第二个皇后被放置在B3（B1和B2
60; 第一皇后的攻击）。然后，我们来看看unattacked平方米 第三列。我们将继续以同样的方式，直到我们到达一列， 没有unattacked广场。在这种情况下，我们返回到上 列和我们尝试将女王摆在那里的另一个unattacked 平方米。我们只审查比以前更高的行广场 之一。如果这是不可能的，我们将另一列，我们尝试 这样做。如果发现，我们在上一篇专栏文章中的一个新的unattacked平方米  0;准备再次向前移动。每次我们都能够放置一个皇后 & #160; 第八行，发现一个新的解决方案。我们增加一个变量，存储 0; 表中的皇后的位置，我们返回到第7列找到 一个新的unattacked平方米。当我们需要返回，搜索完成 从第2列第1列和王后是摆在A8。一个可视化 该算法可以点击"解决"按钮 以前的小程序。 泛化
感性的搜索算法的概念，可以用在更多的&# 160; 一般情况。为了能够重新使用的功能 算法，我们将定义一个"抽象"之谜。这种"抽象"之谜 代表一个N细胞的表，必须由充满未来元素 从一个有序列表（见图1）。 {S0}
图1:一般之谜
为了解决这个谜团电感我们先填写1细胞，然后细胞2等 &# 160; 直到所有的细胞都充满了。该算法的流程图
60; 如下图: {S1}
图2:流程图
，对于这种技术的工作，我们必须定义两个功能: check_placement（M）:如果检查的第一分谜语 M细胞是解决 get_next_element（E）:它给出一个元素e，返回 &# 160; 紧随其后的元素的有序列表。 &# 160;
C类riddle_solverlt; move_tgt;实现
60; "抽象"之谜。

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;

};

  

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);

}

  

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);

}