Problém dvou loupežníků

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

Problém dvou loupežníků jak rozdělit kořist (oceněné věci) mezi 2 loupežníky, aby dostali oba věci ve stejné hodnotě. Jde o NP-úplný problém.

Praktický příklad[editovat | editovat zdroj]

Mějme zadáno N čísel. Otázka zní: lze rozdělit zadaná čísla 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 N oceněných věcí). Pokud je čísel málo, pak lze najít řešení 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ř. N = 50, pak stavový prostor neprojdeme v rozumném čase ani na nejlepším počítači.