圖論的基本算法(已改無錯字)
2022-10-28 15:10:01 本頁面
【正文】 0 的整數(shù) ?對于 v0到 v1的任意一條簡單路 p ? 定義 s(p)為 p上所有邊權(quán)的最大公約數(shù) ?考慮 v0到 v1的所有路 p1,p2,… ? 求所有 s(p1),s(p2),… 的最小公倍數(shù) ? 模型？最短路？ ?路徑長度定義不再是權(quán)和，而是 … ? dijkstra算法還能用嗎？ SSSP：權(quán)任意的情形 ? 最短路有可能不存在！ ? 什么時候不存在？ ? 有負(fù)圈！ ? 標(biāo)號設(shè)定 ?標(biāo)號修正 ?仍然有標(biāo)號 d[i] = k ?但是標(biāo)號 d[i]無法固定，只能不斷更新 ? 新算法 ?如有最短路，則每個頂點最多經(jīng)過一次 ?即：這條路不超過 n1條邊 ? 迭代！依次考慮 1,2,3…n 1條邊的情形 SSSP： bellmanford算法 ? 依次考慮邊長度不超過 1,2…n 1的路 ?考慮長度不超過 1,2,3…k 1的路后，標(biāo)號為 d[] ?長度為 k的路可以由不超過 1,2,…k 1的路增加一條邊得到： for k:=1 to n1 do for 每條邊 (u,v) do if (d[u]∞) and (d[v]d[u]+w(u,v)) then d[v]:=d[u]+w(u,v) ?核心：標(biāo)號修正過程（松弛操作） ?時間復(fù)雜度： O(nm) ?改進(jìn)的終止條件： d都不改變 ?加速：用 dijkstra得到初始 d[] 一個例子 ? 24小時營業(yè)的超市 ? 需要一批出納員來滿足它的需求 ? 每天的不同時段需要不同數(shù)目的出納員 ? 例如：午夜時只需一小批，而下午則需要很多） ? 經(jīng)理已經(jīng)提供你 ? 一天里每一小時需要出納員的最少數(shù)量 —— R(0), R(1), …, R(23)。 ? R(0)表示從午夜到午夜 1:00需要出納員的最少數(shù)目， ? R(1)表示上午 1:00到 2:00之間需要的 … ? 每一天，這些數(shù)據(jù)都是相同的。 ? 有 N人申請這項工作 ? 每個申請者 i在每天 24小時中，從一特定的時刻開始連續(xù)工作恰好 8小時 ? 定義 ti（ 0≤ti≤23）為上面提到的開始時刻 ? 也就是說，如果第 i個申請者被錄用，他將從 ti刻開始連續(xù)工作 8小時。 ? 計算為滿足上述限制需要雇傭的最少出納員數(shù)目 ? 在每一時刻可以有比對應(yīng)的 R(i)更多的出納員在工作。 分析 ? 前 i(0=i=23)小時的雇傭總數(shù)： s[i] ? 規(guī)定 s[1] = 0 ? 第 i(0=i=23)小時需要的出納員： r[i] ? 第 i(0=i=23)小時申請的人數(shù)： t[i] ? 則有不等式 ? 0 = s[i] – s[i1] = t[i] ? s[23] – s[1] = sum ? 取 (i,j)滿足 i = (j+8) mod 24，則 ? i j時 s[i] – s[j] = r[i] ? I j時 s[i] – s[j] = r[i] – sum ? sum已知道時構(gòu)圖 G(1,0,1,…23) ? S[a] – s[b] = c：有向邊 (b, a, c) ? 1為起點的單源最長路 ? 最長路存在且 s[23] = sum，有解 ? 枚舉 sum！二分？ APSP: 基本分析 ? 設(shè) d[i， j， k]是 ?在只允許經(jīng)過結(jié)點 [1… k]的情況下 ? i到 j的最短路長度 ? 則它有兩種情況（想一想，為什么）： ?如果最短路經(jīng)過點 k，那么 ? d[i， j， k]應(yīng)該等于 d[i， k， k1]+d[k， j， k1]； ?如果最短路不經(jīng)過點 k，那么 ? d[i， j， k]應(yīng)該等于 d[i， j， k1]。 ?綜合起來 ? d[i， j， k]=min{d[i， k， k1]+d[k， j， k1]， d[i， j， k1]} ? 邊界條件是 d[i， j， 0]=w(i， j)（不存在的邊權(quán)為 ∞） floydwarshall算法 ? 基本的動態(tài)規(guī)劃 ?把 k放外層循環(huán)，可以節(jié)省內(nèi)存 ?對于每個 k，計算每兩點的目前最短路 for k:=1 to n do for i:=1 to n do for j:=1 to n do if (d[i,k]∞)and(d[k,j]∞) and(d[i,k]+d[k,j]d[i,j]) then d[i,j]:=d[i,k]+d[k,j] ? 一定要背下來！ ? 時間復(fù)雜度： O(n3) ? 用途：預(yù)處理！ 一個例子 ? 一場可怕的戰(zhàn)爭后，瘦陀陀和他的好朋友胖陀陀將要凱旋。 ?瘦陀陀處在城市 A ?胖陀陀處在另外一個未知的城市 ?他們打算選一個城市 X（這個由瘦陀陀來決定） ?胖陀陀會趕在瘦陀陀之前到達(dá)城市 X ?然后等待瘦陀陀也趕到城市 X與他匯合，并舉辦一次慶祝宴會（由瘦陀陀請客） ?接著一起回到他們的家鄉(xiāng)城市 B ?由于胖陀陀嘴饞，他要求舉辦宴會的城市必須是瘦陀陀回家的路線中舉辦宴會最貴的一個城市。 ? 瘦陀陀正專注地看回家的地圖 ?地圖上標(biāo)有 n（ n≤200）個城市和某些城市間直達(dá)的道路 ?以及每條道路的過路費 ?瘦陀陀還知道在每一座城市舉辦宴會的花費。 ? 給出地圖和 A、 B的位置
外語相關(guān)推薦
鄂ICP備17016276號-1