> mol5@0@bjbj22:DXX4444''''4'\\d((((((SSS
\\\\\\\$\]R_b3\SLSSS3\44((#`\[[[S4((
\[S
\[[)[)[(X(Эf'S)[
\v\0\)[`Xn`)[4444`)[SS[SSSSS3\3\$ '['[Examples and algorithms from "Artificial Intelligence ..." Luger and Stubblefield ]
SHAPE \* MERGEFORMAT
breadth first search:
begin
open = [Start]
closed =[ ]
while open <> [ ]
begin
remove leftmost state from open , call it X
if X is a goal then return (success)
else
begin
generate children of X
put X on closed
eliminate children of X on open or closed
put remaining children on right end of open
end
end
return (failure)
end
Trace of the algorithm where Start = A and Goal = U
1. open = [A] closed [ ]
2. open = [B,C,D] closed [A]
3. open = [C,D,E,F] closed [B,A]
4. open = [D,E,F,G,H] closed [C,B,A]
5. open = [E,F,G,H,I,J] closed [D,C,B,A]
6. open = [F,G,H,I,J,K,L] closed [E,D,C,B,A]
7. open = [G,H,I,J,K,L,M] (as L is already in open) closed = [F,E,D,C,B,A]
8. open = [H,I,J,K,L,M] closed [G, F,E,D,C,B,A]
9. and so on until either U is found or open = [ ]
depth first search:
begin
open = [Start]
closed =[ ]
while open <> [ ]
begin
remove leftmost state from open , call it X
if X is a goal then return (success)
else
begin
generate children of X
put X on closed
eliminate children of X on open or closed
put remaining children on left end of open
end
end
return (failure)
end
Trace of the algorithm where Start = A and Goal = U
1. open = [A] closed [ ]
2. open = [B,C,D] closed [A]
3. open = [E,F,C,D] closed [B,A]
4. open = [K,L,F,C,D] closed [E,B,A]
5. open = [S,L,F,C,D] closed [K,E,B,A]
6. open = [L,F,C,D] closed [S,K,E,B,A]
7. open = [T,F,C,D] closed = [L,S,K,E,B,A]
8. open = [F,C,D] closed = [T,L, S,K,E,B,A]
9. open = [M,C,D] (as L is already on closed) closed = [F, T, L, S,K,E,B,A]
10. open = [C,D] closed = [M,F,T,L,S,K,E,B,A]
11. open = [G,H,D] closed = [C,M,F,T, L, S,K,E,B,A]
SHAPE \* MERGEFORMAT
best first search:
begin
open = [Start]
closed =[ ]
while open <> [ ]
begin
remove leftmost state from open , call it X
if X is a goal then return the path from Start to X
else
begin
generate children of X
for each child of X do
case
the child is not on open or closed:
begin
assign the child a heuristic value
add the child to open
end
the child is already on open:
begin
if the child was reached by shorter path
then give the state on open the shorter path
end
the child is already on closed:
if the child was reached by shorter path
begin
remove the state from closed
add the child to open
end
end
put X on closed
reorder states on open by heuristic merit (left most)
end
return (failure)
end
Trace of the algorithm where Start = A and Goal = P
[Note : the heuristic is fallible: the state O has a lower value than the goal itself and is examined first]
1. open = [A5] closed [ ]
2. evaluate A5; open = [B4,C4,D6] closed [A5]
3. evaluate B4; open = [C4,E5,F5,D6] closed [B4,A5]
4. evaluate C4; open = [H3,G4,E5,F5,D6] closed [C4,B4,A5]
5. evaluate H3; open = [O2,P3,G4,E5,F5,D6] closed [H3,C4,B4,A5]
6. evaluate O2; open = [P3,G4,E5,F5,D6] closed [O2,H3,C4,B4,A5]
7. evaluate P3; the solution is found
PPA
B
PPD
C
P
I
O
H
N
G
F
E
PPR
T
L
S
K
M
J
U
PPQ
Graph for breadthfirst and depthfirst search examples
PPA5
B4
PPD6
C4
P3
I
O2
H3
N
G4
F5
E5
PPR
T
L
S
K
M
J
PPQ
Heuristic search of a hypothetical stat
8:;>TVWX[\^adghjklo}~~
TIno{˶˶˶˶˶˶˶ˮ˪hkZhkZhqRh4&vhShkZh2h1h0hJjh##Ujh##UmHnHuh##Zo(h##h 6]hI4hI46]hUh h3oh 5\h3ohI45\hI45WXYZ[]^bcdhkmno~
$dhA$gd##
$dhA$gd0$A$gdn><$ $A$a$gdU@ I ~
E
2
$dhA$gd0
$dhA$gd##2RvI
M
I
$dhA$gd0=?_a /179VW`bdgj
!"$'*.0125@AKõõõõõõõjh##UmHnHuh##h##Zo(hLhmnQhmnQhJhLhLhLhUhY$h gh0hEh4&vF7Y1b !#$()*$A$gdn><$
$dhA$gd0*.1345Ahijklmnopqr
$dhA$gdv
$dhA$gd<
$dhA$gd##$A$gdn><KLcdefgk*1vxGINlp Qz;^_ɥɹ١١١hhhhhhCJaJhhh&CJaJh&ha9_h9iha9_>*h9ih>*h9ih1>*h9ihWi>*h1hvhF?hWih<jh##Ujh##UmHnHuh##jh##U3Ja{@hT~&N P
$dhA$gdv
$dhA$gdWi
$dhA$gd
$dhA$gd1
$dhA$gdF?
$dhA$gd<;F[_'Z\
$$A$gdn><
$dA$gd{/
$dhA$gd&
$dhA$gdv
$dhA$gd</<DLWXbow[d
"$&(*,.02468:<>@BDFHJLNPTVZ\^`bdfhjlnprth##5CJ\aJh##hr5h##5CJ\aJh##Zo(h{/hIKNh
HhYCh{h<hwL $&*,0268<>BDHJNPXZ^`dfjlp$A$gdn><$prvx~$&.08:>@HJR $A$a$gdn><$A$gdn><$tvxz~$&(,.068:<>@FHJPRTVXZbdlnvx~h.\h##5\h.\h##5CJ\aJh.\h##5Z\o(hpWh##CJaJhpWh##5\hpWh##5CJ\aJhpWh##5Z\o(h##Zo(h##5CJ\aJh##hr5h##5CJ\aJ5RTXZbdlnvx$A$gdn><$@@ @
@@@h<hn><h_Uh##Zo(h##5CJ\aJh##hr5h##5CJ\aJe space
@ @
@@@
$dhA$gd<$ $A$a$gd_ $A$a$gdn><81h:p. A!"#$%(2*2Dd ~D
3@@"?Dd ~D
3@@"?J@J9'/J$A$CJ_HaJmH sH tH >A>.7 'DAB1) 'D'A*1'6JLiL ,/HD 9'/J4
l4a,k, (D' B'&E)
"%(0369<?BG
+*%$#"/
=?>@YXSRQPED]KJIH36;<)
"%(0369<?BG
!"#$%&'()*+DWXYZ[]^bcdhkmno~I~E2RvIMI7Y1b ! # $ ( ) * . 1 3 4 5 A h i j k l m n o p q r
J
a
{
@hT~&
N
P;F[_'Z\ $%'(,12459:>?CDHIKLNOQRTUWXZ[\`a00p0p000000000000000000000 00000p0p0p0p0p0p00p0p0p000 00 00p0 00 0 0000 00 00 0 00000p0p0p0p0p0p0000p00p0 00p0 0p00 0p0 0 00p0p000 0 00 00 00p0p0p0p0p0p0p00p0p0p00p0p0p00p0p0000p00p000000000000000000000000000000000000 0 00000000000p0@00@00@00@00@00@00@00@00@00@00@00@0000@00@00@00@000000000000p@00p@00p@00p@00p@00p@00p@00p@00p@00p@00p@00p@00p00p@00p@00p@00p@0000p000p00p@0p0Kt@2*pR@!@K c f __8kl@@#[k"(
&)
03 s"*?A`
1
c$X99? &)`B
2
c$D;h
3
3(3"`f
(`B
4B
c$DZB
5
SD h
6
3)6"`#$
)`B
7
c$D!{`B
:
c$D<$u%h
;
3+;"` g"
+h
<
3,<"``&&;)
,ZB
V
SDh
Y
3Y"`{[
x &)
3 s"*?!`
c$X99? &)ZB
SD;h
3"`f
ZB
B
SDZB
SD` h
3"`#$
ZB
SD!{h
3
"`;!
ZB
SD;ZB
SD<$u%h
3
"` g"
h
3"``&&;)
\
3"`
\
3"`
\
3"`
\
3"`
NB
@
SDNB
SDNB
SD\
3"`
\
3"`
NB
@
SDNB
SD\
3"`
\
3"`
\
3"`
\
3"`
NB
@
SDNB
SDNB
SDNB
!
SD\
"
3
""`
\
#
3 #"`
\
$
3$"`
\
%
3%"`
NB
&@
SDNB
'
SDNB
(
SDNB
)
SD\
*
3*"`
\
+
3+"`
NB
,@
SDNB

SD
NB
.
SD \
/
3
/"`
\
=
3="`"
\
>
3>"`&
\
?
3?"`(
\
@
3@"`'
NB
A@
SD#NB
B
SD%TB
C
c$D$\
D
3"D"`/
"\
E
3!E"`.
!TB
F@
c$D)TB
G
c$D*\
H
3'H"`@
'\
I
3&I"`?
&\
J
3%J"`>
%\
K
3$K"`<
$TB
L@
c$D9TB
M
c$D=TB
N
c$D;TB
O
c$D:\
P
3 P"`
\
Q
3Q"`5
\
R
3R"`,
\
S
3S"`7
TB
T@
c$D4TB
U
c$D3NB
W
SD6\
X
3X"`2
TB
Z@
c$D1TB
[
c$D0TB
\
c$D+\
]
3#]"`8
#B
S ?[^_`defhikopqrstuvwxyz{~! $ % & * + , . / 1 5 6 7 8 9 : ; < = > ? A B C D E F G H I J d Tpr@HrHrHr$ @r rr8 Pr Pr.lrr,0r+4Pr*4Pr(r'r&x0r%Hdr$Hdr#,r",r)0r$ @r8r/!rT$r!T8$r 8@8r
r@r$@rLh
rL$h@rX r=TdprA@HrCHrBHr>r@r?$ rF8 PrG Pr\lrRHrPrE$ rDr[rZ0rX4PrUrTx0rQ,rW0rSHr]!rLT$rOT8$rN8@8rK
rM@rJ$@rILh
rHL$h@r0X r>C
#Y[$\_8<X\!']_(`c"?Cae
9=jnr v
[
_
u
z
bg69x}J
M
p
s
39z}BEJP[^l
/7bj'dl33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333>~9r 3P
)
#%&(+02358:=?BDGIJLMOPRSUVXY\_****32&WiRvU.##Y${/2I4n><F?E,}IIKNmnQqRpW.\a9_3o4&vhkZe
HUJe_9iuy1S<1"Lm g0hwLv YC{@
H
(@@@@@UnknownGz Times New Roman5Symbol3&z Arial"qhMh?/Y24 3 H ?breadth first search********Oh+'0
8D
P\dltbreadth first search1rea****th ******Normal.dots****l.d63*Microsoft Word 10.0@T*@>@PO՜.+,0hp
**** A
breadth first search
!"$%&'()*,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[]^_`abcefghijknqsruvwxyz{}~Root Entry F`XpData
#1Table+`WordDocument:DSummaryInformation(\DocumentSummaryInformation8dCompObjgMsoDataStore`X`X
F Microsoft Word
MSWordDocWord.Document.89qDocumentLibraryFormDocumentLibraryFormDocumentLibraryFormCreate a new document." ma:contentTyp
This value indicates the number of saves or revisions. The application is responsible for updating this value after each revision.