Page 84 - 4495

елементи видалити з відношення – то обмеження стане стиснутим
(tightened).

Проблема оптимізації

Поряд з класичними методами пошуку можна застосовувати та-
кож додаткові методи дослідження простору рішень. У більшості ви-
падків задача полягає в пошуку одного розв’язку, всіх розв’язків чи

деякого найкращого розв’язку щодо заданого критерію. Пошук таких
розв’язків здійснюється в контексті оптимізаційної проблеми
(optimization problem) (чи більш точно оптимізаційної проблеми задо-
волення обмежень (constraint satisfaction optimization problem))

Означення 5. Цільовою функцією F - вважається функція, що
задає відображення змінних V в деяку впорядковану множину W .
Підмножина мінімальних значеннь W згідно з відношенням впоряд-

кування w вважається цільовою множино відображення.
Як оптимізаційну проблему можна розглядати класичну CSP за-
дачу з введеною цільовою функцією F .
Згідно з такою постановкою оптимізаційної проблеми вважаєть-

ся, що присвоєння  є більш бажаним за присвоєння  , якщо значен-
ня цільової функції для  є меншим від значення для  , тобто,

F  F .
Оптимальним розв’язком згідно з таким формулюванням вважа-
ється такий розв’язок  що не існує жодного розв’зку з меншим зна-
ченням цільової функції.

Часто цільова функція – це вираз, що оцінює дійсні числа і зна-
чення якого потрібно мінімізувати. Проблема максимізації дуже про-
сто трансформується в еквівалентну мінімізаційну проблему простою

заміною цільової функції F на негативну. Однак, наше загальне озна-
чення також включає складені критерії оптимізаційної проблеми. У
такій постановці проблеми впорядкування можливо багато-вимірної
множини W повинно бути означене більш-детально.

Введення означення можливого розв’язку дозволяє розглядати
також суб-оптимальні розв’язки. Такі розв’язки можуть мати значен-
ня цільової функції, що обмежені деяким граничним значенням.

Іноді деякі вимоги (обмеження) можуть бути суперечливими, що
ускладнює вибір будь-якого розв’язку. Після послаблення деяких об-
межень в надобмеженій проблемі, вона може бути трансформована в
оптимізаційну проблему де цільова функція може виражати деяку ін-

терпретацію в плані пошуку найкращого можливого рішення.

84