Жадібні алгоритми. Частина 1

Задача про розклад уроків 📚

Уявімо, що у нас є навчальний клас, у якому треба провести якомога більшу кількість уроків.

Провести всі уроки в класі не вийде, адже деякі з них пересікаються за часом.

Основною умовою є проведення у класі якомога більше уроків. Як обрати уроки, щоб отриманий набір виявився найбільшим із усіх можливих?
На допомогу приходить жадібний алгоритм. Працює він наступним чином:
1. Обрати урок, який закінчується раніше за всі інші. Це перший урок, який буде проведено в класі.

  1. Наступним кроком необхідно обрати урок, який починається по завершенню першого уроку. І знову необхідно обрати урок, який закінчується раніше за інші. Він буде другим у розкладі.

  2. Продовжувати виконувати 2 крок алгоритму допоки не закінчиться список уроків - і ви отримаєте відповідь!

Спробуємо використати алгоритм на нашому прикладі. Ми можемо побачити, що малювання закінчується раніше за всі інші уроки ( о 10:00), тому його ми й оберемо першим уроком.

Тепер необхідно знайти наступний урок, який починається після 10:00 і закінчується раніше за всі інші.

Англійська мова відпадає, бо її початок пересікається з малюванням. Проте математика підходить. Нарешті, інформатика має перетин із математикою, а ось музика може бути третім уроком.

Отже, розклад матиме наступний вигляд:

Жадібний алгоритм достатньо простий: на кожному кроці він обирає оптимальний варіант. У нашому прикладі, він обирає предмет, який завершиться раніше за всі інші. В технічній термінології: на кожному кроці обирається локально-оптимальне рішення, а, як результат, ви отримуєте глобально-оптимальне рішення. Цей алгоритм знаходить оптимальне рішення задачі зіставлення розкладу.

Поділись своїми ідеями в новій публікації.
Ми чекаємо саме на твій довгочит!
@yllbnts
@yllbnts@yllbnts

184Прочитань
1Автори
4Читачі
На Друкарні з 11 березня

Більше від автора

  • Жадібні алгоритми. Фінальна 3 частина

    Викоритання жадібних алгоритмів для вирішення NP-повних задач на прикладі задачі про комівояжера ( фургон Нової Пошти )

    Теми цього довгочиту:

    Programming
  • Жадібні алгоритми. Частина 2

    Чому жадібні алгоритми не завжди працюють на прикладі Шахрая із Дори-мандрівниці.

    Теми цього довгочиту:

    Programming

Вам також сподобається

Коментарі (0)

Підтримайте автора першим.
Напишіть коментар!

Вам також сподобається