Завдання по алгоритмам
Доброго дня. На першому курсі бакалаврату Академічного університету Новомосковскется річний курс алгоритмів. Кожна лекція супроводжується семінаром, на якому ми розбираємо алгоритмічні завдання. Практичні семінари проходять в невеликих групах. У цьому семестрі я Новомосковськ лекції та веду практику у одній з груп.
Сьогодні хочу поділитися з Вами двома завданнями з цих семінарів.
Завдання 1. На прямій дано n відрізків, потрібно вибрати максимальне за розміром підмножина непересічних.
Завдання 2. На окружності дано n дуг (відрізків), потрібно вибрати максимальне за розміром підмножина непересічних.
Перше завдання - один із прикладів на тему «жадібні алгоритми». Рішення можна подивитися внизу. Якщо коротко, передбачається рішення сортуванням за O (sort + n). Тут за sort я позначаю час на сортування масиву довжини n. До речі, sort - необов'язково nlogn (наприклад, bucket sort, radix sort, вхідні дані з обмеженого діапазону).
Друге завдання має гарне розподіл усіх рішення за O (sort + n). Не дивлячись на свою схожість на першу, друге завдання в лоб жадібністю не наважується. Вірніше особисто мені невідомо жадібне рішення, якщо хто-небудь з Новомосковсктелей придумає і поділиться, буду радий послухати. А щоб простіше було думати, я відразу опишу кілька непрацюючих ідей, найбільш часто спливаючих при спробах вирішувати цю задачу:
- Нехай на окружності є точка, не покрита ні одним відрізком, тоді коло можна розрізати в цій точці і отримати завдання про пряму, яку ми вже вміємо вирішувати!
Так. Але таких точок може не бути. Більш того, кожна точка кола може бути покрита 2, 10, або навіть Θ (n) відрізками - Розрізати коло по точці, покритої мінімальною кількістю відрізків!
Не працює. Уявіть собі 3 розбиття кола на 10 відрізків. Всього 30 відрізків. У двох з цих «розбиття» відрізки злегка накладаються один на одного. Нам потрібно вгадати третє з розбиття і точкою розрізу вибрати кінець одного з саме цих 10 відрізків. - Вигідно взяти у відповідь найкоротший відрізок!
Ні. Навіть на прямий вже не так: (0,49) (50,100) (48,51) - Вигідно викинути з безлічі найдовший відрізок, який когось перетинає!
Ні. Дивіться попередній приклад. - А ще.
Є багато непрацюючих ідей, зупинимо перерахування на вже озвучених.
рішення задач
Рішення завдання 1.
У кожного відрізка i є лівий кінець L [i] і правий кінець R [i]. Відсортуємо відрізки в порядку зростання R [i]. В такому порядку будемо перебирати відрізки. Черговий відрізок будемо додавати у відповідь, якщо його ліва межа більше максимуму правих меж вже доданих відрізків.
Рішення завдання 2.
Попереджаю, рішення довге і набагато складніше попереднього. З іншого боку принципово складних ідей тут немає, так що все можна зрозуміти без початкової підготовки.
Для початку скажемо, як задаються дуги на окружності. Нехай окружність - зациклений відрізок [0..M), а дуги (відрізки) окружності задаються парами L [i] .. R [i]. Якщо R [i]
Представляючи всі об'єкти на окружності, вирішувати завдання не дуже зручно. Тому, використовуючи прийом «подвоєння окружності», перейдемо на пряму.
1. Якщо у якогось відрізка R [i]
Тепер у нас є 2n відрізків на прямій, а окружність з розрізом в точці x відповідає відрізок цієї прямої [x..x + M), де 0 <= x Рішення завдання 2 за O (sort + n 2). Відсортувати один раз відрізки по правому кінця, потім перебрати n можливих точок розрізу R [i], вирішуючи для кожної завдання за O (n), так само як Задачу 1. Рішення завдання 2 за O (sort + nk). де k - розмір безлічі-відповіді на завдання. Залишимо сортування. Тепер зробимо цікаве спостереження: у залежності від точки розрізу розмір отриманого нами безлічі відрізняється від оптимального не більше ніж на 1. Тобто, якщо ми розрізали в першій-ліпшій точки і отримали безліч розміру k, нам досить знайти безліч розміру k-1, і воно точно буде оптимальним. Рішення: перебираємо перший відрізок, робимо k-2 кроків вперед за допомогою посилань next, якщо відстань між найправішій і найлівішій точкою менше M, ми знайшли k-1 непересічних дуг. Рішення за O (sort + n) Не завжди на певну тему досить вже готових завдань, регулярно доводиться придумувати нові. Тільки що ми спостерігали забавний ефект: беремо класичну просту задачу на сортування, замінюємо «пряму» на «коло», отримуємо складну задачу на метод двох покажчиків і вірогідну ідею. Багато красиві навчальні завдання так і придумуються. До речі, спробуйте вирішити ще два завдання:
А відразу після сортування скористаємося методом двох покажчиків і за O (n) для кожного відрізка i нарахуємо наступний відрізок next [i], який ми б взяли нашої жадібністю (жадібність: L [next [i]]> R [i], з таких next [i] = min).
Візьмемо раз випадкову точку i = random [0..n-1]. Для кожного i за O (k) спробуємо a = next [i], як в коді вище.
Оскільки, якщо відповідь з k-1 відрізків існує, нам достатньо було потрапити в якийсь один з цих k-1, то ймовірність того, що за спроб ми жодного разу не потрапили дорівнює при прагнуть до нескінченності. Зауважимо, що якщо = Θ (1), то попередній алгоритм за O (nk) нас повністю влаштовував. Тобто ми отримали імовірнісний алгоритм, час роботи якого O (sort + n). Щоб досягти кращої помилки e -T. досить спробувати ні. а точок, час роботи відповідно буде O (sort + Tn).
Завдання 3. Дано n відрізків на прямій, вибрати максимальне за розміром підмножина відрізків таке, що кожна точка покрита не більше ніж k раз (ми її тільки що вирішували для k = 1).
Завдання 4. Дано n дуг (відрізків) на колі ... і те ж саме завдання.Ще більше завдань