, , , . . . : ( ) ( ). :
- ;
- ;
- ;
- , .. , . , . .
, , ( ), . , .. , . , :
. 7.1.
a , e . a e.
, , , , . , . : , , . . , , . , . , : .
, , , , . . 7.2 .
. 7.2.
, 7.3. .
. 7.3.
(. 7.3) :
|
|
((h d b a)
(i e b a)
(j e b a)
(k f c a)
(g c a))
, :
1. , ( ).
2. . , , .. . .
3. - , .
(.. , ) , . : . . FIFO . LIFO .
. , , , . , . 7.4 .
. 7.4.
: , f j . , : , b, d, h, e, i, j. : [, b, , j]. : [a, c, f].
.
DephtFirstSearch. , . .
. DephtFirstSearch PBDPPm, . PBDPPm , DephtFirstSearch . . DephtFirstSearch. , . . , , . , , , . :
|
|
- , ;
- , ;
- , ;
- , . PBDPPm . , , . DephtFirstSearch .
.
type TPNode= ^TNode;
TNode = record
Inf: array [1..10] Of Char;
Left, Right: TPNode;
end;
TPointDQueue = ^TDQueue; { }
TDQueue = record
PNTree: TPNode;
Next, Prev: TPointQueue;
end;
var Rut: TPNode;
BeginQueue,EndQueue: TPointDQueue;
{InsertDQ - }
procedure InsertDQ(var BegQue, EndQue:TPointDQueue;
NewElm: TPNode);
var WP: TpointDQueue;
Begin
New(WP);
WP^.PNTree:= NewElm;
WP^.Next:= Nil;
WP^.Prev:= Nil;
if EndQue = Nil then
Begin
BegQue:= WP; {c }
EndQue:= WP
End
Else
Begin
EndQue^.Next:= WP;
WP^.Prev:= EndQue;
EndQue:= WP
End
end; {InsertDQ}
{EmptyDQ - }
function EmptyDQ(BegQue: TPointDQueue): boolean;
Begin
if BegQue = Nil then Empty: = True
else Empty:= False
end; {EmptyDQ}
{RemoveDQEnd
}
procedure RemoveDQEnd(var BegQue,EndQue:
TpointQueue;
PrevEndQue:TpointQueue);
var WP: TpointQueue;
Begin
if Empty(BegQue) = True then Exit;
{ }
WP:= EndQue;
EndQue:= EndQue^.Prev;
Dispose(WP);
{ () ,
, , BegQue = Nil
EndQue = Nil}
if EndQue = Nil then BegQue:= Nil;
end; {RemoveQEnd}
{PBDPPm
, . ,
}
procedure PBDPPm(PTree: TPNode;
var BegQ, EndQ: TPointQueue);
Begin
{ }
InsertQ (BegQ, EndQ, PTree);
if Ptree^.Left <> Nil then
PBDPPm(PTree^.Left, BegQ, EndQ)
Else
if Ptree^.Right <> Nil then
PBDPPm(PTree^.Right, BegQ, EndQ)
end; {PBDPPm}
{DephtFirstSearch
, ,
.}
procedure DephtFirstSearch(var WRoot: TNode;
var BegQ, EndQ: TPointQueue);
var Prev, Curr: TPointQueue;
Begin
{ .}
if BegQ = EndQ then
{ -
}
PBDPPm(WRoot, BegQ, EndQ)
Else
{ .
}
Begin
Prev:= BegQ;
Curr:= BegQ^.Next;
if Curr <> Nil then
{ .
..
}
if (WRoot^.Left^.Inf=Curr^.Inf) then
|
|
Begin
{ }
DephtFirstSearch
(WRoot^.Left, Curr, EndQ);
{ }
if (WRoot^.Right = Nil) then
{ ,
,
}
RemoveQEnd
(BegQ, EndQ, PrevEndQue)
Else
{ ,
,
,
.
}
PBDPPm
(WRoot^.Right, BegQ, EndQ);
End
Else
Begin
{ }
DephtFirstSearch
(WRoot^.Right, Curr, EndQ);
{ }
RemoveQEnd(BegQ, EndQ,PrevEndQue);
{
}
End
Else
{
}
RemoveQEnd(BegQ, EndQ, PrevEndQue);
end;
end; {DephtFirstSearch}
:
Begin
BeginQueue:= Nil;
EndQueue:= Nil;
{ }
InsertQ(BeginQueue, EndQueue, Rut);
{ }
DephtFirstSearch(Rut, BeginQueue, EndQueue);
{ }
DephtFirstSearch(Rut, BeginQueue, EndQueue);
end.
:
1. :
[[]]
2. []:
[[b,], [,]]
( , .)
3. : [[d,b,a], [,b,]], . :
[[d,b,a], [,b,], [, a]]
4. [d,b,a] , . :
[[h,d,b,a], [,b,], [c,a]]
5. [h,d,b,a] . . [,b,] . :
[[i,,b,], [j,e,b,a], [c,a]]
6. [i,,b,] , [j,e,b,a] . .
, . , , . 7.5.
.7.5.
: , f j . : [, b, , d, e, i]. : [a, c, f] , [a, b, e, j].
, . , -, , . , , . -, -. , , , . . , . , -, :
|
|
- , ;
- ; , .
.
. . . , . , . , , + 1. , ..
.
type TPNode= ^TNode;
TNode = record
Inf: array [1..10] Of Char;
Left, Right: TPNode;
end;
TPointQueue = ^ TQueue;
TQueue = record
PNTree: TPNode;
Next: TPointQueue;
end;
var Rut: TPNode;
BeginQueue, EndQueue, BeginList: TpointQueue;
{ }
procedure InsertQ(var BegQue, EndQue: TPointQueue;
NewElm: TPNode);
var WP: TpointQueue;
Begin
New (WP);
WP^.PNTree:= NewElm;
WP^.Next:= Nil;
if EndQue = Nil then
Begin
BegQue:= WP; {c }
EndQue:= WP
End
Else
Begin
EndQue^.Next:= WP;
EndQue:= WP;
End
end; {InsertQ}
{ }
function EmptyQ(BegQue: TPointQueue): boolean;
Begin
if BegQue = Nil then Empty:= True
else Empty:= False
end; {EmptyQ}
{RemoveQL - , }
procedure RemoveQL(var BegQue, EndQue, BegQueL:
TPointQueue);
Begin
if Empty (BegQue) = False then
Begin
{ }
BegQueL:= BegQue;
BegQue:= BegQue^.Next;
if BegQue = Nil then EndQue:= Nil
{ () ,
, ,
BegQue = Nil EndQue = Nil}
End
end; {RemoveQL}
, , = 1- N.
procedure BreadthFirstSearch(var BegQ, EndQ:
TPointQueue);
var WP: TPointQueue;
Begin
WP:= EndQ;
Repeat
{ ,
.}
if BegQ^.PNTree^.Left <> Nil then
{ .}
InsertQ (BegQ, EndQ, WPB^.PNTree^.Left);
if BegQ^.PNTree^.Right <> Nil then
{ .}
InsertQ (BegQ, EndQ, WPB^.PNTree^.Right);
{ }
RemoveQL(BegQ, EndQ, BegL: TPointQueue);
until (BegQ = WP);
end; {BreadthFirstSearch}
:
Begin
BeginQueue:= Nil;
EndQueue:= Nil;
{ }
InsertQ (BeginQueue, EndQueue, Rut);
{ }
BreadthFirstSearch(BeginQueue, EndQueue);
{ }
BreadthFirstSearch(BeginQueue, EndQueue);
End.
:
1. :
[[]]
2. []:
[[b,], [,]]
( , .)
3. :
[[d,b,a], [,b,]]
:
[,a], [d,b,a], [,b,]]
4. [, ], . :
[[d,b,a], [,b,], [f,c,a], [g,c,a]]
, , [d,b,a] [,b,] , :
[[f,c,a],[g,c,a],[h,d,b,a],[i,e,b,a],[j,e,b,a]]
|
|
[f, c, a], f. .
:
, , , - . . (.. , ) . , . , , , . , -. , (.. ), : . s , t . n, s t, f(n). f , n f(n) . - , . f(n) , s , n. f(n) (. 7.6.): f(n) = g(n) + h(n). g(n) s n; h(n) - n t.
. 7.6. f(n) s t.
n, : s n , ( , (n, n) n e- n'). (, , s n), g(n) s n. h(n), - , , n t, . , , h(n) , .. , . h , . , h , .
. , , .. . , .. , , .. f. , f- - . . - : , , , . , . , . , , , .
7.7 . , , s t. n (n, t) n t.. , f(n)= g(n) + h(n) = g(n) + (n, t).
. 7.7 s t
7.7() . ; t. . 7.7(b) , . . . , , , .
, . : _1 a, _2 e. _1 , f , . _1 c, _2 e, :
f(c) = g(c) + h(c) = 6 + 4 = 10
f(e) = g(e) + h(e) = 2 + 7 = 9
f(e) < f(c), _2 f, _1 .
f(f) = 7 + 4 = 11
f(c) = 10
f(c) < f(f)
_2 , _1 , d, f(d)=12>11. _2, , , t.
- : . , . : . .
- . . .
- , , .