java - 汉诺塔问题——线性规划

Question

我正在做一项关于使用线性规划规划汉诺塔问题的作业，我不允许使用任何递归函数。问题是我的解决方案不像递归方法那样是最优的。它会产生冗余步骤。例如:

我有 3 个杆子，分别命名为 A、B、C，还有 2 个圆盘，分别命名为 1、2(圆盘 1 比圆盘 2 小，圆盘 1 在圆盘 2 上)，那么有 2 种方法可以移动所有圆盘从杆 A 到杆 C 使用杆 B 作为中间杆如下:

1. (像递归算法的输出一样最优)
   • 将圆盘 1 移动到杆 B
   • 将圆盘 2 移动到杆 C
   • 将圆盘 1 移动到杆 C
2. (非最优使用规划)
   • 将圆盘 1 移动到杆 C
   • 将圆盘 2 移动到杆 B
   • 将圆盘 1 移动到杆 A
   • 将圆盘 2 移动到杆 C
   • 将圆盘 1 移动到杆 C

那么我如何(更准确地说:一种可编程的算法)知道磁盘 1 必须先移动到杆 B 而不是移动到磁盘 C 以获得最优解？非常感谢你的帮助。谢谢!

Answer 1

我想想象一下棘轮怪胎的答案。

尺寸 5 的示例

6号示例

较大尺寸的工作方式相同。

其他详细信息

• 任务是写Hamilton path算法实现。
• 有 3 根杆{initial, spare, destination}。您的开始行动取决于 2 的提醒:
  • 如果 n % 2 == 0，从备用杆开始
  • 如果 n % 2 == 1，从目标杆开始
• 需要 2^n-1 步，才能将整个堆栈移动到目标堆栈。