搜索引擎進(jìn)行信息檢索的優(yōu)化策略方法(編程找出所有可行道路中沒(méi)有重復的點(diǎn)怎么辦?)
優(yōu)采云 發(fā)布時(shí)間: 2022-03-24 01:01搜索引擎進(jìn)行信息檢索的優(yōu)化策略方法(編程找出所有可行道路中沒(méi)有重復的點(diǎn)怎么辦?)
什么是搜索?搜索就是不斷地尋找一個(gè)問(wèn)題的可行解,然后找到最優(yōu)可行解。搜索被稱(chēng)為“通用問(wèn)題解決”,但在大多數情況下,搜索所需的時(shí)間復雜度很高。搜索一般分為:深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)?;厮菟惴?一般的深度優(yōu)先搜索問(wèn)題需要回溯算法。每次遍歷不能繼續,就回溯到上一點(diǎn),繼續遍歷。例1:走迷宮的問(wèn)題(進(jìn)階版) 有am*n-square的迷宮(意思是m行n列),有的可以走,有的不能走。如果你用1表示你可以去,0表示你可以' t go 將文件讀入m*n個(gè)數據和起點(diǎn)和終點(diǎn)(起點(diǎn)和終點(diǎn)都是用兩個(gè)數據描述的,分別代表這個(gè)點(diǎn)的行號和列號)?,F在讓你編程找出所有可行的道路,要求你行駛的道路上沒(méi)有重復的點(diǎn),你只能在四個(gè)方向上行駛:上、下、左、右。如果沒(méi)有一條路徑是可行的,則輸出相應的信息(使用-1表示沒(méi)有路徑)。例1分析,當我們使用深度優(yōu)先搜索擴展一個(gè)點(diǎn)時(shí),我們按照深度優(yōu)先搜索向四個(gè)方向擴展,但是注意一些已經(jīng)訪(fǎng)問(wèn)過(guò)的點(diǎn)不能再次通過(guò)。到達目標點(diǎn)時(shí),不展開(kāi),計數器加一,輸出答案,并進(jìn)行回溯。當當前點(diǎn)無(wú)法繼續展開(kāi)時(shí),返回上一個(gè)節點(diǎn)展開(kāi)。搜索的優(yōu)化方法 Search method 深度優(yōu)先搜索的優(yōu)化 自定義回溯邊界條件,剪除不能得到最優(yōu)解的子樹(shù),并使用memoization方法使部分遍歷的子樹(shù)不被重復遍歷,以減少遍歷的總狀態(tài)數。2:訂單(ceoi 測試題) 一位店長(cháng)按照標簽的字母順序對所有商品進(jìn)行了分類(lèi)。并使用 memoization 方法使一些遍歷的子樹(shù)不被重復遍歷,以減少遍歷的狀態(tài)總數。2:訂單(ceoi 測試題) 一位店長(cháng)按照標簽的字母順序對所有商品進(jìn)行了分類(lèi)。并使用 memoization 方法使一些遍歷的子樹(shù)不被重復遍歷,以減少遍歷的狀態(tài)總數。2:訂單(ceoi 測試題) 一位店長(cháng)按照標簽的字母順序對所有商品進(jìn)行了分類(lèi)。
所有具有相同首字母的貨物都存放在同一個(gè)倉庫中,該倉庫也標有該字母。某天,經(jīng)理收到并登記了許多訂單,每個(gè)訂單只需要一種商品。您已經(jīng)知道經(jīng)理當天需要處理的所有訂單,但您不知道它們的注冊順序。計算所有可能的倉庫訪(fǎng)問(wèn)權限,以解決經(jīng)理當天的所有訂單。輸入文件 ORDERS.IN 中只有一行,其中收錄所有必需項目的編號(以隨機順序)。每種商品由其標簽的第一個(gè)字母表示,僅使用英文小寫(xiě)字母。訂單數量不超過(guò) 200 輸出文件 ORDERS.OUT 是收錄經(jīng)理訪(fǎng)問(wèn)倉庫的所有可能的訂單。示例 Order.inorder。out bbjdbbdj jdbb分析 因為題目要求我們輸出所有可能的注冊順序,而且數據范圍不大,不難看出是搜索題。由于方案的數量可能比較多,所以沒(méi)有必要保存所有的方案。因此,我們應該使用深度搜索并將它們放在一邊。一般來(lái)說(shuō),要確定某個(gè)順序的第一個(gè)位置的字母,我們從“a”開(kāi)始,到“z”循環(huán),依次搜索,看看哪個(gè)字母可以再次被選中。當可選字母的個(gè)數比較少,可選字母中的每個(gè)字母可以被選擇的次數較多時(shí),每個(gè)循環(huán)的掃描次數較多。的。我們可以對這種情況進(jìn)行優(yōu)化如下:輸入完成后,先統計各種字母的總數,
這樣可以保證每次循環(huán)掃描到的字母都是可選的,搜索中幾乎沒(méi)有多余的操作。搜索剪枝 在很多情況下,我們找到了一套比較好的解決方案。但是電腦還是會(huì )搜索比它“更糟糕”的其他解決方案,只能搜索后返回。為了避免這種情況,我們需要靈活地自定義回溯搜索的邊界。剪枝2、準確性:在保證第一原則的情況下,盡量剪掉不收錄最優(yōu)答案的分支3、效率:通過(guò)剪枝,必須能夠實(shí)現更快 逼近最優(yōu)解 常見(jiàn)剪枝最優(yōu)性 剪枝示例 3:計算機網(wǎng)絡(luò )連接 (gdoi) If n(n=kx, 那么這個(gè)方案的總長(cháng)度一定不能小于kx,那么就不需要再進(jìn)一步搜索了,直接替換下一個(gè)節點(diǎn)繼續搜索即可。優(yōu)化路徑A1-A2-…An和路徑An-An-1-…A1這兩條路徑是“正負”關(guān)系,本質(zhì)上是一樣的,所以我們可以規定起點(diǎn)總是小于終點(diǎn)的下標。優(yōu)化3 如果路徑的ABCD的長(cháng)度=n/2,x至少要乘1倍才能達到n,所以這種情況下,前面的剪枝效果很低。不難發(fā)現,如果x>=n/2,那么要相乘的數其實(shí)是小于n/2的,而且之前也計算過(guò)要相乘的數,所以可以考慮用動(dòng)態(tài)規劃求最優(yōu)解,
示例 6:彩票問(wèn)題 如果 1/A1+2/A2+…+1/An=X/Y,則中獎(獲得紀念品)。輸出:要準備的紀念品數量從以上兩個(gè)問(wèn)題,我們學(xué)習了可行性剪枝和最優(yōu)剪枝的應用和技巧。其實(shí)除了上面的一些剪枝,還有其他的剪枝技術(shù)。分析:對于每一個(gè)數字,有兩種可能選擇和不選擇。顯然,可以建立以下模型: 這變成了一個(gè)01背包問(wèn)題。每個(gè)包裹的體積為 T。從 M 中選擇 N 填滿(mǎn)方框。找出選項的數量。如何優(yōu)化?? T]=min{f[i-1,T],f[i-1,TT ]+1} 按照 x 的順序搜索。假設x,如果f[p-1,TS]+L>N,那么可以不繼續搜索就回溯。T~O(米?。?。太大!f數組打不開(kāi),時(shí)間不允許。動(dòng)態(tài)規劃的思想,空間矛盾太大,抓住矛盾:解決空間問(wèn)題!T太大了,有什么辦法可以變小嗎?=T,至少有多少x T]=min{f[i-1,T],f[i-1,TT T]=min{f[i-1,T],f[i-1,( TT )modP]+1} 順序搜索。假設x,如果f[p-1,(TS)mod P]+L>N,那么可以不繼續搜索就回溯。剪枝效果減弱但空間復雜度降低到O(mP),其中P可以任意選擇。
廣度優(yōu)先搜索 當狀態(tài)數較多時(shí),可以采用循環(huán)隊列或動(dòng)態(tài)鏈表來(lái)處理廣度優(yōu)先搜索。黑白棋游戲的棋盤(pán)由 44 個(gè)方格組成。棋盤(pán)的每個(gè)方格都有一個(gè)棋子,有8個(gè)白棋子和8個(gè)黑棋子。16 個(gè)棋子的每一個(gè)位置構成一個(gè)游戲狀態(tài)。棋盤(pán)上有 1 個(gè)公共邊的 2 個(gè)方格稱(chēng)為相鄰方格。一個(gè)方格最多可以有 4 個(gè)相鄰方格。在黑白棋游戲中,每一步都可以交換任意兩個(gè)相鄰的方格。對于給定的初始游戲狀態(tài)和目標游戲狀態(tài),程序計算從初始游戲狀態(tài)變?yōu)槟繕擞螒驙顟B(tài)的最短移動(dòng)序列。例7:黑白棋游戲(進(jìn)階版) 我們可以考慮用深度優(yōu)先搜索來(lái)做這道題,但是如果之前的狀態(tài)出現在下一步呢?直接判斷時(shí)間復雜度可能有點(diǎn)大。這個(gè)問(wèn)題的最佳解決方案是使用廣度優(yōu)先搜索。我們可以有初始狀態(tài),并根據廣度優(yōu)先搜索遍歷擴展每個(gè)點(diǎn),從而達到目標狀態(tài)的步數是確定的。是最優(yōu)的(隨著(zhù)步數的增加單調)。但問(wèn)題是,如果出現重復的情況,我們要判斷權重,但是簡(jiǎn)單的判斷可以達到狀態(tài)數的級別。其實(shí)我們可以考慮使用哈希表來(lái)判斷權重。例7:黑白棋游戲(進(jìn)階版) 哈希表:思路是直接根據鍵碼值進(jìn)行訪(fǎng)問(wèn)。即,將鍵值映射到表中的某個(gè)位置以訪(fǎng)問(wèn)記錄的過(guò)程。
那么這兩點(diǎn)不需要擴展,兩個(gè)擴展步驟之和就是答案。不必要的狀態(tài)廣度優(yōu)先搜索的優(yōu)化注意:一般的廣度優(yōu)先搜索可以通過(guò)這兩個(gè)優(yōu)化來(lái)解決。例8:pku1729在一個(gè)N*N(N>Time[n](Time[i]代表處理器的處理時(shí)間)中,這樣可以設置閾值:例如當前處理器的處理時(shí)間>= 當前最佳解決方案,或剩余處理器數量中前一個(gè)處理器的處理時(shí)間