Sök Flashcards
Att söka är en form av
problemlösning
Problemrymd
alla möjliga lösningar
Startpunkten måste..
definieras
Vad skiljer sökalgoritmerna åt?
Metoden för att söka igenom problemrymden
Solving agent
all form av AI utformad för att lösa problem
Fringe
lista av avklarade noder som inte var den sökta
Sökalgoritmer kan delas upp i två:
Uninformed
Informed
Uninformed sökalgoritm
Används då sökningen görs i blindo
Ingen info utöver start och slut
Hittar alltid en lösning
Expandera
Vilken nod som ska undersökas härnäst
Tree search algorithm
algoritmer som är UNINFORMED och presenterar problemrymden i ett träd
Breadth search algorithm
Från start punkt
- Lager efter lager
- Vänster till höger
- FIFO - first in first out
Depth first search algorithm
Från start
- Checkar av varje gren nedåt
- Uppifrån och nedåt
- Utgår från vänster
Uniform cost search algorithm
Viktat träd med liknande vikter
- Expandera till nod med kortast väg
- Lägst vikt i samma lager
- Bryr sig ej om längd på väg, endast låg kostnad
Hur svarar man på vägen i en uniformed cost search?
- Alternativen (nod , vikt)
- “Expand (nod , vikt)”
- “giving nod , nod , (vikt + vikt = vikt)”
Man förklarar vägen
Informed algoritms
Hjälpande information om problemrymden som visar vägen till målet
- Ofta heuristiker
Hill-climbing search algorithm
Informed search
- Utvärderingsfunktion för att hela tiden förbättra positionen MOT målet
- Tar alltid längsta vägen, kostnaden
Planing agent
AI för att lösa problem i föränderlig miljö
- Vart är vi nu?
- Vad ska göras?
- I vilken ordning?
Hur presenteras varje handling för planing agent?
I ett schema med startläge och slutläge
Agenten fortsätter tills slutläge är uppfyllt
STRIPS
En planing agent
- Means-end analysis
- Goal-based agent
Means-end analysis
Metod där man agerar för att hela tiden ta sig närmre målet
- Vad är tillståndet nu?
- Vad är målet ?
- Hur gör jag för att närma mig målet?
Hur ser schemat för planing egent ut?
Action
- P = precondition
- E = effect
Unstack (x,y)
- P = HANDEMPTY , BLOCK(x) , CLEAR(y)
- E = ON(x,y)
Deterministiska problem
Är observerbara för agenten
- Vet status och lösning är sekvens av handlingar
- Alltid samma output för en viss input
Nondeterministiskt
Går inte att förutsäga output för input
Non-deterministisk polynomial problem
Problem där effektiva lösningar saknas
Måste gå igenom alla lösningar och jämföra dem
