GQ+H a2`+?
HB+2 :Q
G2+im`2 e
_2/BM;b, _L 9XR- SJ 9Xd @ 9X3
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q R f j3

PmiHBM2
G2`MBM; :QHb
AMi`Q/m+iBQM iQ GQ+H a2`+?
GQ+H a2`+? H;Q`Bi?Kb
Ai2`iBp2 "2bi AKT`Qp2K2Mi
:`22/v /2b+2Mi rBi? `M/QKBxiBQM
aBKmHi2/ MM2HBM;
SQTmHiBQM@"b2/ H;Q`Bi?Kb
_2pBbBiBM; i?2 G2`MBM; ;QHb
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q k f j3
G2`MBM; :QHb
"v i?2 2M/ Q7 i?2 H2+im`2- vQm b?QmH/ #2 #H2 iQ
! .2b+`B#2 i?2 /pMi;2b Q7 HQ+H b2`+? Qp2` Qi?2` b2`+?
H;Q`Bi?KbX
! 6Q`KmHi2 `2H rQ`H/ T`Q#H2K b HQ+H b2`+? T`Q#H2KX
! o2`B7v r?2i?2` bii2 Bb HQ+Hf;HQ#H QTiBKmKX
! .2b+`B#2 bi`i2;B2b 7Q` 2b+TBM; HQ+H QTiBKX
! h`+2 i?2 2t2+miBQM Q7 ;`22/v /2b+2Mi- ;`22/v /2b+2Mi rBi?
`M/QK `2bi`ib- bBKmHi2/ MM2HBM;- M/ ;2M2iB+ H;Q`Bi?KbX
! *QKT`2 M/ +QMi`bi i?2 T`QT2`iB2b Q7 HQ+H b2`+?
H;Q`Bi?KbX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q j f j3
q?v mb2 HQ+H b2`+?\
aQ 7`- i?2 b2`+? H;Q`Bi?Kb 2tTHQ`2 i?2 bT+2 bvbi2KiB+HHv
M/ F22T i`+F Q7 QM2 Q` KQ`2 Ti?bX
! h?2 b2`+? bT+2 +M #2 iQQ #B; Q` BM}MBi2X
! 6Q` bQHpBM; *aSb- i?2 Ti? iQ ;QH Bb B``2H2pMiX
aQHmiBQM, HQ+H b2`+?
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q 9 f j3
S`QT2`iB2b Q7 HQ+H b2`+?
! 1tTHQ`2b QMHv TQ`iBQM Q7 i?2 b2`+? bT+2X
! _2[mB`2b HBiiH2 K2KQ`vX
/pMi;2b,
! *M }M/ bQHmiBQMb [mB+FHv QM p2`;2X
! qQ`Fb 7Q` *aSb M/ ;2M2`H QTiBKBxiBQM T`Q#H2KbX
.Bb/pMi;2b,
! LQ ;m`Mi22 i?i bQHmiBQM rBHH #2 7QmM/ B7 QM2 2tBbibX
*MMQi T`Qp2 i?i MQ bQHmiBQM 2tBbibX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q 8 f j3
q?i Bb HQ+H b2`+?\
! ai`i rBi? +QKTH2i2 bbB;MK2Mi Q7 pHm2b iQ p`B#H2bX
! hF2 bi2Tb iQ BKT`Qp2 i?2 bQHmiBQM Bi2`iBp2HvX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q e f j3
GQ+H a2`+?
HQ+H b2`+? T`Q#H2K +QMbBbib Q7,
! bii2 , +QKTH2i2 bbB;MK2Mi iQ HH Q7 i?2 p`B#H2bX
! M2B;?#Qm` `2HiBQM, r?B+? bii2b /Q A 2tTHQ`2 M2ti\
! +Qbi 7mM+iBQM, ?Qr ;QQ/ Bb 2+? bii2\
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q d f j3
9@Zm22Mb S`Q#H2K b GQ+H a2`+? S`Q#H2K
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q 3 f j3
Variables : Xo . Xi , Xz , Xs where Xi is the row position
of the queen in column i. Assume that there is
one queen per column . I
E LO, 1.2.33
.
Domains : Xi e fo . I , 2,33 Hi . row positions.
Initial state : 4 queens on the board in random×
Goal state : 4 queens on the board .
No pair of queens are attacking each other.
Neighbour relation :
- Version A i move a single queen to a different row
in the same column.
- Version B i swap the row positions of two queens .
9@Zm22Mb S`Q#H2K b GQ+H a2`+? S`Q#H2K
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q N f j3
Cost function : the number of pairs of queens
attacking each other, directly or indirectly .
cost - a
G2`MBM; :QHb
AMi`Q/m+iBQM iQ GQ+H a2`+?
GQ+H a2`+? H;Q`Bi?Kb
Ai2`iBp2 "2bi AKT`Qp2K2Mi
:`22/v /2b+2Mi rBi? `M/QKBxiBQM
aBKmHi2/ MM2HBM;
SQTmHiBQM@"b2/ H;Q`Bi?Kb
_2pBbBiBM; i?2 G2`MBM; ;QHb
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q Ry f j3
:`22/v /2b+2Mi
XFXX ?BHH +HBK#BM; Q` ;`22/v b+2MiX
! ai`i rBi? `M/QK bii2X
! JQp2 iQ M2B;?#Qm` rBi? i?2 HQr2bi +Qbi
B7 BiǶb #2ii2` i?M i?2 +m``2Mi bii2X
! aiQT r?2M MQ M2B;?#Qm` ?b HQr2` +Qbi i?M +m``2Mi bii2X
! PMHv `2K2K#2`b i?2 +m``2Mi MQ/2X
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q RR f j3
If a neighbour is an improvement ,
then move to the best neighbour .
Greedily : does not look beyond the immediate
neighbours.
I
4 If no neighbour is an improvement, stop !requires very
current state is one of the best
little memory . States in the neighbourhood .
:`22/v /2b+2Mi BM QM2 b2Mi2M+2
.2b+2M/ BMiQ +MvQM BM i?B+F 7Q; rBi? KM2bB
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q Rk f j3
① descend : minimize cost .
Move to a neighbour w/ a lower cost .
② thick fog : can only see immediate neighbours .
① ② ③
③ amnesia : no memory of where we've been .
may stumble on
the same state multiple
times w/ realizing it .
S`QT2`iB2b Q7 :`22/v .2b+2Mi
! S2`7Q`Kb [mBi2 r2HH BM T`+iB+2X
JF2b `TB/ T`Q;`2bb iQr`/b bQHmiBQMX
! :Bp2M 2MQm;? iBK2-
rBHH ;`22/v /2b+2Mi }M/ i?2 ;HQ#H QTiBKmK\
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q Rj f j3
the state w/ lowest cost
among all the States.
T
No
. Greedy descent can get
stuck at local optimums .
q?2`2 +M :`22/v .2b+2Mi ;2i bim+F\
! GQ+H QTiBKmK, LQ M2B;?#Qm` ?b Ubi`B+iHvV HQr2` +QbiX
! :HQ#H QTiBKmK, bii2 i?i ?b i?2 HQr2bi +Qbi
KQM; HH i?2 bii2bX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q R9 f j3
(a special type of local optimum. )
y
possible to escape it
flat local opt
strict I
cannot escape this easily .
*Z, GQ+H M/ ;HQ#H QTiBKmK URV
*Z, *QMbB/2` i?2 7QHHQrBM; bii2 Q7 i?2 9@[m22Mb T`Q#H2KX
*QMbB/2` M2B;?#Qm` `2HiBQM ", brT i?2 `Qr TQbBiBQMb Q7 irQ
[m22MbX q?B+? Q7 i?2 7QHHQrBM; Bb +Q``2+i\
Z
Z
Z
Z
UV h?Bb bii2 Bb HQ+H QTiBKmK M/ Bb ;HQ#H QTiBKmKX
U"V h?Bb bii2 Bb HQ+H QTiBKmK M/ Bb LPh ;HQ#H QTiBKmKX
U*V h?Bb bii2 Bb LPh HQ+H QTiBKmK M/ LPh ;HQ#H
QTiBKmKX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q R8 f j3
State : 3201 (2)
o
2301 (4) , 3021 (l )
0231 ( l ) 2 3102 (l )
1203 ( l ) 3 3210 (6)
*Z, GQ+H M/ ;HQ#H QTiBKmK UkV
*Z, *QMbB/2` i?2 7QHHQrBM; bii2 Q7 i?2 9@[m22Mb T`Q#H2KX
*QMbB/2` M2B;?#Qm` `2HiBQM , KQp2 bBM;H2 [m22M iQ MQi?2`
b[m`2 BM i?2 bK2 +QHmKMX q?B+? Q7 i?2 7QHHQrBM; Bb +Q``2+i\
Z
Z
Z
Z
UV h?Bb Bb HQ+H QTiBKmK M/ Bb ;HQ#H QTiBKmKX
U"V h?Bb Bb HQ+H QTiBKmK M/ Bb LPh ;HQ#H QTiBKmKX
U*V h?Bb Bb LPh HQ+H QTiBKmK M/ LPh ;HQ#H QTiBKmKX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q Re f j3
22 4 cost -_ 2
3 34
3 3 2
33 2
1b+TBM; ~i HQ+H QTiBKmKb
! aB/2rv KQp2b, HHQr i?2 H;Q`Bi?K iQ KQp2 iQ M2B;?#Qm`
i?i ?b i?2 bK2 +QbiX
! h#m HBbi, F22T bKHH HBbi Q7 `2+2MiHv pBbBi2/ bii2b
M/ 7Q`#B/ i?2 H;Q`Bi?K iQ `2im`M iQ i?Qb2 bii2bX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q Rd f j3
stop after a # of consecutive sideway moves
some short term memory .
S2`7Q`KM+2 Q7 :`22/v .2b+2Mi rBi? bB/2rv KQp2b
3@[m22Mb T`Q#H2K, ≈ Rd KBHHBQM bii2bX
! :`22/v /2b+2Mi
W Q7 BMbiM+2b bQHp2/, R9W
O Q7 bi2Tb mMiBH bm++2bbf7BHm`2, j@9 bi2Tb QM p2`;2 mMiBH
bm++2bb Q` 7BHm`2X
! :`22/v /2b+2Mi Y ≤ Ryy +QMb2+miBp2 bB/2rv KQp2b,
W Q7 BMbiM+2b bQHp2/, N9W
O Q7 bi2Tb mMiBH bm++2bbf7BHm`2, kR bi2Tb mMiBH bm++2bb M/ e9
bi2Tb mMiBH 7BHm`2X
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q R3 f j3
G2`MBM; :QHb
AMi`Q/m+iBQM iQ GQ+H a2`+?
GQ+H a2`+? H;Q`Bi?Kb
Ai2`iBp2 "2bi AKT`Qp2K2Mi
:`22/v /2b+2Mi rBi? `M/QKBxiBQM
aBKmHi2/ MM2HBM;
SQTmHiBQM@"b2/ H;Q`Bi?Kb
_2pBbBiBM; i?2 G2`MBM; ;QHb
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q RN f j3
_M/QK `2bi`ib M/ `M/QK rHFb
:`22/v /2b+2Mi +M ;2i bim+F i HQ+H QTiBKmK
Ui?i Bb MQi ;HQ#H QTiBKmKVX q?i +M r2 /Q\
! _M/QK `2bi`ib,
`2bi`i b2`+? BM /Bz2`2Mi T`i Q7 i?2 bT+2X
1tKTH2, :`22/v /2b+2Mi rBi? `M/QK `2bi`ib
! _M/QK rHFb,
KQp2 iQ bii2 rBi? ?B;?2` +Qbi Q++bBQMHHvX
1tKTH2, aBKmHi2/ MM2HBM;
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q ky f j3
_M/QK `2bi`ib pb `M/QK rHFb
URV q?B+? ivT2 Q7 `M/QKBxiBQM Bb #2ii2` 7Q` HM/b+T2 UV \
UV _M/QK `2bi`ib
U"V _M/QK rHFb
UkV q?B+? ivT2 Q7 `M/QKBxiBQM Bb #2ii2` 7Q` HM/b+T2 U#V \
UV _M/QK `2bi`ib
U"V _M/QK rHFb
(a) (b)
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q kR f j3
a global random move .
a local random move .
Ms. . :*. .
←→
* •
Ds D
:`22/v /2b+2Mi rBi? `M/QK `2bi`ib
A7 i }`bi vQm /QMǶi bm++22/- i`v- i`v ;BMX
! S2`7Q`Kb KmHiBTH2 ;`22/v /2b+2Mib
7`QK `M/QKHv ;2M2`i2/ BMBiBH bii2bX
! qBHH ;`22/v /2b+2Mi rBi? `M/QK `2bi`ib
}M/ i?2 ;HQ#H QTiBKmK\
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q kk f j3
It will find the global optimum w/ probability
approaching 1 . Eventually , it will generate
the global optimum as the initial state .
G2`MBM; :QHb
AMi`Q/m+iBQM iQ GQ+H a2`+?
GQ+H a2`+? H;Q`Bi?Kb
Ai2`iBp2 "2bi AKT`Qp2K2Mi
:`22/v /2b+2Mi rBi? `M/QKBxiBQM
aBKmHi2/ MM2HBM;
SQTmHiBQM@"b2/ H;Q`Bi?Kb
_2pBbBiBM; i?2 G2`MBM; ;QHb
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q kj f j3
aQ 7`XXX
:`22/v /2b+2Mi 7Q+mb2b QM QTiBKBxiBQMf2tTHQBiiBQM-
r?2`2b `M/QK KQp2b HHQr mb iQ 2tTHQ`2 i?2 b2`+? bT+2X
*M r2 +QK#BM2 2tTHQ`iBQM M/ QTiBKBxiBQM BMiQ QM2 H;Q`Bi?K\
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q k9 f j3
aBKmHi2/ MM2HBM;
! MM2HBM;, bHQrHv +QQH /QrM KQHi2M K2iHb
iQ KF2 i?2K bi`QM;2`X
! ai`i rBi? ?B;? i2KT2`im`2 M/ `2/m+2 Bi bHQrHvX
! i 2+? bi2T- +?QQb2 `M/QK M2B;?#Qm`X
A7 i?2 M2B;?#Qm` Bb M BKT`Qp2K2Mi- KQp2 iQ BiX
A7 i?2 M2B;?#Qm` Bb MQi M BKT`Qp2K2Mi-
KQp2 iQ i?2 M2B;?#Qm` T`Q##BHBbiB+HHv /2T2M/BM; QM
! i?2 +m``2Mi i2KT2`im`2 h
! ?Qr Km+? rQ`b2 Bb i?2 M2B;?#Qm` +QKT`2/ iQ +m``2Mi bii2
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q k8 f j3
>Qr HBF2Hv /Q r2 KQp2 iQ rQ`b2 M2B;?#Qm`\
Bb i?2 +m``2Mi bii2 M/ ′ Bb i?2 rQ`b2 M2B;?#Qm`X
G2i ∆* = +Qbi(′)− +Qbi()X h?2 +m``2Mi i2KT2`im`2 Bb hX
q2 KQp2 iQ i?2 M2B;?#Qm` ′ rBi? T`Q##BHBiv
2−∆*h
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q ke f j3
Gibbs distribution ( Boltzmann distribution .
*Z, S`Q##BHBiv Q7 KQpBM; iQ rQ`b2 M2B;?#Qm`
*Z R, Bb i?2 +m``2Mi bii2 M/ ′ Bb i?2 rQ`b2 M2B;?#Qm`X
G2i ∆* = +Qbi(′)− +Qbi()X
b h /2+`2b2b- ?Qr /Q2b i?2 T`Q##BHBiv Q7
KQpBM; iQ i?2 rQ`b2 M2B;?#Qm` U2−∆*h V +?M;2\
UV b h /2+`2b2b- r2 `2 KQ`2 HBF2Hv iQ KQp2 iQ i?2 M2B;?#Qm`X
U"V b h /2+`2b2b- r2 `2 H2bb HBF2Hv iQ KQp2 iQ i?2 M2B;?#Qm`X
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q kd f j3
Oc > O , -170, ¥70 . Tlv , #T . - Eth , e-¥4
Of 10 -1=100 e-
'0/100
= e
-0-1=0.9
-1=10 e-
""O
= e
-'
= 0.36
*Z, S`Q##BHBiv Q7 KQpBM; iQ rQ`b2 M2B;?#Qm`
*Z k, Bb i?2 +m``2Mi bii2 M/ ′ Bb i?2 rQ`b2 M2B;?#Qm`X
G2i ∆* = +Qbi(′)− +Qbi()X
b ∆* BM+`2b2b Ui?2 M2B;?#Qm` #2+QK2b rQ`b2V- ?Qr /Q2b
i?2 T`Q##BHBiv Q7 KQpBM; iQ i?2 rQ`b2 M2B;?#Qm` U2−∆*h V +?M;2\
UV b ∆* BM+`2b2b- r2 `2 KQ`2 HBF2Hv iQ KQp2 iQ i?2 M2B;?#Qm`X
U"V b ∆* BM+`2b2b- r2 `2 H2bb HBF2Hv iQ KQp2 iQ i?2 M2B;?#Qm`X
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q k3 f j3
ooo
, -170 , ¥70 . OCT , T . - ¥4 , e-Flu
-1=10 OC - IO e
- 1%0=0.36
.
oC= too e- 10%0=0.000045
.
aBKmHi2/ MM2HBM; H;Q`Bi?K
H;Q`Bi?K R aBKmHi2/ MM2HBM;
R, +m``2Mi ← BMBiBH@bii2
k, h ← H`;2 TQbBiBp2 pHm2
j, r?BH2 h > y /Q
9, M2ti ← `M/QK M2B;?#Qm` Q7 +m``2Mi
8, ∆*← +QbiUM2tiV @ +QbiU+m``2MiV
e, B7 ∆* < y i?2M
d, +m``2Mi ← M2ti
3, 2Hb2
N, +m``2Mi ← M2ti rBi? T`Q##HBiv T = 2−∆*h
Ry, /2+`2b2 h
RR, `2im`M +m``2Mi
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q kN f j3
current do
← next nothing
⇒
O P a
MM2HBM; a+?2/mH2
>Qr b?QmH/ r2 /2+`2b2 h\
! AM i?2Q`v- r2 rMi iQ /2+`2b2 i?2 i2KT2`im`2 p2`v bHQrHvX
! AM T`+iB+2- TQTmH` b+?2/mH2 Bb ;2QK2i`B+ +QQHBM;X
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q jy f j3
If the temperature decreases slowly enough ,
simulated annealing is guaranteed to find the global optimum
with probability approaching 1 .
Start w/ T= 10 . Multiply by 0.99 at each step.
aBKmHi2/ MM2HBM; Bb HBF2 HB72XXX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q jR f j3
G2`MBM; :QHb
AMi`Q/m+iBQM iQ GQ+H a2`+?
GQ+H a2`+? H;Q`Bi?Kb
Ai2`iBp2 "2bi AKT`Qp2K2Mi
:`22/v /2b+2Mi rBi? `M/QKBxiBQM
aBKmHi2/ MM2HBM;
SQTmHiBQM@"b2/ H;Q`Bi?Kb
_2pBbBiBM; i?2 G2`MBM; ;QHb
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q jk f j3
"2K a2`+?
! _2K2K#2` F bii2bX
! *?QQb2 i?2 F #2bi bii2b Qmi Q7 HH Q7 i?2 M2B;?#Q`bX
! F +QMi`QHb bT+2 M/ T`HH2HBbKX
q?i Bb #2K b2`+? r?2M F = R\
>Qr Bb #2K b2`+? /Bz2`2Mi 7`QK F `M/QK `2bi`ib BM T`HH2H\
`2 i?2`2 T`Q#H2Kb rBi? #2K b2`+?\
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q j9 f j3
① greedy descent
②
③
② w/ random restarts, each search is independent of the others.
for beam search, useful info is passed among parallel searches.
③ suffers from a lack of diversity among the k States.
can quickly become concentrated in a small region .
aiQ+?biB+ "2K a2`+?
! *?QQb2 i?2 F bii2b T`Q##BHBbiB+HHvX
! S`Q##BHBiv Q7 +?QQbBM; M2B;?#Qm` Bb
T`QTQ`iBQMH iQ Bib }iM2bbX
! JBMiBMb /Bp2`bBiv BM i?2 TQTmHiBQM Q7 bii2bX
! JBKB+b Mim`H b2H2+iBQMX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q j8 f j3
:2M2iB+ H;Q`Bi?K
! JBMiBM TQTmHiBQM Q7 F bii2bX
! _M/QKHv +?QQb2 irQ bii2b iQ `2T`Q/m+2X
S`Q##BHBiv Q7 +?QQbBM; bii2 7Q` `2T`Q/m+iBQM Bb
T`QTQ`iBQMH iQ i?2 }iM2bb Q7 i?2 bii2X
! hrQ T`2Mi bii2b +`QbbQp2` iQ T`Q/m+2 +?BH/ bii2X
! h?2 +?BH/ bii2 Kmii2b rBi? bKHH T`Q##BHBivX
! _2T2i i?2 bi2Tb #Qp2 iQ T`Q/m+2 M2r TQTmHiBQMX
! _2T2i mMiBH i?2 biQTTBM; +`Bi2`B Bb biBb}2/X
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q je f j3
stochastic beam search - asexual reproduction
genetic algorithm - sexual reproduction .
"
I
*QKT`BM; ;`22/v /2b+2Mi M/ ;2M2iB+ H;Q`Bi?K
! >Qr /Q i?2 H;Q`Bi?Kb 2tTHQ`2 i?2 bii2 bT+2\
:`22/v /2b+2Mi ;2M2`i2b M2B;?#Qm`b Q7 i?2 bii2 #b2/ QM
i?2 M2B;?#Qm` `2HiBQMX
:2M2iB+ H;Q`Bi?K XXX
! >Qr /Q i?2 H;Q`Bi?Kb QTiBKBx2 i?2 [mHBiv Q7 i?2 TQTmHiBQM\
:`22/v /2b+2Mi KQp2b iQ i?2 #2bi M2B;?#Qm`X
:2M2iB+ H;Q`Bi?K XXX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q jd f j3
crosses over parent States randomly to
produce a child state and mutates the child state .
chooses parent States probabilistically
based on the fitness of the States .
_2pBbBiBM; i?2 G2`MBM; :QHb
"v i?2 2M/ Q7 i?2 H2+im`2- vQm b?QmH/ #2 #H2 iQ
! .2b+`B#2 i?2 /pMi;2b Q7 HQ+H b2`+? Qp2` Qi?2` b2`+?
H;Q`Bi?KbX
! 6Q`KmHi2 `2H rQ`H/ T`Q#H2K b HQ+H b2`+? T`Q#H2KX
! o2`B7v r?2i?2` bii2 Bb HQ+Hf;HQ#H QTiBKmKX
! .2b+`B#2 bi`i2;B2b 7Q` 2b+TBM; HQ+H QTiBKX
! h`+2 i?2 2t2+miBQM Q7 ;`22/v /2b+2Mi- ;`22/v /2b+2Mi rBi?
`M/QK `2bi`ib- bBKmHi2/ MM2HBM;- M/ ;2M2iB+ H;Q`Bi?KbX
! *QKT`2 M/ +QMi`bi i?2 T`QT2`iB2b Q7 HQ+H b2`+?
H;Q`Bi?KbX
*a 93e AMi`Q/m+iBQM iQ `iB}+BH AMi2HHB;2M+2 aT`BM; kyky HB+2 :Q j3 f j3

欢迎咨询51作业君