Problém dvou loupežníků
Problém dvou loupežníků je v matematické informatice NP-úplný problém, jak rozdělit kořist (oceněné věci) mezi dva loupežníky tak, aby lup byl rozdělen rovným dílem (součet hodnot věcí v jedné skupině byl roven součtu hodnot věcí v druhé skupině).
Praktický příklad
Mějme zadáno čísel. Otázka zní: Lze zadaná čísla rozdělit do dvou skupin tak, aby součet čísel v obou skupinách byl stejný (tj. aby se dva loupežníci mohli spravedlivě rozdělit o kořist oceněných věcí)?
Pokud je čísel málo, řešení lze nalézt celkem snadno — pomocí prozkoumání všech možných rozdělení čísel do dvou skupin. Počet možných rozdělení do dvou skupin však roste exponenciálně, a pokud bychom si vzali např. , pak stavový prostor v rozumném čase neprojdeme ani na výkonném počítači.
Související články
- NP-úplnost
- Stavový prostor
![]() | Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |