Temat: Algorytm heurystyczne (sid, temat 3) - zadania (fwd)


[trzeba] Mamy plansze podzielona na kwadraty. Czesc pol jest niedostepna
(znajduja sie tam dziury. Funkcja heurystyczna h1 okreslona
w nastepujacy sposob:
- najmniejsza ilosc pol pomiedzy polem docelowym i obecnym.
Funkcja heurystyczna h2 okreslona w nastepujacy sposob:
- jezeli punkt obecny i docelowy znajduja sie w tej samej linii poziomej
  lub pionowej, to jezeli pomiedzy nimi znajduje sie dziura, to do liczby
  pol pomiedzy nimi dodajemy 2,
- jezeli punkt obecny i docelowy nie znajduja sie w tej samej linii,
  to jako wartosc funkcji przyjmujemy najmniejsza liczbe pol pomiedzy nimi.

-------------
| | | | | | |
-------------
| | |w| | | |
-------------
| | |s| |x|d|
-------------
| | | | | | |
-------------

x - dziura
s, w - stany rozpatrywane
d - stan docelowy

h1(s) = 3
h2(s) = 5
h1(w) = 4
h2(w) = 4

Polecenie:
zasymuluj dzialanie algorytmu A* wykorzystujac funkcje heurystyczna
h1 oraz h2 przyjmujac za stan pocztkowy s. Jakie beda roznice w przypadku
uzycia tych funkcji heurystycznych

[trzeba] Dla ukladanki w 8 puzzli zaprezentowac dzialanie algorytmu
rekurencyjnego przeszukiwania pierwszy najlepszy. Moze dobrym pomyslem
jest zastartowac od stanu prowadzacego do rozwiazania w miare szybko np:
123
468
75 
lub od stanu gdzies ze srodka ukladanki np:
 83
142
675


[mozna] Pokazac, ze jezeli heurystyka jest spojna, to jest dopuszczalna.
(wsk) indukcja po "dlugosci" sciezki dla h*.

[mozna] Jezeli heurystyka h1 nie dominuje heurystyki h2, ani odwrotnie,
to jaka heurystyke oplaca sie uzyc w algorytmie A*?

[mozna] Mamy dany graf. Chcemy znalesc wezel o najwiekszej liczbie sasiadow.
Funkcja sasiedztwa (dla algorytmow przeszukujacych) dla danego wierzcholka
to zbior wierzcholkow polaczonych z danym krawedzia. Zastosowac, albo moze
zobrazowac, ze startujac od wierzcholka startowego (Vs) metoda hill-climing
nie doprowadzi Nas do globalnego maximum, natomiast symulowane wyzarzanie
daje nam taka mozliwosc. Graf:

		Vs
		|
		V1  v9	 v10
		|     \	/
		V2-v7-v8-v11
		|	\
		v3	 v12
	      / | \
	     v4 v5 v6

algorytm hc zakonczy dzialanie w v3
algorytm sw moze zakonczyc w v8.

[mozna] Czy w algorytmach genetycznych mozna zastapic krzyzowanie mutacjami?
Chodzi o to, czy mozemy bez uszczerbku dla dzialania algorytmu zrezygnowac
z kroku w ktorym odbywa sie krzyzowanie. (odp. tak)
Czy w algorytmach genetycznych mozna zastapic mutacje krzyzowaniami?
(odp nie) Warto wyciagnac od studentow, co jest tego przyczyna. Jezeli
wsrod osobnikow brakuje pewnego genu, to jedynie mutacja jest w stanie go 
wprowadzic.

Pozdrawiam,
Michal Przybylski.