POJ 3134 Power Calculus：冪運算最少步數 IDA* 搜索

問題描述

從 x 出發，通過乘法/除法運算已得到的冪次，求得到 x^n 的最少運算次數。運算中間結果必須為正整數冪次（不允許負指數）。n ≤ 1000。

為什麼不用 BFS？

BFS 狀態需包含「已得到的冪次集合」，狀態空間極大且難以去重。DFS 更自然：每一步從現有集合中選兩個數相加（乘法）或相減（除法），生成新冪次加入集合。

IDA* (Iterative Deepening A*) 算法

1. 設置深度限制 maxDepth 從 0 開始遞增
2. 深度優先搜索，當前深度 d，已得最大冪次 curMax
3. 剪枝 1：若 curMax * 2^(maxDepth-d) < n，即使剩餘步驟全做平方也達不到 n，剪枝
4. 剪枝 2：生成的新冪次 ≤ 0 或 ≥ 2000（經驗上界）直接跳過
5. 找到 n 返回成功，否則增加 maxDepth 繼續

完整代碼

#include 
using namespace std;

int n, maxDepth;
int powList[20]; // 當前路徑上得到的冪次
bool found;

void dfs(int depth) {
    if (found) return;
    if (depth > maxDepth) return;
    int curMax = powList[depth];
    // 剪枝：剩餘步驟全平方也達不到 n
    if (curMax << (maxDepth - depth) < n) return;
    if (curMax == n) { found = true; return; }
    
    // 嘗試與所有已有冪次組合（為避免重複，只組合 depth 及之前）
    for (int i = 0; i <= depth; ++i) {
        // 乘法：相加指數
        int nxt = curMax + powList[i];
        if (nxt > 0 && nxt < 2000) {
            powList[depth+1] = nxt;
            dfs(depth+1);
            if (found) return;
        }
        // 除法：相減指數（取絕對值，因為 x^a / x^b = x^|a-b|）
        nxt = abs(curMax - powList[i]);
        if (nxt > 0 && nxt < 2000) {
            powList[depth+1] = nxt;
            dfs(depth+1);
            if (found) return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n, n) {
        if (n == 1) { cout << 0 << '\n'; continue; }
        maxDepth = 0;
        while (true) {
            found = false;
            powList[0] = 1;
            dfs(0);
            if (found) break;
            ++maxDepth;
        }
        cout << maxDepth << '\n';
    }
    return 0;
}

關鍵優化解析

• curMax << (maxDepth-depth) 利用位移快速計算 curMax * 2^k，極其高效
• 只與當前路徑上的冪次組合（i <= depth），避免重複組合
• 除法取絕對值，因為 x^a / x^b = x^|a-b|（題目要求正指數）
• 上界 2000 經驗值，n≤1000 時足夠

樣例驗證

n=31: maxDepth=6 (x^2, x^4, x^8, x^16, x^32, x^31)
n=70: maxDepth=8
n=512: maxDepth=9 (全平方: 2,4,8,16,32,64,128,256,512)

總結

POJ 3134 是 IDA* 經典應用。關鍵在於：將「已有冪次集合」簡化為「路徑上最大冪次」進行剪枝估價，利用「剩餘步驟全平方」作為樂觀下界。此技巧將指數級搜索空間大幅剪枝，在 n≤1000 限制內極快求解。掌握 IDA* 模板（迭代加深 + 啟發式剪枝）可解決大量最短路徑/最少步數搜索問題。