Widzieliśmy, że jednym ze sposobów wymyślenia heurystyki jest wymyślenie zrelaksowanego problemu, dla którego można łatwo znaleźć optymalne rozwiązanie. Alternatywą jest uczenie się na doświadczeniu. „Doświadczenie” oznacza tutaj na przykład rozwiązywanie wielu 8-zagadek. Każde optymalne rozwiązanie.
Zadanie 8-zagadkowe dostarcza przykładowej pary (cel, ścieżka). Na podstawie tych przykładów algorytm uczenia może być użyty do skonstruowania funkcji, która może (przy odrobinie szczęścia) przybliżyć rzeczywisty koszt ścieżki dla innych stanów, które pojawiają się podczas wyszukiwania. Większość z tych podejść uczy się niedoskonałego przybliżenia funkcji heurystycznej, a tym samym ryzykuje niedopuszczalność. Prowadzi to do nieuniknionego kompromisu między czasem nauki, czasem wykonywania wyszukiwania i kosztem rozwiązania. Techniki uczenia maszynowego przedstawiono w rozdziale 19 . Metody uczenia się przez wzmacnianie opisane w rozdziale 22 mają również zastosowanie do wyszukiwania. Niektóre techniki uczenia maszynowego działają lepiej, gdy są dostarczane z funkcjami stanu, które są istotne dla przewidywania wartości heurystycznej stanu, a nie tylko z surowym opisem stanu. Na przykład funkcja „liczba niewłaściwie umieszczonych kafelków” może być pomocna w przewidywaniu rzeczywistej odległości stanu 8-puzzli od celu. Nazwijmy tę funkcję x1(n).
Moglibyśmy wziąć 100 losowo wygenerowanych 8-zagadkowych konfiguracji i zebrać statystyki dotyczące ich rzeczywistych kosztów rozwiązania. Możemy stwierdzić, że gdy x1(n) wynosi 5, średni koszt rozwiązania wynosi około 14 i tak dalej. Oczywiście możemy korzystać z wielu funkcji. Drugą cechą x2(n) może być „liczba par sąsiednich płytek, które nie sąsiadują ze sobą w stanie docelowym”. Jak należy połączyć x1(n) i x2(n), aby przewidzieć h(n)? Powszechnym podejściem jest użycie kombinacji liniowej:
Stałe c1 i c2 są dostosowywane, aby zapewnić najlepsze dopasowanie do rzeczywistych danych w losowo generowanych konfiguracjach. Oczekuje się, że zarówno c1 jak i c2 będą dodatnie, ponieważ źle ułożone płytki i nieprawidłowe sąsiednie pary utrudniają rozwiązanie problemu. Zauważ, że ta heurystyka spełnia warunek h(n) = 0 dla stanów celu, ale niekoniecznie jest to dopuszczalne lub spójne.