20xx搜索算法深入(編輯修改稿)
2024-08-21 15:45 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ]。 y1:=y+dy[k]。 solutions[x1,y1]:=solutions[x1,y1]+1。 N皇后問(wèn)題 ? 更大的棋盤 n*n（ n=13） ? 有 n個(gè)棋子被放置在棋盤上，使得每行，每列，每條對(duì)角線 (包括兩條主對(duì)角線的所有對(duì)角線 )上都至多有一個(gè)棋子。 ? 求方案總數(shù) N皇后問(wè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皇后問(wèn)題優(yōu)化test(row,ld,rd:longint)。 if rowupperlim（ n個(gè) 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)。 序關(guān)系計(jì)數(shù)問(wèn)題 ? 用關(guān)系 “ ”和 “ =”將 3 個(gè)數(shù) A、 B和 C依序排列時(shí)有 13 種不同的序關(guān)系： A=B=C， A=BC， AB=C， ABC，ACB， A=CB， BA=C， BAC，BCA， B=CA， CA=B， CAB， CBA。 將 n 個(gè)數(shù)（ 1 = n =50）依序排列時(shí)有多少種序關(guān)系。 方案 1 ? 枚舉所有序關(guān)系表達(dá)式 ? A=b b=a 等價(jià) 保證降序就可 字母 關(guān)系 字母 關(guān)系 字母 關(guān)系 … … 字母 關(guān)系 優(yōu)化策略 ? 策略 1：減少冗余運(yùn)算 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個(gè)字母之后添加第一個(gè) “ ”，則： ? 前 k個(gè)字母都用 “ =”連接 ? 在此基礎(chǔ)上繼續(xù)搜索，將產(chǎn)生 f(nk)個(gè)序關(guān)系 )()(1knfCnfnkkn ?? ??深搜優(yōu)化策略小結(jié) ? (1)縮小搜索范圍 ? (2)改變搜索次序 ? (3)剪枝 ? (4)記憶化搜索、動(dòng)態(tài)規(guī)劃 ? (5)位運(yùn)算 ? …… 關(guān)于寬搜 ? 判重 ? 在寬搜過(guò)程中，隊(duì)列以幾何數(shù)量級(jí)擴(kuò)展，擴(kuò)展層數(shù)越大，對(duì)存儲(chǔ)的威脅越大 ?哈希表 ?雙向搜索 倒油問(wèn)題 ? 倒油問(wèn)題。三個(gè)油桶，容量分別為 10ml、7ml和 3ml，開(kāi)始在 10ml的油桶中裝滿油，另外兩個(gè)油桶為空，怎樣用這三個(gè)油桶分出5ml的油來(lái)？ ? 請(qǐng)寫出寬搜隊(duì)列 ? 能否采用雙向搜索？ 棋盤游戲 ? 在一個(gè) 4*4的棋盤上有 8個(gè)黑和 8個(gè)棋白棋，當(dāng)且僅當(dāng)兩個(gè)格子有公共邊，這兩個(gè)格子上的棋是相鄰的。移動(dòng)棋子的規(guī)則是交換相鄰兩個(gè)棋子?，F(xiàn)在給出一個(gè)初始棋盤和一個(gè)最終棋盤，要求你找出一個(gè)最短的移動(dòng)系列使棋盤變?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 解決方案 ? 如何存儲(chǔ)棋盤狀態(tài)？ ? 如何描述棋盤的移動(dòng)規(guī)則？ 0000000011111111~1111111100000000 Longint 可以解決 0010 0100 1100 1111 0000 0110 1100 1111 0010 0100 1100 1111 0010 1100 0100 1111 規(guī)則描述 ? 運(yùn)算精確到位？ 位運(yùn)算 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è)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1