NPC problémy (obsah)

Problém batohu (0-1 knapsack problem) je úloha kombinatorické optimalizace, jejímž cílem je umístění podmnožiny předmětů (předmět má specifikován svoji cenu a váhu) do přepravky omezené kapacity (nosnosti) tak, aby cena nákladu byla maximální. Předměty nelze dělit – buď jsou v přepravce umístěny celé, nebo zde nejsou vůbec. Rozhodovací NP-úplná varianta problému řeší otázku, zda-li lze do batohu dané kapacity umístit podmnožinu daných předmětů ...

Nejkratší cesta Problém nejkratší cesty je NP-úplná grafová úloha, jejímž cílem je nalézt v zadaném grafu nejkratší cestu mezi uzly a . Rozhodovací varianta úlohy pak odpovídá na otázku, zda-li v daném grafu existuje mezi body a cesta délky maximálně . Problém nejdelší cesty Velmi podobným problémem je úloha nalezení nejdelší cesty, jejímž cílem je nalézt mezi body a cestu nejvyšší délky. V...

Problém obchodního cestujícího (Travelling salesman problem) je úloha kombinatorické optimalizace, jejíž cílem je nalézt v zadaném ohodnoceném úplném grafu kružnici takovou, že prochází všemi vrcholy a zároveň je její cena minimální. Jinými slovy se jedná o nalezení nejkratší hamiltonovské kružnice v ohodnoceném grafu. Motivace V dané zemi existuje mnoho měst, mezi všemi městy je postavené silnice. Cílem obchodního cestujícího je objet všechna ...