四柱汉诺塔 -- 动态规划求解最优移动次数

Love The Way You Lie 2022-04-11 04:46 270阅读 0赞

自己用Java写了一个前台进行四柱汉诺塔的移动演示，是按照最优次序进行移动的，链接里有详细的代码实现：[https://download.csdn.net/download/qq\_40285036/10841684][https_download.csdn.net_download_qq_40285036_10841684]

## 1.问题描述 ##

四柱汉诺塔，在A柱上有N个盘子，**最少**经过多少次移动能把盘子全部移动到D上？

![四柱汉诺塔][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70]

## 2.问题分析 ##

1.  先来回顾一下三柱汉诺塔，对于三柱汉诺塔问题，他的移动次数是固定的，若有N个盘子，那么移动次数就是2^N - 1。
2.  四柱汉诺塔多了一柱，所以移动次序变为  
    （1）先把k个盘子，从A柱经过C，D移动到B上。  
    （2）再把A柱上的N-K个盘子，经过C，移动到D上（这个子问题就是三柱汉诺塔问题，他的移动次数为2^(n-k) - 1。）  
    （3）再把k个盘子，从B柱上经过A，C移动到D上。  
    3.从刚才的分析不难看出，我们起初先向B柱上移动的K个盘子决定了我最终的移动次数，所以目标是找到一个最优解K，使我最终的移动次数最小。

## 3.最优子结构 ##

令dp\[ n \]表示有n个盘子时的最优值，从2的分析中可以看出  
（1）先把k个盘子，从A柱经过C，D移动到B上。**–>移动次数为 dp\[ k \]**  
（2）再把A柱上的N-K个盘子，经过C，移动到D上（这个子问题就是三柱汉诺塔问题，他的移动次数为2^(n-k) - 1。）**–>移动次数为 2^(n-k) - 1**  
（3）再把k个盘子，从B柱上经过A，C移动到D上。 **–> 移动次数为dp\[ k \]**

那么： dp\[ n \] = 2 \* dp\[ k \] + 2^(n-k) - 1  
枚举K值求最优，**则最优子结构为：dp\[ n \] = min(2 \* dp\[ k \] + 2 ^ (n - k) - 1), k = 1 … n  
初始化 : dp\[1\] = 1(只有一个盘子，只需要一次移动)；dp\[2\] = 3（两个盘子至少要移动三次）**

## 4.代码 ##

#include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    
    using namespace std;
    
    #define N 100
    #define INF 0x3f3f3f3f
    
    typedef long long ll;
    ll dp[N];
    int optimalPath[N];
    
    void TraceBack(vector<int> &path,int n)
    {
        
    	if (optimalPath[n] == n)
    	{
        
    		path.push_back(n);
    		return;
    	}
    	path.push_back(optimalPath[n]);
    	TraceBack(path, optimalPath[n]);
    	
    }
    
    
    int main()
    {
        
    	int n;
    	while (cin >> n, n)
    	{
        
    		for (int i = 1; i <= n; i++)
    			dp[i] = INF;
    		dp[1] = 1;
    		dp[2] = 3;
    
    		for (int i = 3; i <= n; i++)
    		{
        
    			for (int k = 1; k <= i; k++)
    			{
        
    				ll tmp = 2 * dp[i - k] + (ll)pow(2, k) - 1;
    				if (dp[i] > tmp)
    				{
        
    					dp[i] = tmp;
    					optimalPath[i] = k;
    				}
    			}
    		}
    		cout << "最优移动次数为: " << dp[n] << endl;
    		vector<int> path;
    		TraceBack(path, n);
    		cout << "optimal path:" << endl;
    		for (int i : path)
    		{
        
    			cout << i << " ";
    		}
    		cout << endl;
    	}
    }

[https_download.csdn.net_download_qq_40285036_10841684]: https://download.csdn.net/download/qq_40285036/10841684
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjg1MDM2_size_16_color_FFFFFF_t_70]: /images/20220411/e60722ddb95647fa995b55a57ddf640c.png