poniedziałek, sierpnia 15, 2011

Przyśpieszanie backtrackingu

Taka obserwacja sprzed chwili :-)
Gdy masz jakiś backtracking, który bazuje na jakiejś heurystyce, która wybiera najlepszych wg. niej kandydatów i nie wiesz czy ma ona sens spróbuj zastąpić tą heurystykę lub jej fragment losowaniem.
Jeśli to przyśpieszy wykonanie na tych samych danych i jeśli większość wyników jest osiągana szybciej z włączoną losowością to może być dobry znak, że jest jakaś lepsza heurystyka, a ta używana jest do bani ;-)
Może to też znaczyć, że trzeba zmienić podejście ;-)

Właśnie się o tym przekonuję w mojej rozwiązywarce Sudoku.
Do teraz działała tak, że wybierała jako kandydata (czyli pole, które będzie wypełniane) do rozpatrywania pierwsze pole dla którego była najmniejsza ilość możliwości.
Rozwiązanie działało nieźle, ale wiem, że są lepsze ;-)
Kolejne podejście działa tak, że zamiast pierwszego z najmniejszą ilością możliwości wybieram tego, który ma najmniejszą ilość możliwych "prób" (ma ją ten kandydat, w którym suma dotychczasowych użyć dopuszczalnych liczb jest największa... o i chyba widzę gdzie jest problem ;-)).
Działa to lepiej, ale nadal nie najlepiej.
Dlatego zastąpiłem to wybieranie najbardziej obiecującego kandydata z listy tych z minimalną listą możliwości przez losowanie jednego z nich.
Okazuje się, że zwykle takie coś działa lepiej ;-) Co by znaczyło, że moja heurystyka jest do bani ;-)

W końcu skoro losowanie radzi sobie lepiej to zapewne istnieje przewidywalny sposób lepszego wybierania kandydatów ;-)


Podobne postybeta
Sudoku - przyśpieszamy, ale jeszcze nie za bardzo ;-)
Heurystyka dostępności a strach przed imigrantami
Sudoku - atak pierwszy ;-)
Losowanie dobre
A gdyby tak...