Problém dvou loupežníků

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]