Widzieliśmy, że zarówno h1 (niewłaściwie umieszczone kafelki), jak i h2 (odległość Manhattanu) są całkiem dobrą heurystyką dla 8-puzzli i że h2 jest lepsze. Jak można wymyślić h2? Czy komputer może wymyślić taką heurystykę mechanicznie? h1 i h2 są szacunkowymi pozostałymi długościami ścieżki dla 8-puzzli, ale są również idealnie dokładnymi długościami ścieżek dla uproszczonych wersji układanki. Gdyby zasady łamigłówki zostały zmienione tak, aby płytka mogła się przesunąć w dowolne miejsce, a nie tylko do sąsiedniego pustego pola, to h1 dałoby dokładną długość najkrótszego rozwiązania. Podobnie, gdyby płytka mogła przesunąć się o jedno pole w dowolnym kierunku, nawet na zajęte pole, to h2 dałoby dokładną długość najkrótszego rozwiązania. Problem z mniejszymi ograniczeniami w działaniach nazywany jest zrelaksowanym problemem. Graf w przestrzeni stanów rozluźnionego problemu jest supergrafem oryginalnej przestrzeni stanów, ponieważ usunięcie ograniczeń tworzy dodatkowe krawędzie w grafie.
Ponieważ zrelaksowany problem dodaje krawędzie do grafu w przestrzeni stanów, każde optymalne rozwiązanie w pierwotnym problemie jest z definicji również rozwiązaniem w zrelaksowanym problemie; ale rozluźniony problem może mieć lepsze rozwiązania, jeśli dodane krawędzie zapewniają skróty. Stąd koszt optymalnego rozwiązania rozluźnionego problemu jest dopuszczalną heurystyką dla pierwotnego problemu. Ponadto, ponieważ pochodna heurystyka jest dokładnym kosztem rozwiązania problemu rozluźnionego, musi być zgodna z nierównością trójkąta i dlatego jest spójna . Jeśli definicja problemu jest napisana w języku formalnym, możliwe jest automatyczne konstruowanie zrelaksowanych problemów. Na przykład, jeśli akcje 8-puzzli są opisane jako
Płytka może przesunąć się z kwadratu X na kwadrat Y, jeśli
X sąsiaduje z Y, a Y jest puste,
możemy wygenerować trzy rozluźnione problemy, usuwając jeden lub oba warunki:
- Płytka może przesunąć się z pola X na pole Y, jeśli X sąsiaduje z Y.
- Płytka może przesunąć się z pola X do pola Y, jeśli Y jest puste.
- Płytka może przesunąć się z pola X do pola Y.
Z (a) możemy wyprowadzić h2 (odległość Manhattanu). Rozumowanie jest takie, że h2 byłoby właściwym wynikiem, gdybyśmy przesunęli po kolei każdą płytkę do miejsca przeznaczenia. Z (c) możemy wyprowadzić h1 (niewłaściwie umieszczone płytki), ponieważ byłby to właściwy wynik, gdyby płytki mogły przemieścić się do zamierzonego miejsca w jednej akcji. Zauważ, że bardzo ważne jest, aby rozluźnione problemy generowane przez tę technikę można było rozwiązać zasadniczo bez wyszukiwania, ponieważ rozluźnione reguły pozwalają rozłożyć problem na osiem niezależnych podproblemów. Jeśli zrelaksowany problem jest trudny do rozwiązania, wtedy uzyskanie wartości odpowiedniej heurystyki będzie kosztowne. Program o nazwie ABSOLVER może automatycznie generować heurystyki z definicji problemów, używając metody „rozluźnionego problemu” i różnych innych technik. ABSOLVER wygenerował nową heurystykę dla 8-zagadek, która była lepsza niż jakakolwiek wcześniejsza heurystyka i znalazł pierwszą przydatną heurystykę dla słynnej układanki z kostką Rubika. Jeśli dla problemu dostępny jest zbiór dopuszczalnych heurystyk h1…hm i żadna z nich nie jest wyraźnie lepsza od pozostałych, co powinniśmy wybrać? Jak się okazuje, możemy mieć to, co najlepsze ze wszystkich światów, definiując
h(n) = max{h1(n),…, hk(n)}
Ta złożona heurystyka wybiera tę funkcję, która jest najdokładniejsza w danym węźle. Ponieważ składniki hi są dopuszczalne, jest dopuszczalne (a jeśli wszystkie hi są spójne, to h jest zgodne). Co więcej, h dominuje nad wszystkimi heurystykami składowymi. Jedyną wadą jest h(n), której obliczenie zajmuje więcej czasu. Jeśli jest to problem, alternatywą jest losowy wybór jednej z heurystyk przy każdej ocenie lub użycie algorytmu uczenia maszynowego, aby przewidzieć, która heurystyka będzie najlepsza. Takie postępowanie może skutkować niespójną heurystyką (nawet jeśli każde hi jest spójne), ale w praktyce zwykle prowadzi to do szybszego rozwiązywania problemów.