Türme von Hanoi, jedoch mit willkürlicher Anfangs- und Endkonfiguration

Kürzlich bin ich auf dieses Problem gestoßen , eine Variation von Türmen von Hanoi .

Problemstellung:

Betrachten Sie die folgende Variation des bekannten Problems Towers of Hanoi:

Wir erhalten Türme und m Scheiben der Größen 1 , 2 , 3 , … , m, die auf einigen Türmen gestapelt sind. Ihr Ziel ist es, alle Festplatten in so wenigen Zügen wie möglich auf den k- ten Turm zu übertragen , wobei jedoch die folgenden Regeln zu beachten sind:$n$$1,2,3,\dots,m$$k^{\text{th}}$

• jeweils nur eine Festplatte verschieben,
• Verschieben Sie niemals eine größere Festplatte auf eine kleinere.
• Bewegen nur zwischen Türmen in der Ferne höchstens .$d$

(Grenzen im ursprünglichen Problem: und m ≤ 100. Anzahl der Testfälle ≤ 1000. Sie können davon ausgehen, dass alle Probleme in nicht mehr als 20000 Zügen gelöst werden können .)$3 \le n \le 1000$$m \le 100$$\le 1000$$20000$

Es ist interessant. Die klassischen Türme des Hanoi-Problems haben eine Quelle, ein Ziel und einen temporären Turm, mit denen die Festplatten von der Quelle zum Ziel bewegt werden. Das Problem auf dieser Site hat im Grunde eine anfängliche und endgültige Konfiguration.

Wie geht man dieses Problem an?

Der erfolgreichste Ansatz, um mit der Originalversion der Towers of Hanoi umzugehen, ist die Verwendung von Pattern Databases (PDBs). Der aktuelle Stand der Technik ist in " Jüngste Fortschritte bei der heuristischen Suche: Eine Fallstudie der Vier-Peg-Türme des Hanoi-Problems " beschrieben.

$t$

$d$

Ich sehe in der Tat keinen Grund, den typischen Ansatz nur angesichts dieser besonderen Einschränkung zu ändern.

Hoffe das hilft,