To tylko jedna z 18 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
•
•
•
•
Struktury i strategie przeszukiwania stanów
Przeszukiwanie heurystyczne
Metody stochastyczne
Sterowanie i implementacje przeszukiwania stanów
Podejścia do
przeszukiwania
stanów
Ślepe
Metodyczne
Analityczne
Heurystyczne
Stochastyczne
Systematyczne
(B-FS, D-FS)
Zalety i wady podejścia metodycznego
2. Przeszukiwanie heurystyczne – istota
Archimedes – „eureka”
Heurystyka – studiowanie metod i reguł
odkrywania i wynalazczości (G. Polya)
Heurystyka – reguły wyboru gałęzi w przeszukiwaniu
przestrzeni stanów „najbardziej prowadzących” do
akceptowalnego rozwiązania problemu.
Własności heurystyki:
-odkrywanie i tworzenie nowych rzeczy i zjawisk
- kreatywne rozwiązywanie problemów
- wykrywanie powiązań między faktami
- dochodzenie do prawdy, tworzenie hipotez
- brak gwarancji uzyskania najlepszego rozwiązania
2. Przeszukiwanie heurystyczne zastosowania
Wykorzystanie heurystyki w rozwiązywaniu
problemów:
• nie ma jednoznacznego (dokładnego) rozwiązania;
słabo zdefiniowany problem, brak danych (np.
diagnozowanie najbardziej prawdopodobnej przyczyny,
wizualizacja zdarzeń),
• problem ma jednoznaczne rozwiązanie ale
wymagające dużej pracochłonności w jego osiągnięciu
(np. gra w szachy, szukanie połączeń)
2. Przeszukiwanie heurystyczne - przykład
X
X
X
X O
X
O
X
X
X
O
O
O
O
O
X
X
O X
X
X
X
X
O
O
O
O
Redukcja przestrzeni przeszukiwania przez symetrie
2. Przeszukiwanie heurystyczne - przykład
X
X
Różne możliwości zwycięstwa przy
określonym otwarciu
X
2. Przeszukiwanie heurystyczne - przykład
X
X
X
3
2
4
O
O
X
O
X
O
X
O
X
X
3
X
O
X
X
X
4
4
X
5
X
O
O
X
O
X X
X
X
O
X
X
5
4
4
4
Redukcja heurystyczna przestrzeni
przeszukiwania
2. Przeszukiwanie heurystyczne
– procedura hill-climbing (H-C)
Procedura H-C: rozwijany jest bieżący stan i oceniane
są otrzymane rezultaty (szukanie najbardziej
korzystnego ); ryzyko uznania lokalnego maksimum jako
osiągniętego celu
function Hill-Climbing (problem) returns a solution state
inputs : problem
// a problem.
local variables : current // a node.
next
// a node.
current Make-Node ( Initial-State [ problem ]) // make random
loop do
// initial state.
next a highest-valued successor of current
if Value [next]
(…)
… 3
2
3
5 4 3 2 3
2. Przeszukiwanie heurystyczne
– dynamiczne programowanie (DP)
Programowanie dynamiczne (forward-backward):
utrzymuje stany dotyczące rozwiązań lokalnych problemów do
wykorzystania przy rozwiązaniu problemów wyższego rzędu
Przykłady szukania:
• najmniejszych różnic pomiędzy dwoma ciągami znaków
• najlepszej sekwencji znaków dotyczących wskazanych
łańcuchów
- a b c d e f
g h
-
0
1
2…
…
9
10
9
8
9
10
o
8
9
10
9
10
11
10
9
8
9
n
9
10
11
10
11
12
11
10
9
8
function dynamic (source, sl, target, tl)return cost(i,j);
create array cost(sl+1, tl+1)
cost (0,0) :=0
%initialize
for i:=1 to sl+1 do
for j:= 1 to tl +1 do
cost(i,j) :=min[cost(i-1,j) + insertion cost targeti-1
% add1
cost(i-1,j-1) + replace cost sourcej-1 targeti-1
% add2
cost(i,j-1) + delete cost sourcej-1
% add1
2…
... zobacz całą notatkę
Komentarze użytkowników (0)