算法合集之匹配算法在搜索問題中的應(yīng)用-文庫吧資料
2024-10-22 20:30本頁面
【正文】 n3)。 優(yōu)化： 優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。 時(shí)間上很難承受，如果使用卡時(shí)，正確性受到影響，效果不會(huì)很好。 下面任務(wù)就是將 B國武器根據(jù)編號劃分為若干段 +二分圖匹配判斷。 建圖：左邊 x個(gè)點(diǎn)，表示 B國武器根據(jù)編號分為的 x段，右邊 N個(gè)點(diǎn)，表示 A國的 N顆炸彈。amp。 建圖： C[S][T][I] 表示 A國炸彈 I是否可以炸到 B國武器S,S+1..T1,T。 （２）判斷是否可以從 A國的 N顆炸彈中選出 x顆，分別可以炸掉其中的一段。 然后的任務(wù)就是判斷是否可以從 A國的 N顆炸彈中選出 x顆，分別可以炸掉其中的一段。 即使加上優(yōu)化，程序效率也不是很高。 普通的搜索方法： 每次尋找一個(gè)編號最小的沒有被炸掉的B國武器，選擇一顆沒有使用過并能炸到此武器的 A國炸彈，然后使用這顆炸彈炸掉 B國武器連續(xù)的一段，繼續(xù)深度優(yōu)先搜索下一顆炸彈的編號，如果發(fā)現(xiàn) B國武器已經(jīng)全部炸毀就可以回溯。 進(jìn)一步分析： 每一顆炸彈必定炸掉 B國武器中編號連續(xù)的一段。 初步分析： A國炸彈 i可以炸到 B國武器 j的條件： (u[i]x[j])2+(v[i]y[j])2=R2 結(jié)論：很難找到求最優(yōu)解的多項(xiàng)式算法。 輸入： N,M及武器和炸彈的坐標(biāo)。 任務(wù)： 決定一個(gè)序列 a a a3… 使得在第 ax號炸彈引爆的時(shí)間內(nèi)連環(huán)陣被摧毀。 A國有 N個(gè)炸彈，每個(gè)炸彈的作用半徑均為 k，且會(huì)持續(xù)爆炸 5分鐘。最初， 1號武器處于攻擊狀態(tài)，其他武器都處在無敵自衛(wèi)狀態(tài)。 一個(gè)部分搜索 +匹配算法的經(jīng)典例子。 例如上面的例子，如果我們先知道了 3和 5的位置后，不用匹配，其實(shí)我們是在用搜索來求匹配，效率當(dāng)然不會(huì)高。兩者相互促進(jìn)，同時(shí)也彌補(bǔ)對方的不足。 部分搜索 +匹配 的方法充分發(fā)揮了搜索和匹配算法的雙重優(yōu)勢。 就本題而言就是：先搜索一定數(shù)量（而不是全部）物品的位置，使問題內(nèi)其它物品的關(guān)系簡化為二分圖關(guān)系，用二分圖匹配來解決余下的物品。 這時(shí)我們發(fā)現(xiàn)一個(gè)新的搜索方法： 部分搜索 +匹配 。 好像似乎也只能這樣。 面對這一系列類似的問題，我們一般只有搜索，如何搜索又如何優(yōu)化呢？ 簡單分析： 如果
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1