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:- konečná množina X={x1, x2, ... , xn} (proměnné)
- konečná množina W={w1, w2, ... , wn} (váhy proměnných)
- booleovská formule v proměnných x1, x2, ... , xn
Zkonstruujte ohodnocení Y={y1, y2, ... , yn} proněnných x1, x2, ... ,xn }tak, aby platilo:
- F(Y)=1 (formule je splněna)
- výraz w1x1+w2x2 + ... + wnxn nabýval maximální hodnoty (váha ohodnocení je nejvyssí možná)
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:- booleovská formule F proměnnných X=(x1, x2, ... , xn) v konjunktivní normální formě (tj. součin součtů).
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:- celé číslo n (počet věcí)
- celé číslo M (kapacita batohu)
- konečná množina V={v1, v2, ... ,vn } (hmotnosti věcí)
- konečná množina C={c1, c2, ... ,cn } (ceny věcí)
Zkonstruujte množinu X={x1, x2, ... ,xn }, kde každé xi je 0 nebo 1, tak, aby platilo:
- v1x1+v2x2 + ... + vnxn <= M (batoh nebyl přetížen).
- výraz c1x1+c2x2 + ... + cnxn nabýval maximální možné hodnoty (cena věcí v batohu byla maximální).
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:- celé číslo m (počet měst)
- konečná množina C={c1, c2, ... ,cm} (města)
- funkce vzdálenosti dist(ci, cj) pro každý pár ci, cj
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.