npc問(wèn)題與近似算法(參考版)
2024-10-21 23:47本頁(yè)面
【正文】 Approximation Algorithm ?算法 網(wǎng)絡(luò)流？ 不行 ?網(wǎng)絡(luò)流無(wú)法保證 Si以 Ti為終點(diǎn) ?尋找近似算法 Approximation Algorithm ?近似算法 repeat pick an index i . the shortest path Pi from si to ti is shortest delete Pi from the graph THM：這個(gè)算法是一個(gè) 近似算法 mApproximation Algorithm 例 5：背包問(wèn)題 ?算法：對(duì)于給定的常數(shù) c, k= ?在改變價(jià)值的情況下用 DP解決（ polytime），得到 Soltuion nc??????m a x? ii ppkp?????Approximation Algorithm ?在未改變的情況中選擇 Solution中的元素得到我們的近似解 ?THM：這是一個(gè)（ 1+c）近似算法 Thank you Approximation Algorithm 更多的問(wèn)題： ?旅行商問(wèn)題 ?最大割問(wèn)題 ?斯特林樹(shù)問(wèn)題 。 amp。 1. 2. 對(duì)于任意 Definition of NPCompleteness X NP?, pY NP Y X??Reducibility of NPCompleteness Reducibility of NPCompleteness 證明： The Clique Problem is Npplete ① Show that a given clique can be checked in polytime ② Show that 3CNFSAT
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1