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 posty^beta
"Czy uważasz, że powinien zarabiać tyle co Ty?" ;-)
Sudoku - przyśpieszamy, ale jeszcze nie za bardzo ;-)
Sudoku - atak pierwszy ;-)
Heurystyka dostępności a strach przed imigrantami
A gdyby tak...