Page 1
Mo
tyw
acj
a
Jest
esm
yek
sper
tem
/dor
adca
wje
dnej
zag
encj
irz
adow
ych,
iw
nied
ziel
ew
iecz
orem
prez
esag
encj
idz
won
ido
nas
nako
mor
k e,
zeby
poi
nfor
mow
ac,
zew
pon
iedz
ia le
kra
noo
godz
inie
10-t
ejod
bed
zie
sie
waz
nana
rada
wM
inis
ters
twie
Infr
astr
uktu
ry,
iko
niec
zna
jest
nasz
ani
ezaw
odna
obec
nosc
.
Co
robi
c?
Mam
yw
iele
moz
liwos
ci,
moz
emy
wro
cic
doko
lacj
iz
rodz
ina,
moz
emy
pojs
cna
spac
erze
bysi
eod
stre
sow
ac.
Wie
my
jedn
ak,
zem
usim
yza
plan
owac
pod
roz
doW
arsz
awy.
Sam
olot
nie
jest
dobr
aop
cja.
Wta
nich
linia
chlo
tnic
zych
wsz
ystk
iem
iejs
casa
daw
now
ykup
ione
,a
wL
OT
sap
ewni
eje
szcz
em
iejs
ca,
ale
jak
rano
bed
zie
mg l
ai
sam
olot
nie
odle
ci,
tozo
staw
imy
szef
ana
lodz
ie,
ip
otem
pew
nie
moz
emy
sie
juz
wog
ole
nie
pok
azyw
acw
agen
cji
(odp
raw
epr
zysl
ana
mna
kont
o).
Co
gors
za,
PK
Pw
dzis
iejs
zych
czas
ach
row
niez
ma
zwyc
zaj
odw
o lyw
acp
ocia
giz
dnia
nadz
ien,
ini
em
ap
ewno
sci,
czy
moz
emy
liczy
cna
nocn
yp
ocia
g1:
32(j
est
wW
arsz
awie
o7:
32).
Moz
emy
spra
wdz
icte
opcj
e,al
em
oze
sie
okaz
ac,
zecz
eka
nas
jazd
asa
moc
hode
m.
Met
od
ypr
zesz
uki
wan
ia—
mo
tyw
acja
1
Ogo
lnie
,je
stsz
ereg
moz
liwos
ci,
kazd
az
nich
wym
aga
star
anne
goro
zwaz
enia
.P
row
adzi
todo
prz
esz
uk
iwa
nia
.
Prz
eszu
kiw
anie
jest
elem
ente
msk
lado
wym
wsz
ystk
ich
met
odsz
tucz
nej
inte
ligen
cji,
izd
olno
scsk
utec
zneg
opr
zesz
ukiw
ania
wog
ole
zdaj
esi
eby
cin
here
ntny
mel
emen
tem
inte
ligen
cji.
Met
od
ypr
zesz
uki
wan
ia—
mo
tyw
acja
2
Re
pre
zen
tacj
aw
prz
est
rze
ni
sta
no
w
1.op
ispr
zest
rzen
ist
anow
•cz
esto
prze
strz
enm
oze
mie
cp
osta
cilo
czyn
uka
rtez
jans
kieg
odz
iedz
inpa
ram
etro
wop
isu
•pr
zest
rzen
moz
eby
csk
oncz
ona
lub
nies
konc
zona
,ch
ocni
em
usi
toby
czw
iaza
nez
trud
nosc
iapr
oble
mu
(np.
szac
hy)
•cz
asem
czes
cca
lej
form
alni
ezd
efini
owan
ejpr
zest
rzen
ist
anow
iast
any
nied
ozw
olon
e(i
nacz
ej:
nieo
siag
alne
)
2.op
isst
anu
poc
zatk
oweg
o,za
wsz
eja
wny
3.op
isst
anu
celo
weg
o,ja
wny
lub
niej
awny
(war
unek
osia
gnie
cia
celu
)
4.op
isdo
step
nych
oper
ator
owpr
zejs
cia
odst
anu
dost
anu
•np
.w
pos
taci
war
unko
wst
osow
alno
sci
ief
ekto
wdz
ia la
nia
•op
erat
orm
oze
byc
spar
amet
ryzo
wan
y(n
p.w
labi
rync
iem
ozem
ym
iec
jede
nop
erat
orru
chu,
czte
ryop
erat
ory,
alb
olic
zbe
mie
jsc
razy
czte
ry)
⇒Z
adan
iem
jest
wyz
nacz
enie
sekw
encj
iop
erat
orow
prow
adza
cych
zest
anu
poc
zatk
oweg
odo
celo
weg
o.
Met
od
ypr
zesz
uki
wan
ia—
repr
ezen
tacj
aw
prze
strz
eni
stan
ow
3
Og
oln
ysc
he
ma
tp
rze
szu
kiw
an
iaw
prz
est
rze
ni
sta
no
w
PROCEDUREGT(St)
;St-
opisstanupoczatkowego
BEGIN
UNTILTerm(St)DO
;stanStspelniawarunekcelu
BEGIN
Op:=first(ApplOps(St));
wybierzoperatorstosowalnywstanieSt
St:=Apply(Op,St)
;rezultatzastosowaniaOpdo
stanuSt
END
END
Co
praw
dap
owyz
szy
zapi
sal
gory
tmu
GT
(Generate-and-Test)
suge
ruje
,ze
wyb
iera
onpi
erw
szy
moz
liwy
doza
stos
owan
iaw
stan
ieS
top
erat
or,
jedn
akal
gory
tmm
aw
p lyw
nate
nw
ybor
oper
ator
apr
zez
odp
owie
dnie
pos
orto
wan
ielis
tyop
erat
orow
.M
etod
ew
ybor
uop
erat
ora
prze
zal
gory
tmpr
zesz
ukiw
ania
nazy
wam
yst
rate
gia
.
Zas
toso
wan
iedo
brej
stra
tegi
ije
stw
algo
rytm
ach
prze
szuk
iwan
iaza
gadn
ieni
emkl
uczo
wym
.
Met
od
ypr
zesz
uki
wan
ia—
repr
ezen
tacj
aw
prze
strz
eni
stan
ow
4
Page 2
Str
ate
gie
sle
pe
ip
oin
form
ow
an
e
Str
ateg
iam
oze
byc
ca lk
owic
ieog
olna
,ba
zuja
caty
lko
nasy
ntak
tycz
nych
w la
snos
ciac
hre
prez
enta
cji
zaga
dnie
nia,
ida
jaca
sie
wyk
orzy
stac
we
wsz
ystk
ich
moz
liwyc
hpr
zypa
dkac
h.T
akie
stra
tegi
ena
zyw
asi
esl
ep
ymi.
Prz
yk la
d:ca
lkie
muz
ytec
zna
slep
a(i
todo
s low
nie)
stra
tegi
aw
prze
szuk
iwan
iula
biry
ntow
jest
stra
tegi
apr
awej
reki
.S
trat
egia
tap
ozw
ala
znal
ezc
wyj
scie
zla
biry
ntu,
jesl
ity
lko
tako
we
istn
ieje
.
Str
ateg
iem
oga
row
niez
wyk
orzy
styw
acin
form
acje
ost
anie
,sp
ecyfi
czne
dla
dane
jdz
iedz
iny
prob
lem
owej
.T
akie
stra
tegi
ena
zyw
amy
po
info
rmo
wa
nym
i.
Str
ateg
iep
oinf
orm
owan
eko
rzys
taja
zin
form
acji,
ktor
ew
ogol
nym
przy
padk
uni
esa
dost
epne
,i
mog
aby
cni
ezro
zum
ia le
dla
osob
yp
ostr
onne
j,or
azdl
aca
lkow
icie
ogol
nego
algo
rytm
upr
zesz
ukiw
ania
.
Prz
yk la
d:w
yobr
azm
yso
bie,
zep
oszu
kuja
cw
yjsc
iaz
labi
rynt
uw
iem
y,ze
naze
wna
trz
jest
ha la
s(n
p.sz
umm
orza
),a
wla
biry
ncie
ca lk
owit
aci
sza.
Wte
dyzw
ycza
jne
nads
luch
iwan
iew
ew
szys
tkic
hki
erun
kach
mog
loby
byc
zrod
lem
stra
tegi
ip
oinf
orm
owan
ej,
pom
agaj
acw
wyb
orze
w la
sciw
ych
krok
ow(c
hoc
stra
tegi
ata
moz
eby
csk
utec
zna
tylk
ow
pew
nej
niew
ielk
iej
odle
g los
ciod
wyj
scia
).
Met
od
ypr
zesz
uki
wan
ia—
po
dst
awow
est
rate
gie
5
Prz
esz
uk
iwa
nie
nie
od
wra
caln
ei
zin
tro
spe
kcj
a
Moz
naro
zpat
ryw
acdw
ap
odej
scia
doza
gadn
ieni
apr
zesz
ukiw
ania
:
•gd
yis
tnie
jem
ozliw
osc
intr
osp
ekc
ji,
tozn
aczy
wgl
adu
wca
lapr
zest
rzen
prze
szuk
iwan
ia,
alb
oin
acze
j:sy
mul
acji
rozw
iaza
nia
”nasu
cho”
,al
bo
inac
zej:
cofa
nia
ruch
ow,
•gd
yta
kiej
moz
liwos
cini
em
ai
wyk
onyw
ane
ruch
ysa
nie
od
wra
caln
e.
⇒N
awet
jesl
ip
osia
dam
yko
mpl
etny
ist
upro
cent
owo
pew
nyop
isza
gadn
ieni
ato
intr
osp
ekcj
am
oze
byc
ogra
nicz
ona
prze
zw
ielk
osc
prze
strz
eni,
np.
szac
hy.
⇒z
kole
iw
niek
tory
chza
gadn
ieni
ach
wsz
ystk
ieop
erat
ory
mog
am
iec
oper
ator
yod
wro
tne,
copr
akty
czni
eda
jem
ozliw
osc
cofa
nia
ruch
ow,
naw
etje
sli
teor
etyc
znie
ona
nie
istn
ieje
.W
tedy
jedn
akm
ozliw
esa
pet
le.
Met
od
ypr
zesz
uki
wan
ia—
po
dst
awow
est
rate
gie
6
Za
ga
dn
ien
iate
sto
we
—m
isjo
nar
zei
ka
nib
ale
Sfo
rmu l
owan
osz
ereg
zaga
dnie
nte
stow
ych
(toy
problems)
—pr
osty
chi
pog
lado
wyc
h—
ale
zaw
iera
jacy
chja
kas
trud
nosc
,p
ozw
alaj
aca
spra
wdz
icp
odst
awow
em
ozliw
osci
algo
rytm
owro
zwia
zyw
ania
prob
lem
ow.
Jedn
ymz
taki
chza
gadn
ien
test
owyc
hje
stpr
oble
mm
isjo
nar
zyi
kan
iba
li:
•3
mis
jona
rzy
i3
kani
bali
naje
dnym
brze
gurz
eki,
•dw
uoso
bow
a lo
dz,
•na
lezy
prze
praw
icw
szys
tkic
hna
drug
ibr
zeg
rzek
ita
k,ab
ylic
zba
kani
bali
wza
dnym
mie
jscu
icz
asie
nie
prze
krac
za la
liczb
ym
isjo
narz
y.
Met
od
ypr
zesz
uki
wan
ia—
po
dst
awow
est
rate
gie
7
Pro
ble
mm
a lp
yi
ba
na
no
w
Inny
mkl
asyc
znym
zaga
dnie
niem
test
owym
jest
prob
lem
ma
lpy
ib
an
an
ow
:
•m
a lpa
wza
mkn
iety
mp
okoj
u,
•na
sufi
cie
wis
zaba
nany
,zb
ytw
ysok
oby
ma l
pam
og la
ich
dosi
egna
c,
•z
bok
ust
oist
o l,
zkt
oreg
om
og la
bydo
sieg
nac
bana
now
,gd
yby
good
pow
iedn
iopr
zesu
nac.
Met
od
ypr
zesz
uki
wan
ia—
po
dst
awow
est
rate
gie
8
Page 3
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.Z
czeg
osk
lada
sie
repr
ezen
tacj
apr
oble
mu
wpr
zest
rzen
ist
anow
?
2.C
oto
sasl
epe
ip
oinf
orm
owan
est
rate
gie
prze
szuk
iwan
ia?
Czy
msi
ero
znia
?
Met
od
ypr
zesz
uki
wan
ia—
po
dst
awow
est
rate
gie
9
Met
od
ypr
zesz
uki
wan
ia—
po
dst
awow
est
rate
gie
10
Prz
esz
uk
iwa
nie
zn
awra
can
iem
(BT
)
FUNCTIONBT(st)
BEGIN
IFTerm(st)
THENRETURN(NIL)
;trywialnerozwiazanie
IFDeadEnd(st)
THENRETURN(FAIL)
;brakrozwiazania
ops:=ApplOps(st)
;listaoper.stosowalnych
L:IFnull(ops)
THENRETURN(FAIL)
;brakrozwiazania
o1:=first(ops)
ops:=rest(ops)
st2:=Apply(o1,st)
path:=
BT(st2)
IFpath==FAIL
THENGOTOL
RETURN(push(o1,path))
END
Alg
oryt
mB
Tsk
utec
znie
prze
szuk
uje
prze
strz
enro
zwia
zan
bez
jaw
nego
budo
wan
iadr
zew
apr
zesz
ukiw
ania
prze
strz
eni.
Str
uktu
ryja
kich
uzyw
ado
zapa
mie
tani
ast
anu
prze
szuk
iwan
sani
ejaw
ne(n
ast
osie
).M
ozna
skon
stru
owac
iter
acyj
naw
ersj
ete
goal
gory
tmu,
ktor
abu
duje
test
rukt
ury
jaw
nie.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zn
awra
can
iem
11
Prz
esz
uk
iwa
nie
zn
awra
can
iem
—w
lasn
osc
i
BT
ma
min
imal
new
ymag
ania
pam
ieci
owe.
Wtr
akci
epr
acy
pam
ieta
tylk
op
ojed
yncz
asc
iezk
edo
rozw
iaza
nia
(ora
zp
ewie
nko
ntek
stdl
aka
zdeg
oel
emen
tute
jsc
iezk
i).
Zat
emje
goz l
ozo
no
scp
am
ieci
ow
ap
rzyp
ad
ku
sre
dn
ieg
ow
yno
siO(d),
gdzi
ed
-od
leg l
osc
stan
up
ocza
tkow
ego
odro
zwia
zani
a(w
sens
ielic
zby
oper
ator
ow).
Efe
ktyw
nosc
czas
owa
jest
gors
za.
Wna
jgor
szym
przy
padk
ual
gory
tmB
Tm
oze
od
wie
dzi
cw
szys
tkie
sta
ny
prz
est
rze
ni
prze
dzn
alez
ieni
emro
zwia
zani
a.P
ozw
ala
jedn
akna
uzyc
iest
rate
gii
—p
oinf
orm
owan
ejlu
bsl
epej
—w
mom
enci
etw
orze
nia
listy
oper
ator
ow,
prze
zje
jod
pow
iedn
iep
osor
tow
anie
.
Pow
azny
mpr
oble
mem
algo
rytm
uB
Tje
stfa
kt,
zem
oze
on
nie
zna
lezc
rozw
iaza
nia
,na
wet
jesl
iis
tnie
jeon
ow
niew
ielk
iej
odle
g los
ciod
stan
ust
arto
weg
o.Je
sli
np.
prze
strz
enst
anow
jest
nies
konc
zona
,al
gory
tmm
oze
wp
ewny
mm
omen
cie
prze
szuk
iwan
iaw
ybra
cop
erat
orpr
owad
zacy
dost
anu,
zkt
oreg
opr
owad
zadr
ogi
doni
esko
nczo
nej
liczb
yst
anow
,al
eza
den
zni
chni
eje
stst
anem
doce
low
ym.
Wta
kim
przy
padk
ual
gory
tmB
Tni
gdy
nie
zako
nczy
prze
szuk
iwan
iate
jcz
esci
prze
strz
eni
stan
ow,
ini
gdy
nie
bed
zie
mog
lw
ycof
acsi
ez
niew
lasc
iweg
ow
ybor
uop
erat
ora.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zn
awra
can
iem
12
Page 4
Wyk
ryw
an
iep
ow
tarz
aja
cych
sie
sta
no
w
Jedn
ymz
prob
lem
owal
gory
tmu
BT
—ja
kro
wni
ezw
szys
tkic
hin
nych
algo
rytm
owpr
zesz
ukiw
ania
—je
stm
ozliw
osc
pow
staw
ania
pet
li.Je
sli
algo
rytm
kied
ykol
wie
kw
ygen
eruj
eop
isst
anu,
dokt
oreg
odo
szed
l,al
ekt
ory
juz
istn
ieje
naje
godr
odze
odst
anu
poc
zatk
oweg
o,to
nieu
chro
nnie
zacz
nie
pow
tarz
acba
dani
est
anow
wcz
esni
ejzb
adan
ych.
Zja
wis
kute
mu
moz
naoc
zyw
isci
eza
pob
iec.
Naj
pros
tszy
msp
osob
emby
loby
spra
wdz
enie
,p
ow
ygen
erow
aniu
kazd
ego
now
ego
stan
u,cz
yte
nst
anni
ezn
ajdu
jesi
eju
zna
biez
acej
scie
zce
odst
anu
poc
zatk
oweg
o.
Moz
naro
wni
ezsp
raw
dzic
dok l
adni
ej—
czy
now
ow
ygen
erow
any
stan
nie
zost
a lju
zw
ogol
eki
edyk
olw
iek
wcz
esni
ejzn
alez
iony
,i
zbad
any.
Wym
aga
topa
mie
tani
azb
ioru
stan
owzb
adan
ych,
tzw
.lis
tyClosed
.L
ista
taw
algo
rytm
iere
kure
ncyj
nym
mus
iby
cgl
obal
nai
kazd
yno
wo
wyg
ener
owan
yop
isst
anu
mus
iby
cp
orow
nyw
any
zew
szys
tkim
ist
anam
iju
zob
ecny
mi
nalis
cie.
Jedn
oi
drug
iesp
raw
dzan
ieje
stdo
scko
szto
wne
oblic
zeni
owo.
Dla
zaos
zcze
dzen
iacz
asu
moz
naje
pom
inac
,ry
zyku
jac
jedn
akza
pet
leni
epr
oced
ury.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zn
awra
can
iem
13
Og
ran
icze
nie
g le
bo
ko
sci
zit
era
cyjn
ymp
og
leb
ian
iem
Pow
azny
mpr
oble
mem
dla
algo
rytm
uB
Tsa
nies
konc
zone
prze
strz
enie
,z
ktor
ymi
algo
rytm
ogol
nie
sobi
eni
era
dzi.
Pod
obni
ezr
eszt
aja
kin
neal
gory
tmy
och
arak
terz
e(h
ura-
)opt
ymis
tycz
nym
,kt
ore
pref
eruj
am
arsz
dopr
zodu
,o
ilety
lko
jest
moz
liwy.
Pro
stym
rozw
iaza
niem
jest
og
ran
icze
nie
g le
bo
kosc
ipr
zesz
ukiw
ania
doja
kiej
s
”rozs
adne
j”w
arto
sci.
Zau
waz
my,
zep
oza
zab
ezpi
ecze
niem
prze
dni
esko
nczo
nym
ipr
zest
rzen
iam
i,za
bez
piec
zaon
oje
dnoc
zesn
iepr
zed
wpa
dnie
ciem
wp
etle
,co
poz
wal
ap
omin
acw
ykry
wan
iep
owta
rzaj
acyc
hsi
est
anow
.W
ogol
nym
przy
padk
um
oze
nie
byc
jedn
ak la
twe
okre
slen
ieta
kiej
war
tosc
i,a
jej
nied
osza
cow
anie
groz
ioc
zyw
isci
ep
oraz
kaal
gory
tmu
ini
ezna
lezi
enie
mro
zwia
zani
a,kt
ore
istn
ieje
.
Dla
szer
egu
algo
rytm
owp
odob
nie
jak
BT
opty
mis
tycz
nych
(pre
feru
jacy
chru
chy
wg l
ab)
stos
uje
sie
zate
mo
gra
nic
zen
ieg
leb
oko
sci
zit
era
cyjn
ymp
og
leb
ian
iem
.T
enw
aria
ntgw
aran
tuje
znal
ezie
nie
rozw
iaza
nia,
oile
istn
ieje
.
Jedn
akw
przy
padk
ual
gory
tmu
BT
tam
etod
am
oze
byc
bard
zoni
eefe
ktyw
na.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zn
awra
can
iem
14
He
ury
styk
ii
fun
kcj
eo
cen
yst
an
u
Alg
oryt
my
doty
chcz
aspr
zeds
taw
ione
saog
olne
ini
ew
ymag
aja
dosw
ojej
prac
yst
rate
gii
poi
nfor
mow
anej
.Je
dnak
wka
zdym
prak
tycz
nym
zaga
dnie
niu
pos
iada
nie
taki
ejst
rate
gii
jest
bard
zop
ozad
ane.
He
ury
styk
ab
edzi
emy
nazy
wac
wie
dze
odz
iedz
inie
prob
lem
owej
:
•kt
orej
nie
moz
nauz
yska
cz
synt
akty
czne
jan
aliz
yop
isu
prob
lem
u,•
ktor
am
oze
nie
mie
cfo
rmal
nie
pop
raw
nego
uzas
adni
enia
,a
takz
e—
cow
iece
j—
ktor
am
oze
nie
wka
zdym
przy
padk
usp
raw
dzac
sie,
icz
asam
ida
wac
myl
new
skaz
owki
,•
ale
ktor
aog
olni
ep
omag
aw
doko
nyw
aniu
dobr
ych
wyb
orow
wpr
zesz
ukiw
aniu
.
Pos
iada
nie
heur
ysty
kip
ozw
ala
budo
wac
stra
tegi
ep
oinf
orm
owan
e.O
goln
ymi
czes
tost
osow
anym
sche
mat
emko
nstr
ukcj
ist
rate
gii
wyk
orzy
stuj
acym
info
rmac
jehe
urys
tycz
na,
jest
sta
tycz
na
fun
kcja
oce
ny
sta
nu
.D
laka
zdeg
ost
anu
okre
sla
ona
jego
”dobr
oc”,
czyl
isz
anse
,ze
prze
zte
nst
anpr
owad
zidr
oga
doro
zwia
zani
a.W
arto
scte
jfu
nkcj
im
ozna
row
niez
inte
rpre
tow
acja
kom
iare
odle
g los
cist
anu
odro
zwia
zani
a.
Met
od
ypr
zesz
uki
wan
ia—
heu
ryst
yczn
efu
nkc
jeo
cen
yst
any
15
Me
tod
yg
rad
ien
tow
e
Fun
kcje
ocen
yst
anu
moz
naw
prze
szuk
iwan
iuza
stos
owac
bez
pos
redn
io.
Pro
wad
zito
dom
etod
ylu
bm
etod
gra
die
nto
wyc
h(hill-clim
bing)
.M
etod
yte
okre
sla
sie
win
form
atyc
eja
kom
etod
yza
ch la
nne.
Ich
bez
pos
redn
ieza
stos
owan
ieog
rani
czon
eje
stdo
dzie
dzin
zba
rdzo
regu
larn
afu
nkcj
aoc
eny
(np.
scis
lem
onot
onic
zna)
.W
prak
tyce
mam
yty
pow
odo
czyn
ieni
az
nast
epuj
acym
ipr
oble
mam
i:
1.lo
kaln
em
aksi
ma
funk
cji
ocen
y2.
obsz
ary
”plat
eau”
funk
cji
ocen
y3.
ukos
negr
anie
funk
cji
ocen
y
curr
ent
stat
e
obje
ctiv
e fu
nctio
n
stat
e sp
ace
glob
al m
axim
um
loca
l max
imum
"fla
t" lo
cal m
axim
um
shou
lder
Met
od
ypr
zesz
uki
wan
ia—
met
od
yg
rad
ien
tow
e1
6
Page 5
Wyz
arza
nie
Sku
tecz
nai
czes
tost
osow
ana
grup
em
etod
grad
ient
owyc
hst
anow
ite
chni
kazw
ana
wyz
arza
niem
(simulatedannealing)
.Je
jna
zwa
odw
o luj
esi
edo
anal
ogii
zpr
oces
emw
ytap
iani
am
etal
u,ki
edy
stop
niow
ei
pow
olne
zmni
ejsz
anie
tem
per
atur
yp
ozw
ala
osia
gnac
stan
glob
alne
goop
tim
umen
erge
tycz
nego
,z
pe l
nym
upor
zadk
owan
iem
czas
tecz
ekw
ca le
job
jeto
sci
met
alu.
Met
oda
pol
ega
nage
nero
wan
iuru
chow
loso
wyc
h,i
nast
epni
ew
ykon
ywan
iuic
h,lu
bni
e,zg
odni
ez
prze
dsta
wio
nym
naw
ykre
sie
rozk
lade
mpr
awdo
pod
obie
nstw
a.
Jak
wid
ac,
jesl
iw
ygen
erow
any
ruch
pop
raw
iaw
arto
scfu
nkcj
ioc
eny
toje
stza
wsz
ew
ykon
ywan
y,na
tom
iast
jesl
ija
pog
arsz
ato
jest
wyk
onyw
any
zpr
awdo
pod
obie
nstw
emp<
1za
lezn
ymod
stop
nia
pog
orsz
enia
ocen
y,w
por
owna
niu
zest
anem
aktu
alny
m.
Met
od
ypr
zesz
uki
wan
ia—
met
od
yg
rad
ien
tow
e1
7
Jedn
ocze
snie
,w
trak
cie
prac
yal
gory
tmu
stop
niow
oob
niza
naje
stte
mp
erat
ura,
cop
owod
uje
zmni
ejsz
anie
praw
dop
odob
iens
twa
wyb
oru
ruch
ow”z l
ych”
.
Met
ode
wyz
arza
nia
stos
uje
sie
zp
owod
zeni
emdo
proj
ekto
wan
iauk
lado
wV
LS
I,si
eci
rozn
ego
rodz
aju,
przy
dzia
luza
dan
wpr
oces
ach
prod
ukcy
jnyc
h,i
inny
chza
dan
opty
mal
izac
jipr
oces
owz l
ozon
ych.
Pro
blem
emw
jej
zast
osow
aniu
jest
dobo
rpa
ram
etro
w,
np.
algo
rytm
uob
niza
nia
tem
per
atur
y.
Met
od
ypr
zesz
uki
wan
ia—
met
od
yg
rad
ien
tow
e1
8
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.Ja
kie
wym
agan
iaal
gory
tmu
BT
saba
rdzi
ejkr
ytyc
zne:
pam
ieci
owe
czy
czas
owe?
Uza
sadn
ijod
pow
iedz
.
2.W
jaki
chsy
tuac
jach
algo
rytm
BT
moz
eni
ezn
alez
cro
zwi a
zani
a,gd
yon
ois
tnie
je?
3.N
acz
ymp
oleg
azj
awis
kop
owta
rzaj
acyc
hsi
est
anow
wal
gory
tmac
hpr
zesz
ukiw
ania
?Ja
kie
saje
gom
ozliw
eko
nsek
wen
cje?
4.Ja
kipr
oble
mro
zwia
zuje
met
oda
iter
acyj
nego
pog
lebi
ania
?W
jaki
chpr
zypa
dkac
hko
niec
zne
jest
jej
stos
owan
ie?
5.Ja
kie
sag l
owne
prob
lem
yja
kosc
iow
e(n
ieuw
zgle
dnia
jac
z loz
onos
ci)
wza
stos
owan
iugr
adie
ntow
ych
met
odpr
zesz
ukiw
ania
?
Met
od
ypr
zesz
uki
wan
ia—
met
od
yg
rad
ien
tow
e1
9
Met
od
ypr
zesz
uki
wan
ia—
met
od
yg
rad
ien
tow
e2
0
Page 6
Prz
esz
uk
iwa
nie
gra
fow
Prz
ypom
nijm
yso
bie
wer
sje
algo
rytm
uB
Tz
iter
acyj
nym
pog
lebi
anie
m,
iko
niec
znos
cw
ielo
krot
nego
prze
szuk
iwan
iap
ocza
tkow
ejcz
esci
prze
strz
eni.
Aby
unik
nac
wie
lokr
otne
good
wie
dzan
iaty
chsa
myc
hst
anow
moz
nauz
ycst
rukt
ury
graf
owej
dopa
mie
tani
azb
adan
ych
juz
czes
cipr
zest
rzen
ist
anow
.A
lgor
ytm
y,kt
ore
uzyw
aja
taki
ejst
rukt
ury
saal
gory
tmam
ip
rze
szu
kiw
an
iag
rafo
w.
Ogo
lne
stra
tegi
epr
zesz
ukiw
ania
graf
ow(s
lep
e):
•st
rate
gia
wsz
erz
BF
S(breadth-firstsearch
)
•st
rate
gia
wg l
abD
FS
(depth-firstsearch
),
•in
nest
rate
gie.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
21
Prz
yk la
d:
8-k
a(8
-pu
zzle
)
12
34
56
78
910
1112
1314
15U
k lad
anka
15-t
ka(15-puzzle
)—
pop
ular
naw
szko
lep
odst
awow
ej.
8-ka
(8-puzzle
)—
zmni
ejsz
ona
wer
sja,
odp
owie
dnia
doilu
stra
cji
dzia
lani
aro
znyc
hst
rate
gii
ial
gory
tmow
sztu
czne
jin
telig
encj
i.
732
618
54
765
84
123
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
22
Prz
esz
uk
iwa
nie
wsz
erz
(BF
S)
•B
adaj
wsz
ystk
iest
any
wod
leg l
oscid
odst
anu
poc
zatk
oweg
os0
prze
dzb
adan
iem
jaki
egok
olw
iek
stan
uw
odle
g los
ci(d
+1)
ods0.
•Z
awsz
egw
aran
tuje
znal
ezie
nie
rozw
iaza
nia
jesl
ity
lko
istn
ieje
.
•C
ow
iece
j,za
wsz
ezn
ajdu
jero
zwia
zani
eop
tym
alne
(tzn
.zn
ajdu
jena
jkro
tsza
drog
eze
stan
up
ocza
tkow
ego
doka
zdeg
ost
anu)
.
•N
ieje
stin
here
ntni
eod
por
nyna
wpa
dani
ew
pet
lest
anow
im
oze
wym
agac
zast
osow
ania
listy
Closed
.
•Z
lozo
nosc
pam
ieci
owa
icz
asow
afa
taln
a,ob
ieO(b
d),
gdzi
e:b
-sr
edni
alic
zba
ga le
ziw
yras
taja
cych
zw
ez la
(tzw
.branchingfactor
),d
-od
leg l
osc
stan
up
ocza
tkow
ego
odro
zwia
zani
a(l
iczb
aop
erat
orow
).
•P
rakt
yczn
ieje
dnak
owa
z loz
onos
cpr
zypa
dku
najg
orsz
ego
isr
edni
ego
(jak
row
niez
najle
psze
go).
•U
wag
aim
plem
enta
cyjn
a:do
daw
ajno
wo
odkr
yte
stan
yna
koni
eclis
tyOpen
.(P
omim
oiz
mow
isi
eo
lista
chw
ez lo
w,
zew
zgle
duna
czes
teod
wo l
ania
wpr
akty
cest
osuj
esi
esz
ybsz
est
rukt
ury
dany
ch,
np.
tabl
ice
hasz
owe.
)
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
23
Prz
esz
uk
iwa
nie
wsz
erz
—p
rzyk
lad
Dia
gram
prze
dsta
wia
frag
men
tgr
afu
prze
szuk
iwan
iaw
szer
z.N
umer
yna
dpl
ansz
ami
(1–2
6)p
okaz
uja
tuko
lejn
osc
wyb
oru
wez
low
doek
span
sji
graf
u.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
24
Page 7
Prz
esz
uk
iwa
nie
wg
lab
(DF
S)
•B
adaj
wsz
ystk
ieno
wo
odkr
yte
stan
yp
ocho
dne
(pot
omki
)da
nego
stan
un
prze
dp
owro
tem
doba
dani
asa
siad
owst
anun
.
•N
ieda
jeza
dnyc
hz
gwar
ancj
iB
FS
(pew
nosc
izn
alez
ieni
aro
zwia
zani
aop
tym
alne
go,
alb
ow
ogol
ezn
alez
ieni
aja
kieg
osro
zwia
zani
a).
•Z
lozo
nosc
oblic
zeni
owa
przy
padk
una
jgor
szeg
o:pr
zetw
arza
nie
ipa
mi e
tani
ew
szys
tkic
hst
anow
.
•Z
lozo
nosc
przy
padk
usr
edni
ego:
O(b
d)
pam
ieci
owa
icz
asow
a.
•D
lapr
zest
rzen
ini
esko
nczo
nych
jedy
nym
prak
tycz
nie
uzyt
eczn
ymw
aria
ntem
jest
ogra
nicz
enie
g leb
okos
ciz
iter
acyj
nym
pog
lebi
anie
m(a
lepr
zesz
ukiw
anie
graf
uD
FS
nie
jest
azta
kb
ezse
nsow
nie
stra
tne
jak
algo
rytm
BT
).
•E
fekt
ywno
scal
gory
tmu
gwa l
tow
nie
pol
epsz
asi
edl
apr
zypa
dkow
isto
tnie
leps
zych
niz
sred
ni(c
zyli
wyj
atko
wo
szcz
esliw
ych)
,za
tem
sens
jego
stos
owan
iaje
stty
lko
wp
o lac
zeni
uz
dobr
ymi
heur
ysty
kam
i.
•U
wag
aim
plem
enta
cyjn
a:do
daw
ajno
wo
odkr
yte
stan
yna
poc
zate
klis
tyOpen
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
25
Prz
esz
uk
iwa
nie
wg
lab
—p
rzyk
lad
Fra
gmen
t”pr
zeci
etne
go”
graf
upr
zesz
ukiw
ania
wg l
abz
ogra
nicz
enie
mg l
ebok
osci
do5.
Num
ery
wez
low
pok
azuj
ako
lejn
osc
wyb
oru
wez
low
doek
span
sji
graf
u.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
26
Prz
esz
uk
iwa
nie
row
no
ko
szto
we
UC
S
Wpr
zypa
dku,
gdy
kosz
typ
ojed
yncz
ych
ruch
owni
esa
row
ne,
prze
szuk
iwan
iew
szer
zop
arte
nalic
zbie
ruch
oww
oczy
wis
tysp
osob
nie
gwar
antu
jezn
alez
ieni
aop
tym
alne
jsc
iezk
i.M
ozna
okre
slic
pros
tam
odyfi
kacj
eal
gory
tmu
wsz
erz,
ktor
azn
ajdz
ieop
tym
alna
scie
zke
dla
dow
olny
ch(d
odat
nich
)ko
szto
wp
ojed
yncz
ych
ruch
ow.
Ta
mod
yfika
cja,
zwan
aal
gory
tmem
row
ne
go
kosz
tu(uniform-cost
search
UC
S),
wym
aga
kazd
oraz
owo
wyb
rani
aw
ez la
ona
jniz
szym
kosz
cie
scie
zki.
SG
55
33
3S
G
55
33
3S
G
55
33
3S
G
55
33
3S
G
55
33
3
Wpr
zypa
dku
row
nych
kosz
tow
ruch
owsp
row
adza
sie
todo
met
ody
wsz
erz.
Opt
ymal
nosc
algo
rytm
um
ozna
(try
wia
lnie
)w
ykaz
acp
odw
arun
kiem
,ze
kosz
tp
ojed
yncz
ego
ruch
uje
stja
kas
war
tosc
iado
datn
ia(≥
ǫ).
Pon
iew
azal
gory
tmki
eruj
esi
ed l
ugos
cia
scie
zki,
jego
z loz
onos
cini
em
ozna
scha
rakt
eryz
owac
jako
funk
cjib
id
.Z
amia
stte
go,
ozna
czaj
acpr
zezC
∗ko
szt
opty
mal
nego
rozw
iaza
nia,
moz
naot
rzym
acz l
ozon
osc
najg
orsz
ego
przy
padk
u,za
row
nocz
asow
aja
ki
pam
ieci
owa,
jako
O(b
1+⌊C
∗/ǫ⌋).
Wpr
zypa
dku
row
nych
kosz
tow
form
u la
tare
duku
jesi
edo
O(b
d).
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
27
Za
ko
ncz
en
iep
rze
szu
kiw
an
ia
Cel
empr
zesz
ukiw
ania
moz
eby
csa
mo
znal
ezie
nie
scie
zki
doro
zwia
zani
a,ba
dzzn
alez
ieni
esc
iezk
iop
tym
alne
j.W
pier
wsz
ympr
zypa
dku,
algo
rytm
moz
eza
konc
zyc
prac
eju
zw
mom
enci
e,ki
edy
now
yst
an,
wyg
ener
owan
yw
wyn
iku
kole
jneg
oru
chu,
okaz
esi
est
anem
doce
low
ym,
aw
iec
zost
anie
umie
szcz
ony
nalis
cieOpen
.A
lecz
yta
ksa
mo
moz
emy
pos
tapi
cw
przy
padk
up
oszu
kiw
ania
rozw
iaza
nia
opty
mal
nego
?
SG
55
33
3S
G
55
33
3S
G
55
33
3S
G
55
33
3S
G
55
33
3
Prz
eszu
kiw
anie
nale
zyza
konc
zyc
wm
omen
cie,
gdy
algo
rytm
prze
szuk
iwan
iaop
tym
alne
gow
ybie
rze
doek
span
sji
wez
e l,
ktor
yje
stw
ez le
mdo
celo
wym
(czy
liju
zw
czes
niej
znal
az l
jede
nlu
bki
lka
wez
low
doce
low
ych)
.Je
goek
span
sji
moz
naw
tedy
zani
echa
c,a
najle
psza
znal
ezio
nado
nieg
osc
iezk
aje
stro
zwia
zani
emop
tym
alny
m.
Pon
iew
azal
gory
tmsy
stem
atyc
znie
znaj
duje
wsz
ystk
iena
jtan
sze
scie
zki,
wie
cm
omen
tw
ybra
nia
wez
lado
eksp
ansj
ioz
nacz
a,ze
nie
moz
esi
eju
zw
grafi
ezn
alez
cza
dna
tans
zasc
iezk
ado
nieg
o.
Jedn
akza
nim
tona
stap
i,al
gory
tmba
dasc
iezk
io
nizs
zych
kosz
tach
,i
nie
ma
pew
nosc
i,ze
ktor
asz
nich
nie
okaz
esi
eno
wa,
leps
zasc
iezk
ado
wez
lace
low
ego.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
28
Page 8
Prz
esz
uk
iwa
nie
na
jpie
rw-n
ajl
ep
szy
Zas
toso
wan
iehe
urys
tycz
nej
funk
cji
ocen
ydo
prze
szuk
iwan
iana
graf
ach
wna
jpro
stsz
ympr
zypa
dku
daje
tzw
.pr
zesz
ukiw
anie
na
jpie
rw-n
ajl
ep
szy
(best-firstsearch
).W
kazd
ejch
wili
wyk
onuj
eon
oru
ch,
ktor
ym
inim
aliz
uje
funk
cje
ocen
y.Je
sli
funk
cja
ocen
yje
stdo
bra,
w la
sciw
iew
ybie
rast
any
doan
aliz
y,i
odp
owie
dnio
mal
eje
wzd
luz
drog
ido
rozw
iaza
nia,
tow
tedy
tam
etod
a
”idzi
e”b
ezp
osre
dnio
doce
lu,
nie
trac
accz
asu
naro
zwija
nie
jaki
chko
lwie
kni
epot
rzeb
nych
wez
low
graf
u.
Row
niez
wpr
zypa
dku
drob
nych
defe
ktow
funk
cji
ocen
y,ki
edy
niek
tore
jej
war
tosc
isa
niet
rafn
ei
zle
ocen
iaja
stan
y,al
ep
oro
zwin
ieci
uki
lku
niep
otrz
ebny
chw
ez lo
wfu
nkcj
aoc
enia
dals
zew
ez ly
wpr
zybl
izen
iup
opra
wni
e,te
nsc
hem
atpr
zesz
ukiw
ania
dobr
zesi
esp
raw
dza.
K lo
pot
yza
czyn
aja
sie
jedn
akki
edy
funk
cja
ma
jaki
sb l
adsy
stem
atyc
zny,
np.
jako
najle
psza
kons
ekw
entn
iew
skaz
uje
drog
e,kt
ora
wog
ole
nie
prow
adzi
doce
lu.
Wte
dym
etod
ana
jpie
rw-n
ajle
pszy
ma
taki
esa
me
wad
yja
km
etod
aw
g lab
,p
omim
o,iz
funk
cja
byc
moz
ep
opra
wni
eos
zaco
wuj
ew
iele
wez
low
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
29
Na
jpie
rw-n
ajl
ep
szy
jako
we
rsja
prz
esz
uk
iwa
nia
wg
lab
Sp
ostr
zeze
nie,
zem
etod
ana
jpie
rw-n
ajle
pszy
zach
owuj
esi
ep
odob
nie
jak
met
oda
wg l
abp
ozw
ala
naw
ycia
gnie
cie
pew
nych
wni
osko
w.
Alg
oryt
mna
jpie
rw-n
ajle
pszy
jest
obar
czon
yw
szys
tkim
ip
oten
cjal
nym
iw
adam
ial
gory
tmow
wg l
ab,
taki
mi
jak
moz
liwos
cni
ezna
lezi
enia
rozw
iaza
nia,
ktor
eis
tnie
je,
wpa
dani
aw
b led
neal
eni
esko
nczo
nega
lezi
e,it
p.M
aza
tem
sens
stos
owan
iew
obec
niej
ogra
nicz
enia
g leb
okos
ci(z
iter
acyj
nym
pog
lebi
anie
m),
itp.
Jak
wkr
otce
zoba
czym
y,is
tnie
jep
ewna
”inte
ligen
tna”
met
oda
wyk
orzy
stan
iast
rate
gii
heur
ysty
czne
jw
algo
rytm
iew
g lab
,za
bez
piec
zaja
capr
zed
prze
szuk
iwan
iem
nies
konc
zony
chpr
zest
rzen
ile
piej
niz
szty
wne
ogra
nicz
enie
g leb
okos
ci.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
30
Prz
esz
uk
iwa
nie
gra
fuo
par
ten
ako
szta
ch
Na
poz
or,
algo
rytm
UC
Sro
zni
sie
zasa
dnic
zood
algo
rytm
una
jpie
rw-n
ajle
pszy
.P
ierw
szy
jest
algo
rytm
emsl
epym
,a
drug
ip
oinf
orm
owan
ym.
Jedn
akp
orow
nani
eko
duty
chal
gory
tmow
wsk
azuj
e,ze
sani
emal
iden
tycz
ne.
Oba
doko
nuja
syst
emat
yczn
ejek
span
sji
graf
u,w
ybie
raja
cz
listy
Open
wez
e lo
najn
izsz
ejw
arto
sci
ocen
y,a
nast
epni
epr
zeno
sza
gona
liste
Closed
wyk
onuj
acje
dnoc
zesn
ieje
goek
span
sje.
Eks
pans
jap
oleg
ana
wyg
ener
owan
iuw
szys
tkic
hje
gona
step
niko
w,
zain
stal
owan
iuic
hna
grafi
ei
doda
niu
dolis
tyOpen
.
Roz
nica
pom
iedz
yty
mi
algo
rytm
ami
pol
ega
wie
cty
lko
nast
osow
aniu
rozn
ych
kryt
erio
ww
ybor
uw
ez la
doek
span
sji.
Wpi
erw
szym
jest
ono
dete
rmin
isty
czne
,a
wdr
ugim
heur
ysty
czne
.
Pon
iew
azob
ast
ale
wyb
iera
jana
jleps
zyw
eze l
zlis
tyOpen
,m
ase
nsje
jim
plem
enta
cja
jako
listy
sort
owan
ej.
Inny
mdo
brym
wyb
orem
stru
ktur
yda
nych
dla
listy
Open
jest
kole
jka
prio
ryte
tow
a,p
ozw
alaj
aca
na la
twy
wyb
orna
jleps
zego
kand
ydat
az
listy
,i
tani
eop
erac
jedo
daw
ania
ius
uwan
iaz
listy
(O(log
(N))
).
Sle
pe
algo
rytm
yB
FS
iD
FS
rozn
iasi
ety
lko
tym
,ze
nie
por
zadk
uja
listy
Open
,al
esz
tyw
nodo
daja
now
ew
ez ly
nako
niec
lub
poc
zate
klis
ty.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
31
War
totu
doda
c,ze
istn
ieje
algo
rytm
Dijk
stry
(195
9)zn
ajdo
wan
iana
jkro
tszy
chdr
ogna
grafi
ez
jedn
ego
wez
lado
wsz
ystk
ich
wez
low
graf
u.W
pew
nym
sens
ieje
ston
row
now
azny
algo
rytm
owi
UC
S.
Jedn
akD
ijkst
raza
k lad
a lop
erac
jena
grafi
esk
oncz
onym
,w
ca lo
sci
znan
ym,
zbud
owan
ym,
iza
lado
wan
ymdo
pam
ieci
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
32
Page 9
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.C
zym
rozn
isi
epr
zesz
ukiw
anie
row
noko
szto
we
odpr
zesz
ukiw
ania
wsz
erz?
2.C
zym
rozn
isi
epr
zesz
ukiw
anie
wg l
abod
prze
szuk
iwan
iana
jpie
rw-n
ajle
pszy
?
3.O
pisz
bazo
wy
cykl
prac
yal
gory
tmu
prze
szuk
iwan
iagr
afow
.
4.O
pisz
oper
acje
nalis
tach
Op
eni
Clo
sed
wro
znyc
hal
gory
tmac
hpr
zesz
ukiw
ania
graf
ow.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
33
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
34
Mo
dyfi
ka
cja
fun
kcj
iw
ybo
ru—
ko
szt
prz
eb
yte
jd
rog
i
Roz
waz
my
nast
epuj
ace
dete
rmin
isty
czne
funk
cje
ocen
y(w
ez la
):
h*(n)
–ko
szt
kosz
tow
o-op
tym
alne
jdr
ogi
zn
doce
lug
*(n)
–ko
szt
kosz
tow
o-op
tym
alne
jdr
ogi
zs0
don
Wte
dy:
f*(n):=
g*(n)+h
*(n)
f*(n)
–ko
szt
kosz
tow
o-op
tym
alne
jdr
ogi
zs0
doce
lubi
egna
cej
prze
zn
Zna
jom
osc
funk
cjif
*(n)
poz
wol
i laby
zaw
sze
wyb
iera
cty
lko
wez
lyle
zace
naop
tym
alne
jdr
odze
odp
ocza
tku
doce
lu.
Pod
obni
ezr
eszt
aw
ysta
rczy
laby
dote
gozn
ajom
osc
sam
ejfu
nkcj
ih
*(n).
Nie
stet
y,zw
ykle
funk
cjeh
*(n)
anig
*(n)
nie
sado
step
ne.
Jest
esm
yzm
usze
nip
os lu
giw
acsi
eic
hpr
zybl
izen
iam
i,kt
ore
poz
wal
aja
jedy
nie
apro
ksym
owac
wyb
iera
nie
w la
sciw
ych
wez
low
.Je
dnak
gdy
pos
lugu
jem
ysi
epr
zybl
izen
iam
i,w
tedy
prze
szuk
iwan
ieba
zuja
cena
funk
cjif
*(n)
nie
mus
iju
zda
wac
taki
chsa
myc
hw
ynik
owja
kto
opie
raja
cesi
ena
funk
cjih
*(n).
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
35
Mo
dyfi
ka
cja
fun
kcj
iw
ybo
ru—
alg
ory
tmA
*
Roz
waz
my
zate
mna
step
ujac
ehe
urys
tycz
nefu
nkcj
eoc
eny
wez
la:
h(n)
–fu
nkcj
ahe
urys
tycz
naap
roks
ymuj
acah
*(n)
g(n)
–ko
szt
najle
psze
jzn
anej
drog
izs0
don
;za
uwaz
myg(n)≥
g*(n)
f(n):=
g(n)+h(n)
Jak
dzia
lata
kok
resl
ona
stra
tegi
a?Je
sli
funk
cjah(n)
osza
cow
ujeh
*(n)
bard
zopr
ecyz
yjni
e,to
algo
rytm
dzia
lani
emal
idea
lnie
,i
zmie
rza
pros
todo
celu
.
Jedn
akgd
yfu
nkcj
ah(n)
pop
e lni
ab l
edy,
inp
.op
tym
isty
czni
eok
resl
aja
kies
stan
yja
kole
psze
niz
saon
ew
rzec
zyw
isto
sci,
toal
gory
tmna
jpie
rwp
odaz
aw
ich
kier
unku
,zw
abio
nyni
ska
war
tosc
iafu
nkcj
ih(n),
gdyg(n)
jest
pom
ijaln
e.
Po
jaki
ms
czas
ie,
tak
b led
nie
osza
cow
ane
scie
zki
prze
staj
aby
cat
rakc
yjne
,ze
wzg
ledu
nana
rast
ajac
ysk
ladn
ikg(n),
ial
gory
tmz
koni
eczn
osci
prze
rzuc
asw
oje
zain
tere
sow
anie
nain
neat
rakc
yjne
wez
ly.
Prz
yty
mna
atra
kcyj
nosc
nie
ma
wp l
ywu,
czy
saon
eba
rdzi
ejcz
ym
niej
odda
lone
odst
artu
.D
ecyd
uje
lacz
naoc
ena,
czy
prze
zda
nyst
anpr
owad
zina
jleps
zadr
oga
doro
zwia
zani
a.
Alg
oryt
mpr
zesz
ukiw
ania
graf
owst
osuj
acy
pow
yzsz
afu
nkcj
ef(n)
jako
swoj
ast
rate
gie
nazy
wa
sie
alg
ory
tme
mA
*.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
36
Page 10
Fu
nkcj
ao
cen
yw
alg
ory
tmie
A*
Sk l
adni
kih(n)
ig(n)
repr
ezen
tuja
wfu
nkcj
if(n)
dwie
prze
ciw
staw
nete
nden
cje:
opty
miz
m(h(n))
iko
nser
wat
yzm
(g(n))
.M
ozem
yca
lkie
msw
obod
nie
ster
owac
stra
tegi
aw
jedn
alu
bdr
uga
stro
nest
osuj
acw
zor:
f(n):=
(1−k)∗g(n)+k∗h(n)
Zw
ieks
zaja
cw
spo l
czyn
nik
wag
ik
moz
emy
nada
wac
prze
szuk
iwan
iuch
arak
ter
bard
ziej
agre
syw
ny(i
ryzy
kow
ny),
gdy
np.
mam
yza
ufan
iedo
funk
cjih(n)
ich
cem
yp
osuw
acsi
esz
ybko
dopr
zodu
.z
kole
izm
niej
szaj
acte
nw
spo l
czyn
nik,
zap
ewni
amy
dok l
adni
ejsz
eba
dani
epr
zest
rzen
i,p
osuw
ajac
sie
wol
niej
dopr
zodu
,al
eko
mp
ensu
jac
niek
tore
b led
yfu
nkcj
ih(n).
Zau
waz
my,
zew
skra
jnyc
hpr
zypa
dkac
h,k=
1da
jepr
zesz
ukiw
anie
najp
ierw
-naj
leps
zy,
nato
mia
stk=
0da
jepr
zesz
ukiw
anie
row
noko
szto
we.
Jedn
akna
jwie
kszy
wp l
ywna
prze
bieg
prze
szuk
iwan
iam
aja
kosc
funk
cjih(n).
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
37
W la
sno
sci
fun
kcj
ih
(n)
wa
lgo
rytm
ieA
*
Heu
ryty
czna
funk
cje
ocen
yh(n)
wal
gory
tmie
A*
nazy
wam
yd
op
usz
cza
lna
(admissible
)gd
yog
rani
cza
ona
oddo
lurz
eczy
wis
tafu
nkcj
eh
*(n),
czyl
i∀nh(n)≤
h*(n).
Dop
uszc
zaln
osc
ozna
cza
chro
nicz
neni
edos
zaco
wyw
anie
przy
sz ly
chko
szto
w,
zate
mby
wa
nazy
wan
eop
tym
izm
em.
Moz
nado
wie
sc,
zeje
sli
tylk
ois
tnie
jesc
iezk
az
wez
lap
ocza
tkow
ego
doce
low
ego,
toA
*z
dopu
szcz
alna
heur
ysty
kaza
wsz
ezn
ajdu
jeop
tym
alna
taka
scie
zke.
Czy
trud
noje
stzn
alez
cta
kado
pusz
czal
nahe
urys
tyke
?N
ieko
niec
znie
,np
.h(n)≡
0rz
eczy
wis
cie
ogra
nicz
az
do lu
h*(n),
dla
dow
olne
goza
gadn
ieni
a.C
zyta
katr
ywia
lna
heur
ysty
kam
oze
byc
przy
datn
a?O
dpow
iedz
brzm
i:ra
czej
rzad
ko.
Tak
ial
gory
tmw
ybie
raza
wsz
ew
ez ly
ona
jkro
tsze
jdr
odze
zs0,
aza
tem
jest
toal
gory
tmw
szer
z(o
goln
iej:
row
nego
kosz
tu),
ktor
yrz
eczy
wis
cie
zaw
sze
znaj
duje
opty
mal
nadr
oge,
ale
sam
ow
sobi
eto
jesz
cze
nie
jest
wie
lka
zale
ta.
Ocz
ywis
cie
imle
piejh(n)
przy
bliz
ah
*(n)
tym
efek
tyw
niej
sze
prze
szuk
iwan
ie.
Jesl
im
amy
dwie
funk
cjeh1(n),h2(n),
taki
eze
dla
wsz
ystk
ich
wez
low
h1(n)<
h2(n)≤
h*(n)
tom
ozna
dow
iesc
,ze
uzyc
ieh1
prow
adzi
doro
zwin
ieci
aco
najm
niej
tyle
sam
ow
ez lo
wco
h2.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
38
W la
sno
sci
fun
kcj
ih
(n)
wa
lgo
rytm
ieA
*(c
d.)
Dop
uszc
zaln
osc
funk
cjih(n)
jest
ciek
awa
w la
snos
cia,
ktor
acz
esto
moz
naud
owod
nic
dla
funk
cji
bard
zozg
rubn
ieos
zaco
wuj
acejh
*(n),
ale
juz
niek
onie
czni
edl
am
ozol
nie
opra
cow
anej
funk
cji,
np.
zw
ykor
zyst
anie
mnu
mer
yczn
ego
ucze
nia
sie
nase
rii
przy
k lad
ow(c
oja
ksi
eok
aze
jest
jedn
az
met
odko
nstr
ukcj
ita
kich
funk
cji)
.
Jesz
cze
moc
niej
sza
w la
snos
cia
heur
ysty
czne
jfu
nkcj
ioc
enyh(n)
jest
jej
spo
jno
sc(consistency
),zw
ana
row
niez
og
ran
icze
nie
mm
on
oto
nic
znym
(monotonerestriction
),lu
bp
opr
ostu
nier
owno
scia
troj
kata
:
∀ni→
nj
h(n
i)−h(n
j)≤
c(ni,nj)
Moz
nado
wie
sc,
zedl
afu
nkcj
ih(n)
spe l
niaj
acyc
hog
rani
czen
iem
onot
onic
zne
algo
rytm
A*
zaw
sze
ma
juz
znal
ezio
naop
tym
alna
drog
edo
kazd
ego
wez
la,
ktor
yde
cydu
jesi
ero
zwija
c.W
prak
tyce
poz
wal
ato
niec
oup
rosc
icim
plem
enta
cje
algo
rytm
upr
zesz
ukiw
ania
,je
sli
wie
my,
zefu
nkcj
aoc
eny
jest
spoj
na.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
39
Z lo
zon
osc
ob
licz
en
iow
aa
lgo
rytm
uA
*
Dla
wie
kszo
sci
prak
tycz
nych
prob
lem
owlic
zba
wez
low
prze
strz
eni
stan
owro
snie
eksp
onen
cjal
nie
zd l
ugos
cia
pos
zuki
wan
ego
rozw
iaza
nia.
Ocz
ywis
cie,
efek
tyw
nahe
urys
tyka
mog
laby
zmni
ejsz
ycz l
ozon
osc
oblic
zeni
owa
algo
rytm
u.P
ytan
ie,
kied
ym
oglib
ysm
yna
tolic
zyc?
Moz
nado
wie
sc,
zeab
yto
osia
gnac
,cz
yli
aby
algo
rytm
A*
dzia
la l
wcz
asie
wie
lom
iano
wym
,b l
adw
heur
ysty
czne
jfu
nkcj
ioc
eny
nie
pow
inie
npr
zekr
oczy
clo
gary
tmu
rzec
zyw
iste
jd l
ugos
ciro
zwia
zani
a:
|h(n)−h∗(n)|≤
O(log
h∗(n))
Pyt
anie
:cz
yta
kie
heur
ysty
kisa
prak
tycz
ne?
Wpr
akty
czny
chpr
zypa
dkac
hni
em
ozna
liczy
cna
znal
ezie
nie
tak
dobr
ych
heur
ysty
k.Z
atem
algo
rytm
A*
nale
zyog
olni
euw
azac
zaek
spon
encj
alny
.T
oje
dnak
zwyk
leni
eje
stje
gona
jwie
ksza
wad
a.P
odob
nie
jak
wsz
ystk
ieal
gory
tmy
prze
szuk
iwan
iana
graf
ach,
prze
chow
uje
onw
szys
tkie
wez
lygr
afu
wpa
mie
cii
zre
gu ly
wyc
zerp
uje
pam
iec
kom
pute
radu
zow
czes
niej
niz
dost
epny
czas
!!
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
40
Page 11
Mo
dyfi
ka
cje
alg
ory
tmu
A*
zo
gra
nic
zon
ymi
wym
ag
an
iam
ip
am
ieci
ow
ymi
Istn
ieja
mod
yfika
cje
algo
rytm
uA
*p
ozw
alaj
ace
pok
onac
prob
lem
yz
zap
otrz
ebow
anie
mna
pam
iec.
Alg
oryt
mID
A*
(Iterative-DeepeningA*)
doda
jest
anda
rdow
eog
rani
czen
ieg l
ebok
osci
.P
oos
iagn
ieci
ulim
itu
g leb
okos
cipr
zesz
ukiw
ania
jest
onzw
ieks
zany
,pr
zyje
dnoc
zesn
ymus
unie
ciu
prze
bada
nych
wez
low
graf
uz
pam
ieci
.
Alg
oryt
mR
BF
S(RecursiveBest-First
Search
)je
stp
odob
nydo
algo
rytm
uB
Tw
wer
sji
reku
renc
yjne
j.P
rzes
zuku
jeon
reku
renc
yjni
ep
ojed
yncz
asc
iezk
egr
afu,
pam
ieta
jac
jedn
ocze
snie
naka
zdym
poz
iom
iere
kure
ncji
najle
psza
alte
rnat
ywe
poj
edyn
czeg
okr
oku.
Kie
dyak
tual
nie
anal
izow
ana
scie
zka
okaz
uje
sie
gors
zaod
tej
alte
rnat
ywy,
algo
rytm
wra
ca,
kasu
jac
wyn
iki
swoj
ejpr
acy
(lec
zw
chod
zac
wno
we
wyw
o lan
iare
kure
ncyj
ne,
pon
owni
eza
pam
ietu
jena
jleps
zaal
tern
atyw
e).
Alg
oryt
mS
MA
*(Simplified
Mem
ory-Bounded
A*)
dzia
lado
k lad
nie
jak
A*,
ale
tylk
odo
mom
entu
zap
e lni
enia
ca le
jdo
step
nej
pam
ieci
.W
tym
mom
enci
e,al
gory
tmko
ntyn
uuje
prac
e,ka
suja
cje
dnak
najg
orsz
ezn
ane
wez
lygr
afu
aby
zrob
icm
iejs
cena
now
ood
kryw
ane
stan
y.Je
dnak
osza
cow
anie
skas
owan
ych
wez
low
jest
prze
chow
ywan
ew
ich
rodz
icac
h,ab
ym
ozliw
eby
lop
onow
nep
odje
cie
prze
szuk
iwan
iaw
dane
jcz
esci
graf
u.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
41
Alg
ory
tmA
*w
pra
kty
ce
Dob
rym
pyta
niem
jest
,cz
yal
gory
tmy
heur
ysty
czne
gopr
zesz
ukiw
ania
graf
ow,
taki
eja
kA
*,m
aja
zast
osow
ania
prak
tycz
new
swie
cie
rzec
zyw
isty
m.
Odp
owie
dzna
topy
tani
ebr
zmi:
tak,
wp
ewny
chog
rani
czon
ych
dzie
dzin
ach,
jak
np.
plan
owan
ieop
tym
alne
jtr
asy
prze
jazd
uro
bot
a,al
bo
znaj
dow
anie
najk
rots
zej
drog
iw
grac
hko
mpu
tero
wyc
h.
Alg
oryt
mA
*je
sthe
urys
tycz
naw
ersj
aal
gory
tmu
Dijk
stry
(195
9)ob
licza
jace
gona
jkro
tsze
drog
iod
usta
lone
gow
ez la
dow
szys
tkic
hp
ozos
ta ly
chw
ez lo
wgr
afu.
Alg
oryt
mD
ijkst
ryje
stro
wni
ezst
osow
any
ww
ielu
zaga
dnie
niac
hte
chni
czny
ch,
jak
np.
siec
iow
epr
otok
o ly
tras
owan
ia(routing
),ta
kie
jak
OS
PF
,or
azzn
ajdo
wan
iedr
ogi
nam
apie
wna
wig
acja
chG
PS
.W
tych
osta
tnic
hza
stos
owan
iach
,ze
wzg
l edu
naw
ielk
osc
graf
u,al
gory
tmD
ijkst
rym
usi
byc
wsp
omag
any
prze
zdo
datk
owe
tech
niki
.M
oga
toby
cw
lasn
iehe
urys
tyki
,al
bo
wpr
owad
zeni
eab
stra
kcji
ihi
erar
chii
scie
zek.
Jedn
akze
wzg
ledu
nako
mer
cyjn
yas
pek
tte
jba
rdzo
rozw
ijaja
cej
sie
tech
nolo
gii,
tech
niki
nie
sazb
ytcz
esto
szcz
ego l
owo
opis
ywan
e.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
42
Prz
esz
uk
iwa
nie
wst
ecz
Prz
eszu
kiw
anie
prze
strz
eni
stan
owm
ozna
prow
adzi
cro
wni
edo
brze
wpr
zod
jak
iw
stec
z.P
rze
szu
kiw
an
iew
ste
czza
czyn
asi
eod
stan
uko
ncow
ego
(lub
ca le
gozb
ioru
stan
owko
ncow
ych)
,i
wpi
erw
szym
krok
uzn
ajdu
jezb
ior
stan
owp
oprz
edza
jacy
ch,
zkt
oryc
hm
ozna
osia
gnac
jaki
sst
anko
ncow
yw
jedn
ymkr
oku
prze
zkt
orys
zdo
step
nych
oper
ator
ow.
Wko
lejn
ych
krok
ach
proc
esje
stko
ntyn
uow
any.
Prz
eszu
kiw
anie
wst
ecz
moz
eby
cro
wni
e la
twe
wre
aliz
acji
oblic
zeni
owej
jak
prze
szuk
iwan
iew
przo
d,al
bo
moz
eby
cut
rudn
ione
zew
zgle
duna
w la
snos
cipr
zyje
tej
repr
ezen
tacj
i.W
tym
drug
impr
zypa
dku
koni
eczn
am
oze
byc
zmia
nare
prez
enta
cji.
Klu
czow
aje
stje
dnak
latw
osc
poz
yska
nia
heur
ysty
k.W
przy
padk
upr
zesz
ukiw
ania
wpr
zod
heur
ysty
kap
owin
nap
odp
owia
dac
nam
,ja
kie
krok
ina
lezy
wyb
iera
c,ab
ysk
utec
znie
przy
bliz
acsi
edo
celu
.W
niek
tory
chza
gadn
ieni
ach
brak
jest
w la
sciw
ych
intu
icji.
Wpr
zypa
dku
prze
szuk
iwan
iaw
stec
zhe
rust
yka
pow
inna
pod
pow
iada
c,kt
ore
krok
ipr
zybl
izaj
ana
sod
niez
nane
gost
anu
doce
low
ego,
dodo
brze
znan
ego
srod
owis
kast
arto
weg
o.C
zase
m la
twie
jje
sto
intu
icje
wsp
omag
ajac
ep
odej
mow
anie
taki
chde
cyzj
i.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
43
Prz
esz
uk
iwa
nie
dw
uk
ieru
nko
we
Idee
prze
szuk
iwan
iaw
stec
zm
ozna
latw
ouo
goln
icdo
prz
esz
uk
iwa
nia
dw
uk
ieru
nko
we
go
.Je
sli
repr
ezen
tacj
ana
top
ozw
ala,
todl
acze
goni
ero
bic
napr
zem
ian
krok
owpr
zesz
ukiw
ania
wpr
zod
iw
stec
z.Ja
kw
idac
nary
sunk
up
ole
wej
,m
og lo
byto
przy
nies
cos
zcze
dnos
cirz
edu
50%
(πr2≈
2×π(r 2)2
):
Jedn
akja
kp
okaz
uje
rysu
nek
po
praw
ej,
zam
iast
zaos
zcze
dzic
,m
ozna
nad l
ozyc
prac
y.P
rzes
zuki
wan
iedw
ukie
runk
owe
latw
opr
zyno
sios
zcze
dnos
ciw
przy
padk
ual
gory
tmu
Dijk
stry
(row
noko
szto
weg
o),
jedn
akp
osia
daja
cw
yrafi
now
ana,
ukie
runk
owan
ahe
urys
tyke
,le
piej
jej
zauf
aci
pod
azac
zani
aw
jedn
ymki
erun
ku.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
44
Page 12
Ap
let
prz
esz
uk
iwa
nia
lab
iryn
tua
lgo
rytm
em
A*
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
45
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.C
zym
rozn
isi
eal
gory
tmA
*od
prze
szuk
iwan
iana
jpie
rw-n
ajle
pszy
?Ja
kisk
utek
wyw
iera
taro
znic
ana
proc
espr
zesz
ukiw
ania
?
2.C
oto
sado
pusz
czal
nehe
urys
tyki
dla
algo
rytm
uA
*?Ja
kie
maj
azn
acze
nie
prak
tycz
ne?
3.A
lgor
ytm
heur
ysty
czne
gopr
zesz
ukiw
ania
graf
owA
*z
dopu
szcz
alna
funk
cja
ocen
yh
gwar
antu
jezn
alez
ieni
eop
tym
alne
goro
zwia
zani
apr
oble
mu,
oile
tylk
ota
kie
istn
ieje
nagr
afie.
Roz
waz
pon
izsz
em
odyfi
kacj
efu
nkcj
if
iod
pow
iedz
,cz
yza
chow
uja
one
pow
yzsz
aw
lasn
osc
algo
rytm
uA
*.O
dpow
iedz
uzas
adni
j.
(a)
wpr
owad
zeni
ego
rneg
oog
rani
czen
ia(k
resu
)na
war
tosc
funk
cji
h(n)
(b)
wpr
owad
zeni
edo
lneg
oog
rani
czen
ia(k
resu
)na
war
tosc
funk
cji
g(n)
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
gra
fow
—al
gor
ytm
A*
46
Ko
nst
rukcj
afu
nkcj
ih
eu
ryst
yczn
ych
Jak
wog
olny
mpr
zypa
dku
skon
stru
owac
funk
cje
heur
ysty
czna
,gd
yni
ezn
amy
dost
atec
znie
dobr
zeza
gadn
ieni
a,ze
byj a
po
pros
tuw
ymys
lec ?
Eks
per
ymen
tow
ac,
eksp
erym
ento
wac
,ek
sper
ymen
tow
ac!
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
47
Prz
yk la
d:
he
ury
styk
id
la8
-pu
zzle
Heu
ryst
yka
1:p
olic
zel
emen
tyni
ena
swoi
chm
iejs
cach
,fu
nkcj
ah1(n)=
W(n)
Heu
ryst
yka
2:dl
aw
szys
tkic
hel
emen
tow
nie
nasw
oich
mie
jsca
ch,
zsum
ujod
leg l
osci
odic
hw
lasc
iwyc
hm
iejs
c(t
zw.
odle
g los
cM
anha
ttan
u).
Otr
zym
ana
liczb
ab
edzi
ena
pew
nom
niej
sza
niz
liczb
aru
chow
wka
zdym
rozw
iaza
niu
(dol
neos
zaco
wan
ieko
sztu
rozw
iaza
nia)
.N
azw
ijmy
jafu
nkcj
ah2(n)=
P(n)
Heu
ryst
yka
3:h3(n)=
P(n)+3∗S(n)
gdzi
efu
nkcj
aS(n)
jest
oblic
zana
dla
elem
ento
wna
obrz
ezu
uk la
dank
i,bi
orac
0dl
ael
emen
tow
,p
okt
oryc
hna
step
uje
ich
w la
sciw
ypr
awy
sasi
ad,
i2
dla
kazd
ego
elem
entu
,p
okt
orym
nast
epuj
eni
ew la
sciw
yel
emen
t.S
rode
kw
nosi
1,je
sli
jest
.
Ani
S(n)
anih3(n)
nie
sado
lnym
ios
zaco
wan
iam
irz
eczy
wis
tej
odle
g los
cido
rozw
iaza
nia
uk la
dank
i,a
jedn
akh3(n)
jest
jedn
az
najle
pszy
chfu
nkcj
ioc
eny
dla
uk la
dank
i8-
puzz
le,
daja
cani
ezw
ykle
ukie
runk
owan
ei
efek
tyw
nepr
zesz
ukiw
anie
.
Zau
waz
my,
zedo
lnym
osza
cow
anie
mod
leg l
osci
odro
zwia
zani
a,za
tem
gwar
antu
jacy
mzn
alez
ieni
ero
zwia
zani
aop
tym
alne
go,
jest
funk
cjah0(n)≡
0.Je
stto
ilust
racj
aog
olne
gofa
ktu,
zep
opra
wno
scfo
rmal
nani
eza
wsz
eid
zie
wpa
rze
zdo
bra
efek
tyw
nosc
iaob
licze
niow
a.
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
48
Page 13
Ja
ko
scfu
nkcj
ih
eu
ryst
yczn
ej
ako
szt
prz
esz
uk
iwa
nia
A*
Prz
ybliz
ona
liczb
aw
ez lo
wID
Sdl
ad=
24:
54,0
00,0
00,0
00
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
49
Prz
esz
uk
iwa
nie
he
ury
styc
zne
drz
ew
a8
-pu
zzle
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
50
Ko
nst
rukcj
afu
nkcj
ih
eu
ryst
yczn
ych
(cd
.)
Jedn
az
ogol
nych
met
odtw
orze
nia
funk
cji
heur
ysty
czny
chje
stna
step
ujac
a.N
alez
yro
zwaz
ycza
dani
eup
rosz
czon
e,w
ktor
ymre
zygn
uje
sie
zja
kieg
ostr
udne
gow
ymag
ania
,ab
yza
dani
eda
wa l
osi
ero
zwia
zac.
Dla
kazd
ego
wyg
ener
owan
ego
stan
uro
zwia
zuje
sie
zada
nie
upro
szcz
one
(np.
met
oda
pe l
nego
prze
glad
u).
Kos
ztop
tym
alne
goro
zwia
zani
aza
dani
aup
rosz
czon
ego
przy
jmuj
esi
ena
step
nie
jako
osza
cow
anie
(dol
ne)
kosz
turo
zwia
zani
aza
dani
aor
ygin
alne
go.
Na
przy
k lad
,je
sli
stan
yw
zaga
dnie
niu
maj
an
para
met
row
,cz
yli
sael
emen
tam
in
-wym
iaro
wej
prze
strz
eni,
tom
ozem
yp
orzu
cic
jede
nz
tych
para
met
row
,cz
yli
zrzu
tow
acst
any
dopr
zest
rzen
i(n
−1)
-wym
iaro
wej
.
Jesl
iis
tnie
jeki
lka
wer
sji
upro
szcz
enia
,p
omie
dzy
ktor
ymi
nie
wie
my
jak
wyb
rac
(np.
ktor
azm
ienn
ast
anu
odrz
ucic
),to
moz
emy
uzyc
ich
kom
bina
cji
jako
funk
cji
ocen
y:h(n)=
max
k(h
1(n),...,hk(n))
Zau
waz
my,
zegd
ybys
my
wuk
lada
nce
8-pu
zzle
zezw
olili
nate
lep
orta
cje
elem
ento
wje
dnym
ruch
emna
swoj
em
iejs
ce,
toby
loby
topr
zyk l
adem
taki
ego
w la
snie
pod
ejsc
ia,
ida
loby
wef
ekci
efu
nkcj
eh1(n).
Nat
omia
stzg
oda
napr
zesu
wan
ieel
emen
tow
oje
dna
poz
ycje
,al
eni
ezal
ezni
eod
po l
ozen
iain
nych
elem
ento
w,
da la
byfu
nkcj
eoc
enyh2(n).
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
51
Ko
nst
rukcj
afu
nkcj
ih
eu
ryst
yczn
ych
(cd
.)
Inna
met
oda
opra
cow
ania
funk
cji
heur
ysty
czne
jje
stje
jza
mod
elow
anie
stat
ysty
czne
.
Nal
ezy
wyz
nacz
ycat
rybu
tyst
anu,
ktor
em
ozna
uwaz
acza
znac
zace
dla
osza
cow
ania
odle
g los
cido
rozw
iaza
nia.
Wte
dyde
fini
ujac
funk
cje
heur
ysty
czna
jako
kom
bina
cje
linio
wa
tych
atry
buto
w,
zni
ezna
nym
iw
spo l
czyn
nika
mi,
moz
nana
uczy
csi
ety
chw
spo l
czyn
niko
ww
ykon
ujac
pew
nalic
zbe
eksp
erym
ento
ww
ykor
zyst
ujac
ych
pe l
nepr
zesz
ukiw
anie
lub
inna
funk
cje
heur
ysty
czna
.
Otr
zym
ane
d lug
osci
opty
mal
nych
rozw
iaza
nm
ozna
uzyc
dosk
onst
ruow
ania
uk la
duro
wna
ni
wef
ekci
ew
yzna
czen
iapr
zybl
izon
ych
war
tosc
iw
spo l
czyn
niko
w.
Zau
waz
my,
zeta
met
oda
moz
naby
otrz
ymac
funk
cje
ocen
yh3(n)
dla
8-pu
zzle
.F
unkc
jeW
(n)
iP(n)
moz
nauz
nac
zapr
zyda
tne
dobu
dow
ydo
brej
heur
ysty
ki.
Moz
nate
zuz
nac,
zefu
nkcj
aS(n)
dobr
zeod
daje
trud
nosc
osia
gnie
cia
stan
udo
celo
weg
o.Z
aczy
naja
cod
funk
cjih(n)=
a∗W
(n)+b∗P(n)+c∗S(n)
ipr
zepr
owad
zaja
cw
iele
eksp
erym
ento
w,
jest
moz
liwe,
zeop
tym
alne
war
tosc
iok
aza l
yby
sie
zbliz
one
do:a≈
0,b≈
1ic≈
3,co
wef
ekci
eda
loby
funk
cje
h3(n).
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
52
Page 14
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.W
ymie
ni
opis
zzn
ane
Ci
ogol
nem
etod
ytw
orze
nia
heur
ysty
czny
chfu
nkcj
ioc
eny.
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
53
Met
od
ypr
zesz
uki
wan
ia—
kon
stru
kcja
fun
kcji
heu
ryst
yczn
ych
54
Prz
esz
uk
iwa
nie
dla
gie
rd
wu
oso
bo
wyc
h
Gry
safa
scyn
ujac
aro
zryw
kai
czes
tost
anow
iaw
yzw
anie
dla
inte
lekt
ucz
low
ieka
.N
icdz
iwne
go,
zeod
daw
naby
lyob
iekt
emza
inte
reso
wan
iasz
tucz
nej
inte
ligen
cji.
Met
ody
prze
szuk
iwan
iaw
prze
strz
eni
stan
owni
eda
jasi
eb
ezp
osre
dnio
zast
osow
acw
typ
owej
grze
dwuo
sob
owej
zew
zgle
duna
koni
eczn
osc
uwzg
ledn
ieni
aru
chow
prze
ciw
nika
,kt
ore
nie
sazn
ane.
”Roz
wia
zani
em”
mus
iby
ctu
sche
mat
uwzg
ledn
iaja
cyw
szys
tkie
moz
liwe
reak
cje
prze
ciw
nika
.
Dod
atko
wo,
wni
ekto
rych
grac
hp
e lna
wie
dza
ost
anie
wog
ole
nie
jest
dost
epna
dla
obu
grac
zy.
Rod
zaje
gier
:
dete
rmin
isty
czne
loso
we
zp
e lna
szac
hy,
war
caby
,ba
ckga
mm
on,
info
rmac
jago
,ot
hello
mon
opol
zni
epe l
nast
atki
,ko
lko
ibr
ydz,
pok
er,
info
rmac
jakr
zyzy
kna
slep
osc
rabb
le
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
dla
gie
r5
5
Drz
ew
og
ryd
wu
oso
bo
we
j
XX
XX
XX
X
XX
MA
X (
X)
MIN
(O
)
XX
O
OO
XO O
OO
OO
O
MA
X (
X)
XO
XO
XO
XX
X
XX
XX
MIN
(O
)
XO
XX
OX
XO
X
. . .
. . .
. . .
. . .
. . .
. . .
. . .
TE
RM
INA
LX
X
−1 0
+1U
tility
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
dla
gie
r5
6
Page 15
Pro
ced
ura
min
ima
ksu
Moz
naw
yzna
czyc
opty
mal
nast
rate
gie
gry
dla
gry
dete
rmin
isty
czne
jz
pe l
nain
form
acja
zap
omoc
ana
step
ujac
ejpr
oced
ury,
zwan
ejpr
oced
ura
min
ima
x.O
blic
zaon
aw
arto
scw
ez la
star
tow
ego
prze
zpr
opag
acje
war
tosc
iko
ncow
ych
(war
tosc
iw
ygra
nej
dla
nasz
ego
grac
za)
wgo
redr
zew
agr
y:
1.p
ozio
my
drze
wa
odp
owia
daja
ruch
omgr
aczy
:M
AX
-ai
MIN
-a;
przy
jmuj
emy,
zeM
AX
ma
pier
wsz
yru
ch,
2.st
anom
term
inal
nym
wlis
ciac
hdr
zew
apr
zypi
suje
my
war
tosc
wyg
rane
jM
AX
’a(u
jem
na,
jesl
ifa
ktyc
znie
jest
toje
gopr
zegr
ana)
3.w
ez lo
mdr
zew
ap
owyz
ejlis
cipr
zypi
suje
my
stop
niow
ow
arto
sci:
mak
sym
alna
zew
szys
tkic
hga
lezi
jesl
iw
eze l
odp
owia
daru
chow
iM
AX
-a,
im
inim
alna
zew
szys
tkic
hga
lezi
jesl
iw
eze l
odp
owia
daru
chow
iM
IN-a
,4.
najw
yzsz
aga
laz
ona
jwie
ksza
war
tosc
iaw
skaz
uje
opty
mal
nyru
chM
AX
-a.
MA
X
312
86
42
145
2
MIN
3
A1
A3
A2
A13
A12
A11
A21
A23
A22
A33
A32
A31
32
2
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
57
Og
ran
icze
nie
zaso
bo
w—
zast
oso
wa
nie
he
ury
styk
i
Pro
cedu
ram
inim
aksu
defi
niuj
eop
tym
alna
stra
tegi
egr
acza
przy
za lo
zeni
u,ze
prze
ciw
nik
row
niez
gra
opty
mal
nie.
Jedn
akty
lko
pod
war
unki
em,
zeda
sie
prze
anal
izow
acca
ledr
zew
ogr
y.
Dla
praw
dziw
ego
drze
wa
gry
moz
eby
cz
tym
prob
lem
.N
p.,
dla
szac
how
b≈
35,m
≈100
dla
sens
owne
jro
zgry
wki
,i
kom
plet
nedr
zew
ogr
ym
oze
mie
cok
o lo35
100≈
10155
wez
low
.(L
iczb
aat
omow
wzn
anej
czes
ciW
szec
hsw
iata
szac
owan
aje
stna
1080.)
Aby
rozw
iaza
cte
npr
oble
m,
moz
nap
os lu
zyc
sie
he
ury
styc
zna
fun
kcja
oce
ny
war
tosc
ip
ozy
cji,
aby
pod
obni
eja
kw
zwyk
lych
met
odac
hpr
zesz
ukiw
ania
prze
strz
eni
stan
ow,
wyz
nacz
acdo
bry
ruch
bez
pos
iada
nia
jaw
nej
repr
ezen
tacj
ica
lej
prze
strz
eni.
Wpr
zypa
dku
gry
dwuo
sob
owej
poz
wol
i loby
toza
stos
owac
tesa
ma
zasa
dem
inim
aksu
,al
eog
rani
czyc
anal
ize
doki
lku
ruch
ow.
Dla
szac
how
,m
ozna
taka
ocen
eob
liczy
cja
kow
arto
scm
ate
ria
lna
pos
iada
nych
figu
r,np
.1
zapi
ona,
3za
wie
zelu
bgo
nca,
5za
skoc
zka,
i9
zahe
tman
a.D
odat
kow
om
ozna
uwzg
ledn
icw
arto
scp
ozyc
jita
kich
jak
”dobr
ero
zsta
wie
nie
pion
ow”,
alb
ow
yzsz
aw
arto
scw
iezy
wko
ncow
cegr
y,a
jesz
cze
wyz
sza
dwoc
hw
iez.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
58
Za
sto
sow
an
ieh
eu
ryst
yk—
sytu
acj
esp
ecj
aln
e
Ogr
anic
zeni
eg l
ebok
osci
anal
izy
czas
ami
prow
adzi
dosy
tuac
jisz
czeg
olny
ch,
ktor
ew
ymag
aja
niec
ozm
odyfi
kow
aneg
op
odej
scia
.
Jedn
az
nich
jest
zaga
dnie
nie
op
an
ow
an
eg
oza
gro
zen
ia.
Wni
ekto
rych
sytu
acja
chfu
nkcj
aoc
eny
moz
esu
gero
wac
war
tosc
iko
rzys
tne
dla
jedn
ego
zgr
aczy
,al
ena
jbliz
sze
ruch
y—
poz
ag l
ebok
osci
auw
zgle
dnio
napr
zez
funk
cje
prze
szuk
iwan
ia—
nieu
chro
nnie
dopr
owad
zado
dras
tycz
nej
zmia
ny.
Roz
wia
zani
emje
stw
ykry
wan
ieta
kich
nies
tabi
lnyc
hsy
tuac
jiza
groz
enia
ip
og le
bien
iepr
zesz
ukiw
ania
azdo
osia
gnie
cia
stan
owba
rdzi
ejst
abiln
ych
(quiescentstates
).
Inny
mpr
oble
mem
jest
pro
ble
mh
ory
zon
tu.
Ma
onm
iejs
cew
tedy
,gd
yna
dcho
dzi
nieu
chro
nne
zagr
ozen
iedl
aje
dneg
oz
grac
zy,
ale
jest
onw
stan
ieod
suw
acje
wcz
asie
wyk
onuj
acru
chy,
ktor
eje
dnak
nie
rozw
iazu
japr
oble
mu.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
59
Prz
esz
uk
iwa
nie
min
ima
x—
od
cin
an
iep
rze
szu
kiw
an
ia
Na
jaki
eef
ekty
prak
tycz
nem
ozna
liczy
cst
osuj
acoc
ene
heur
ysty
czna
nag l
ebok
osci
kilk
uru
chow
?
Np.
,dl
asz
acho
w,
przy
jmuj
ac10
6w
ez lo
wna
seku
nde,
i180
seku
ndna
ruch
,m
ozem
yzb
adac
108≈
355
poz
ycji,
czyl
ido
5ru
chow
wpr
zod.
Pro
gram
graj
acy
wte
nsp
osob
zach
owuj
esi
era
cjon
alni
e,le
czpr
zeci
etne
mu
cz lo
wie
kow
ini
etru
dno
zni
mw
ygra
c.P
otrz
ebne
sado
datk
owe
met
ody
zwie
ksza
jace
efek
tyw
nosc
prze
szuk
iwan
ia.
Lat
wo
zauw
azyc
,ze
moz
naw
anal
izie
min
imak
sow
ejdr
zew
agr
yp
oczy
nic
pew
neos
zcze
dnos
ci.
Naj
pros
tsze
zni
chna
zyw
ane
saod
ciec
iam
ial
fa-b
eta.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
60
Page 16
Od
cie
ciaα
–β
—il
ust
racj
a
Cw
icze
nie:
znaj
dzb l
adw
pow
yzsz
ymdr
zew
ie(z
rod l
o:P
atri
ckH
enry
Win
ston
,ArtificialIntelligence
,3r
ded
.).
Odp
owiedz:
wkroku
10
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
61
Od
cie
ciaα
–β
—a
lgo
rytm
PROCEDUREMINIMAX-ALPHA-BETA(n,alpha,beta,depth)
BEGIN
IFdepth==MAXDEPTHTHENRETURN(h(n))
choices:=
Lista_potomkow(n)
WHILE(NOTEmpty(choices))AND(alpha<
beta)DO
;;zaniechaniebadaniakolejnychpotomkowwezlan
oznaczaodciecie
BEGIN
n1
:=First(choices)
choices:=Rest(choices)
w1
:=MINIMAX-ALPHA-BETA(n1,alpha,beta,depth+1)
IF
EVEN(depth)THEN
;dlawezlowMAX’a
IFw1>
alphaTHENalpha:=w1
IF
ODD(depth)THEN
;dlawezlowMIN’a
IFw1<
betaTHENbeta:=w1
END
IFEVEN(depth)THENRETURN(alpha)
;wezelMAX’a
ELSERETURN(beta)
;wezelMIN’a
END
⇒w
pier
wsz
ymw
ywo l
aniu
przy
jmuj
emyα=
−∞
,β=
+∞
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
62
Oci
eci
aα
–β
—p
rzyp
ad
ek
op
tym
aln
y
Opt
ymal
nypr
zypa
dek
prze
szuk
iwan
iam
inim
akso
weg
oz
odci
ecia
mi
alfa
-bet
aza
chod
zigd
yna
kazd
ymp
ozio
mie
wez
lysa
rozp
atry
wan
ew
kole
jnos
ciod
najb
ardz
iej
korz
ystn
ego,
dla
dane
gogr
acza
.W
tedy
wka
zdym
pod
drze
wie
oblic
zana
jest
tylk
oje
dna
”seri
a”w
ez lo
w,
nato
mia
stpr
zyka
zdym
pow
roci
ew
gore
drze
wa
nast
epuj
eod
ciec
ie.
Na
pow
yzsz
ymdi
agra
mie
oszc
zedn
osc
wyn
osi
16w
ez lo
w;
na27
wez
low
nana
jniz
szym
poz
iom
ieob
liczo
nych
mus
iby
cty
lko
11.
Zro
d lo:
Pat
rick
Hen
ryW
inst
on,ArtificialIntelligence
,3r
ded
.(u
wag
a,b l
ad:
wez
ly18
,19
,21
,i
22m
og ly
byro
wni
ezby
cod
ciet
e).
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
63
W la
sno
sci
alg
ory
tmuα
–β
Zas
toso
wan
ieod
ciec
wan
aliz
iedr
zew
am
inim
axni
ezm
ieni
aos
tate
czne
gow
ynik
u,tz
n.ru
chu
grac
za.
Dob
reup
orza
dkow
anie
poz
wal
aos
iagn
acw
ieks
zaef
ekty
wno
scod
cina
nia.
Wgr
anic
y,op
tym
alne
odci
ecia
poz
wal
aja
osia
gnac
O(b
m/2).
Wpr
akty
cep
ozw
ala
top
odw
oic
g leb
okos
cpr
zesz
ukiw
ania
.
Wyn
ikan
aliz
ym
inim
ax/α
–βni
eza
lezy
odko
nkre
tnyc
hw
arto
sci
funk
cji
ocen
y.Is
totn
eje
stty
lko
upor
zadk
owan
iew
arto
sci.
Ozn
acza
to,
zedo
wol
natr
ansf
orm
acja
mon
oton
iczn
afu
nkcj
aoc
eny
dzia
lata
ksa
mo
jak
oryg
inal
nafu
nkcj
a.
MIN
MA
X
211
422
20
1 140
02020
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
64
Page 17
Min
ima
x—
uo
go
lnie
nie
dla
gry
wie
loo
sob
ow
ej
Alg
oryt
mm
inim
aksu
moz
na la
two
uogo
lnic
napr
zypa
dek
gry
wie
loos
obow
ej.
Zam
iast
skal
arne
jna
lezy
zast
osow
acw
ekto
row
afu
nkcj
eoc
eny,
ktor
azw
raca
wek
tor
ocen
war
tosc
ip
ozyc
jiz
punk
tuw
idze
nia
pos
zcze
goln
ych
grac
zy.
Kaz
dygr
acz
mak
sym
aliz
uje
swoj
elem
ent
wek
tora
,i
proc
edur
apr
opag
acji
ocen
yw
gore
drze
wa
gry
prze
bieg
ap
odob
nie
jak
wpr
zypa
dku
gry
dwuo
sob
owej
.
to m
ove
A B C A
( 1,
2, 6
)(
4, 2
, 3)
( 6,
1, 2
)(
7, 4
,−1)
( 5,
−1,
−1)
(−1,
5, 2
)(7
, 7,−
1)(
5, 4
, 5)
( 1,
2, 6
)(
6, 1
, 2)
(−1,
5, 2
)(
5, 4
, 5)
( 1,
2, 6
)(−
1, 5
, 2)
( 1,
2, 6
)
Wgr
ach
wie
loos
obow
ych
poj
awia
jasi
eje
dnak
doda
tkow
eel
emen
tyst
rate
gii
taki
eja
kso
jusz
e.C
zasa
mi
grac
zom
op la
casi
eza
wie
rac
soju
sze
prze
ciw
inny
mgr
aczo
m,
ana
wet
dyna
mic
znie
zmie
niac
teso
jusz
ew
trak
cie
rozg
ryw
ki.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
65
Pra
kty
ka
ko
mp
ute
row
ych
gie
rd
wu
oso
bo
wyc
h
War
caby
:pr
ogra
mC
hino
okw
1994
zako
nczy
l40
-let
nia
dom
inac
jem
istr
zasw
iata
Mar
iona
Tin
sley
a1R
okpo
znie
jpr
ogra
mp
okon
a lko
lejn
ego
mis
trza
.
Sza
chy:
prog
ram
Dee
pB
lue
w19
97p
ora
zpi
erw
szy
pok
ona l
mis
trza
swia
taG
ary
Kas
paro
wa
wot
war
tym
mec
zu(r
okw
czes
niej
mis
trz
prze
gra l
zty
msa
mym
prog
ram
empi
erw
sza
gre)
.P
rzez
kole
jne
10la
tpr
ogra
my
szac
how
eni
eod
nios
lyw
ieks
zych
zwyc
iest
w.
Wro
ku20
06pr
ogra
mD
eep
Fri
tzp
okon
a lw
turn
ieju
mis
trza
swia
taV
ladi
mir
aK
ram
nika
.P
oty
mzw
ycie
stw
ieza
inte
reso
wan
iero
zgry
wka
mi
najle
pszy
chpr
ogra
mow
zlu
dzm
iza
cze l
osp
adac
.
Oth
ello
:m
istr
zow
ieni
ech
cagr
acz
kom
pute
ram
i,kt
ore
sazb
ytdo
bre.
Go:
mis
trzo
wie
nie
chca
grac
zko
mpu
tera
mi,
ktor
esa
zbyt
s lab
e.W
gob>
300
wie
cza
mia
stsy
stem
atyc
zneg
opr
zesz
ukiw
ania
drze
wa
gry,
wie
kszo
scpr
ogra
mow
uzyw
are
gu lo
wej
bazy
wie
dzy
doge
nera
cji
ruch
ow.
1A
czko
lwie
km
istr
zw
yco
fa l
sie
ztu
rnie
juz
przy
czyn
zdro
wo
tnyc
hi
wkr
otc
ep
ote
mzm
ar l
na
raka
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
66
Za
sto
sow
an
iem
inim
ak
sui
he
ury
styk
do
gry
ww
arca
by
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
67
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
min
imax
68
Page 18
Gry
ze
lem
en
tam
ilo
sow
ymi
—e
xpe
ctim
ax
Jeze
liw
grze
wys
tepu
jecz
ynni
klo
sow
y,np
.w
ynik
pew
nych
ruch
owza
lezy
odel
emen
tulo
sow
ego,
jak
rzut
kost
ka,
toan
aliz
ata
kiej
gry
jest
bard
ziej
z loz
ona.
Wym
aga
rozw
azen
iaw
szys
tkic
hm
ozliw
osci
,i
oblic
zani
aw
arto
sci
ocze
kiw
anej
po
dyst
rybu
cji
zmie
nnyc
hlo
sow
ych
repr
ezen
tuja
cych
elem
enty
loso
we.
Na
przy
k lad
,m
ozna
rozw
azac
gry
jedn
ooso
bow
ez
czyn
niki
emlo
sow
ym.
Co
drug
ikr
okje
stw
ybor
emgr
acza
,kt
ory
mak
sym
aliz
uje
war
tosc
swoj
ejfu
nkcj
ioc
eny,
aco
drug
ikr
okje
stlo
sow
y(l
ubtr
aktu
jem
ygo
jako
loso
wy)
,ze
znan
ymze
staw
emw
ynik
owi
znan
ymro
zk la
dem
praw
dop
odob
iens
twa
tych
wyn
ikow
.A
lgor
ytm
dost
osow
any
doan
aliz
yta
kich
gier
nazy
wa
sie
exp
ect
ima
x.
Met
od
ypr
zesz
uki
wan
ia—
exp
ecti
max
69
Da
lsze
uo
go
lnie
nie
—e
xpe
ctim
inim
ax
Pe l
neuo
goln
ieni
eal
gory
tmu
min
imak
suo
czyn
niki
loso
we
nazy
wam
yuw
zgle
dnia
ruch
ygr
aczy
MA
Xa
iM
INa
oraz
krok
ilo
sow
e.A
lgor
ytm
anal
izy
drze
wa
taki
ejgr
yna
zyw
asi
ee
xpe
ctim
inim
ax.
Met
od
ypr
zesz
uki
wan
ia—
exp
ecti
max
70
He
ury
styc
zna
fun
kcj
ao
cen
yw
exp
ect
imin
ima
x
Zau
waz
my
rozn
ice
w la
snos
ciw
odni
esie
niu
dost
osow
anej
funk
cji
ocen
y.W
ybor
ruch
una
pod
staw
iean
aliz
ym
inim
axje
stid
enty
czny
dla
wsz
ystk
ich
funk
cji
ocen
yda
jace
jte
nsa
mp
orza
dek
wez
low
.T
ejw
lasn
osci
nie
zach
owuj
eex
pec
tim
inim
ax,
jak
wid
acna
pon
izsz
ymry
sunk
u.R
uch
wyb
rany
dla
prze
dsta
wio
nych
drze
wje
stro
zny,
ab
ezkr
oku
loso
weg
oza
kazd
ymra
zem
wyb
rany
by lb
ypr
awy.
DIC
E
MIN
MA
X
22
33
11
44
23
14
.9.1
.9.1
2.1
1.3
2020
3030
11
400
400
2030
140
0
.9.1
.9.1
2140
.9
Wpr
zypa
dku
exp
ecti
min
imak
sufu
nkcj
aoc
eny
nie
moz
eby
cdo
wol
nafu
nkcj
ap
opra
wni
ep
orza
dkuj
aca
ocen
iane
poz
ycje
.W
prak
tyce
mus
ion
aod
zwie
rcie
dlac
ocze
kiw
ana
wyg
rana
(lub
jej
doda
tnia
linio
wa
tran
sfor
mac
je).
Met
od
ypr
zesz
uki
wan
ia—
exp
ecti
max
71
Met
od
ypr
zesz
uki
wan
ia—
exp
ecti
max
72
Page 19
Gry
zn
iep
e ln
ain
form
acj
a
Prz
yk la
d:ro
zne
gry
wka
rty.
Moz
naob
liczy
cpr
awdo
pod
obie
nstw
aw
szys
tkic
hko
mbi
nacj
iro
zdan
ia.
Idea
:ob
licz
war
tosc
min
imax
kazd
ejm
ozliw
ejak
cji
dla
kazd
ego
rozd
ania
,na
step
nie
wyb
ierz
akcj
ez
najw
ieks
zaw
arto
scia
ocze
kiw
ana
oblic
zona
dla
wsz
ystk
ich
moz
liwyc
hro
zdan
.
Naj
leps
zepr
ogra
my
dogr
yw
bryd
zaim
plem
entu
jato
pod
ejsc
iepr
zez
wyg
ener
owan
iew
ielu
rozd
anzg
odny
chz
info
rmac
jaw
ywni
osko
wan
az
doty
chcz
asow
ego
prze
bieg
ulic
ytac
jii
rozg
ryw
ki,
iw
ybie
raja
akcj
e,kt
ora
mak
sym
aliz
uje
liczb
ew
ygra
nych
.
Met
od
ypr
zesz
uki
wan
ia—
gry
zn
iep
e ln
ain
form
acja
73
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.D
lap
oniz
szeg
odr
zew
agr
ydw
uoso
bow
ej,
pod
ajdo
k lad
nase
kwen
cje
war
tosc
ifu
nkcj
ioc
eny
oblic
zony
chpr
zez
algo
rytm
min
imak
suz
odci
ecia
mi
alfa
/bet
a(w
por
zadk
uod
lew
ejdo
praw
ej).
MA
X
312
86
42
145
2
MIN
3
A1
A3
A2
A13
A12
A11
A21
A23
A22
A33
A32
A31
32
2
Met
od
ypr
zesz
uki
wan
ia7
4
Prz
esz
uk
iwa
nie
zw
ieza
mi
Zag
adni
enia
prze
szuk
iwan
iaz
wie
zam
i(Constrained
SatisfactionProblem,
CSP
),al
bo
zog
rani
czen
iam
i,st
anow
iasp
ecyfi
czna
grup
epr
oble
mow
prze
szuk
iwan
iaw
prze
strz
eni
stan
ow,
zdefi
niow
ane
jako
:
•sk
oncz
ony
zbio
rzm
ienn
ychX
={x
1,x
2,...,x
n}
•dl
aka
zdej
zmie
nnejxi
skon
czon
yzb
ior
moz
liwyc
hje
jw
arto
sci,
zwan
yd
zie
dzi
na
dane
jzm
ienn
ej
•sk
oncz
ony
zbio
rw
iezo
w(constraints
),zw
anyc
hro
wni
ezog
rani
czen
iam
i,na
kom
bina
cje
war
tosc
izm
ienn
ych,
np.,
jesl
ix1=
5,to
x2
mus
iby
cpa
rzys
te,
ako
mbi
nacj
a(x
1=
5,x2=
8,x3=
11)
jest
nied
ozw
olon
a
Roz
wia
zani
empr
oble
mu
CS
Pje
stka
zda
kom
bina
cja
war
tosc
izm
ienn
ych,
ktor
asp
e lni
aw
szys
tkie
wie
zy.
Zau
waz
my,
zepr
oble
my
CS
Psa
wis
toci
esz
czeg
olny
mpr
zypa
dkie
mog
olne
gopr
zesz
ukiw
ania
wpr
zest
rzen
ist
anow
,je
sli
pot
rakt
ujem
yzb
ior
wie
zow
jako
spec
yfika
cje
celu
,a
przy
pisy
wan
iew
arto
sci
zmie
nnym
jako
oper
ator
y.M
ozna
zate
mza
stos
owac
doty
chza
gadn
ien
wsz
ystk
iew
czes
niej
poz
nane
met
ody.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
75
Prz
esz
uk
iwa
nie
zw
ieza
mi
—b
lizs
zaa
na
liza
Prz
yk la
dypr
oble
mow
CS
P:
kolo
row
anie
graf
ulu
bm
apy,
prob
lem
8-he
tman
ow(k
lasy
ka),
prob
lem
SA
T(p
rzyp
isan
iew
arto
sci
0/1
elem
ento
mfo
rmu l
ylo
gicz
nej
spe l
niaj
ace
tefo
rmu l
e),
kryp
toar
ytm
etyk
a,pr
ojek
tow
anie
uk la
dow
VL
SI,
tzw
.pr
oble
met
ykie
tow
ania
wez
low
poz
wal
ajac
yro
zpoz
naw
acob
iekt
yna
obra
zach
po
ich
kont
urow
aniu
,ko
lejk
owan
ieza
dan,
plan
owan
ie,
iw
iele
inny
ch.
Wie
lesp
osro
dty
chza
gadn
ien
stan
owia
prob
lem
yN
P-t
rudn
e.
Roz
wia
zani
epr
oble
mu
CS
Pm
oze
istn
iec
lub
nie,
badz
moz
eis
tnie
cw
iele
rozw
iaza
n.C
elem
prze
szuk
iwan
iam
oze
byc
znal
ezie
nie
jedn
ego
dow
olne
goro
zwia
zani
a,w
szys
tkic
hro
zwia
zan,
badz
rozw
iaza
nia
opty
mal
nego
wse
nsie
jaki
ejs
dane
jfu
nkcj
iko
sztu
.
Moz
natr
akto
wac
wie
zyw
yste
puja
cew
CS
Pja
kobi
narn
e,cz
yli
obej
muj
ace
pary
zmie
nnyc
h.W
iezy
obej
muj
ace
wie
cej
zmie
nnyc
hm
ozna
prze
kszt
a lci
cna
bina
rne,
aw
iezy
nap
ojed
yncz
ezm
ienn
em
ozna
wbu
dow
acw
defi
nicj
eic
hdz
iedz
iny.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
76
Page 20
Lo
ka
lne
spe
lnia
nie
wie
zow
Roz
waz
my
prob
lem
kolo
row
ania
map
y.N
alez
yta
kpr
zypi
sac
obsz
arom
dane
jm
apy
kolo
ryze
zbio
row
dopu
szcz
alny
chko
loro
w,
byc
moz
ero
znyc
hdl
aro
znyc
hob
szar
ow,
aby
obsz
ary
sasi
aduj
ace
mia
lypr
zypi
sane
rozn
eko
lory
.
D1=
{R,G
,B}
D2=
{R,G
}
D3=
{R}
Zan
imza
czni
emy
prze
szuk
iwac
prze
strz
enm
ozliw
ych
pod
staw
ien
war
tosc
izm
ienn
ych,
moz
emy
prze
prow
adzi
cp
ewne
anal
izy
loka
lne
go
spe l
nian
iaw
iezo
w.
Roz
waz
my
gra
fw
iezo
w,
ktor
ego
wez
lyod
pow
iada
jazm
ienn
ym,
a lu
ki—
wie
zom
oryg
inal
nego
prob
lem
u(b
inar
nym
).T
rakt
ujem
y lu
kgr
afu
jako
pare
prze
ciw
sobn
ych
luko
wsk
iero
wan
ych,
iok
resl
amy
spo
jno
sc lu
kow
a(arc
consistency
) lu
kusk
iero
wan
egoxi−→
xj
graf
u,kt
ora
zach
odzi
jesl
i∀x∈D
i∃y∈D
ji
para
(x,y)
spe l
nia
wsz
ystk
iew
iezy
okre
slon
ena
luk.
Moz
napr
zyw
roci
csp
ojno
scni
espo
jnym
luko
mpr
zez
usuw
anie
war
tosc
iz
dzie
dzin
pew
nych
zmie
nnyc
h(k
onkr
etni
e,ty
chw
arto
scix∈D
idl
akt
oryc
hni
eis
tnie
jew
arto
scy∈D
jsp
e lni
ajac
aja
kis
wyb
rany
wie
z).
Ta
proc
edur
ap
ozw
ala
nazr
eduk
owan
iei
upro
szcz
enie
oryg
inal
nego
prob
lem
u.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
77
Sp
ojn
osc
luko
wa
Roz
waz
my
nast
epuj
ace
przy
k lad
owe
zaga
dnie
nie
kolo
row
ania
map
y:D
1=
{R,G
,B},
D2=
{R,G
},D
3=
{R},
C=
{x16=
x2,x
26=
x3,x
16=
x3}.
D2=
{R,G
}
D1=
{R,G
,B}
D3=
{R}
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
x1∈{
R,G
,B}
x2∈{
R,G}
x3∈{
R}
6=
6=
6=
Dla
luku
(x1—x2)
spoj
nosc
luko
wa
zach
odzi
,p
onie
waz
zaro
wno
∀x∈D
1∃y∈D
2x6=
yja
ki∀y∈D
2∃x∈D
1x6=
y.
Fak
tza
chod
zeni
asp
ojno
sci
luko
wej
tow
efek
cie
niez
byt
poz
ytyw
naw
iado
mos
c.O
znac
zaon
,ze
anal
iza
spoj
nosc
ite
goko
nkre
tneg
o lu
kuw
grafi
eni
cni
ew
nosi
.Je
dnak
pe l
naan
aliz
agr
afu
CS
Pm
oze
czas
ami
przy
nies
cba
rdzo
wym
iern
ew
ynik
i.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
78
Prz
yk la
d:
ko
loro
wa
nie
ma
py
Pon
owni
ero
zwaz
my
zaga
dnie
nie
kolo
row
ania
map
y:D
1=
{R,G
,B},
D2=
{R,G
},D
3=
{R},
C=
{x16=
x2,x
26=
x3,x
16=
x3}.
Ana
liza
pier
wsz
ego
wie
zu(x
16=
x2)
nie
daje
zadn
ych
wyn
ikow
,b
o,ja
kju
zst
wie
rdzi
lism
y,dl
ate
gow
iezu
istn
ieje
spoj
nosc
luko
wa.
(Dla
kazd
ejw
arto
sci
zD
1is
tnie
jewD
2w
arto
scsp
e lni
ajac
aog
rani
czen
ie,
ina
odw
rot.
)
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
x1∈{
R,G
,B}
x2∈{
R,G}
x3∈{
R}
6=
6=
6=
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
x1∈{
R,G
,B}
x2∈{6R
,G}
={
G}
x3∈{
R}
6=
6=
6=
Jedn
akan
aliz
adr
ugie
gow
iezu
(x26=
x3)
przy
nosi
pew
nep
ozyt
ywne
rezu
ltat
y.O
iledl
ax3=
Ris
tnie
jeod
pow
iedn
iaw
arto
scdl
ax2,
todl
ax2=
Rni
eda
sie
dobr
acw
arto
scix3
spe l
niaj
acej
ten
wie
z.Z
atem
war
tosc
Rm
ozem
yus
unac
zdz
iedz
iny
zmie
nnejx2.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
79
Prz
yk la
d:
ko
loro
wa
nie
ma
py
(cd
.)
Pod
obna
anal
iza
wod
nies
ieni
udo
wie
zu(x
16=
x3)
poz
wal
aw
yklu
czyc
zdz
iedz
iny
zmie
nnejx1
war
tosc
R:
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
x1∈{6R
,G,B}
={
G,B}
x2∈{6R
,G}
={
G}
x3∈{
R}
6=
6=
6=
Ana
liza
wsz
ystk
ich
wie
zow
zako
nczy
lasi
ecz
esci
owym
usun
ieci
emw
arto
sci
zdz
iedz
inzm
ienn
ych.
Zag
adni
enie
zost
a lo
zred
ukow
ane
(mni
ejje
stm
ozliw
ych
przy
pisa
nw
arto
sci
zmie
nnym
),al
ena
dal
istn
ieje
wie
cej
niz
jedn
op
oten
cjal
nero
zwia
zani
e.
Lat
wo
jedn
akza
uwaz
yc,
zean
aliz
esp
ojno
sci
luko
wej
moz
na,
ina
lezy
,ko
ntyn
uow
ac.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
80
Page 21
Pro
pa
ga
cja
wie
zow
Pon
iew
azw
ynik
iem
spra
wdz
ania
spoj
nosc
i lu
kow
ejje
stre
dukc
jadz
iedz
inni
ekto
rych
zmie
nnyc
h,m
ase
nsje
gop
owto
rzen
iena
wet
dla
luko
wgr
afu,
ktor
epi
erw
otni
esp
ojno
scp
osia
da ly
,ba
dzzo
sta l
aim
ona
przy
wro
cona
.P
row
adzi
todo
pro
pa
ga
cji
wie
zow
,cz
yli
pow
tarz
ania
anal
izy
spoj
nosc
iw
i ezo
wi
redu
kcji
dzie
dzin
tak
d lug
oja
kda
jeto
jaki
esef
ekty
.
Pro
paga
cja
wie
zow
wom
awia
nym
przy
k lad
zie
kolo
row
ania
map
yp
owod
uje
dla
luku
(x16=
x2)
—p
ocza
tkow
osp
ojne
go—
usun
ieci
ew
arto
sci
Gz
dzie
dzin
yx1:
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
x1∈{6R
,6G
,B}
={
B}
x2∈{6R
,G}
={
G}
x3∈{
R}
6=
6=
6=
Ost
atec
znie
wsz
ystk
iezm
ienn
em
aja
jedn
oele
men
tow
edz
iedz
iny,
iw
doda
tku
zaw
arte
wni
chw
arto
sci
spe l
niaj
aw
szys
tkie
wie
zy.
Zat
empr
opag
acja
wie
zow
dopr
owad
zi la
wty
mpr
zypa
dku
dozn
alez
ieni
aje
dyne
goro
zwia
zani
a.
Wog
olno
sci
jedn
akan
aliz
asp
ojno
sci
ipr
opag
acja
wie
zow
prow
adzi
jedy
nie
doup
rosz
czen
ia,
ani
ekon
iecz
nie
doca
lkow
iteg
oro
zwia
zani
apr
oble
mu.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
81
Sp
ojn
osc
luko
wa
—p
rzyk
lad
yn
iero
zwia
zan
e
Jak
latw
oza
uwaz
yc,
wpr
zeds
taw
iony
mtu
inny
mpr
zyk l
adzi
eza
gadn
ieni
ako
loro
wan
iam
apy,
wsz
ystk
ie lu
kisa
spoj
ne.
Pom
imo
to,
zaga
dnie
nie
nie
pos
iada
rozw
iaza
nia.
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
D1={
R,G}
D2={
R,G}
D3={
R,G}
6=
6=
6=
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
D1={
B,G}
D2={
R,G}
D3={
R,G}
6=
6=
6=
Wko
lejn
ympr
zyk l
adzi
ep
onow
nie
wsz
ystk
ie lu
kisa
spoj
ne.
Zag
adni
enie
pos
iada
dwa
rozw
iaza
nia,
lecz
prop
agac
jaw
iezo
wni
ep
ozw
ala
ich
wyz
nacz
yc,
aw
recz
nie
przy
nosi
zadn
ych
redu
kcji
dzie
dzin
zam
ienn
ych.
Jesl
ido
pop
rzed
nieg
opr
zyk l
adu
doda
my
wie
z:(x
16=
B)∨(x
26=
R)
toot
rzym
amy
war
iant
,w
ktor
ymty
lko
jedn
oz
dwoc
hro
zwia
zan
jest
dopu
szcz
alne
,al
eni
eda
sie
gow
yzna
czyc
met
oda
prop
agac
jiw
iezo
w.
✉✟
✟✟
✟✟
✟✟
✟✟
✟✟ ✟✉ PPPPPPPPP✉✂✂✂✂✂✂✂✂✂
D1={
B,G}
D2={
R,G}
D3={
R,G}
6=(x
16=
B)
∨(x
26=
R)
6=
6=
Zat
emob
licza
nie
spoj
nosc
i lu
kow
eji
prop
agac
jaw
iezo
wsa
me
wso
bie
nie
gwar
antu
jazn
alez
ieni
aro
zwia
zani
a.K
onie
czne
jest
prze
szuk
iwan
ie.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
82
Alg
ory
tmy
pro
pa
ga
cji
wie
zow
Naj
pros
tszy
msp
osob
emsp
raw
dzan
iasp
ojno
sci
luko
wej
jest
bran
iep
oko
lei
wsz
ystk
ich
wie
zow
,i
oblic
zani
eic
hw
arun
kow
logi
czny
ch,
oraz
pow
tarz
anie
proc
esu
tak
d lug
o,az
pe l
nycy
klsp
raw
dzan
iaw
szys
tkic
hw
iezo
wni
epr
zyni
esie
zadn
ych
zmia
n.P
rzy
wie
luw
ieza
chm
oze
totr
wac
d lug
o.Je
dnak
pon
iew
azte
sam
ew
arun
kisp
raw
dzan
esa
wie
lera
zy,
moz
liwe
sap
ewne
oszc
zedn
osci
.
Moz
naza
uwaz
yc,
zep
ow
ykon
aniu
redu
kcji
pew
nej
dzie
dzin
yD
ipr
opag
acja
moz
epr
zyni
esc
now
yw
ynik
tylk
opr
zyp
owto
rnym
spra
wdz
aniu
luko
wo
pos
taci
(Dk,D
i),
ity
lko
taki
ew
arto
spra
wdz
ac.
Co
wie
cej,
przy
jaki
ejko
lwie
kre
dukc
jiwD
kni
em
aju
zp
otrz
eby
spra
wdz
ania
luku
(Di,D
k),
pon
iew
azel
emen
tyus
unie
tew
wyn
iku
tej
redu
kcji
zD
kni
eby
lyju
zp
otrz
ebne
dla
zap
ewni
enia
spe l
nien
iaja
kieg
okol
wie
kw
iezu
dla
zadn
ego
elem
entu
zD
i.T
aki
spos
obpr
opag
acji
wie
zow
nazy
wa
sie
algo
rytm
emA
C-3
(197
7).
Kie
dysp
ojno
sc lu
kusp
raw
dzan
aje
stp
ora
zko
lejn
y,w
arun
kisa
spra
wdz
ane
dla
tych
sam
ych
par
war
tosc
i.Z
apam
ieta
nie
tych
spra
wdz
onyc
hpa
rw
arto
sci
wod
pow
iedn
iej
stru
ktur
zeda
nych
poz
wol
i loby
nie
pow
tarz
acic
hsp
raw
dzan
iaw
kole
jnyc
hcy
klac
h.W
ykor
zyst
uje
toal
gory
tmpr
opag
acji
wie
zow
AC
-4(1
986)
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
83
Nie
bin
arn
ew
iezy
Na
poc
zatk
upr
zyje
lism
yza
loze
nie,
zem
ozna
ogra
nicz
ycsi
edo
rozw
azan
iaw
iezo
wbi
narn
ych,
tzn.
obej
muj
acyc
hdo
k lad
nie
dwie
zmie
nne.
Wie
zyob
ejm
ujac
ew
iece
jzm
ienn
ych
moz
napr
zeks
zta l
cic
nabi
narn
e.
Jede
nz
najp
rost
szyc
hsc
hem
atow
konw
ersj
iw
iezo
wna
bina
rne,
tzw
.ko
do
wa
nie
du
aln
e(dualencoding
)p
oleg
ana
wpr
owad
zeni
uno
wej
zmie
nnej
dla
kazd
ego
wie
zuor
ygin
alne
gopr
oble
mu.
Dzi
edzi
naka
zdej
now
ejzm
ienn
ejje
stzb
ior
n-ek
war
tosc
ity
chor
ygin
alny
chzm
ienn
ych,
ktor
ew
yste
pow
a ly
ww
iezi
e.Z
auw
azm
y,ze
taki
ew
prow
adze
nie
zmie
nnyc
hod
razu
gwar
antu
jein
dyw
idua
lne
spe l
nien
iew
szys
tkic
hw
iezo
w.
Poz
osta
jesp
raw
dzic
,kt
ore
kom
bina
cje
war
tosc
isp
e lni
aja
wsz
ystk
iew
iezy
nara
z.W
tym
celu
kodo
wan
iedu
alne
wpr
owad
zaod
pow
iedn
iew
iezy
,kt
ore
wys
tepu
jap
omie
dzy
wsz
ystk
imi
para
mi
zmie
nnyc
h(n
owyc
h),
ktor
eza
wie
raja
tesa
me
zmie
nne
oryg
inal
ne.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
84
Page 22
Nie
bin
arn
ew
iezy
—p
rzyk
lad
Roz
waz
my
przy
k lad
zaga
dnie
nia
CS
Pz
trze
ma
zmie
nnym
i:X
={x
,y,z},
ich
dzie
dzin
amiD
x,y,z=
{1,2,3},
idw
oma
wie
zam
i:C=
{x+y=
z,x
<y}.
Kod
owan
iedu
alne
dla
tego
prob
lem
uza
wie
radw
iezm
ienn
ei
dwa
wie
zy:
U1
:〈o
c1,[x,y,z]〉,D
U1=
{(1
,2,3),(2
,1,3),(1
,1,2)}
U2
:〈o
c2,[x,y]〉,
DU2=
{(1
,2),(1
,3),(2
,3)}
C1
:arg(1
,U
1)=
arg(1
,U
2)
C2
:arg(2
,U
1)=
arg(2
,U
2)
Nie
stet
y,an
aliz
asp
ojno
sci
dla
tego
prob
lem
uni
cni
ew
nosi
,p
onie
waz
dla
kazd
ejw
arto
sci
jedn
ejzm
ienn
ejis
tnie
jaw
arto
sci
drug
iej
zezg
odny
mi
pos
zcze
goln
ymi
argu
men
tam
i.Je
dnak
wie
kszo
scw
arto
sci
zmie
nnyc
hdu
alny
chst
anow
ian-
kini
edop
uszc
zaln
ew
rozw
iaza
niu
oryg
inal
nego
zada
nia.
Ogo
lnie
,ko
nwer
sja
wie
zow
wie
loar
gum
ento
wyc
hna
bina
rne
prow
adzi
czas
ami
dosf
orm
u low
anpr
oble
mow
,kt
ore
nie
pod
daja
sie
anal
izie
spoj
nosc
i.D
late
goop
raco
wan
oro
wni
ezsz
ereg
algo
rytm
owsp
ojno
sci
luko
wej
dla
wie
zow
wie
loar
gum
ento
wyc
h.T
eal
gory
tmy
nie
bed
atu
omaw
iane
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
85
Sp
ojn
osc
scie
zko
wa
Defi
niuj
emy
dla
graf
uw
iezo
wpr
oble
mu
CS
Pp
ojec
ieK
-sp
ojn
osc
i.G
raf
jest
K-s
pojn
y(d
lap
ewne
goK
),je
sli
dla
dow
olny
ch(K
-1)
zmie
nnyc
h,kt
ore
maj
asp
e lni
one
wsz
ystk
iew
iezy
mie
dzy
soba
,dl
ado
wol
nej
(K-1
)-tk
iw
arto
sci
tych
(K-1
)zm
ienn
ych
spe l
niaj
acej
wsz
ystk
iew
iezy
dla
(K-1
)zm
ienn
ych,
istn
ieje
war
tosc
wdz
iedz
inie
dow
olni
edo
bran
ejK
-tej
zmie
nnej
,ta
ka,
zep
owst
a la
wte
nsp
osob
K-t
kaw
arto
sci
zmie
nnyc
hsp
e lni
aw
szys
tkie
wie
zydl
aK
zmie
nnyc
h.G
raf
wie
zow
jest
siln
ieK
-sp
ojn
yje
sli
jest
K-s
pojn
ydl
aka
zdeg
oJ,
J<K
.
Zau
waz
my,
zezd
efini
owan
aw
czes
niej
spoj
nosc
luko
wa
jest
row
now
azna
siln
ej2-
spoj
nosc
igr
afu
wie
zow
.
Siln
a3-
spoj
nosc
graf
uje
stro
wni
ezna
zyw
ana
spo
jno
scia
scie
zko
wa
(path
consistency
).
Zna
czen
ieK
-spo
jnos
cije
stta
kie,
zeje
sli
graf
prob
lem
uC
SP
zn
wez
lam
ije
stsi
lnien
-spo
jny,
topr
oble
mm
ozna
rozw
iaza
cb
ezpr
zesz
ukiw
ania
.Je
dnak
algo
rytm
yos
iaga
nia
K-s
pojn
osci
saek
spon
encj
alne
,w
iec
zwyk
lesi
eto
nie
op la
ca.
Wyj
atki
emje
stos
labi
ona
wer
sja
spoj
nosc
isc
iezk
owej
—o
gra
nic
zon
asp
ojn
osc
scie
zko
wa
(restrictedpathconsistency
),dl
akt
orej
algo
rytm
jest
czas
emst
osow
any.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
86
Prz
esz
uk
iwa
nie
wza
ga
dn
ien
iach
CS
P
Wza
gadn
ieni
ach
CS
Pm
ozna
stos
owac
wsz
ystk
ieom
owio
new
czes
niej
algo
rytm
ypr
zesz
ukiw
ania
.Je
dnak
ww
i eks
zosc
iis
totn
ietr
udny
chpr
oble
mow
CS
P,
gdzi
ew
iezy
maj
ach
arak
ter
trud
nych
doro
zwia
zani
a,ci
asny
chko
mpr
omis
ow,
najw
ieks
zezn
acze
nie
ma
w la
snie
synt
akty
czna
ise
man
tycz
naan
aliz
aw
iezo
w.
Nat
omia
stzw
ykle
trud
noje
stw
ypra
cow
acuz
ytec
zna
heur
ysty
ke,
ktor
aby
laby
zdol
nap
okie
row
acpr
oces
empr
zesz
ukiw
ania
prze
strz
eni
przy
pisa
nw
arto
sci
zmie
nnym
.
Dla
tego
czes
tost
osow
anym
algo
rytm
emje
stna
jpro
stsz
yz
algo
rytm
owpr
zesz
ukiw
ania
,cz
yli
prze
szuk
iwan
iez
naw
raca
niem
BT
.Z
amia
stdo
brej
heur
ysty
kiw
ybie
raja
cej
najle
psze
moz
liwos
ciw
pier
wsz
ejko
lejn
osci
,te
nal
gory
tmje
stuz
upe l
nion
ylo
kaln
aan
aliz
aw
iezo
w.
Pow
oduj
eto
redu
kcje
liczb
ym
ozliw
osci
wko
lejn
ych
krok
ach
wg l
abal
gory
tmu.
Wsk
rajn
ympr
zypa
dku,
gdyb
ydz
iedz
ina
ktor
ejs
zezm
ienn
ych
zred
ukow
a la
sie
dozb
ioru
pust
ego,
algo
rytm
doko
nuje
naty
chm
iast
oweg
ona
wro
tudo
alte
rnat
ywny
chw
arto
sci
wcz
esni
ejsz
ych
przy
pisa
n.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
87
Prz
yk la
d:
pro
ble
m4
he
tma
no
w
Roz
waz
my
zast
osow
anie
algo
rytm
upr
zesz
ukiw
ania
zna
wra
cani
em(B
T)
dopr
oble
mu
4he
tman
ow.
Pon
izsz
yry
sune
kpr
zeds
taw
iafr
agm
ent
drze
wa
prze
szuk
iwan
ia(n
alez
ypa
mie
tac,
zeal
gory
tmB
Tpr
zesz
ukuj
eto
drze
wo
syst
emat
yczn
ie,
lecz
nie
pam
ieta
ca le
jje
gost
rukt
ury,
aje
dyni
ebi
ezac
asc
iezk
e):
Alg
oryt
moc
zyw
isci
ep
orad
ziso
bie
zpr
oble
mem
,je
dnak
spra
wdz
aw
iele
moz
liwos
ci,
ktor
em
ozna
by la
two
wyk
lucz
ycz
rozw
azan
spra
wdz
ajac
spe l
nien
iew
iezo
w.
Zau
waz
my,
zew
szys
tkie
zazn
aczo
neko
nfigu
racj
eko
ncow
esa
niep
opra
wne
zew
zgle
duna
umie
szcz
enie
drug
iego
hetm
ana,
iw
idac
toju
zna
drug
imp
ozio
mie
zag l
ebie
nia.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
88
Page 23
Prz
yk la
d:
pro
ble
m4
he
tma
no
w(c
d.)
Ocz
ywis
tym
ulep
szen
iem
algo
rytm
uje
stw
iec
naty
chm
iast
owe
spra
wdz
anie
wsz
ystk
ich
wie
zow
bina
rnyc
h,gd
yty
lko
przy
pisa
nezo
stan
azm
ienn
ew
chod
zace
wsk
lad
dane
gow
iezu
.S
twie
rdze
nie
naru
szen
iakt
oreg
okol
wie
kw
iezu
pow
oduj
ena
wro
t.N
azw
iem
yte
nal
gory
tmB
T-E
C(earlychecking)
.Z
auw
azm
y,ze
wcz
esni
ejsz
esp
raw
dzan
iew
i ezo
wza
wsz
esi
eop
laca
,p
onie
waz
tesa
me
wie
zym
usia
lyby
ita
kby
csp
raw
dzon
epo
znie
j.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
89
Prz
yk la
d:
pro
ble
m4
he
tma
no
w(c
d.)
Po l
acze
nie
prze
szuk
iwan
iaz
naw
raca
niem
zm
inim
alna
form
asp
raw
dzan
iasp
ojno
sci
wie
zow
zwan
eje
stal
gory
tmem
spra
wd
zan
iaw
prz
od
BT
-FC
(forwardchecking)
.S
praw
dzan
esa
wsz
ystk
iew
iezy
doty
czac
eka
zdor
azow
op
odst
awio
nej
zmie
nnej
,i
tylk
oon
e.T
enal
gory
tmw
praw
ieka
zdym
przy
padk
uda
jele
psze
wyn
iki
niz
BT
-EC
,i
oczy
wis
cie
BT
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
90
Prz
yk la
d:
pro
ble
m4
he
tma
no
w(c
d.)
Moz
emy
row
niez
zast
osow
acp
e lne
spra
wdz
anie
spoj
nosc
i lu
kow
ej,
zpr
opag
acja
wie
zow
nadz
iedz
iny
wsz
ystk
ich
zmie
nnyc
h,ro
wni
ezty
chje
szcz
eni
epod
staw
iony
ch.
Tak
iw
aria
ntpr
zesz
ukiw
ania
nazy
wan
yje
stal
gory
tmem
BT
-LA
(look-ahead
).W
wie
lupr
zypa
dkac
hp
ozw
ala
tow
yelim
inow
acw
ieks
zosc
prze
szuk
iwan
ia,
jedn
akilo
scob
licze
nw
tym
przy
padk
um
oze
byc
wie
ksza
niz
wpr
zypa
dku
inny
chal
gory
tmow
,ta
kich
jak
BT
-FC
,i
stos
owan
ieB
T-L
Ani
eza
wsz
esi
eop
laca
.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
91
Naw
raca
nie
ste
row
an
eza
lezn
osc
iam
i
Wpr
zesz
ukiw
aniu
drze
wa
CS
Pm
ozem
yna
trafi
cna
por
azke
wyw
o luj
aca
naw
rot
algo
rytm
uB
T,
ktor
ejpr
zycz
yna
nie
by lo
jedn
akos
tatn
iodo
kona
nepr
zypi
sani
ew
arto
sci,
ale
ktor
ysz
wcz
esni
ejsz
ych
krok
ow.
Wta
kim
przy
padk
ual
gory
tmb
edzi
epr
obow
a lro
znyc
hm
ozliw
osci
,st
ale
gene
ruja
cp
oraz
ki,
azdo
mom
entu
,ki
edy
naw
roci
dost
atec
znie
g leb
oko,
izm
ieni
war
tosc
kluc
zow
ejzm
ienn
ej.
Jest
moz
liwe
wyk
ryci
eta
kiej
sytu
acji
—gd
yzb
ior
zmie
nnyc
hw
chod
zacy
chw
wie
zyz
biez
aca
zmie
nna,
tzw
.zb
ior
konfl
ikto
wy
(conflictset)
,ni
eob
ejm
uje
zmie
nnej
osta
tnio
przy
pisa
nej.
Wte
dyna
wro
tm
og lb
yzo
stac
wyk
onan
ydo
osta
tnio
przy
pisa
nej
zmie
nnej
zte
gozb
ioru
.A
lgor
ytm
taki
zwan
yje
stB
J(backjumping)
.
Pro
sty
algo
rytm
BJ
ma
znac
zeni
era
czej
tylk
ohi
stor
yczn
e,p
onie
waz
rozw
iazu
jepr
oble
m,
dokt
oreg
ona
wet
nie
dopu
szcz
aja
algo
rytm
ysp
ojno
sci:
BT
-FC
ida
lsze
.Je
dnak
moz
nask
onst
ruow
acba
rdzi
ejw
yrafi
now
ana
(isz
ersz
a)de
fini
cje
zbio
ruko
nflik
tow
ego,
jako
zbio
ruty
chzm
ienn
ych,
ktor
ych
przy
pisa
new
arto
sci
spow
odow
a ly
por
azke
biez
acej
zmie
nnej
,w
raz
zpo
znie
jpr
zypi
sany
mi
zmie
nnym
i.W
ersj
aB
Jop
arta
nata
kiej
defi
nicj
i,zw
anaconflict-directed
backjumping
wpr
owad
zada
lsze
uspr
awni
enie
proc
esu
prze
szuk
iwan
ia.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
92
Page 24
Dyn
am
iczn
ep
orz
ad
ko
wa
nie
Wsp
omni
elis
my
wcz
esni
ej,
zew
wie
kszo
sci
prob
lem
owC
SP
trud
noo
rzec
zyw
iste
heur
ysty
kiw
spom
agaj
ace
wyb
or”do
bryc
h”ru
chow
nadr
zew
iepr
zesz
ukiw
ania
.Is
tnie
jaje
dnak
inne
tech
niki
wsp
omag
ajac
epr
zesz
ukiw
anie
,zw
iaza
nez
dyn
am
iczn
ymp
orz
ad
kow
an
iem
(dynam
icordering)
zaro
wno
zmie
nnyc
h,dl
akt
oryc
hop
laca
sie
doko
nyw
acpr
zypi
sani
aw
pier
wsz
ejko
lejn
osci
,ja
ki
war
tosc
i,kt
ore
war
topr
obow
acw
pier
w.
Heu
ryst
yka
na
jbar
dzi
ej
og
ran
iczo
ne
jzm
ien
ne
j(m
ostconstrained
variable
)(z
wan
aro
wni
ezM
RV
,minimum
remainingvalues
),su
geru
jew
ybor
zmie
nnyc
hz
najb
ardz
iej
ogra
nicz
onym
i(l
iczn
ymi)
dzie
dzin
ami.
Tak
iw
ybor
daje
najw
ieks
zasz
anse
natr
afien
iana
nies
pojn
osci
,i
wyn
ikaj
acyc
hz
nich
redu
kcji
prob
lem
u.T
ahe
urys
tyka
dobr
zew
spo l
prac
uje
zal
gory
tmem
BT
-FC
.
Inna
jest
heur
ysty
karz
ed
u(degreeheuristic
),su
geru
jaca
wyb
orzm
ienn
ejw
yste
puja
cej
wna
jwie
ksze
jlic
zbie
wie
zow
zni
epod
staw
iony
mi
zmie
nnym
i.
Po
wyb
orze
zmie
nnej
przy
daje
sie
heur
ysty
kan
ajm
nie
jo
gra
nic
zon
ej
war
tosc
i(least
constrainingvalue)
,pr
efer
ujac
aw
arto
sci
wyk
lucz
ajac
ena
jmni
ejw
arto
sci
inny
chzm
ienn
ych.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
93
Prz
esz
uk
iwa
nie
loka
lne
wza
ga
dn
ien
iach
CS
P
Moz
liwe
jest
jesz
cze
inne
pod
ejsc
iedo
prob
lem
owC
SP
,p
oleg
ajac
ena
mni
ejlu
bba
rdzi
ejpr
zypa
dkow
ymw
ybor
zew
step
nego
przy
pisa
nia
war
tosc
izm
ienn
ych,
ina
step
nie
napr
awie
nia
go,
jesl
ina
rusz
a lo
jaki
esw
iezy
.C
ow
iece
j,pr
oces
tego
napr
awia
nia
pol
ega
napr
zesz
ukiw
aniu
zach
lann
ym,
aw
iec
nies
yste
mat
yczn
ym.
Jedn
az
heur
ysty
ksp
raw
dzaj
acyc
hsi
ew
prze
szuk
iwan
iulo
kaln
ymje
sthe
urys
tyka
zwan
amin-conflict
ip
oleg
ajac
ana
loso
wym
wyb
orze
jedn
ejze
zmie
nnyc
h,kt
oryc
hw
arto
scna
rusz
aja
kies
wie
zy,
ipr
zypi
sani
uje
jin
nej
war
tosc
i,w
ybra
nej
tak,
aby
pow
odow
a la
najm
niej
konfl
ikto
w(n
arus
zen
wie
zow
)z
inny
mi
zmie
nnym
i.
Alg
oryt
my
prze
szuk
iwan
ialo
kaln
ego
opar
tena
pow
yzsz
ymsc
hem
acie
spra
wdz
aja
sie
zask
akuj
aco
dobr
zew
wie
luza
gadn
ieni
ach
CS
P.
Klu
czow
ymic
hel
emen
tem
jest
loso
wos
c,kt
ora
poz
wal
auc
iec
odm
aksi
mow
loka
lnyc
hi
inny
chpu
lap
ek,
oraz
natr
afic
nakl
uczo
wa
zmie
nna
dop
opra
wie
nia,
lub
pom
inac
nief
ortu
nnie
wyb
rana
zmie
nna,
ktor
ejw
arto
scna
lezy
przy
pisa
cpo
znie
j.
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
94
Kro
tkie
po
dsu
mo
wa
nie
—p
yta
nia
spra
wd
zaja
ce
1.R
ozw
azpr
oble
mC
SP
zcz
tere
ma
zmie
nnym
i:A,B
,C,D
zdz
iedz
inam
i:{1,2,3}
dla
kazd
ejz
nich
,i
zbio
rem
wi e
zow
pod
anym
nize
j.N
arys
ujgr
afw
iezo
wza
dani
a,p
ocz
ymsp
robu
jje
rozw
iaza
cm
etod
apr
opag
acji
wie
zow
(spo
jnos
ci lu
kow
ej).
Pok
azka
zdy
krok
rozw
iaza
nia
(bez
rysu
nku)
.P
rzed
staw
graf
po
zako
ncze
niu
prop
agac
jiw
iezo
w.
Ilere
prez
entu
jeon
moz
liwyc
hro
zwia
zan
prob
lem
uC
SP
?N
apis
zje
dno
zni
ch.
Zbi
orw
iezo
w:
C=
{C6=
D,B
>D,B
>C}
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
95
Lin
ki
do
lite
ratu
ry
Dob
rew
prow
adze
nie
doza
gadn
ien
CS
PR
oman
aB
arta
kahttp://ktiml.mff.cuni.cz/~bartak/constraints/constrsat.html
Met
od
ypr
zesz
uki
wan
ia—
prze
szu
kiw
anie
zw
ieza
mi
96
![京都大学生活協同組合 Kyoto University CO-OP...Êù»q vb ·ÛÆ U åx Ë ]p 5^ b {sx \ z tmMoßQ b{® G \wh w· ÑÂ É¿Ä ¯ \ \Æ ßQ Ó G \ w ì»Æ vb A :q`ow ·ÛÆ](https://static.dokumenty.site/doc/80x56/5f86c62272493c6144396d91/efcoec-kyoto-university-co-op-q-vb-u-x.jpg)
![· .11Y2rnoLdm'3 HNO \5dm3 3mOldtñf5 Hcl -6dm3 No'3 moldmt3, drn -3 niõll mol] dm-3 3moldm - 2 mol drn-3 13moldñ1 -3 HO (l) Ca (OH)2 +02 (100g C2H2](https://static.dokumenty.site/doc/80x56/5fb5988393e9bd0bcf01b0aa/11y2rnoldm3-hno-5dm3-3moldtf5-hcl-6dm3-no3-moldmt3-drn-3-nill-mol-dm-3.jpg)
