Argument nabíjení - Charging argument

v počítačová věda, a argument nabíjení se používá k porovnání výstupu optimalizačního algoritmu s optimálním řešením. Obvykle se používá k prokázání, že algoritmus produkuje optimální výsledky tím, že prokazuje existenci konkrétního injekční funkce. Pro maximalizace zisku problémy, funkcí může být libovolné individuální mapování od prvků optimálního řešení k prvkům výstupu algoritmu. Pro problémy s minimalizací nákladů může být funkcí libovolné individuální mapování od prvků výstupu algoritmu k prvkům optimálního řešení.

Správnost

Aby mohl algoritmus optimálně vyřešit problém s maximalizací zisku, musí algoritmus vytvořit výstup, který má stejný zisk jako optimální řešení pro každý možný vstup. Nechat |A (I)| označuje zisk z výstupu algoritmu daného vstupu Jáa nechte |OPT (I)| označit zisk optimálního řešení pro Já. Pokud jde o injekční funkci h: OPT (I) → A (I) z toho vyplývá |OPT (I)| ≤ |A (I)|. Jelikož optimální řešení má největší dosažitelný zisk, znamená to, že výstup daný algoritmem je stejně výnosný jako optimální řešení, a proto je algoritmus optimální.

Správnost argumentu zpoplatnění problému s minimalizací nákladů je symetrická. Li |A (I)| a |OPT (I)| označit náklady na výstup algoritmu, respektive optimální řešení, pak existenci injektivní funkce h: A (I) → OPT (I) by to znamenalo |A (I)| ≤ |OPT (I)|. Protože optimální řešení má nejnižší náklady a náklady na algoritmus jsou stejné jako náklady na optimální řešení problému minimalizace, pak algoritmus také problém optimálně řeší.

Variace

K zobrazení výsledků aproximace lze také použít argumenty nabíjení. Zejména jej lze použít k prokázání, že algoritmus je n- přiblížení se problému optimalizace. Místo toho, abyste ukázali, že algoritmus produkuje výstupy se stejnou hodnotou zisku nebo nákladů jako optimální řešení, ukažte, že tuto hodnotu dosahuje v rámci faktoru n. Namísto prokázání existence funkce jedna ku jedné se argument nabíjení zaměřuje na prokázání, že nfunkce-to-one existuje za účelem prokázání výsledků aproximace.

Příklady

Problém s intervalovým plánováním

Hlavní článek: intervalové plánování

Vzhledem k souboru n intervaly I = {I1, Já2, ..., ján}, kde každý interval Jái ∈ Já má počáteční čas si a čas na dokončení Fi, kde si i, cílem je najít maximální podmnožinu vzájemně kompatibilních intervalů v Já. Tady, dva intervaly Jáj a Ják jsou považovány za kompatibilní, pokud se v tom nepřekrývají sj j ≤ sk k.

Zvažte nejbližší čas dokončení chamtivý algoritmus popsaný následovně:

  • Začněte prázdnou sadou intervalů.
  • Seřaďte intervaly dovnitř Já vzestupným dokončovacím časem.
  • Zvažte každý interval v Já v seřazeném pořadí. Přidejte interval do sady, pokud není v rozporu s intervaly již obsaženými v sadě. Jinak interval ignorujte.

Na problém s intervalovým plánováním lze pohlížet jako na problém maximalizace zisku, kde počet intervalů ve vzájemně kompatibilní podmnožině je zisk. Argument nabíjení lze použít k ukázce, že pro problém s časovým plánováním je optimální nejstarší algoritmus doby dokončení.

Vzhledem k souboru intervalů I = {I1, Já2, ..., ján}, nechť OPT (I) být jakýmkoli optimálním řešením problému s intervalovým plánováním a nechat EFT (I) být řešením nejstaršího algoritmu doby dokončení. Pro jakýkoli interval J ∈ OPT (I), definovat h (J) jako interval J '∈ EFT (I) který se protíná J s nejčasnější dobou dokončení mezi všemi intervaly v EFT (I) protínající se J. Chcete-li ukázat, že algoritmus nejbližšího času dokončení je optimální pomocí argumentu nabíjení, h musí být ukázáno jako intervaly mapování funkcí jedna ku jedné v OPT (I) těm v EFT (I). Předpokládat J je libovolný interval v OPT (I).

Ukaž to h je mapování funkcí OPT (I) na EFT (I).

Předpokládejme rozpor, že neexistuje žádný interval J '∈ EFT (I) uspokojující h (J) = J '. Podle definice h, to znamená, že v intervalu není žádný interval EFT (I) protíná se J. To by však také znamenalo, že J je kompatibilní s každým intervalem v EFT (I), a tak by se přidal algoritmus nejranějšího času dokončení J do EFT (I)a tak J ∈ EFT (I). Vzniká rozpor J Předpokládalo se, že se neprotínají s žádným intervalem v EFT (I), dosud J je v EFT (I), a J protíná se sama se sebou. Rozporem tedy J musí se protínat s alespoň jedním intervalem v EFT (I).
Zbývá to ukázat h (J) je jedinečný. Na základě definice kompatibility se nikdy nemůže stát, že dva kompatibilní intervaly mají stejnou dobu dokončení. Protože všechny intervaly v EFT (I) jsou vzájemně kompatibilní, žádný z těchto intervalů nemá stejnou dobu dokončení. Zejména každý interval v EFT (I) který se protíná s J mají zřetelné časy dokončení atd h (J) je jedinečný.

Ukaž to h je jedna ku jedné.

Předpokládejme rozpor h není injekční. Pak existují dva odlišné intervaly OPT (I), J1 a J2, takový, že h mapuje obě J1 a J2 do stejného intervalu J '∈ EFT (I). Bez ztráty obecnosti předpokládejme, že f1 2. Intervaly J1 a J2 nemohou protínat, protože jsou oba v optimálním řešení, a tak f1 ≤ s22. Od té doby EFT (I) obsahuje J ' namísto J1, který narazil na algoritmus nejbližší doby dokončení J ' před J1. Tím pádem, f '≤ f1. To však znamená, že f '≤ f1 ≤ s22, tak J ' a J2 neprotínají se. To je rozpor, protože h nelze mapovat J2 na J ' pokud se neprotínají. Rozporem tedy h je injekční.

Proto, h je individuální funkce mapující intervaly v OPT (I) těm v EFT (I). Argumentem nabíjení je optimální algoritmus nejbližší doby dokončení.

Problém s plánováním intervalu úloh

Zvažte problém plánování intervalu úloh, an NP-tvrdé varianta problému s intervalovým plánováním navštívená dříve. Stejně jako dříve je cílem najít maximální podmnožinu vzájemně kompatibilních intervalů v dané sadě n intervaly, I = {I1, Já2, ..., ján}. Každý interval Jái ∈ Já má počáteční čas si, čas dokončení Fia pracovní třída Ci. Tady, dva intervaly Jáj a Ják jsou považovány za kompatibilní, pokud se nepřekrývají a mají různé třídy.

Připomeňme si nejstarší algoritmus doby dokončení z předchozího příkladu. Po úpravě definice kompatibility v algoritmu lze argumentem nabíjení ukázat, že nejstarší algoritmus doby dokončení je algoritmus 2-aproximace pro problém plánování intervalu úloh.

Nechat OPT (I) a EFT (I) označují optimální řešení a řešení vytvořené algoritmem nejbližší doby dokončení, jak bylo dříve definováno. Pro jakýkoli interval J ∈ OPT (I), definovat h jak následuje:

Chcete-li ukázat, že nejstarší algoritmus času dokončení je algoritmus 2-aproximace pomocí argumentu nabíjení, h musí být ukázáno jako intervaly mapování funkcí dva na jednoho v OPT (I) těm v EFT (I). Předpokládat J je libovolný interval v OPT (I).

Ukaž to h je mapování funkcí OPT (I) na EFT (I).

Nejprve si všimněte, že existuje buď nějaký interval EFT (I) se stejnou třídou práce jako Jnebo není.
Případ 1. Předpokládejme, že nějaký interval v EFT (I) má stejnou třídu zaměstnání jako J.
Pokud existuje interval v EFT (I) se stejnou třídou jako J, pak J bude mapovat na tento interval. Od intervalů v EFT (I) jsou vzájemně kompatibilní, každý interval v EFT (I) musí mít jinou třídu zaměstnání. Takový interval je tedy jedinečný.
Případ 2. Předpokládejme, že v něm nejsou žádné intervaly EFT (I) se stejnou třídou práce jako J.
Pokud v něm nejsou žádné intervaly EFT (I) se stejnou třídou jako J, pak h mapy J do intervalu s nejčasnější dobou ukončení mezi všemi intervaly protínajícími se EFT (I) J. Důkaz existence a jedinečnosti takového intervalu je uveden v předchozím příkladu.

Ukaž to h je dva ku jedné.

Předpokládejme rozpor h není dva ku jedné. Pak existují tři odlišné intervaly OPT (I), J1, J2, a J3, takový, že h mapuje každou z J1, J2, a J3 do stejného intervalu J '∈ EFT (I). Podle princip pigeonhole, byly namapovány nejméně dva ze tří intervalů J ' protože mají stejnou pracovní třídu jako J nebo proto J „je interval s nejčasnější dobou ukončení mezi všemi intervaly v EFT (I) protínajícími oba intervaly. Bez ztráty obecnosti předpokládejme, že tyto dva intervaly jsou J1 a J2.
Případ 1. Předpokládat J1 a J2 byly mapovány na J „protože mají stejnou pracovní třídu jako J '.
Pak každý J ', J1, a J2 mít stejnou třídu zaměstnání. To je rozpor, protože intervaly v optimálním řešení musí být přesto kompatibilní J1 a J2 nejsou.
Případ 2. Předpokládat J „je interval s nejčasnější dobou ukončení mezi všemi intervaly v EFT (I) protínajícími oba J1 a J2.
Důkaz tohoto případu je rovnocenný s důkazem v předchozím příkladu, který ukázal injektivitu. Z výše uvedeného důkazu vyplývá rozpor.

Proto, h mapuje ne více než dva odlišné intervaly ve formátu OPT (I) do stejného intervalu v EFT (I)a tak h je dva ku jedné. Argumentem nabíjení je nejčasnějším algoritmem doby dokončení algoritmus dvou aproximace pro problém plánování intervalu úloh.

Reference