npc問題與近似算法-在線瀏覽
2024-12-20 23:47本頁(yè)面
【正文】 ijT t t O P TmS o luti o n T O P T t O P T? ? ?? ? ? ? ??Approximation Algorithm 近似算法 2 每次選擇一個(gè)未安排的工作中用時(shí)最多的，將它安排在當(dāng)前負(fù)載最小的機(jī)器上 ?這是一個(gè) Approximation Algorithm 例 2： KCenter Problem 問題描述： 1. 給定一張圖 G(V,E)滿足 G 是 metric 2. 要求選擇 k個(gè)點(diǎn)作為圖的中心 3. 目標(biāo)：最小化 m a x ( , )( : ( , ) m i n ( , ) )vVuCradi us di st v Cps di st v C di st v u????Approximation Algorithm 近似算法 1 ?每次假設(shè)圖的 radius（至多 |E|個(gè)），然后執(zhí)行以下算法 : 1. S=V C=empty 2. While S!=empty choose an arbitary v in S C?C+v 3. if |C|=k succeed else increase radius Approximation Algorithm 近似算法 2 1. C1 ={v} v 為圖中任意點(diǎn) 2. for i=2 to k choose vi . Dist(vi,Ci1) is largest Ci?Ci1+Vi Approximation Algorithm 例 3： Set Cover 算法： Approximation Algorithm 例 4： Weighted Set Cover 問題描述： Set Cover的加強(qiáng)，每個(gè) subset從花費(fèi)都是
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1