20xx搜索算法深入(編輯修改稿)
2025-08-21 15:45 本頁面
【文章內容簡介】 ]。 y1:=y+dy[k]。 solutions[x1,y1]:=solutions[x1,y1]+1。 N皇后問題 ? 更大的棋盤 n*n（ n=13） ? 有 n個棋子被放置在棋盤上，使得每行，每列，每條對角線 (包括兩條主對角線的所有對角線 )上都至多有一個棋子。 ? 求方案總數 N皇后問題 try(i) For j:=1 to n do if b[j] and c[I+j] and d[Ij] then a[i[]:=j。 b[j]:=f。 c[I+j]:=f。 d[Ij]:=f。 if In then try(I+1) else print。 b[j]:=t。 c[I+j]:=t。 d[Ij]:=t。 N皇后問題優(yōu)化test(row,ld,rd:longint)。 if rowupperlim（ n個 1） then pos:=upperlim and not (row or ld or rd)。 while pos0 do p:=pos and pos。 pos:=posp。 test(row+p,(ld+p)shl 1,(rd+p)shr 1)。 else inc(sum)。 序關系計數問題 ? 用關系 “ ”和 “ =”將 3 個數 A、 B和 C依序排列時有 13 種不同的序關系： A=B=C， A=BC， AB=C， ABC，ACB， A=CB， BA=C， BAC，BCA， B=CA， CA=B， CAB， CBA。 將 n 個數（ 1 = n =50）依序排列時有多少種序關系。 方案 1 ? 枚舉所有序關系表達式 ? A=b b=a 等價 保證降序就可 字母 關系 字母 關系 字母 關系 … … 字母 關系 優(yōu)化策略 ? 策略 1：減少冗余運算 root a b c = b c = c c = b b c = c c = b = a c = c c = a c = a = a b = b b = a 優(yōu)化策略 ? 策略 2：充分利用信息 ? 如果在第 k個字母之后添加第一個 “ ”，則： ? 前 k個字母都用 “ =”連接 ? 在此基礎上繼續(xù)搜索，將產生 f(nk)個序關系 )()(1knfCnfnkkn ?? ??深搜優(yōu)化策略小結 ? (1)縮小搜索范圍 ? (2)改變搜索次序 ? (3)剪枝 ? (4)記憶化搜索、動態(tài)規(guī)劃 ? (5)位運算 ? …… 關于寬搜 ? 判重 ? 在寬搜過程中，隊列以幾何數量級擴展，擴展層數越大，對存儲的威脅越大 ?哈希表 ?雙向搜索 倒油問題 ? 倒油問題。三個油桶，容量分別為 10ml、7ml和 3ml，開始在 10ml的油桶中裝滿油，另外兩個油桶為空，怎樣用這三個油桶分出5ml的油來？ ? 請寫出寬搜隊列 ? 能否采用雙向搜索？ 棋盤游戲 ? 在一個 4*4的棋盤上有 8個黑和 8個棋白棋，當且僅當兩個格子有公共邊，這兩個格子上的棋是相鄰的。移動棋子的規(guī)則是交換相鄰兩個棋子。現在給出一個初始棋盤和一個最終棋盤，要求你找出一個最短的移動系列使棋盤變?yōu)樽罱K棋盤。 樣例 ? 1111 0000 1110 0010 1010 0101 1010 0101 ? 4 1 2 2 2 1 4 2 4 3 2 4 2 4 3 4 4 解決方案 ? 如何存儲棋盤狀態(tài)？ ? 如何描述棋盤的移動規(guī)則？ 0000000011111111~1111111100000000 Longint 可以解決 0010 0100 1100 1111 0000 0110 1100 1111 0010 0100 1100 1111 0010 1100 0100 1111 規(guī)則描述 ? 運算精確到位？ 位運算 0010 0100 1100 1111 0000 0110 1100 1111 0010 0100 1100 1111 0010 1100 0100 1111 0010010011001111 xor 0010001000000000 0010010011001111 xor 0000100010000000 10 010001 0100 010010010001100? ? xor 17*2R ? ? xor 3*2R 可行性 ? (?? Xor
職業(yè)教育相關推薦
鄂ICP備17016276號-1