Informerte søkemetoder

1

INFO OM PAPER (velg leserbakgrunn selv, begynn min 2-3 uker før,
hovedjobben er å finne artikler og lese/sette seg inn i disse)

- fullfør forrige forelesning

- best-først søk:
	evalueringsfunksjon som avgjør hvilke node som skal utvides 
	(figur 4.1)

- vi trenger et mål som estimerer sti-pris fra nu-tilstanden til nærmeste
mål-tilstand

- heuristikk = tommelfingerregel

- heuristikkfunksjon (en type evalueringsfunksjon):
	h(n) = estimert laveste pris fra node n til en mål-tilstand

- best-først søk som benytter h kalles grådig-søk

- e.g. figur 4.2, heuristikk: rett-linje-avstand til målet, figur 4.3

- samme problemer som dybde-først søk

- kombinerer heuristikkfunksjonen (h) med hittil-tilbakelagt-sti-pris (g),
mao kombinerer ensartet-pris-søk med grådig-søk:
	f(n) = g(n) + h(n) 
	A* søk (viktig)
	f(n) = beste løsning gjennom node n

- A* er optimal viss h er en tilatelig heuristikk, dvs h kan ikke
overestimere prisen (alltid optimistisk, e.g. rett-linje-avstand)

- eksempel hvordan søk i et rom blir til en ellipse i stedet for en sirkel
(burde brukt en del javademo her)

- en heuristikk er monoton viss f-prisen aldri synker når en node utvides:
	dette kan garanteres ved bruk av sti-max likningen:
	f(n') = max( f(n) , g(n')+h(n') )

- A* er optimalt effektiv (mm man hopper over noder...og da er ikke
garantert løsning)

- (les bevis selv 99-101)

- tilatelige heuristikker for 8-puslespillet:
	1. antall feilplasserte brikker
	2. summen av distansen av brikkene fra sine målposisjoner 
	   (Manhatten distanse)

- mål av heuristikk-kvalitet: effektiv greine faktor, b*
	N = 1 + b* + (b*)^2 ... + (b*)^d

- figur 4.8

- velg alltid den heuristikken som gir høyest verdier (men ikke
overestimerer)


2

- avslappet problem:
	løsner på reglene (evn fjerner regler) for å lage en god
	heuristikk

- ABSOLVER

- bruk h(n) = max( h1(n), ... , hm(n) ) , så lenge alle hx er tilatelige
vil h også være det

- bruke egenskaper, statistiske beregninger, men husk at en kompleks
heuristikk vil kreve regnekapasitet

- figur 4.9, (CSP ikke så kritisk ?)

- IDA* og SMA* søk: triksing/forbedring av A* for å bruke mindre minne
(ikke alltid optimale...viss tid kikk på figur 4.11)

- gradient søk (gradient descent, hill climbing) og simulert annealing


3

- oppgaver til neste gang: 4.1, 4.2 b,c , 4.3, 4.9

3.3 c-f , 3.4 , 3.9