《高級(jí)算法設(shè)計(jì)》課件 第6章 在線算法

高級(jí)算法設(shè)計(jì)與分析在線算法林海lin.hai@B站：foretmer目錄基本概念確定性在線算法在線最小生成樹時(shí)間序列搜索隨機(jī)在線算法租買問題在線二分圖最大匹配概述離線算法在前面討論的算法中，問題實(shí)例的所有數(shù)據(jù)在計(jì)算時(shí)，都是已知的，稱為離線算法在線算法問題實(shí)例的數(shù)據(jù)是逐漸到來的，但是又需要對(duì)已經(jīng)到來的數(shù)據(jù)進(jìn)行計(jì)算，也就是說算法必須在輸入數(shù)據(jù)不是很完全可知的情況下，完成相應(yīng)的計(jì)算并輸出結(jié)果如股票買賣、物流中的裝車問題在線算法是近似算法概述人工智能算法試圖從以往的數(shù)據(jù)中尋找出規(guī)律，并根據(jù)目前的分配狀態(tài)，來智能的分配目前到達(dá)的任務(wù)在線算法數(shù)據(jù)完全未知假設(shè)存在一個(gè)對(duì)手(adversary)：這個(gè)對(duì)手對(duì)設(shè)計(jì)的算法了如指掌，所以能夠針對(duì)算法給出最壞數(shù)據(jù)到達(dá)實(shí)例(稱為最壞實(shí)例)，來使得算法的效率最低，所以設(shè)計(jì)在線算法時(shí)，通常需要分析在最壞實(shí)例下算法的性能。概述：流程股票買賣為例概述：定義競(jìng)爭度ρ概述：定義在線算法的下界下界表達(dá)式給出了在最差實(shí)例下，任意在線算法ALG和OPT存在大于等于的關(guān)系，如果某算法ALG′的ρ=α，且c=0,b=0，說明在線算法ALG′的性能已經(jīng)最優(yōu)，因?yàn)樗性诰€算法在最壞實(shí)例下都是大于等于競(jìng)爭度ρ的，當(dāng)在線算法ALG′的競(jìng)爭度是小于等于ρ，顯然ALG′已經(jīng)最優(yōu)。確定性在線算法：在線最小生成樹在線最小生成樹圖中的頂點(diǎn)不是一開始就已知，而是逐個(gè)到達(dá)，并要求一旦一個(gè)頂點(diǎn)到達(dá)就需要加入到樹中，且讓生成的樹總代價(jià)盡量小。一個(gè)比較簡單的在線算法是讓到達(dá)的頂點(diǎn)通過離樹內(nèi)最近的頂點(diǎn)加入到樹中。如，在第k個(gè)頂點(diǎn)到達(dá)時(shí)，選取前面k?1個(gè)頂點(diǎn)中和第k個(gè)頂點(diǎn)距離最近的頂點(diǎn)，通過此頂點(diǎn)將第k個(gè)頂點(diǎn)加入到樹中。我們把這種算法稱為最小生成樹的貪心在線算法。確定性在線算法：在線最小生成樹在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：在線最小生成樹確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索確定性在線算法：時(shí)間序列搜索目錄基本概念確定性在線算法在線最小生成樹時(shí)間序列搜索隨機(jī)在線算法租買問題在線二分圖最大匹配隨機(jī)在線算法策略的做出是隨機(jī)性，形成隨機(jī)在線算法，隨機(jī)在線算法的好處是，假設(shè)的對(duì)手無法猜測(cè)算法的策略。隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題回到上面租買問題的例子ρ=4/3

的競(jìng)爭度，這個(gè)競(jìng)爭度比任意的確定性算法都要好，但這個(gè)競(jìng)爭度是實(shí)例{I1,I2,I3}下的最優(yōu)競(jìng)爭度嗎隨機(jī)在線算法：租買問題隨機(jī)實(shí)例下確定性算法費(fèi)用和競(jìng)爭度的計(jì)算隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：租買問題隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在線二分圖最大匹配按秩進(jìn)行貪心匹配的確定性算法隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在線二分圖最大匹配在小數(shù)二分圖匹配中，一個(gè)到達(dá)的頂點(diǎn)(a∈A)可以和B中的頂點(diǎn)(可以有多個(gè))部分匹配隨機(jī)在線算法：在線二分圖最大匹配一個(gè)非常簡單的算法是:當(dāng)一個(gè)頂點(diǎn)ai到達(dá)時(shí)，和所有可匹配的頂點(diǎn)進(jìn)行均勻匹配水位算法(waterlevelalgorithm)是一個(gè)非常著名的確定性在線算法，當(dāng)A中的一個(gè)頂點(diǎn)a到達(dá)時(shí)，算法依據(jù)頂點(diǎn)a所有鄰頂點(diǎn)的匹配狀態(tài)，將a的匹配分配到這些鄰頂點(diǎn)中，使得分配后，所有的鄰頂點(diǎn)的匹配總量相似隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在線二分圖最大匹配隨機(jī)在線算法：在