Skip to main content.

WeightedSAT - Problém vážené splnitelnosti booleovské formule

Je dána booleovská formule F proměnnných X=(x1, x2, ... , xn) v konjunktivní normální formě (tj. součin součtů). Dále jsou dány celočíselné kladné váhy W=(w1, w2, ... , wn). Najděte ohodnocení Y=(y1, y2, ... , yn) proměnných x1, x2, ... , xn tak, aby F(Y)=1 a součet vah proměnných, které jsou ohodnoceny jedničkou, byl maximální.

Je dáno:

Zkonstruujte ohodnocení Y={y1, y2, ... , yn} proněnných x1, x2, ... ,xn }tak, aby platilo:

Pozn.: větší část definice je převzata ze stránek předmětu 36PAA

MaxSAT - Splnitelnost booleovské formule

Je dána booleovská formule v konjunktivní normální formě. Cílem je nalezení takového ohodnoceni proměnných, aby byla formule splněna. Pro některá zadání nemusí takové ohodnocení existovat, v tom případě je hledanám cílem ohodnocení, které splní maximální počet klauzulí dané formule.

Je dáno:

Nalezněte ohodnocení Y=(y1, y2, ... , yn) proměnných x1, x2, ... , xn tak, aby počet splněných klauzulí formule byl maximální.

Knapsack - Batoh

Je dána množina věcí (items), z nichž každá má přiřazenu hmotnost a cenu. Dále je dána maximální hmotnost batohu (kapacita). Cílem je nalézt takovou kombinaci věcí, které se do batohu "vejdou" (tj. jejich hmotnost nepřekročí kapacitu) a zárověň součet jejich cen bude nejvyšší možný.

Je dáno:

Zkonstruujte množinu X={x1, x2, ... ,xn }, kde každé xi je 0 nebo 1, tak, aby platilo:

Traveling Salesman Problem - Obchodní cestující

Je dáno m měst. Některá města jsou propojena silnicemi, délka silnic je známa. Úkolem obchodního cestujícího je navštívit všechna města a vrátit se do výchozího města. Cílem úlohy je nalézt takovou posloupnost měst, aby délka absolvované cesty byla minimální.

Je dáno: Zkonstruujte posloupnost π : [c1..cm] → [c1..cm] tak, aby součet:
dist(cπ(m), cπ(1)) + ∑dist(cπ(i), cπ(i+1))
byla minimální.

Find global minimum - hledání globálního minima

Úloha nespadá pod NP problémy! Implementoval jsem ji pro svoji jednoduchost a celkem vysokou vypovídací a didaktickou hodnotu o simulovaném ochlazování.

Je dána funkce implicitním předpisem y=f(x), nalezněte její minimum.