bartekltg <b...@g...com> napisał(a):

> Wracajac do pytanie, sokoban jest NP-trudny, wiec dobrze bysmy
> sie zastanowili, co tak naprawde chcemy.

Co chcemy? Spędzić kilka miłych chwil przy pogawędce o sokobanie.

Moje przemyślenia:

1) Najpierw siłowe przeszukiwanie grafu w szerz - złożoność to brench faktor
do potęgi depth.
2) Później drobne usprawnienie - odrzucamy pola-pułapki z których nie
da się dotrzeć do celu.
3) Kolejny krok, to spamiętywanie węzłów przeszukanych w przeszłości -
dzięki temu algorytm nie będzie chodził w kółko. Złożoność obliczeniowa
spadnie do (n nad k), ale złożoność pamięciowa wzrośnie do n nad k.
4) Gdy pamięci zabraknie, dobra heurystyka do wyboru które węzły
trzymać zapamiętane a które nadpisać nowymi.
5) Dobra heurystyka które węzły odrzucić bez przeszukiwania
6) Gdy z powodu rozmiaru nie ma szans na rozwiązanie optymalne albo
bliskie optymalnemu, to dwa algorytmy:
a) pierwszy generuje dowolne rozwiązanie
b) drugi im pracuje dłużej, tym ma większe szanse na poprawienie
rozwiązania

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/