Potrzebuję pomocy w znalezieniu dobrej heurystyki dla następującego problemu:

OtrzymujeszR-przez-C siatka i sześcioboczna kostka. Pozwolićstart iend być dwiema odrębnymi komórkami na tej siatce. Znajdź drogę odstart doend tak, że suma powierzchni matrycy patrzących w górę, gdy kostka obraca się wzdłuż ścieżki, jest minimalna.

Początkowa orientacja kości jest następująca („2” jest skierowane na południe):

Sposób, w jaki modelowałem ten problem, polega na uwzględnieniu wartości powierzchni kości jako kosztu krawędzi na wykresie. Wierzchołki wykresu mają postać(row, col, die) (tj. pozycja w siatce i aktualny stan / orientacja matrycy). Powód, dla którego wierzchołek nie jest prosty(row, col) jest tak, ponieważ możesz skończyć na tej samej komórce z wieloma konfiguracjami / orientacjami kości.

Użyłem A *, aby znaleźć rozwiązanie problemu; podane odpowiedzi są poprawne, ale nie są wystarczająco skuteczne. Ustaliłem, że problemem jest heurystyka, której używam. Obecnie używam odległości na Manhattanie, co jest oczywiście dopuszczalne. Jeśli mnożę heurystykę ze stałą, nie jest to już dopuszczalne: działa znacznie szybciej, ale nie zawsze znajduje właściwą odpowiedź.

Potrzebuję pomocy w znalezieniu lepszej odległości heurystycznej niż na Manhattanie.