pascal深搜

NecerBac 5级 2010-10-30

深度优先搜索我也是深有其感啊，当年也是就结了很久

 

以下是我的看法和我的框架，你看看能不能帮到你

 

深度优先搜索法有两个显著特点

（1）对已产生的结点按深度排序存储，深度大的先得到扩展，即先产生它的子结点；

（2）深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此该算法应该用堆栈作为的主要数据结构存储产生的结点：先把产生的数入栈，然后产生栈顶（即深度最大的结点）的子结点。子结点产生完后，出栈（pop）再产生栈顶的子结点。

                                     

                              深度优先搜索算法描述

  程序实现有两种方式--递归与非递归。

　　递归过程为：
　　Procedure DFS(step)
　　　for i:=1 to max do
　　　　begin
  if 子结点符合条件 then
　　　　　begin
    产生新的子结点入栈；
　　　　　　if 子结点是目标结点 then 输出
　　　　　　　else DFS(step+1)；
　　　　　　栈顶结点出栈；
　　　　　end；
　　　　end；
　　主程序为：
　　Program DFS；
　　 Begin
      初始状态入栈；
　　　DFS(1)；
     End.
　　
  非递归
　　Program DEF(step)；
　　 Begin
 depth:=0;
 repeat
  if 当前节点可以扩展
   then begin
  inc(depth);
  扩展该状态的可用一种决策;  //即对拓展节点进行处理；
  if depth=目标深度 then 输出结果；
        end
   else if 该状态有其余可用方案
  then 扩展该状态的可用一种决策
  else begin
   消除当前深度的尝试对其他变量的影响；
   dec(depth);
       end;
 until depth=0;
     End.
 
----------------------------------

两种方式本质上是等价，但两者也时有区别的。

1．  递归方式实现简单，非递归方式较之比较复杂；

2．  递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。

满意答案

山水 6级 2010-10-30

一般用递归深搜

比如全排列

procedure search(x:longint);

var

 

begin

  if x=n then check(生成后的操作)

  else for i:=1 to n do if f[i] then

     begin

        f[i]:=false;

        c[x]:=i;

        search(x+1);(递归搜索下一个值)

        f[i]:=true;

    end;

end;

只是一个过程，深搜用递归编比较简单

追问：

我编的深搜就没过过，无语了。

回答：

没事没事啦，正常的，多打几次就会了

其他回答(1)

- + 5级 2010-10-30

dfs就是不断向深层扩展

procedure    dfs（x:longint);

var

    i,j,k,t:longint;

begin

      if x>深度 then

     begin

         输出结果；

          exit;

      end

else

     枚举与x相连的点j；

    if    j   可扩展  then

     begin

       操作 ；

         dfs（j）;

       回溯；

     end;

end；