Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Rozwiązywanie

zadań przy użyciu

algorytmów

przeszukiwania

przestrzeni rozwiązań

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Problem

Rozwiązanie

Algorytm

przeszukiwania

Rozwiązanie zadania jest elementem znanego

zbioru „kandydatów”

Algorytmy przeszukiwania -

wprowadzenie

Problem - określić

sekwencję

czynności prowadzących

do rozwiązania

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Znaczenie

Termin

Zbiór

stanów

i

akcji

określonych dla

rozważanego problemu

Zbiór stanów spełniających warunki

postawionego zadania

Ścieżka, prowadząca ze

stanu

początkowego

do

stanu doeclowego

Przestrzeń
rozwiązań

Cel

Rozwiązanie

Algorytmy przeszukiwania - terminologia

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Sformułowanie

problemu

Przeszukiwanie

przestrzeni

stanu

Procedura rozwiązywania problemu

Wykonanie

znalezionej

sekwencji

Określenie możliwych

stanów

, dozwolonych

akcji

, relacji

akcja->

stan (

operatory

) i

określenie

celu

Przeszukuj

przestrzeń stanów

w celu

określenia

ścieżki

prowadzącej do

celu (wykonuj

testy uzyskania

rozwiązania

). Dodatkowo,

minimalizuj

koszt

procedury

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Przestrzeń stanu

Stan

początkowy

Cel

s

0

= Stan początkowy

Algorytmy przeszukiwania

s

i +1

= o ( s

i

)

Cel ( s

i

) ?

NIE

TAK

Koniec poszukiwań:
zapamiętaj ścieżkę

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Środowisko

Akcje: Idź w kierunku: E, N, W, S; dokonuj testu

obecności skarbu w komórce c

ij

: f(c

ij

) =?

Cel:

Zdobyć skarb

- f(c

ij

) ==

prawda

0

1

2

0

1

2

Przykładowy problem -

poszukiwacz skarbów

Przestrzeń stanów

określony dla każdej komórki

zbiór par danych postaci

{ położenie , obecność skarbu}

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Przykładowy problem -

poszukiwacz skarbów

Graf procedury przeszukiwania

[0,0]

f(0,0)=0

Cel prac - opracować

systematyczną

procedurę przeszukiwania

[0,1]

f(0,1)=0

[2,2]

f(2,2)=0

[1,1]

f(1,0)=0

[1,0]

f(1,1)=0

[2,1]

f(2,1)=0

[2,0]

f(1,2)=0

[0,2]

f(0,2)=1

O(s)=E

O(s)=S

O(s)=S

O(s)=N

O(s)=E

[2,1]

f(2,2)=0

[1,2]

f(2,2)=0

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Przykładowy problem -

planowanie podróży

Łódź

Wąchock

Rzym

Chreptiów

Ceske

Budejovice

Pacanów

Casablanca

Berkeley

Rio

100

600

12000

11000

8000

400

1800

1300

10000

Cel:

znajdź najkrótszą trasę

- f(c

ij

) ==

min

Akcje: próbuj kolejną sekwencję przystanków, testuj cel

Przestrzeń

stanów

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Koszt procedury =

koszt przeszukiwania

+

koszt wykonania

Rozwiązywanie problemów przy użyciu algorytmów

przeszukiwania jest możliwe dla problemów o

ograniczonej złożoności

i

definiowalnej

przestrzeni

stanów

Algorytmy przeszukiwania

Zwykle konieczny kompromis !

Koszt wykonania

: Addytywna funkcja przypisana znalezionej ścieżce

Koszt przeszukiwania:

Czas i zasoby niezbędne do znalezienia
rozwiązania

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

A

X

Y

Metody przeszukiwania przestrzeni stanów

A

B

C D E

o ( A ) =

B
C
D
E

o ( . ) - operator

X

Y

{

Jak organizować

przeszukiwanie i jak

je przeprowadzać?

Reguła wybierania kolejnych stanów

Strategia przeszukiwania

Wybór sposobu

wybierania

kolejnych stanów

Wybór stanu

startowego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

…

…

Terminologia

Węzły

Implementacja

programowa

węzła

Drzewo poszukiwań

Stan
Stan poprzedni
Operator (generujący dany węzeł)
Głębokość, koszt ścieżki itd.

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Kolejka

:

sposób reprezentacji węzłów oczekujących
na ekspansję

A

X

Y

Terminologia

A

B

C D E

X

Y

Q = ( A, X, Y)

Q

- Kolejka

Q = ( B, C, D, E, X, Y)

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Klasyfikacje strategii poszukiwania

Kryterium: zasada ekspansji węzłów

Strategie

Warstwowe

Ekspansja „pozioma”

Wgłębne

Ekspansja „pionowa”

Kombinacje

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Kryteria oceny strategii przeszukiwania

Kompletność

(pewność uzyskania rozwiązania)

Złożoność czasowa

(znalezienia rozwiązania)

Zasoby

(pamięć)

Optymalność

(znalezionego rozwiązania)

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Nie istnieje żadna

informacja, sugestia ani

reguła pozwalająca na

stwierdzenie poprawności

wybranego kierunku

poszukiwań - poszukiwanie

musi odbywać się na oślep.

Przeszukiwanie

po omacku

W każdej chwili można

podejmować próby

oszacowania trafności

wyboru przyjętego

kierunku poszukiwań

Przeszukiwanie

heurystyczne

Klasyfikacje strategii poszukiwania

Kryterium: istnienie wskazówek co do zbliżania się do celu

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Określ ścieżkę prowadzącą od stanu

początkowego do stanu będącego rozwiązaniem

Dane

Jedyną informację co do poprawności

poszukiwania daje test

osiągnięcia celu

Zakładając,

że:

przestrzeń stanów dla problemu

zbiór stanów będących rozwiązaniem

zbiór operatorów

Strategie przeszukiwania po omacku

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Strategia 1:

Przeszukiwanie warstwowe

Kolejka

Q = ( A, B C)

A

B

C

A

A

1

B

C

A

2

A

3

A

4

A

B

C

A

1

A

2

A

3

A

4

B

1

B

2

B

3

B

4

Q = (B, C, A

1

, A

2

,

A

3

, A

4

)

Q = (C, A

1

, A

2

,

A

3

, A

4,

B

1

, B

2

, B

3

, B

4,

)

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

20

21

10

22

11

11

10

21

20

21 10

20

21

10

12

01

10

21

12

01

21

...

...

02

11

……...

02

11

0
1
2

0

1

2

Kolejność ekspansji węzłów

Przykład

Przeszukiwanie warstwowe

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Kompletność

Czy można zagwarantować znalezienie rozwiązania ?

Można wykazać, że strategia jest kompletna

Optymalność

Czy uzyskane rozwiązanie jest optymalne ?

Można wykazać, że strategia jest optymalna, jeżeli

koszt poszukiwania jest niemalejącą funkcją

liczby poziomów drzewa poszukiwań

Właściwości przeszukiwania warstwowego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Złożoność czasowa

Ile czasu potrzeba na znalezienie rozwiązania ?

Złożoność czasowa procedury przeszukiwania warstwowego jest

BARDZO DUŻA

- rośnie wykładniczo w funkcji głębokości drzewa

i

współczynnika rozgałęzienia

...

b

1

Współczynnik rozgałęzienia

(b) -

średnia liczba gałęzi wychodzących
z każdego węzła

t = 1 + b + b

2

+ b

3

+ … + b

d

t - czas, d - głębokość drzewa (liczba poziomów)

Właściwości przeszukiwania warstwowego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Wymagane zasoby

jaka pamięć jest wymagana dla uzyskania rozwiązania ?

Wymagane zasoby dla przeprowadzenia procedury przeszukiwania

warstwowego jest

BARDZO DUŻA

(podobnie jak złożoność czasowa)

m = 1 + b + b

2

+ b

3

+ … + b

d

gdzie: m - wymagana pamięć, , d - głębokość drzewa , b - wsp. rozgałęzienia

Przykład:

d=20 (20 miast - węzłów),
b=3 (średnio - trzy połączenia/miasto)
m = t = 1 + … + 3

20

≅

3

20

≅

10

10

f zegara: 10

-9

([GHz]) - 10s

Pamięć:

10 GB !!!

Właściwości przeszukiwania warstwowego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Strategię można stosować wyłącznie dla

rozwiązywania bardzo prostych problemów

Główna wada - wymagane zasoby

Złożoność czasowa - również może okazać się

poważnym ograniczeniem

Właściwości przeszukiwania warstwowego -

podsumowania

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

następny węzeł - n

i,j,k

Cel dla n

i,j,k

?

Więcej węzłów dla

przodka “i” ?

j=j+1

Więcej węzłów dla “k”

?

i=i+1

Więcej poziomów ?

k=k+1

Brak rozwiązania

Start: k=0 (poziom zerowy), i=j=0

Określ ścieżkę

T

T

T

T

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Kolejka

Q = ( A, B C)

A

B

C

Q = (A

21

, A

22

, A

23

,

A

2

, B, C)

Strategia 2:

Przeszukiwanie

wgłębne

A

A

1

B

C

A

2

Q = (A

1

, A

2

, B, C)

A

A

1

B

C

A

21

A

2

A

22

A

23

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

0

1
2

0 1

2

Koszt ścieżki - liczba posunięć

20

21

10

22

11

11

10

21

20

21 10

20

21

10

12

01

10

21

12

01

21

...

...

02

11

……...

02

11

Kolejność ekspansji węzłów

Przeszukiwanie wgłębne

Przykład

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Kompletność

Czy można zagwarantować znalezienie rozwiązania ?

Przeszukiwanie wgłębne

nie jest

kompletne

20

0
1
2

0

1

2

21

22

12

22

12

22

12

22

:

Właściwości przeszukiwania wgłębnego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Optymalność

Ponieważ nie jest kompletne, nie jest optymalne

Złożoność czasowa

Złożoność czasowa przeszukiwania jest

BARDZO DUŻA

- rośnie

wykładniczo z głębokością drzewa i

współczynnikiem

rozgałęzienia

t ~ 2b

d

t - czas, d - głębokość drzewa poszukiwań

Właściwości przeszukiwania wgłębnego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Wymagane zasoby

Zasoby wymagane dla przeprowadzenia procedury są

BARDZO MAŁE

Zapamiętana musi być tylko jedna ścieżka od stanu początkowego

m

∝

∝

∝

∝

d

2

gdzie: m - wielkość pamięci, , d - głębokość drzewa

Wniosek: strategia ryzykowna

Główna wada - niekompletność

Główna zaleta - małe wymagania pamięciowe

Właściwości przeszukiwania wgłębnego

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Przeszukiwanie z ograniczoną głębokością

Idea metody - wykorzystać zalety przeszukiwania wgłębnego

eliminując problem niekompletności procedury w drodze

ograniczenia głębokości przeszukiwania

d

Problem: wybór odpowiedniej wartości

d

MAX

Możliwe rozwiązanie:

d = rozmiar przestrzeni stanów

Optymalność

Strategia jest optymalna

Kompletność

Strategia jest kompletna

Złożoność czasowa

Duża

Zasoby

Małe

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

20

21

22

10

21

12

11

21

01

...

02

22

21

...

Ekspansja węzłów

do co najwyżej

d - poziomów

0
1
2

0

1

2

d = 6

Przeszukiwanie z ograniczoną głębokością

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Przeszukiwanie

wgłębne

Przeszukiwanie

warstwowe

Przeszukiwanie z iteracyjnym pogłębianiem

Przeszukiwanie z iteracyjnym pogłębianiem

Idea: iteracyjnie zwiększaj głębokość drzewa,

Idea: iteracyjnie zwiększaj głębokość drzewa,

rozpoczynając od d=1

rozpoczynając od d=1

Przeszukiwanie z iteracyjnym pogłębianiem

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

0
1
2

0 1

2

d=1

21

20

10

d=2

21

20

10

21

20

10

21

20

10

d=3

21

20

10

21

20

10

21

20

10

Iteracyjne pogłębianie -

przykład

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Złożoność czasowa

Duża - dodatkowe zwiększenie czasu poszukiwań za sprawą

wielokrotnej ekspansji tych samych węzłów (nie jest to jednak

krytyczne, bo większość węzłów jest na najniższym poziomie)

Iteracyjne pogłębianie -

właściwości

Optymalność

Strategia jest optymalna

Kompletność

Strategia jest kompletna

Zasoby

Małe

Wprowadzenie do zagadnień sztucznej inteligencji

Krzysztof Ślot

© 1999- 2001

Wybrane aplikacje metod przeszukiwania

przestrzeni stanów

Rozpoznawanie wypowiedzi

Założenia

Wypowiedzi są łańcuchami fonemów
Wypowiedzi zawierają dowolne ilości fonemów

Drzewo poszukiwań określone dla problemu

a

al

as

...

ala

ale

alt

…

alek

z

za

...