算法合集之匹配算法在搜索問題中的應用(編輯修改稿)
2024-11-12 20:30 本頁面
【文章內容簡介】 為[Si,Ti] (S1=1,Ti=Si,Ti+1=Si+1)。 然后的任務就是判斷是否可以從 A國的 N顆炸彈中選出 x顆，分別可以炸掉其中的一段。 其實我們把搜索分為了兩部分， （１）將 B國武器根據(jù)編號分為 x段。 （２）判斷是否可以從 A國的 N顆炸彈中選出 x顆，分別可以炸掉其中的一段。 其實第二部分可以用匹配來解決。 建圖： C[S][T][I] 表示 A國炸彈 I是否可以炸到 B國武器S,S+1..T1,T。 C[S][S][I]=((u[I]x[S])2+(v[I]y[S])2=R2) C[S][T][I]=C[S][T1][I] amp。amp。C[T][T][I] (ST) 求 C的時間復雜度為 O(n3)。 建圖：左邊 x個點，表示 B國武器根據(jù)編號分為的 x段，右邊 N個點，表示 A國的 N顆炸彈。左邊第 i個點到右邊第 j個點有邊的條件即： C[Si][Ti][j]。 下面任務就是將 B國武器根據(jù)編號劃分為若干段 +二分圖匹配判斷。 樣例 1： 4 3 6 0 6 6 6 6 0 0 0 1 5 0 3 1 1 如果的劃分方法是： x=3， 3段分別為 12,33,44 最大匹配 =x， 滿足 如果的劃分方法是： x=4， 4段分別為 11,22,33,44 最大匹配 x， 不滿足 性能分析（ 1）： 搜索的基本框架已經(jīng)建立，雖然數(shù)據(jù)是隨機生成的，但是 m個 B國武器的劃分方案還是非常多的，有時可能高達 2m。 時間上很難承受，如果使用卡時，正確性受到影響，效果不會很好。 只有 4個數(shù)據(jù)可以在時限內出解，另外 6個如果卡時，有 2個也可以得到最優(yōu)解。 優(yōu)化： 優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。 優(yōu)化一（最優(yōu)性）： 如果 A國炸彈可以重復使用，設： Dist[i]=炸掉 B國武器 i－ m的最少使用炸彈數(shù)。 可以用動態(tài)規(guī)劃計算 Dist值，狀態(tài)轉移方程如下： Dist[m+1]=0, Dist[i]=min{Dist[j]+1|C[i][j1][k](0k=n)) (1=i=N) (ij=N+1) 求 Dist的時間復雜度為 O(n3)。 從而產(chǎn)生了一個最優(yōu)性剪枝條件：
教學課件相關推薦
鄂ICP備17016276號-1