如何把深度算法改为广度算法，即把递归调用改为非递归调用代码?(50分)

W

WilliamGui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-07

• #1

向大家请教，
说说算法的大致方法，过程
十二万分感谢

 

C

CJ

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-07

• #2

这个就要具体问题具体考虑了吧？似乎没有一概而论的方法了。广度也是用栈的。

 

行

行素

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-07

• #3

太笼统了，如何答起

 

F

firemeteor

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-07

• #4

需要自己实现堆栈（深度）和队列（广度）
深度优先搜索的非递归化就是把递归调用转成压栈和退栈，不过时机要具体分析
你的问题确实太笼统了

 

U

UnderAttack

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-09-11

• #5

不一定

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-13

• #6

最近在写一个小游戏，刚好用到了这两种算法

深度优先：
向节点栈中压入第一个可生长节点;
while 可生长节点数>0 do
begin
选取节点栈的第一个节点，以它为基础生成新的结点;
遍历新节点，如果达到目标状态，则跳出循环;
从可生长节点栈顶删除已使用过的第一个节点;
将新节点压入可生长节点栈;
end;

广度优先：
初始化可生长节点链表，向其中加入第一个可生长节点;
while 可生长节点链表头<>nil do
begin
新节点链表头:=nil;
遍历可生长节点链表，如果达到目标状态，则跳出循环;
遍历可生长节点链表，由各个节点分别生成新节点，加入到新节点链表中去;
释放可生长节点链表;
可生长节点链表头:=新节点链表头;
end;

上面的算法流程很粗略，实际使用中，还要采取措施以避免重复搜索（即新产生的结点状态
已经被搜索过了）。

 

B

bigroute

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-13

• #7

看

 

S

SS2000

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-21

• #8

up,hehe

 

D

dz2050

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-21

• #9

其实就是自己写一个堆栈

 

Y

youngyxy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-10-21

• #10

如果还是需要使用堆栈，那么所谓广度遍历算法与采用递归实现的深度遍历
没有运行时间上的任何优越性，而且算法本身结构不好。

 

J

jsxjd

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-15

• #11

要视具体情况！
以阶乘为例：

function jc(n:integer):integer;
begin
if n<=1 then result:=1 else
result:=n*jc(n-1);
end;

function jc2(n:integer):integer;
var
i:integer;
begin
result:=1;
for i:=2 to n do result:=result*i;
end;

 

W

WilliamGui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-11-09

• #12

.