【正文】 ? continue。i=n。i++){ ? if(map[si+dir[i][0]][sj+dir[i][1]]!=39。 ? int n,m,t,di,dj。否則轉(zhuǎn)向（ 2）循環(huán)。i) for (j=i。amp。（事實(shí)上，不會超過 9091） 2022/8/21 22 搜索時的技巧： ? 搜索順序很重要。 （ 5） 把 node的 所有后繼節(jié)點(diǎn) 放在 OPEN表的末端 。這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分大，且不預(yù)測的情況下就不可取了。1) return。t==0) break。X39。X39。j++) ? { ? cinmap[i][j]。X39。 ? void dfs(int si,int sj,int t) ? { int i,temp。若仍不是目標(biāo)狀態(tài)，就按該分支一直擴(kuò)展到葉節(jié)點(diǎn)，若仍不是目標(biāo)，采用相同的回溯辦法回退到上層節(jié)點(diǎn)，擴(kuò)展可能的分支生成新狀態(tài)， ? ，一直進(jìn)行下去，直到找到目標(biāo)狀態(tài) G為止。 ? 狀態(tài)空間搜索： 就是將問題求解過程表現(xiàn)為從初始狀態(tài)到目標(biāo)狀態(tài)尋找這個路徑的過程。這里要說的是，有些初學(xué)者在學(xué)習(xí)這些搜索基本算法是不太注意剪枝，這是十分不可取的，因?yàn)樗兴阉鞯念}目給你的測試用例都不會有很大的規(guī)模，你往往察覺不出程序運(yùn)行的時間問題，但是真正的測試數(shù)據(jù)一定能過濾出那些沒有剪枝的算法。 p,q中乘積最大的一對 p,q 2022/8/21 19 算法分析 從所有可能的 p,q中尋找滿足條件的一對 ,q的要求 p,q均為質(zhì)數(shù) ,且 p=q=100000。 （ 3） 在 OPEN表中取最前面的節(jié)點(diǎn) node移到CLOSED 表 中。 （ 6） 若后繼節(jié)點(diǎn)中某一個是目標(biāo)節(jié)點(diǎn)，則找到一個解，成功退出。 ? if(escape) return。amp。) { di=i。 ? else coutNOendl。) { si=i。.39。amp。 （ 3） 從 OPEN表中取最前面的節(jié)點(diǎn) node移到CLOSED 表中。構(gòu)成樹的下一層節(jié)點(diǎn)，檢查是否出現(xiàn)目標(biāo)狀態(tài) G，若未出現(xiàn)，就對該層所有狀態(tài)節(jié)點(diǎn)，分別順序利用規(guī)則。 搜索過程實(shí)際上是根據(jù)初始條件和擴(kuò)展規(guī)則構(gòu)造一棵解答樹并尋找符合目標(biāo)狀態(tài)的節(jié)點(diǎn)的過程。 2022/8/21 9 預(yù)熱一下：二分查找 2 3 4 5 6 8 12 20 32 45 65 74 86 95 100 head mid tail 2022/8/21 10 查找示意圖： A[1]~A[15] A[1]~A[7] A[9]~A[15] A[1]~A[3] A[5]~A[7] A[1]~A[1] A[3]~A[3] …… 2022/8/21 11 思考： ? 在一百萬個元素里查找某個元素大約需要比較多少次？ ?時間復(fù)雜度： O(logN) 2022/8/21 12 舉例分析 從簡單的字符串搜索講起 2022/8/21 13 HDOJ_1238 Substrings ?題目鏈接 ? Sample Input 2 3 ABCD BCDFF BRCD 2 rose orchid ?Sample Output 2 2 2022/8/21 14 題目分析： ? 這是一道入門級別的搜索題，基本思想比較簡單，但是如果用 最樸素的算法 ，可能會超時如何降低算法的復(fù)雜度呢？ 下面的算法如何： 先將字符串按長度從短到長