Wieże Hanoi, ale o dowolnej konfiguracji początkowej i końcowej

Ostatnio natknąłem się na ten problem , odmianę wież hanoi .

Opis problemu:

Rozważ następującą odmianę dobrze znanego problemu Wieże Hanoi:

Dostajemy wież i m dysków o rozmiarach 1 , 2 , 3 , … , m ułożonych na niektórych wieżach. Twoim celem jest przeniesienie wszystkich dysków do k- tej wieży w jak najmniejszej liczbie ruchów, jak możesz, ale z uwzględnieniem następujących zasad:$n$$1,2,3,\dots,m$$k^{\text{th}}$

• przenoszenie tylko jednego dysku na raz,
• nigdy nie przenosząc większego dysku na mniejszy,
• poruszanie się tylko między wieżami w odległości co najwyżej .$d$

(Granice pierwotnego problemu: i m ≤ 100. Liczba przypadków testowych ≤ 1000. Możesz założyć, że wszystkie problemy można rozwiązać w nie więcej niż 20000 ruchów.)$3 \le n \le 1000$$m \le 100$$\le 1000$$20000$

To interesujące. Klasyczne wieże problemu hanoi mają jedno źródło, miejsce docelowe i tymczasową wieżę, która służy do przenoszenia dysków ze źródła do miejsca docelowego. Problem postawiony na tej stronie ma w zasadzie początkową i końcową konfigurację.

Jak podejść do tego problemu?

Najbardziej udanym podejściem do radzenia sobie z oryginalną wersją Towers of Hanoi jest użycie wzorcowych baz danych (PDB). Obecny stan wiedzy opisano w „ Najnowsze postępy w poszukiwaniach heurystycznych: studium przypadku problemu czterech wież Hanoi ”

$t$

$d$

Nie widzę żadnego powodu, by zmieniać typowe podejście ze względu na to szczególne ograniczenie.

Mam nadzieję że to pomoże,