valikuprobleemid

Valikuprobleemid on probleeme, kus eesmärk on valida üks või mitu elementi või lahenduste hulka, et saavutada antud piirangute piires parim tulemus. Need võivad olla nii otsustusprobleemid kui ka optimeerimisprobleemid: otsustusprobleem küsib jah/ei vastust, kas kehtib teatud tingimus; optimeerimisprobleem otsib parimat võimalikku lahendust eesmärgiga maksimeerida või vähendada mõni väärtus. Sageli kaasneb piirangute hulk—ressursid, aeg, eelarve, tööjõud või materjalid—ning valikuprobleemide lahendused annavad strateegilise või operatiivse otsuse.

Näited hõlmavad nii klassikalisi kui praktilisi ülesandeid: 0/1 knapsack probleem (maksimeerida väärtus antud kaalupiirangus), travelling salesman problem (reisija müüja probleem), set cover problem (hulgkatmise probleem) ning erinevad ajastamise ja ressursijaotuse ülesanded tootmises või logistikas.

Meetodid ja lähenemisviisid: valikuprobleeme lahendatakse erinevate algoritmidega, sealhulgas dünaamiline programmeerimine, greedy meetodid, backtracking, branch-and-bound ning lineaar- või mitteliniaarprogrammimise (LP/ MILP) meetodid, kui probleem sobib kontinuaalsete muutujate või lineaarsete tingimustega.

Keerukus ja praktika: paljud valikuprobleemid on NP-hard või NP-complete, mistõttu suurte sisendite korral täisjuhendatud lahendus võib olla ebaühtlane. Seetõttu kasutatakse tihti heuristikuid, approximatsioonimeetodeid ja probleemi spetsiifikast sõltuvaid lähenemisi.

Seotud mõisted: optimeerimisprobleemid, otsustusprobleemid, algoritmid, heuristikat.