數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)-展示頁
2025-05-08 08:38本頁面
【正文】 代碼、算法優(yōu)化 ? 可擴展性 ? 軟件復(fù)用 ? 緊盯標(biāo)準(zhǔn) ? 平臺無關(guān) ?在總體設(shè)計上要注意代碼風(fēng)格、可復(fù)用性和可擴展性 ?在關(guān)鍵段要犧牲上面的內(nèi)容來追求性能 ?性能和可擴展性是相互矛盾的 STL中的容器 順序容器 Sequence Containers 關(guān)聯(lián)容器 Associative Containers 容器 Containers vector deque list set, multiset map, multimap STL中的容器 容器適配器 stack queue priority_queue 基本算法 ?問題的狀態(tài)空間 ?窮舉法 ?回溯、搜索 ?貪心法 ?遞歸分治 ?動態(tài)規(guī)劃 八皇后問題 ?在 8 8格的國際象棋棋盤上擺放 8個皇后，使其不能互相攻擊 ?任意兩個皇后都不處于同一 行 、同一 列 或同一 斜線 上 ?問有多少種擺法？ 八皇后問題的一個解 Q Q Q Q Q Q Q Q 窮舉法（枚舉法） ?4個皇后各占一行，窮舉每一行上可能占有的列 ? 共有 44 ＝ 256種情況 ?枚舉時，可以排除直觀不符合條件的情況，減小候選集 ? 有 4! ＝ 24種情況 ?最后輸出合理的解 窮舉法的代價 ? 窮舉問題域的 所有解 ，找到所有最佳解 ? 減少窮舉次數(shù) ? 窮舉的變量 ? 注意窮舉的順序 ? 減少判斷每種情況的時間 ? 時間代價最高 ? 問題規(guī)模 n，搜索空間 Σ，總搜索時間是： ? T= |Σ| ?t， O(n!) = O(nn)， O(2n) ? 指數(shù)級時間代價 狀態(tài)空間 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 四皇后的解空間樹 解空間樹 ? 根（ root）：問題的起點 ? 問題狀態(tài)（ problem states）：樹中結(jié)點 ? 狀態(tài)空間（ state space）：由根結(jié)點到其它結(jié)點的所有路徑 ? 解狀態(tài)（ solution states） S：由根到 S的路徑確定了解空間中的一個元組 ? 答案狀態(tài)（ answer states） S：由根到 S的路徑確定了這問題的一個解（即，它滿足隱式約束條件） 回溯法圖示 ? “ 可行則進，不行則換、換不成則退 ”。搜索過程如下 ： 0 1 ● ● ● ● 0 1 2 ● ● ● ● 0 1 2 3 四后問題求解 ?回溯算法 可行則進，不行則換 換不成則退 八皇后問題的表示 ? 棋盤行列、皇后依次編上 0, 1,… ， 7號 ? A[0..n1][0..n1] 表示 n n棋盤上的格 ? 行號從上至下、列號從左到右依次編號為 0, 1,… ， n1 ? 八后問題的全部解向量為 (x0, x1,… ， x7)。 1 ） ? 重點！ 斜率 +1， i+j={0, 1, …, 14} 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 斜率 1， ij={7, 6, …, 7} 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 皇后的控制范圍 ?第 i個皇后時，前面幾個皇后在各列、各對角線上的占用情況 bool A[n]。 // 斜率為 +1的對角線 bool C[2*n1]。 ? 對第 i個皇后，找正確的位置 (設(shè)為第 j列 ? A[j]、 B[i+j]、 C[ij+7]都沒有被占用 ? 標(biāo)記 A[j]、 B[i+j]、 C[ij+7]為被占用狀態(tài) ? 繼續(xù)安排下一個皇后 (第 i+1個 ) ? 否則，如果找不到合適位置，應(yīng)該退回(即“回溯” )到第 i1行的皇后，重新安排 ? 前面的安排不太合理 回溯過程 ? 如果 8個皇后都排好了，則打印這種方案 ? 為了找到其它方案，應(yīng)該回溯，重新試探皇后的下一種安排方法 ? 抹掉前面試探留下的標(biāo)記，即恢復(fù) A[j]、B[i+j]、 C[ij+7]為未被占用狀態(tài) ? 這種回溯過程將逐步返回 ? 使得各行的皇后都能試探到各種可能的擺法
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1