Цілочисельна та дискретна оптимізація (гілок і меж; рюкзак, комівояжер)

📌 Про що ця тема

Тут перевіряють, як розвʼязувати задачі, де відповідь — ціле число або вибір «так/ні» (взяти предмет чи ні, яким шляхом їхати). Ключові поняття: цілочисельна оптимізація, метод гілок і меж, задача про рюкзак і задача комівояжера. Це класичні NP-складні задачі, для яких важливо розуміти ідею перебору з відсіканням.

📖 Головне

• Дискретна оптимізація — пошук найкращого рішення серед скінченної (часто величезної) множини варіантів, де змінні набувають лише цілих/дискретних значень.

• Повний перебір дає точну відповідь, але його складність експоненційна (O(2ⁿ) для рюкзака, O(n!) для комівояжера) — тому потрібні розумніші методи.

• Метод гілок і меж (branch and bound): весь простір рішень ділять на підмножини («гілки»), для кожної рахують оцінку (межу) найкращого можливого результату. Якщо межа гіршa за вже знайдене рішення — гілку відсікають, не перебираючи.

• Рюкзак (0/1 knapsack): є предмети з вагою wᵢ та цінністю vᵢ, рюкзак витримує вагу W. Треба набрати максимальну сумарну цінність, не перевищивши W. Кожен предмет або беруть повністю, або ні.

• Дробовий рюкзак (fractional) розвʼязують жадібно: сортують за vᵢ/wᵢ і беруть найцінніші за одиницю ваги. Для 0/1 жадібність не гарантує оптимум.

• 0/1 рюкзак точно розвʼязують динамічним програмуванням: dp[i][w] = макс. цінність з перших i предметів при обмеженні w.

• Комівояжер (TSP): знайти найкоротший замкнений маршрут, що проходить через усі міста рівно раз і повертається в початок.

• Для TSP застосовують гілки і межі, динамічне програмування (O(2ⁿ·n²)) або наближені методи (жадібний «найближчий сусід»).

🔢 Як це працює на прикладі

Рюкзак: W=10. Предмети: A(вага 5, цінність 10), B(4, 7), C(6, 9).

• Рахуємо vᵢ/wᵢ: A=2, B=1.75, C=1.5.

• Дробовий рюкзак: беремо A (5кг, 10), потім B (4кг, 7) → 9кг, цінність 17, лишилось 1кг → ще 1/6 C = +1.5 → 18.5.

• 0/1 рюкзак: варіант A+B = вага 9 ≤ 10, цінність 17. Варіант A+C = вага 11 > 10 — не можна. Отже оптимум 17 (A+B).

• Видно: дробове рішення (18.5) слугує «верхньою межею» для гілок і меж.

⚠️ Типові помилки

• Плутають дробовий і 0/1 рюкзак: жадібний алгоритм дає оптимум ТІЛЬКИ для дробового.

• Забувають, що в TSP маршрут замкнений — треба повернутись у старт.

• Вважають «найближчого сусіда» точним методом — це лише наближення, може дати не оптимум.

• Неправильно рахують складність: рюкзак — 2ⁿ, комівояжер — n! (а не навпаки).

• У гілках і межах відсікають гілку за неправильною межею (оцінка має бути оптимістичною, не гіршою за реальний максимум).

🎯 Що завчити напамʼять

• Рюкзак: перебір O(2ⁿ), ДП O(n·W).

• Комівояжер: перебір O(n!), ДП O(2ⁿ·n²).

• Дробовий рюкзак → жадібно за vᵢ/wᵢ.

• Гілки і межі = перебір + відсікання за оцінкою-межею.

• TSP — замкнений маршрут через усі вузли один раз.

🧠 Перевір себе

1. Для якої задачі про рюкзак жадібний метод дає точну відповідь?

2. Яка складність повного перебору для комівояжера з n містами?

3. Що означає «відсікти гілку» в методі гілок і меж?

Відповіді: 1 — для дробового (fractional) рюкзака; 2 — O(n!); 3 — не перебирати підмножину рішень, бо її оцінка-межа гірша за вже знайдений результат.