Problemløsning vha søk

1

mailingliste, forelesningsnotater sent torsdagkveld, 2 timer med en pause?

intelligente agenter

- repeter

- KJERNEN AV TRAINS LØSER PROBLEMER, VI SKAL TA UTGANGSPUNKT I Å LØSE
ENKLE PROBLEMER, OG UTVIDE ETTERHVERT

kap 3 problemløsning
	
	- formulere målet/målsetting

	- formulere problemet

	- søke etter en løsning i form av en handlingssekvens som 
	  tar oss fra problemet til målet

	- eksekvere handlingssekvensen 

- figur 3.1

- tilstander, figur 3.2

- 4 typer problemer:
	
	1 enkelt-tilstand (vet eksakt hvilken tilstand er i og kommer i)

	2 fler-tilstand (handlingene er kjent, men ikke omgivelsene)

 	3 tilfelle-problemer (handlingene har konsekvenser, må ha sensorer
	  ute under eksekvering)

	4 utforskningsproblemer (veit ittno om omgivelsene eller
	  handlingskonsekvensene)

- vi bryr oss bare om 1 og 2

- tilstandsrommet: alle tilstander som kan nåes fra start-tilstand med en
hvilken som helst handlingssekvens.

- sti i tilstandsrommet

- problemdefinering:

datatype problem
{
	<start-tilstand>
	<operatorer>
	<mål-test>
	<sti-pris-funksjon>
}

- utvidelse for fler-tilstandsproblemer:

	- tilstandssettrommet, målet er et sett av tilstander som alle
	  oppfyller kravet som måltilstander, figur 3.6 og 3.7

- abstrahering av problemet (figur 3.3):

	- ignorer detaljer

	- velg riktig operator nivå (fra by til by, ikke trykkåpågass)

- leke-problemer og reelle-problemer

- eksempel leke-problem: 8-puslespillet:
		
	- tilstander: hvor alle brikkene og det tomme feltet er

	- operatorer: tomt felt flyttes venstre, hoyre, opp eller ned
	(<, >, ^, v)

	- mål-test: tilstand stemmer overens med mål-tilstand

	- sti-pris: hvert trekk har en pris på 1 (lengde å flytte)


2

- reelle problemer ss 68, 69, 70

- søketre/node/strategi, figur 3.8, 3.9

- datastruktur for node i søketre:

datatype node
{
	<tilstand>
	<foreldre-node>
	<operator>
	<dybde/nivå>
	<sti-pris>
}

- forskjell mellom søketrenode og tilstand

- figur 3.10:

	- make-queue(elements)
	
	- empty?(queue)

	- remove-front(queue)

	- queing-fn(elements, queue)

- søkestrategi:

	- kompletthet

	- tidkrevende

	- minnekrevende

	- optimal

- O(n), NP-komplett/hard

- ikke-informert/blindt søk 

- informert/heuristisk søk (tommelfingerregelsøk)

- bredde-først-søk, figur 3.11, noder legges til først i køen (listen)

- ensartet-pris-søk, figur 3.13 (mål nådd fordi SBG er mindre enn SC)

- dybde-først-søk, figur 3.14, noder legges til sist i køen, bør unngåes
når søkebybde er stor eller uendelig

- dybde-begrenset og iterativt-dybde-begrenset-søk, figur 3.16:

 	- optimal og komplett som bredde-først, men krever bare minne til
	  dybde-først-søk

	- overhead er ikke så stor siden nodene på laveste nivå er de som
	  gjelder (bare 11% overhead ss 80)

	- i-d-b-s er å foretrekke ved store tilstandsrom og ukjent
	  løsningsdybde

- begge-retninger-søk, figur 3.17

(- sammenligne algoritmer figur 3.18)

- unngå tidligere besøkte tilstander, veldig problem-avhengig, f.eks.
n-dronning problemet

- constraint-satisfaction-søk: tvinger et problem til løsning ved å søke
inntil ett et sett betingelser er tilfredsstilt, f.eks. n-dronning
problemet


3

Lisp:

- oppgave 18, 8, 9