Prohledávání stavového prostoru
Aleš Horák
E-mail: hales@fi.muni.cz http://nlp.fi.muni.cz/uui/
Obsah:
► Prohledávání stavového prostoru
► Neinformované prohledávání
► Informované prohledávání stavového prostoru
► Jak najít dobrou heuristiku?
Úvod do umělé inteligence 2/12
1/38
Prohledávání stavového prostoru
Prohledávání stavového prostoru
Řešení problému prohledáváním stavového prostoru:
► stavový prostor, předpoklady - statické a deterministické prostředí, diskrétní stavy
► počáteční stav problém.init_state
► cílová podmínka        problém.is_goal(State)
► přechodové akce        problém.moves(State) —>► NewStates
Úvod do umělé inteligence 2/12
2/38
Prohledávání stavového prostoru      Problém agenta Vysavače
Problém agenta Vysavače
P L
^0		p			
					vj
		" L			
O
► máme dvě místnosti (L, P)
► jeden vysavač (v L nebo P)
► v každé místnosti je/není špína
► počet stavů je 2 x 22 = 8
^ akce = {do Leva, d o Pravá, Vysávej}
Úvod do umělé inteligence 2/12
3/38
Prohledávání stavového prostoru      Problém agenta Vysavače
Problém agenta Vysavače
Prohledávací strategie - prohledávací strom
► kořenový uzel
► uzel prohledávacího stromu:
• (odkaz na) stav
• rodičovský uzel
• přechodová akce
• hloubka uzlu
• cena - g(n) cesty, c(x, a,y) přechodu
► (optimální) řešení ^
► A (stav
► např. uzel C:
stav -
• rodič - A
• akce - doPrava
• hloubka - 1
• cena - 1
reseni - X
v
Prohledávání stavového prostoru      Řešení problému prohledáváním
Řešení problému prohledáváním
Kostra algoritmu:
function Search (problem)
process ^— collection (problem. init_state ) # stavy ke zpracování while length (process) > 0 do
current-node ^— remove_current_node(process) if problem, is.goal (current-node) then print current-node # řešení foreach child in problem.moves(current-node) do process. aóó-noóe(child)
rekurzivně včetně cesty k řešení:
function RECURSiVESEARCH(prob/e/77, path = collection()) if length(pař/7) = 0 then
return RecursiveSearch(prob/e/77, collection (problem. init_state )) current-node = get_current_node(pař/7)
if problem. is_goal (current-node) then print path # cesta k řešení foreach child in problem.moves(current-node) do RecursiveSearch(problem, path.with_node(c/7/7c/))
Prohledávání stavového prostoru      Prohledávací strategie
Prohledávací strategie
problem.moves(State) —>► NewStates - definuje prohledávací strategii
Porovnání strategií:
► úplnost
► optimálnost
► časová složitost
► prostorová složitost
složitost závisí na:
► b - faktor větvení (branching factor)
► c/ - hloubka cíle (goal depth)
► m - maximální hloubka větve/délka cesty (maximum depth/path, může být oo?)
Úvod do umělé inteligence 2/12
6/38
Neinformované prohledávání
Neinformované prohledávání
► prohledávání do hloubky
► prohledávání do hloubky s limitem
► prohledávání do šířky
► prohledávání podle ceny
► prohledávání s postupným prohlubováním
Úvod do umělé inteligence 2/12
7/38
Neinformované prohledávání     Prohledávání do hloubky
Prohledávání do hloubky
Prohledává se vždy nejlevější a nejhlubší neexpandovaný uzel (Depth-first Search, DFS)
Úvod do umělé inteligence 2/12
8/38
Neinformované prohledávání     Prohledávání do hloubky
Prohledávání do hloubky
function DEPTHFiRSTSEARCH(prob/e/77, path «— []) if length(pař/7) = 0 then
return DepthFirstSearch(prob/e/77, [problem. init_state ]) current-node ^— path, last()   # poslední prvek cesty if problem. is_goal (current-node) then print path
foreach child in problem.moves(current-node) do if child ^ path then
DepthFirstSearch(prob/e/77, path + [c/7/7c/])
úplnost optimálnost časová složitost prostorová složitost
není úplný (nekonečná větev, cykly)
není optimální
0(bm)
O(bm), lineární
Největší problém - nekonečná větev = nenajde se cíl, program neskončí!
Úvod do umělé inteligence 2/12
9/38
Neinformované prohledávání     Prohledávání do hloubky s limitem
Prohledávání do hloubky s limitem
Řešení nekonečné větve - použití "zarážky" = limit hloubky £
function DepthFirstSearchLimited(problem, limit, path «— []) if length(pař/7) = 0 then
return DepthFirstSearchLimited (problem, limit, [problem. init_state ]) current-node ^— path, last()   # poslední prvek cesty if problem, is.goal (current-node) then print path  # cesta k řešení if limit = 0 then return "cutoff" cutofLoccured ^— False
foreach child in problem.moves(current-node) do if child ^ path then
result ^— DepthFirstSearchLimited(prob/e/77, limit-1, path + [c/7/7c/]) if  result = "cutoff" then cutofLoccurred ^— True
if cutofLoccurred then return "cutoff" else return "exhausted"
Úvod do umělé inteligence 2/12
10 / 38
Neinformované prohledávání     Prohledávání do hloubky s limitem
Prohledávání do hloubky s limitem
konec má dvě možné interpretace - vyčerpání limitu nebo neexistenci (dalšího) řešení
Vlastnosti:
úplnost optimálnost
časová složitost prostorová složitost
není úplný (pro £ < d) není optimální (pro £ > d)
0(bl) 0{b£)
dobrá volba limitu £ - podle znalosti problému
Úvod do umělé inteligence 2/12
11 / 38
Neinformované prohledávání     Prohledávání do šířky
Prohledávání do sirky
Prohledává se vždy nejlevější neexpandovaný uzel s nejmenší hloubkou. (Breadth-first Search, BFS)
Úvod do umělé inteligence 2/12
12 / 38
Neinformované prohledávání     Prohledávání do šířky
Prohledávání do sirky
ve frontě (FIFO) udržuje seznam cest
function BreadthFirstSearch(problem)
process ^— [[problem. init_State ]        # seznam cest k aktuálnímu uzlu
while length (process) > 0 do
current-path ^— process, first () current-node ^— current-path. last () if problem, is.goal (current-node) then
print current-path   # vypíše cestu k řešení foreach child in problem.moves(current-node) do if child ^ current-path then
process ^— process + [current-path + [c/7/7c/]
Úvod do umělé inteligence 2/12
13 / 38
Neinformované prohledávání     Prohledávání do šířky
Prohledávání do sirky - vlastnosti
úplnost optimálnost
je úplný (pro konečné b)
je optimální podle délky cesty/není optimální podle obecné ceny
1 + b + b2 + b3 + ... + bd + b(bd - 1) = 0{bd+1), exponenciální v d prostorová složitost   0{bd+1) (každý uzel v paměti)
časová složitost
Největší problém - paměť
Hloubka	Uzlů	Čas	Paměť
2	1100	0.11 sek	1 MB
4	111100	11 sek	106 MB
6	107	19 min	10 GB
8	109	31 hod	1 TB
10	1011	129 dnů	101 TB
12	1013	35 let	10 PB
14	1015	3 523 let	1 EB
Ani čas není dobrý —± potřebujeme informované strategie prohledávání.
Úvod do umělé inteligence 2/12
14 / 38
Neinformované prohledávání     Prohledávání podle ceny
Prohledávání podle ceny
► BFS je optimální pro rovnoměrně ohodnocené stromy x prohledávání podle ceny (Uniform-cost Search) je optimální pro obecné ohodnocení
► fronta uzlů se udržuje uspořádaná podle ceny cesty Vlastnosti:
úplnost je úplný (pro cena > e a b konečné)
optimálnost je optimální (pro cena > e, g(n) roste)
c a sov a složitost        počet uzlů s g < C*,   0(/?1+Lc*AJ), kde
C*... cena optimálního řešení
prostorová složitost
počet uzlů s g < C* 0(b1+Lc*AJ)
15 / 38
Neinformované prohledávání     Prohledávání s postupným prohlubováním
Prohledávání s postupným prohlubováním
prohledávání do hloubky s postupně se zvyšujícím limitem (Iterative deepening DFS, IDS)
I i m it=3
Neinformované prohledávání     Prohledávání s postupným prohlubováním
Prohledávání s postupným prohlubováním - vlastnosti
úplnost je úplný (pro konečné b)
optimálnost je optimální (pro g(n) rovnoměrně neklesající funkce
hloubky)
časová složitost        d(b) + (d - l)b2 + ... + l(bd) = 0(bd) prostorová složitost O(bd)
► kombinuje výhody BFS a DFS:
• nízké paměťové nároky - lineární
• optimálnost, úplnost
► zdánlivé plýtvání opakovaným generováním
ALE generuje o jednu úroveň míň, např. pro b = 10, d = 5:
A/(IDS) = 50 + 400 + 3 000 + 20 000 + 100 000 =   123 450
A/(BFS) = 10 + 100 + 1 000 + 10 000 + 100 000 + 999 990 = 1111100
IDS je nejvhodnější neinformovaná strategie pro velké prostory a neznámou hloubku řešení.
Úvod do umělé inteligence 2/12
17 / 38
Neinformované prohledávání     Shrnutí vlastností algoritmů neinformovaného prohledávání
Shrnutí vlastností algoritmů neinformovaného prohledávání
Vlastnost	do hloubky	do hloubky s limitem	do V/VI sirky	podle    s postupným ceny prohlubováním
úplnost	ne	ano,	ano*	ano* ano*
		pro / > d		
optimálnost	ne	ne	ano*	ano* ano*
časová složitost	0{bm)	0(b£)	0{bd+1)	0(bi+Lc*AJ) 0(bd)
prostorová	O(bm)	0(b£)	0{bd+1)	0(bi+Lc*AJ) 0(bd)
složitost				
Úvod do umělé inteligence 2/12
18 / 38
Informované prohledávání stavového prostoru      Příklad - cesta na mapě
Příklad - cesta na mapě
Najdi cestu z města Arad do města Bukurest
Informované prohledávání stavového prostoru
Příklad - cesta na mapě
Příklad - schéma rumunských měst
Města:	Cesty:			
Arad	Arad		Timisoara	118
Buku rest	Arad		Sibiu	140
Craiova	Arad		Zerind	75
Dobreta	Timisoara		Lugoj	111
Eforie	Sibiu		Fagaras	99
Fagaras	Sibiu		Rimnicu Vilcea	80
Giurgiu	Zerind		Oradea	71
Hirsova				
lasi	Giurgiu		Buku rest	90
Lugoj	Pitesti		Buku rest	101
Mehadia	Fagaras		Buku rest	211
Neamt	Urziceni		Buku rest	85
Informované prohledávání stavového prostoru      Příklad - cesta na mapě
Příklad - schéma rumunských měst
Oradea
Neamt
Arad
11*
Eforie
Arad	366
Bukurešť	0
Craiova	160
Dobreta	242
Eforie	161
Fagaras	176
Giurgiu	77
Hirsova	151
lasi	226
Lugoj	244
Mehadia	241
Neamt	234
Oradea	380
Pitesti	100
Rimnicu Vilcea	193
Sibiu	253
Timisoara	329
Urziceni	80
Vaslui	199
Zerind	374
Úvod do umělé inteligence 2/12
21 / 38
Informované prohledávání stavového prostoru      Příklad - cesta na mapě
Příklad - cesta na mapě
Neinformované prohledávání:
► DFS, BFS a varianty
► nemá (téměř) žádné informace o pozici cíle - slepé prohledávání
► zná pouze:
• počáteční/cílový stav
• přechodovou funkci
Informované prohledávání:
má navíc informaci o (odhadu) blízkosti stavu k cílovému stavu -heuristická funkce (heuristika)
Úvod do umělé inteligence 2/12
22 / 38
Informované prohledávání stavového prostoru      Heuristické hledání nejlepší cesty
Heuristické hledání nejlepší cesty
► Best-first Search
► použití ohodnocovací funkce f(n) pro každý uzel - výpočet přínosu daného uzlu
► udržujeme seznam uzlů uspořádaný {vzestupně) vzhledem k f {n)
► použití heuristické funkce h(n) pro každý uzel - odhad vzdálenosti daného uzlu (stavu) od cíle
► čím menší h(n), tím blíže k cíli, /7(Goal) = 0.
► nejjednodušší varianta - hladové heuristické hledání, Greedy best-first search
f (n) = h(n)
Úvod do umělé inteligence 2/12
23 / 38
Informované prohledávání stavového prostoru      Hladové heuristické hledání
Hladové heuristické hledání - příklad
Hledání cesty z města Arad do města Bukurešť
ohodnocovací funkce f(n) — h(n) — /7vzd_Buk(^)» přímá vzdálenost z n do Bukurešti
Informované prohledávání stavového prostoru      Hladové heuristické hledání
Hladové heuristické hledání - vlastnosti
► expanduje vždy uzel, který se zdá nejblíže k cíli
► Cesta nalezená V příkladu (g(Arad^Sibiu^Fagaras^ Bukurešť) = 450) je
sice úspěšná, ale není optimální
(g"(Arad—} Sibiu—} RimnicuVilcea—} Pitesti—^Bukurest) = 418)
► úplnost obecně není úplný (nekonečný prostor, cykly) optimálnost není optimální
časová složitost        0(bm), hodně záleží na h prostorová složitost   0(bm), každý uzel v paměti
Úvod do umělé inteligence 2/12
25 / 38
Informované prohledávání stavového prostoru      Hledání nejlepší cesty - algoritmus A*
Hledání nejlepší cesty - algoritmus A*
► některé zdroje označují tuto variantu jako Best-first Search
► ohodnocovací funkce - kombinace g(n) a h(n)\
f(n) = g(n) + h(n)
g(n)   je cena cesty do n
h(n)   je odhad ceny cesty z n do cíle
f(n)   je odhad ceny nejlevnější cesty, která vede přes n
► A* algoritmus vyžaduje tzv. přípustnou (admissible) heuristiku:
0 < h(n) < h\n), kde h\n) je skutečná cena cesty z n do cíle
tj. odhad se volí vždycky kratší nebo roven ceně libovolné možné cesty do cíle
Např. přímá vzdálenost /7vzd_Buk nikdy není delší než (jakákoliv) cesta
Úvod do umělé inteligence 2/12
26 / 38
Informované prohledávání stavového prostoru      Hledání nejlepší cesty - algoritmus A*
Heuristické hledání A* - příklad
Hledání cesty z města Arad do města Bukurest ohodnocovací funkce f(n) — g(n) + h(n) — g(n) + /7vzd_Buk(^)
418=418+0     615=455+60 607=414+193
Úvod do umělé inteligence 2/12
27 / 38
Informované prohledávání stavového prostoru      Hledání nejlepší cesty - algoritmus A*
Hledání nejlepší cesty A* - vlastnosti
► expanduje uzly podle f(n) = g(n) + h(n)
A*    expanduje všechny uzly s f(n) < C* A*    expanduje některé uzly s f(n) = C A* neexpanduje žádné   uzly s f(n) > C
►   úplnost je úplný (pokud [počet uzlů s ř < C*] 7^ 00,
tedy cena > e a b konečné) optimálnost je optimální
časová složitost        0((b*)Qf), exponenciální v délce řešení d
b* ... tzv. efektivní faktor větvení, viz dále prostorová složitost   0((b*)Qf), každý uzel v paměti
Problém s prostorovou složitostí řeší algoritmy jako IDA*, RBFS
Úvod do umělé inteligence 2/12
28 / 38
Informované prohledávání stavového prostoru      Hledání nejlepší cesty - algoritmus A*
Důkaz optimálnosti algoritmu A
*
► předpokládejme, že byl vygenerován nějaký suboptimální cíl G2 a je uložen ve frontě.
► dále nechť n je neexpandovaný uzel na nejkratší cestě k optimálnímu cíli G\ (tj. chybně neexpandovaný uzel ve správném řešení)
Pak
f(G2)   = g(G2)
Start
protože h(G2) = 0
> g(G\)   protože G2 je suboptimální
> f(n)     protože h je přípustná
tedy /r(G2) > f{n)   =>* A* nikdy nevybere G2 pro expanzi dřív než expanduje n    —>► spor s předpokladem, že n je neexpandovaný uzel
□
Úvod do umělé inteligence 2/12
29 / 38
Informované prohledávání stavového prostoru      Hledání nejlepší cesty - algoritmus A*
Hledání nejlepší cesty - algoritmus A*
řešení pomocí prioritní fronty
f-hodnota, g-hodnota a cesta k aktuálnímu uzlu
function A*SEARCH(prob/e/77)
process-heap ^— [(0, 0, [problem. init_state ])]     # prioritní fronta podle f while length (process-heap) > 0 do
f, g, current-path ^ process-heap.heap-pop()    # nejmenší f-hodnota current-node ^— current-path. last () if problem. is_goal (current-node) then
print current-path   # vypíše cestu k řešení foreach child, cost in problem.mo\ies(cur rent-node) do
if  child     current-path then      # detekce cyklů - efektivnější process-heap.heap_add( (g-\-cost-\-h(child),
g+cost,
current-path + [ child ]))
Úvod do umělé inteligence 2/12
30 / 38
Informované prohledávání stavového prostoru      Příklad - řešení posunovačky
Příklad - řešení posunovačky
konfigurace = seznam souřadnic (x, y): [pozice^y, pozice^men n
8p. init_state  <- [(2,2), (3,1), (2,3), (2,1), (3,3), (1,2), (3,2), (1,3), (1,1)]
function 8p.is_goal(S)
return S = [(1,3), (2,3), (3,3), (1,2), (2,2), (3,2), (1,1), (2,1), (3,1)]
S=
function 8p.moves(state) # pohyby mezery cena vždy 1 xb> Yb     state.first() # pozice mezery
numbers <— state, without-first ()   # pozice čísel moves <— [ if xj, > 1 then
*nb <~ *b -1; moves.append([(xnb, yb)] + numbers.replace((xnjb, yb), (xb, yb))) if xb < 3 then
*nb <-xb + 1; moves.append([(xnb, yb)] + numbers.replace((xnjb, yb), (xb, yb))) if yb > 1 then
Ynb <- Yb -1; mo\/es.append([(xbl ynb)] + numbers.replace((xb, ynb), (xbl yb))) if yb < 3 then
Ynb ^ Yb + 1; mo\/es.append([(xbl ynb)] + numbers.replace((xb, ynb), (xbl yb))) return map move in moves to (move, 1)
	2 y i	4	3		1 \ J	ľ 1 2 i J
5 l_ _)		6			4 v _)	5
8 i )	3	f ~\ 1	1	6	7 v J	8
Úvod do umělé inteligence 2/12
31 / 38
Informované prohledávání stavového prostoru      Příklad - řešení posunovačky
Příklad - řešení posunovačky pokrač.
Volba přípustné heuristické funkce h\
► hi(n) = počet dlaždiček, které nejsou na svém místě    ^i(S) = 8
► h2(n) = součet manhattanských vzdáleností dlaždic od svých správných pozic    h2{S) = 37 + 12 + 24 + 25 + 36 + 28 + 23 + 31 = 18
hi i /72 jsou přípustné . .. h\S) = 26
A*Search(8p):
[[(2,2), (3,1), (2,3), (2,1), (3,3), (1,2), (3,2), (1,3), (1,1)], [(1,2), (3,1), (2,3), (2,1), (3,3), (2,2), (3,2), (1,3), (1,1)],
[(1,2), (2,3), (3,3), (1,3), (2,2), (3,2), (1,1), (2,1), (3,1)], [(1,3), (2,3), (3,3), (1,2), (2,2), (3,2), (1,1), (2,1), (3,1)]]
Úvod do umělé inteligence 2/12
32 / 38
Jak najít dobrou heuristiku?     Jak najít přípustnou heuristickou funkci?
Jak najít přípustnou heuristickou funkci?
► je možné najít obecné pravidlo, jak objevit heuristiku hi nebo /?2?
► A?i i A?2 jsou délky cest pro zjednodušené verze problému Posunovačka:
• při přenášení dlaždice kamkoliv - /?i=počet kroků nejkratšího řešení
• při posouvání dlaždice kamkoliv o 1 pole (i na plné) - /?2=počet kroků nejkratšího řešení
► relaxovaný problém - méně omezení na akce než původní problém
Cena optimálního řešení relaxovaného problému je přípustná heuristika pro původní problém. optimální řešení původního problému = řešení relaxovaného problému
Posunovačka a relaxovaná posunovačka:
► dlaždice se může přesunout z A na B <^> A sousedí s B A B je prázdná
► (a) dlaždice se může přesunout z A na B <^> A sousedí s B .. h^
(b) dlaždice se může přesunout z A na B <^> B je prázdná ... Gaschnigova h.
(c) dlaždice se může přesunout z A na B ................... h\
Úvod do umělé inteligence 2/12
33 / 38
Jak najít dobrou heuristiku?      Určení kvality heuristiky
Určení kvality heuristiky
efektivní faktor větvení b* — N... počet vygenerovaných uzlů, d... hloubka řešení, idealizovaný strom s N + 1 uzly má faktor větvení b* (reálné číslo):
N + 1 = 1 + b* + (b*)2 + • • • + (b*)d
např.: když A* najde řešení po 52 uzlech v hloubce 5 ... b* = 1.92 heuristika je tím lepší, čím blíže je b* hodnotě 1.
^ měření b* na množině testovacích sad - dobrá představa o přínosu heuristiky
8-posunovačka
	Průměrný počet		uzlů	Efektivní faktor větvení b*		
d	ids	a*(M	a*(/72)	ids	a*(M	a*(/72)
2	10	6	6	2.45	1.79	1.79
6	680	20	18	2.73	1.34	1.30
10	47127	93	39	2.79	1.38	1.22
12	3644035	227	73	2.78	1.42	1.24
18	—	3056	363	—	1.46	1.26
24	—	39135	1641	—	1.48	1.26
/72 dominuje h\ (Vn : h2(n) > hi(n)) ... fi2 je lepší (nebo stejná) než h\ ve všech případech
Úvod do umělé inteligence 2/12
34 / 38
Jak najít dobrou heuristiku?      Příklad - rozvrh práce procesorů
Příklad - rozvrh práce procesorů
► úlohy t; s potřebným časem na zpracování D; (např.: / = 1,... ,7)
► m procesorů (např.: m = 3)
► relace precedence mezi úlohami - které úlohy mohou začít až po skončení dané úlohy
ti/D1 = 4
t2/D2 = 2
h/D3 = 2
tA/DA = 20
r5/D5 = 20
r6/D6 = 11
ti/D7 = 11
► problém: najít rozvrh práce pro každý procesor s minimalizací celkového času
02 4
13
24 33
02 4
13
24 33
CPUi	t3				
CPU2	Í2	<= tj =>•			
					
CPU3					
	h	É5		^= r7	
CPU2	t2	■			
CPU3			r4		
Úvod do umělé inteligence 2/12
35 / 38
Jak najít dobrou heuristiku?      Příklad - rozvrh práce procesorů
Příklad - rozvrh práce procesorů - pokrač.
► stavy:   (nezařazené_úlohy, běžícLúlohy, čas_ukončení)
př.: ([(WaitingT1,D1)9(WaitingT2,D2)9^]9 [(Task1,F1),(Task2,F2),(Task3,F3)], FinTime)
běžícLúlohy udržujeme setříděné F\ < F2 < F3
► počáteční uzel:
proc. init_state  ^ ([("ti",4), (,,t2,,,2), ("t3'\2), ("t4'\20), ("t5'\20), ("t6'\ll),
("ir'Ml)],  [("idle'\0), ("idle'-.O), ("idle'-.O)], 0)
► přechodová funkce proc.moves(Stav) —>► nové stavy s cenami:
function proc.moves (state)
waiting,  active,  finti me = state moves <— [
for task in waiting do  # přednost v čekajících nebo nedokončených
if not check_precedence_waiting (task, waiting, without (task)) then next if not check_precedence_active (task,  active) then next newactive, newfintime <— active, without-first (). insert_sorted (task) moves.append((i/i/a/t/ng". without (task), newactive, newfintime))
moves <— moves + insert_idle(w/a/t/ng", active,  fintime) # čekání na procesor
return moves
► cílová podmínka       function proc.is_goal (state)
return length(state [1]) =0 # žádné čekající
Úvod do umělé inteligence 2/12
36 / 38
Jak najít dobrou heuristiku?      Příklad - rozvrh práce procesorů
Příklad - rozvrh práce procesorů - pokrač.
► heuristika
skutečný (průběžný) čas výpočtu: Fin = max(Fý)
Finall — Fin,   když Finall > Fin 0, jinak
function proc.h (state)
tasks, processors,  fintíme estate
totaLtask-time <— Z_task_time(tasks) # čas ke zpracování totaLproc-time <— Z_proc_tiir\e(processors) # zpracovaný čas finall <— (totaLtask-time + total-proc-time)/length ( processors) if   finall > fintime then
return   finall - fintime return 0
optimální (nedosažitelný) čas:
Finall
m
heuristická funkce      h =
Úvod do umělé inteligence 2/12
37 / 38
Jak najít dobrou heuristiku?      Příklad - rozvrh práce procesorů
Příklad - rozvrh práce procesorů - pokrač.
A*Search(proc):
[   ([(ti,4),(t2,2),(r3,2),(t4,20),(t5,20),(t6,ll),(t7,ll)], [(idle,0),(idle,0),(idle,0)], 0),
([(ti,4),(t2,2),(r4,20),(t5,20),(t6,ll),(t7,ll)], [(idle,0),(idle,0),(t3,2)], 2),
([(ti,4),(t4,20),(t5>20),(t5,ll),(r7,ll)], [(idle,0),(t2,2),(t3,2)], 2),
([(t4,20),(t5,20),(t6,ll),(t7,ll)], [(t2,2),(ř3,2),(r1,4)], 4),
([(t4,20),(t5,20),(t6,ll)], [(t3,2),(t1,4),(r7,13)], 13),
([(ŕ4,20),(t5,20),(t6,ll)], [(idle,4),(ri,4),(t7,13)], 13),
([(t5,20),(t6,ll)], [(ti,4),(f7,13),(t4,24)], 24),
([(«5.11)1. [(t7,13),(t5,24),(r4,24)], 24),
([], [(t6,24),(t5,24),(t4,24)], 24)
Úvod do umělé inteligence 2/12
38 / 38