AI_3_1

Poszukiwania nieinformowane

Poka

emy w jaki sposób agent mo

Poka

emy w jaki sposób agent mo

osi

ąć

zamierzony cel poprzez

osi

ąć

zamierzony cel poprzez

wykonanie ci

gu działa

Działania te b

wyznaczone

Działania te b

wyznaczone

poprzez poszukiwania oparte
wył

cznie na definicji zadania.

wył

cznie na definicji zadania.

© F.A. Dul 2007

Niniejszy rozdział po

cony jest agentom celowym,

3.1. Wprowadzenie

Niniejszy rozdział po

cony jest agentom celowym,

których działanie oparte jest na poszukiwaniu rozwi

zania

w zbiorze rozwi

dopuszczalnych.

w zbiorze rozwi

dopuszczalnych.

Na takiej zasadzie opiera si

działanie wielu agentów, np.:

• agenci - obiekty w grach komputerowych, symulatorach;

• agenci - obiekty w grach komputerowych, symulatorach;
• oprogramowanie przewodników drogi wykorzystuj

cych

system GPS,

• agenci poszukuj

cy w Internecie stron z

żą

dan

zawarto

Poszukiwanie nieinformowane (uninformed search) polega
na wyznaczaniu rozwi

zania zadania wył

cznie na podstawie

danych definiuj

cych zadanie.

danych definiuj

cych zadanie.

Poszukiwanie informowane (informed search) polega na
wyznaczaniu rozwi

zania zadania przy wykorzystaniu innej

© F.A. Dul 2007

wyznaczaniu rozwi

zania zadania przy wykorzystaniu innej

dost

pnej wiedzy, specyficznej dla tego zadania.

3.1. Wprowadzenie

Plan rozdziału

• Agenci rozwi

zuj

cy zadania.

• Rodzaje zada

• Sformułowania zada

• Przykłady zada

• Podstawowe algorytmy poszukiwa

© F.A. Dul 2007

3.2. Agent poszukuj

cy rozwi

zania

Agent poszukuj

cy rozwi

zania jest rodzajem agenta

Agent poszukuj

cy rozwi

zania jest rodzajem agenta

celowego.

Czetry kroki przy rozwi

zywaniu problemu

• Sformułowanie celu zadania

– jaki stan systemu odpowiada osi

gni

ciu celu?

Czetry kroki przy rozwi

zywaniu problemu

– jaki stan systemu odpowiada osi

gni

ciu celu?

• Sformułowanie zadania

– jakie stany i działania nale

y bra

pod uwag

• Poszukiwanie

– okre

optymalne działania które nale

y wykona

aby

osi

ąć

cel

• Wykonanie zadania

– wyznaczy

rozwi

zanie

© F.A. Dul 2007

Algorytm agenta poszukuj

cego rozwi

zania

3.2. Agent poszukuj

cy rozwi

zania

function SIMPLE-PROBLEM-SOLVING-AGENT(percept) return an action

static: seq, an action sequence

state, some description of the current world state

state, some description of the current world state
goal, a goal
problem, a problem formulation

problem, a problem formulation

state

←

UPDATE-STATE(state, percept)

if seq is empty then

goal

←

FORMULATE-GOAL(state)

problem

←

FORMULATE-PROBLEM(state,goal)

problem

←

FORMULATE-PROBLEM(state,goal)

seq

←

SEARCH(problem)

action

←

FIRST(seq)

seq

←

REST(seq)

seq

←

REST(seq)

return action

© F.A. Dul 2007

3.2. Agent poszukuj

cy rozwi

zania

Przykład - poszukiwanie najkrótszej drogi

• Wakacje w Rumunii;

jeste

my w mie

cie

jeste

my w mie

cie

Arad.

• Jutro musimy odlecie

• Sformułowanie celu

• Jutro musimy odlecie

z Bukaresztu.

• Sformułowanie celu

– nale

y jutro rano by

w Bukareszcie.

• Sformułowanie zadania

– stan

: pobyt w jakim

mie

cie;

– działania

: przejazdy pomi

dzy miastami.

– działania

: przejazdy pomi

dzy miastami.

• Znale

źć

rozwi

zanie

– ci

g miast, { Arad , … , Bukareszt }

© F.A. Dul 2007

– ci

g miast, { Arad , … , Bukareszt }

np. { Arad, Sibiu, Fagaras, Bukareszt }.

3.3. Rodzaje zada

Zadanie najprostsze

• Deterministyczne, obserwowalne

⇒

zadanie jednostanowe

– agent wie w jakim jest stanie i w jakim stanie b

dzie;

Zadanie najprostsze

– agent wie w jakim jest stanie i w jakim stanie b

dzie;

rozwi

zanie jest ci

giem stanów;

Zadania znacznie trudniejsze:

• Nieobserwowalne

⇒

zadanie bez czujników (conformant

problem)

Zadania znacznie trudniejsze:

problem)

– agent nie wie, gdzie jest; rozwi

zanie jest ci

giem stanów;

• Niedeterministyczne lub obserwowalne cz

ęś

ciowo

• Niedeterministyczne lub obserwowalne cz

ęś

ciowo

⇒

nieprzewidywalne

(contingency problem)

– obserwacje dostarczaj

nowych

informacji o stanie bie

żą

cym,

– poszukiwania cz

sto

przeplataj

z działaniami.

– poszukiwania cz

sto

przeplataj

z działaniami.

• Nieznana przestrze

stanów

⇒

exploration problem

© F.A. Dul 2007

3.3. Rodzaje zada

Przykład -

wiat agenta-odkurzacza

•

Problem jednostanowy

, start

ze stanu {5}.

Rozwi

zanie

Zbiór wszystkich stanów

Rozwi

zanie

[ W PRAWO , ODKURZAJ ]

•

Bez czujników,

start z dowolnego

•

Bez czujników,

start z dowolnego

stanu spo

ród {1,2,3,4,5,6,7,8}

W PRAWO {2,4,6,8}

Rozwi

zanie

Rozwi

zanie

[ W PRAWO , ODKURZAJ ,

W LEWO , ODKURZAJ ]

•

Nieprzewidywalno

ść

– Niedeterministyczne: ODKURZAJ mo

e za

mieci

czysty dywan

– Niedeterministyczne: ODKURZAJ mo

e za

mieci

czysty dywan

– Cz

ęś

ciowa obserwowalno

ść

: poło

enie,

mieci w aktualnym poło

eniu.

– Obserwacja: [L, CZYSTY], tj. start za stanów 5 lub 7.

Rozwi

zanie

© F.A. Dul 2007

Rozwi

zanie

[ W PRAWO , je

eli

MIECI to ODKURZAJ ]

Zadanie jednostanowe - sformułowanie

3.3. Rodzaje zada

•

stanu pocz

tkowego

, np. "w Arad”,

Zadanie jednostanowe zdefiniowane jest za pomoc

czterech

elementów:

•

stanu pocz

tkowego

, np. "w Arad”,

•

działa

lub funkcji nast

pstwa

S(x) = zbiór par

〈

działanie , stan

〉

S(x) = zbiór par

〈

działanie , stan

〉

np. S(Arad) = {

〈〈〈〈

Arad

→

Zerind, Zerind

〉〉〉〉

, … }

•

testu osi

gni

cia celu

– jawny, np. x = ”w Bukareszcie”,
– niejawny, np.w szachach Mat(x);

•

kosztu drogi

(addytywnego)

•

kosztu drogi

(addytywnego)

– np. sumy odległo

ci, liczby podj

tych działa

, etc.

– c(x,a,y) jest kosztem kroku, z zało

enia c

≥

– c(x,a,y) jest kosztem kroku, z zało

enia c

≥

Rozwi

zaniem zadania jednostanowego jest ci

g działa

prowadz

cych ze stanu pocz

tkowego do stanu docelowego.

© F.A. Dul 2007

prowadz

cych ze stanu pocz

tkowego do stanu docelowego.

Rozwi

zanie optymalne cechuje najmniejszy koszt.

Zadanie jednostanowe - sformułowanie

3.3. Rodzaje zada

•

wiat rzeczywisty jest kra

cowo skomplikowany, dlatego

przestrze

stanów musi by

abstrakcj

stanów rzeczywistych.

Abstrakcja oznacza

pomini

cie szczegółów

Abstrakcja oznacza

pomini

cie szczegółów

• Stan abstrakcyjny = zbiór stanów rzeczywistych.
• Działanie abstrakcyjne = zło

ona kombinacja działa

• Działanie abstrakcyjne = zło

ona kombinacja działa

rzeczywistych,

np. "Arad

→

Zerind" reprezentuje zło

ony zbiór mo

liwych

np. "Arad

→

Zerind" reprezentuje zło

ony zbiór mo

liwych

tras, objazdy, parkingi, etc.

• Aby zapewni

istnienie rozwi

zania, ka

dy stan rzeczywisty

(np. ”Arad“) musi prowadzi

do jakiego

stanu rzeczywistego

(np. ”Arad“) musi prowadzi

do jakiego

stanu rzeczywistego

(np. „Zerind”).

• Rozwi

zanie abstrakcyjne = zbiór rzeczywistych dróg które

• Rozwi

zanie abstrakcyjne = zbiór rzeczywistych dróg które

rozwi

zaniami w

wiecie rzeczywistym.

• Kazde działanie abstrakcyjne powinno by

łatwiejsze ni

© F.A. Dul 2007

• Kazde działanie abstrakcyjne powinno by

łatwiejsze ni

rzeczywiste.

Graf przestrzeni stanów dla

wiata odkurzacza

3.3. Rodzaje zada

• stan:

poło

enie odkurzacza oraz czysto

ść

;

• stan pocz

tkowy: ka

dy;

• stan pocz

tkowy: ka

dy;

• działania:

W LEWO, W PRAWO, ODKURZAJ;

• test celu:

czysto we wszystkich poło

eniach;

© F.A. Dul 2007

• test celu:

czysto we wszystkich poło

eniach;

• koszt:

1 za ka

de działanie;

Przykład: gra w osiem puzzli

3.3. Rodzaje zada

Stan pocz

tkowy Stan docelowy

• stan:

poło

enie puzzli 1 - 8;

• działania: ruch pola pustego: w lewo, w prawo,w gór

w dół;

• test celu:

osi

gni

cie zadanego układu puzzli;

• koszt:

1 za ka

dy ruch;

© F.A. Dul 2007

• koszt:

1 za ka

dy ruch;

Rozwi

zanie optymalne problemu n puzzli jest zadaniem NP-hard

Przykład: monta

przy u

yciu robota

3.3. Rodzaje zada

• stan:

wieloelementowa tablica poło

enia

• stan:

wieloelementowa tablica poło

enia

ramienia robota oraz poło

enia

montowanych elementów;

• działania: ci

gły ruch ramienia robota, chwytanie

• działania: ci

gły ruch ramienia robota, chwytanie

i puszczanie elementów;

• test celu:

zmontowane urz

dznie;

© F.A. Dul 2007

• test celu:

zmontowane urz

dznie;

• koszt:

czas monta

u urz

dzenia;

Inne przykłady zada

wiata rzeczywistego

3.3. Rodzaje zada

• Wyznaczanie drogi: wyznaczanie trasy ł

cej w

zły:

pocz

tkowy i ko

cowy;

• Problem zwiedzania: wyznaczanie trasy przebiegaj

cej

• Problem zwiedzania: wyznaczanie trasy przebiegaj

cej

przez w

zły (np. miasta) tylko jeden raz;

• Problem komiwoja

era: wyznaczenie najkrótszej trasy

• Problem komiwoja

era: wyznaczenie najkrótszej trasy

przebiegaj

cej przez w

zły tylko jeden raz;

• Planowanie obwodów VLSI: rozmieszczanie elementów

układu i wyznaczanie poł

cze

dzy nimi;

układu i wyznaczanie poł

cze

dzy nimi;

• Nawigacja robotów: ci

gła wersja problemu wyznaczania

drogi;

• Planowanie automatycznego monta

u: wyznaczenie

wła

ciwej kolejno

ci monta

u elementów;

• Synteza protein: wyznaczenie wła

ciwej kolejno

aminokwasów białka o okre

lonych własno

ciach;

• Poszukiwania w Internecie: wyznaczenie trasy

© F.A. Dul 2007

• Poszukiwania w Internecie: wyznaczenie trasy

poszukiwa

żą

danych informacji na stronach Internetu;

3.3. Rodzaje zada

Podstawow

zasad

poszukiwa

nieinformowanych jest korzystanie

nieinformowanych jest korzystanie
wył

cznie z definicji zadania - bez

wykorzystywania dodatkowych

wykorzystywania dodatkowych
informacji.

Przypomina to prób

dojechania

w mie

cie samochodem na podany

w mie

cie samochodem na podany

adres gdy zna si

tylko ten adres oraz

adres gdy zna si

tylko ten adres oraz

reguły prowadzenia samochodu.

© F.A. Dul 2007

3.4. Algorytmy przeszukiwania drzew

Idea algorytmów przeszukuj

cych

Idea algorytmów przeszukuj

cych

•

lepe poszukiwania: analiza wszystkich mo

liwych

sekwencji stanów;

– koszt ro

nie gwałtownie ze wzrostem liczby mo

liwych

stanów;

• poszukiwania poprzez budow

drzewa stanów:

• poszukiwania poprzez budow

drzewa stanów:

– KORZE

- stan pocz

tkowy;

– w

zły i gał

zie generowane funkcj

nast

pstwa;

function TREE-SEARCH(problem,strategy) returns a solution or failure

Ogólnie: przeszukiwanie generuje graf.

function TREE-SEARCH(problem,strategy) returns a solution or failure

initialize the search tree using the initial state of problem
do

if there are no candidates to expand then return failure

if there are no candidates to expand then return failure
choose a legal node for expansion according to strategy
if the node contains a goal state then return corresponding solution

else expand the node and add the resulting nodes to the search tree

© F.A. Dul 2007

else expand the node and add the resulting nodes to the search tree

Algorytmy przeszukiwania drzewa - przykład

3.4. Algorytmy przeszukiwania drzew

Stan pocz

tkowy

Poziom 1.

Poziom 2.

function TREE-SEARCH(problem,strategy) returns a solution or failure

initialize the search tree using the initial state of problem
do

function TREE-SEARCH(problem,strategy) returns a solution or failure

initialize the search tree using the initial state of problem

function TREE-SEARCH(problem,strategy) returns a solution or failure

initialize the search tree using the initial state of problem
do

if there are no candidates to expand then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state then return corresponding solution

if there are no candidates to expand then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state then return corresponding solution

if there are no candidates to expand then return failure

choose a leaf node for expansion according to strategy

if the node contains a goal state then return corresponding solution

else expand the node and add the resulting nodes to the search tree

© F.A. Dul 2007

if the node contains a goal state then return corresponding solution

else expand the node and add the resulting nodes to the search tree

if the node contains a goal state then return corresponding solution

else expand the node and add the resulting nodes to the search tree

Ró

nica pomi

dzy stanem a w

złem

3.4. Algorytmy przeszukiwania drzew

• Stan okre

la konfiguracj

fizyczn

obiektu lub zadania;

• Stan okre

la konfiguracj

fizyczn

obiektu lub zadania;

• W

zeł jest to struktura danych okre

laj

ca cz

ęść

drzewa poszukiwa

, obejmuj

ca np.: stan, w

zeł

drzewa poszukiwa

, obejmuj

ca np.: stan, w

zeł

rodzica, w

zły dzieci, koszt gał

zi, aktualn

gł

boko

ść

podejmowane działanie, itp.;

zeł =

〈〈〈〈

stan, w

zeł rodzica, koszt, gł

boko

ść

, działanie

〉〉〉〉

• Funkcja

Expand

tworzy nowe w

zeł, wypełnia odpowiednie

• Funkcja

Expand

tworzy nowe w

zeł, wypełnia odpowiednie

pola, a nast

pnie przy pomocy funkcji

SuccessorFn

tworzy stan w nowym w

ęź

le.

© F.A. Dul 2007

• Brzeg (fringe) to zbiór wszystkich w

złow, które nie zotały

jeszcze rozwini

te.

Strategie algorytmów przeszukiwania drzew

3.4. Algorytmy przeszukiwania drzew

• Strategia poszukiwania jest okre

lona

kolejno

rozwijania w

złów.

• Strategie s

oceniane wg. nast

puj

cych kryterów:

– zupełno

ść

: mo

liwo

ść

znalezienia rozwi

zania, je

eli

istnieje;

– zło

ono

ść

czasowa

: liczba generowanych w

złów;

– zło

ono

ść

pami

ciowa

: najwi

ksza liczba w

złów

w pami

ci;

– zło

ono

ść

pami

ciowa

: najwi

ksza liczba w

złów

w pami

ci;

– optymalno

ść

: mo

liwo

ść

wyznaczenia najta

szego

rozwi

zania.

rozwi

zania.

• Zło

ono

ść

czasowa i pami

ciowa s

szacowane za pomoc

nast

puj

cych wielko

ci:

– b: maksymalny współczynnik rozgał

zienia drzewa

poszukiwa

– d: gł

boko

ść

rozwi

zania optymalnego,

© F.A. Dul 2007

– d: gł

boko

ść

rozwi

zania optymalnego,

– m: maksymalna gł

boko

ść

przestrzeni stanów.

Strategie nieinformowane przeszukiwania drzew

3.4. Algorytmy przeszukiwania drzew

Strategie

nieinformowane

wykorzystuj

tylko informacje

zawarte w definicji zadania.

Rodzaje strategii nieinformowanych:

Strategie nieinformowane - poszukiwania “na o

lep”.

• Poszukiwanie wszerz (breadth-first search),

• Poszukiwanie w gł

b (depth-first search),

• Poszukiwanie w gł

b (depth-first search),

• Poszukiwanie z jednostajnym kosztem

(uniform-cost search),

• Poszukiwanie na ograniczon

gł

boko

ść

(depth-limited search),

• Poszukiwanie pogł

biane iteracyjnie

(iterative deepening search).

• Poszukiwanie dwukierunkowe (bidrectional search).

© F.A. Dul 2007

• Poszukiwanie dwukierunkowe (bidrectional search).

Poszukiwanie wszerz (breadth-first search)

3.4. Algorytmy przeszukiwania drzew

Własno

ci algorytmu

• Zupełno

ść

Tak, je

eli b jest ograniczone

• Zupełno

ść

Tak, je

eli b jest ograniczone

• Czas

1+b+b

+… +b

+ b(b

-1) = O(b

d+1

)

• Pami

ęć

O(b

d+1

) (przechowywanie wszystkich

złów w pami

ci)

złów w pami

ci)

• Optymalno

ść

Tak, je

eli koszt kroku jest stały

• Pami

ęć

jest najwi

kszym problemem, wi

kszym ni

czas

poszukiwa

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Zasada: rozwin

ąć

najgł

bszy nierozwini

ty w

zeł

(najgł

bszy na brzegu).

Brzeg jest kolejk

LIFO, tzn. nowy w

zeł wstawiany jest na

pocz

tek kolejki.

© F.A. Dul 2007

Poszukiwanie w gł

b (depth-first search)

3.4. Algorytmy przeszukiwania drzew

Własno

ci algorytmu

• Zupełno

ść

Tak w przestrzeniach sko

czonych.

• Zupełno

ść

Tak w przestrzeniach sko

czonych.

Nie w przestrzeniach niesko

czonych,

z p

tlami; (wymaga wtedy modyfikacji

w celu unikni

cia powtarzaj

cych si

w celu unikni

cia powtarzaj

cych si

stanów)

• Czas

O(b

) - ogromny je

eli m >> d;

• Czas

O(b ) - ogromny je

eli m >> d;

• Pami

ęć

O(bm) - liniowa wzgl

dem pami

ci;

• Optymalno

ść

Nie

© F.A. Dul 2007

Poszukiwanie z jednostajnym kosztem (uniform cost

3.4. Algorytmy przeszukiwania drzew

search)

Zasada: rozwin

ąć

najta

szy nierozwini

ty w

zeł.

Własno

ci algorytmu

Brzeg jest kolejk

uporz

dkowan

według rosn

cego kosztu.

• Zupełno

ść

Tak je

eli koszt kroku >

> 0.

• Czas

O(b

) - najgorszy przypadek,

C - koszt rozwi

zania optymalnego;

C - koszt rozwi

zania optymalnego;

• Pami

ęć

O(b

);

• Optymalno

ść

Tak - w

zły s

rozwijane według

• Optymalno

ść

Tak - w

zły s

rozwijane według

najwolniej rosn

cego kosztu.

Poszukiwanie na ograniczon

gł

boko

ść

(depth

3.4. Algorytmy przeszukiwania drzew

limited search)

Zasada: jak w algorytmie poszukiwania wgł

b ale z

gł

boko

ograniczon

do poziomu

gł

boko

ograniczon

do poziomu

Algorytm rozwi

zuje problem niesko

czonej

cie

ki.

Własno

ci algorytmu

• Zupełno

ść

Tak je

eli l

≥

• Zupełno

ść

Tak je

eli l

≥

• Czas

O(b

);

• Pami

ęć

O(bl);

• Pami

ęć

O(bl);

• Optymalno

ść

Tak je

eli l

≤

Poszukiwanie pogł

biane iteracyjnie (iterative deepe-

3.4. Algorytmy przeszukiwania drzew

ning search)

Cel jest osi

gni

ty na gł

boko

ci d odpowiadaj

cej

najpłytszemu w

złowi docelowemu.

najpłytszemu w

złowi docelowemu.

Algorytm ł

czy zalety algorytmów poszukiwania wszerz

i w gł

Własno

ci algorytmu

i w gł

• Zupełno

ść

Tak.

• Zupełno

ść

Tak.

• Czas

O(b

);

• Pami

ęć

O(bd);

• Pami

ęć

O(bd);

• Optymalno

ść

Tak je

eli koszt kroku jest stały.

Poszukiwanie dwukierunkowe (bidrectional search)

3.4. Algorytmy przeszukiwania drzew

Zasada: jednoczesne poszukiwanie z pocz

tku i ko

ca;

Nale

y sprawdz

przed rozwini

ciem czy w

zły nale

żą

Nale

y sprawdz

przed rozwini

ciem czy w

zły nale

żą

do drugiego brzegu.

Własno

ci algorytmu

• Zupełno

ść

Tak je

eli oba poszukiwania wszerz.

• Zupełno

ść

Tak je

eli oba poszukiwania wszerz.

• Czas

O(b

d/2

);

• Pami

ęć

O(b

d/2

);

• Pami

ęć

O(b

);

• Optymalno

ść

Tak je

eli oba poszukiwania wszerz.

Porównanie algorytmów przeszukiwania

3.4. Algorytmy przeszukiwania drzew

Kryterium

Wszerz

W gł

Koszt

jednordny

Stała

gł

boko

ść

Pogł

bianie

iteracyjne

Dwukie-

runkowe

Zupełno

ść

TAK

NIE

TAK

TAK (l

≥≥≥≥

TAK

Czas

O(b

d+1

)

O(b

)

O(b

εεεε

)

O(b

)

O(b

)

O(b

d/2

)

Czas

O(b

)

O(b )

O(b

)

O(b )

O(b

)

Pami

ęć

O(b

d+1

)

O(bm)

O(b

εεεε

)

O(bl)

O(bd)

O(b

d/2

)

Optymalno

ść

TAK

NIE

TAK

TAK (l

≤≤≤≤

TAK

3.4. Algorytmy przeszukiwania drzew

Najwi

ksz

wad

poszukiwa

Najwi

ksz

wad

poszukiwa

nieinformowanych jest wykładniczy
wzrost kosztu oblicze

wzrost kosztu oblicze

Krytyczna jest zwłaszcza ilo

ść

Krytyczna jest zwłaszcza ilo

ść

wymaganej pami

ci, gdy

e ona

gigantyczna nawet dla zada

o umiarkowanych wymiarach.

Problem powtarzaj

cych si

stanów

3.4. Algorytmy przeszukiwania drzew

eli powtarzaj

ce si

stany nie s

wykrywane, to zadanie

rozwi

zywalne mo

e zmieni

w nierozwi

zywalne.

(a) zbiór stanów które mog

osi

gane dwiema drogami,

(b) drzewo binarne dla zbioru stanów A, B, C, D...

dy stan mo

e by

osi

gni

ty kosztem liniowym,

koszt przeszukiwania drzewa jest wykładniczy.

e by

osi

gany wieloma ró

nymi drogami.

3.5. Przeszukiwanie grafu (graph search)

Zasada: lista zamkni

ta zawiera wszystkie rozwini

te w

zły.

function GRAPH-SEARCH(problem,fringe) return a solution or failure

closed

←

an empty set

closed

←

an empty set

fringe

←

INSERT(MAKE-NODE(INITIAL-STATE[problem]), fringe)

loop do

if EMPTY?(fringe) then return failure

if EMPTY?(fringe) then return failure
node

←

REMOVE-FIRST(fringe)

if GOAL-TEST[problem] applied to STATE[node] succeeds

then return SOLUTION(node)

if STATE[node] is not in closed then

add STATE[node] to closed
fringe

←

INSERT-ALL(EXPAND(node, problem), fringe)

Własno

ci algorytmu

• Zupełno

ść

Tak

fringe

←

INSERT-ALL(EXPAND(node, problem), fringe)

• Zupełno

ść

Tak

• Czas

~ wymiaru przestrzeni stanu, << O(b

);

• Pami

ęć

~ wymiaru przestrzeni stanu, << O(b

)

• Pami

ęć

~ wymiaru przestrzeni stanu, << O(b )

• Optymalno

ść

Tak je

eli poszukiwania wszerz.

Poszukiwanie w przypadku niepełnej informacji

3.5. Algorytmy przeszukiwania grafów

Zało

enia idealne:

rodowisko jest całkowicie obserwowalne,

rodowisko jest deterministyczne,

- agent zna efekty swojego działania.

Co si

stanie, gdy agent nie ma pełnej informacji

Co si

stanie, gdy agent nie ma pełnej informacji

o stanie lub efektach działania?

• Nieobserwowalne

⇒

zadanie bez czujników (conformant

problem)

– agent nie wie, gdzie jest; rozwi

zanie jest ci

giem stanów;

• Niedeterministyczne lub obserwowalne cz

ęś

ciowo

⇒

nieprzewidywalne

(contingency problem)

⇒

nieprzewidywalne

(contingency problem)

– obserwacje dostarczaj

nowych

informacji o stanie bie

żą

cym,

– poszukiwania cz

sto

przeplataj

z działaniami.

• Nieznana przestrze

stanów

⇒

exploration problem

Zadanie nieobserwowalne (conformant problem)

3.5. Algorytmy przeszukiwania grafów

Start z dowolnego stanu spo

ród

{1,2,3,4,5,6,7,8}

W PRAWO

→

{2,4,6,8}

Rozwi

zanie

[ W PRAWO , ODKURZAJ ,

W LEWO , ODKURZAJ ]

eli

wiat nie jest całkowicie obserwowalny, to stan

wiarygodny (belief state) jest zbiorem stanów, które
mog

osi

gni

te.

mog

osi

gni

te.

Zadanie niedeterministyczne lub obserwowalne
cz

ęś

ciowo (contingency problem)

3.5. Algorytmy przeszukiwania grafów

ęś

ciowo (contingency problem)

Obserwowalno

ść

lokalna: start

z jednego ze stanów {1,3}.

Prawo Murphy’ego

odkurzanie czystego dywanu

e go zabrudzi

Obserwacja lokalna:

zabrudzenie tylko w miejscu

pobytu agenta.

- obserwacja: [L,

MIECI] = {1,3},

- [ODKURZAJ] = {5,7},
- [W PRAWO] = {6,8},

- [W PRAWO] = {6,8},
- [ODKURZAJ] w {6} = {8}, OK
- [ODKURZAJ] w {8} =

LE!

Rozwi

zanie

aden bezwarunkowy ci

g działa

nie gwarantuje powodzenia.

Nale

y uzale

działania od aktualnej sytuacji.

Rozwi

zanie

[ ODKURZAJ, W PRAWO, je

eli

MIECI to ODKURZAJ ]

Podsumowanie

• Rozwi

zywanie zada

poprzez przeszukiwanie wymaga

• Rozwi

zywanie zada

poprzez przeszukiwanie wymaga

sformułowania zadania w postaci abstrakcyjnej.

• Je

eli zadanie jest deterministyczne i obserwowalne

• Je

eli zadanie jest deterministyczne i obserwowalne

(jednostanowe), to do jego rozwi

zania mo

na u

algorytmu poszukiwania nieinformowanego.

• Istnieje wiele algorytmów poszukiwania nieinformowanego:

wszerz, w gł

b, kosztu jednorodnego, stałej gł

boko

ci,

pogł

biania iteracyjnego oraz poszukiwa

dwukierunkowych.

• Algorytm poszukiwania poprzez pogł

bianie iteracyjne jest

najlepszym algorytmem ogólnym - wymaga liniowej pami

a czas oblicze

jest niewiele wi

kszy ni

w przypadku innych

a czas oblicze

jest niewiele wi

kszy ni

w przypadku innych

algorytmów.

• Agenci działaj

cy na zasadzie poszukiwania rozwi

zania

ywani w wielu dziedzinach: wyznaczaniu drogi,

planowaniu układów VLSI, nawigacji robotów, poszukiwa

internetowych;