河内塔问题 - 线性计划

Question

我正在做一个关于使用线性规划来规划河内塔问题的任务,我不允许使用任何递归函数.问题是我的解决方案不像递归方法那样最优.它产生冗余步骤.例如:

我有3个分别命名为A,B,C的棒,有2个名为1,2的磁盘(磁盘1小于磁盘2,磁盘1在磁盘2上),然后有2种方法可以从杆A移动所有磁盘使用杆B作为中间杆的杆C如下:

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路径算法实现.
• 有3根棒{initial, spare, destination}.你的开始动作取决于2的提醒:
  • if n % 2 == 0,从备用杆开始
  • if n % 2 == 1,从目标杆开始
• 它需要2 ^ n-1次移动才能将整个堆栈移动到目标堆栈.

Answer 2

关键是要知道需要移动多少磁盘：

如果堆栈中有偶数个磁盘，则从“备用”杆开始
如果堆栈中有奇数个磁盘，则从“目标”杆开始