Home  >  Article  >  php教程  >  php回溯算法解决n皇后问题

php回溯算法解决n皇后问题

WBOY
WBOYOriginal
2016-06-06 19:46:36833browse

欢迎进入Linux社区论坛,与200万技术人员互动交流 >>进入 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空

欢迎进入Linux社区论坛,与200万技术人员互动交流 >>进入

  回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。

  回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。

  回溯法指导思想--走不通,就掉头。设计过程:确定问题的解空间;确定结点的扩展规则;搜索。

  这里主要展示怎么用php实现该问题

  $tres代表一次可行的尝试

  $res 记录总结果

  详细数据结构分析 可以参考链接。

  $value){

  if($key

  if($value==$c){

  return 0;

  }else if(abs($l-$key)==abs($c-$value)){

  return 0;

  }

  }

  }

  return 1;

  }

  function scan($line){

  global $tres;

  global $res;

  global $n,$count;

  if($line==$n){

  $res[]=$tres;

  // $tres=array();

  $count++;

  }else{

  for($i=0;$i

  if(check($line,$i)==1){

  $tres[$line]=$i;

  $nxline=$line+1;

  scan($nxline);

  }

  }

  }

  }

  $tres=array();

  $res=array();

  $n=8;$count=0;

  $stime=microtime();

  scan(0);

  $etime=microtime();

  var_dump($res);

  echo there is $count ways !

  ;

  $t=$etime-$stime;

  echo (int)$t.seconds used.;

  //还有要说明的 最后面面的时间计算 不太严谨 高精度的变量php是不能直接相减的 会有严重误差。这里只做临时演示,需要精确计算还得调用相关函数。

php回溯算法解决n皇后问题

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn