最小步數模型

定義

最小步數模型通常是指在某種約束條件下，尋找從初始狀態到目標狀態所需的最少操作或移動次數的問題。這類問題廣泛存在于算法、圖論、動態規劃、組合優化等領域。具體來說，它涉及確定一個序列或路徑，使得按照特定規則執行一系列步驟后，能夠從起始位置或狀態轉換到目標位置或狀態，且所花費的步驟盡可能少。

運用情況

1. 圖的最短路徑問題：如Dijkstra算法、Floyd-Warshall算法等，用于尋找兩點間經過邊的最小權重和，即最少步數。
2. 迷宮問題：尋找從起點到終點的最短路徑，每步只能上下左右移動。
3. 跳臺階問題：一個人可以1步或2步上樓梯，求n階樓梯有多少種不同的上法，也是求最小步數的一個變體。
4. 爬樓梯問題：每次可以爬1階或2階，求達到n階樓梯的最少步數，考慮動態規劃解法。
5. 狀態轉換問題：如編輯距離（將一個字符串轉換為另一個字符串最少的插入、刪除、替換操作次數）。

注意事項

1. 狀態定義：明確問題中的狀態如何表示，狀態轉移方程如何建立，這是解決問題的基礎。
2. 邊界條件：正確設定初始狀態和目標狀態，以及任何可能的限制條件，避免無限循環或錯誤解。
3. 避免重復計算：在動態規劃等方法中，使用記憶化技術或遞推公式減少重復子問題的計算。
4. 最優子結構：利用問題的最優子結構，即問題的最優解可以由其子問題的最優解組合得到。
5. 復雜度控制：考慮算法的時間和空間復雜度，選擇合適的算法和數據結構以提高效率。

解題思路

1. 分析問題：明確問題的輸入、輸出及約束條件，識別問題的類型（如是否為最短路徑、最優化問題等）。
2. 選擇模型：根據問題特征選擇合適的算法模型，如貪心、動態規劃、圖算法等。
3. 狀態定義與轉移：定義狀態表示問題的某一階段，構建狀態轉移方程，描述如何從一個狀態轉移到另一個狀態。
4. 設計算法：依據狀態轉移方程設計算法，可能是遞歸、迭代、圖的遍歷等。
5. 實現與優化：編寫代碼實現算法，考慮邊界條件和特殊情況處理，優化算法以降低時間和空間復雜度。
6. 驗證與測試：通過測試用例驗證算法的正確性，確保能正確處理各種邊界條件和特殊情況。

AcWing 1107. 魔板

題目描述

AcWing 1107. 魔板 - AcWing

運行代碼

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>using namespace std;char g[2][4];
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;void set(string state)
{for (int i = 0; i < 4; i ++ ) g[0][i] = state[i];for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i];
}string get()
{string res;for (int i = 0; i < 4; i ++ ) res += g[0][i];for (int i = 3; i >= 0; i -- ) res += g[1][i];return res;
}string move0(string state)
{set(state);for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]);return get();
}string move1(string state)
{set(state);int v0 = g[0][3], v1 = g[1][3];for (int i = 3; i > 0; i -- ){g[0][i] = g[0][i - 1];g[1][i] = g[1][i - 1];}g[0][0] = v0, g[1][0] = v1;return get();
}string move2(string state)
{set(state);int v = g[0][1];g[0][1] = g[1][1];g[1][1] = g[1][2];g[1][2] = g[0][2];g[0][2] = v;return get();
}int bfs(string start, string end)
{if (start == end) return 0;queue<string> q;q.push(start);dist[start] = 0;while (!q.empty()){auto t = q.front();q.pop();string m[3];m[0] = move0(t);m[1] = move1(t);m[2] = move2(t);for (int i = 0; i < 3; i ++ )if (!dist.count(m[i])){dist[m[i]] = dist[t] + 1;pre[m[i]] = {'A' + i, t};q.push(m[i]);if (m[i] == end) return dist[end];}}return -1;
}int main()
{int x;string start, end;for (int i = 0; i < 8; i ++ ){cin >> x;end += char(x + '0');}for (int i = 1; i <= 8; i ++ ) start += char('0' + i);int step = bfs(start, end);cout << step << endl;string res;while (end != start){res += pre[end].first;end = pre[end].second;}reverse(res.begin(), res.end());if (step > 0) cout << res << endl;return 0;
}

代碼思路

1. 狀態表示：用一個長度為8的字符串表示矩陣的狀態，前四位表示第一行，后四位逆序表示第二行。
2. 狀態轉換：定義了三種狀態轉換函數move0、move1和move2，分別對應三種操作。
3. 廣度優先搜索：使用BFS從初始狀態開始搜索，利用一個隊列來存儲待探索的狀態，一個哈希表dist記錄每個狀態到初始狀態的最小步數，另一個哈希表pre記錄每個狀態的前驅狀態和對應的操作。
4. 路徑回溯：當找到目標狀態時，通過pre哈希表回溯并構造出從初始狀態到目標狀態的操作序列。

改進思路

1. 減少空間消耗：使用迭代而非遞歸來保存路徑，可以減少遞歸調用棧的空間消耗。
2. 剪枝：在BFS過程中，可以添加剪枝策略，如遇到已經訪問過且步數更優的狀態時直接跳過，避免重復探索。
3. 輸入驗證：在讀取目標狀態時增加輸入驗證，確保輸入是合法的（例如，確保是0和1組成，且0和1的數量符合要求）。
4. 優化狀態表示：直接使用整型或位操作來表示狀態，可能在某些情況下減少內存使用和加快狀態比較速度。
5. 清晰的函數命名和注釋：增加函數和關鍵變量的注釋，使代碼更易于理解和維護。