Алгоритми в програмуванні.

Сортування

Сортування є хорошим прикладом алгоритму, який часто використовується програмістами. Найпростіший спосіб впорядкувати групу елементів це почати з видалення найменшого елемента з групи, і поставити його першим. Потім видаляється другий за величиною елемент і ставиться другим і т.д. На жаль, час роботи цього алгоритму складає O (N2), а це означає, що потрібно багато часу пропорційне кількості елементів в квадраті. Якби нам довелося сортувати млрд. Елементів, то цей алгоритми б зажадав 1018 операцій. Якщо вважати що звичайні настільні ПК роблять приблизно 109 операцій в секунду, то будуть потрібні роки щоб закінчити сортування цього млрд. Елементів.

На щастя існує ряд більш досконалих алгоритмів, наприклад, швидке сортування (quicksort), пірамідальна сортування (heapsort) і сортування злиття (mergesort). Ці алгоритми мають час виконання O (N * Log (N)). Таким чином, число операцій необхідних для сортування млрд. Елементів скорочується до таких розумних меж, що навіть найдешевший настільний ПК здатний провести таке сортування. Замість млрд. В квадраті операцій (1018) ці алгоритми вимагають не менше 10 млрд. Операцій (1010), тобто в 100 млн. разів швидше.

Найкоротший шлях

Алгоритми пошуку найкоротшого шляху з однієї точки в іншу досліджуються вже протягом багатьох років. Прикладів прикладного застосування цих алгоритмів предостатньо, проте для простоти викладу будемо дотримуватися такої постановки: потрібно знайти найкоротший шлях з точки А в точку Б в місті з кількома вулицями і перехрестями. Існує багато різних алгоритмів для вирішення цього завдання і всі вони зі своїми перевагами і недоліками. Перш ніж ми заглибимося в їх вивчення, давайте розглянемо час виконання простого алгоритму перебором. Якщо алгоритм розглядає кожен можливий шлях від А до Б (який не утворює циклів) він навряд чи закінчиться при нашому житті, навіть якщо А і Б знаходяться в маленькому містечку. Час виконання цього алгоритму є експоненціальним, що позначається як O (CN) для деякого C. Навіть для малих значень C, CN стає астрономічним числом, коли N приймає помірно велике значення.

Один з найшвидших алгоритмів для вирішення цього завдання має час виполненіяO (E + V * Log (V)), де E число дорожніх сегментів, а V число перетинів. Алгоритм займе близько 2 секунд часу, для пошуку найкоротшого шляху в місті з 10000 перетинів і 20000 дорожніх сегментів (зазвичай буває близько 2 дорожніх сегментів на одне перетинання). Цей алгоритм відомий як алгоритм Дейкстри, він є досить таки складним і вимагає використання структури даних чергу з пріоритетом (priority queue). Однак в деяких випадках навіть такий час виконання є занадто повільним (взяти наприклад знаходження найкоротшого шляху від Нью-Йорка до Сан-Франциско - в США є мільйони перетинів), в таких випадках програмісти намагаються поліпшити час виконання з допомогою так званої евристики. Евристика - це наближене значення чогось, що має відношення до задачі. У задачі пошуку найкоротшого шляху, наприклад, може виявитися корисним знати, як далеко знаходиться точка від пункту призначення. Знаючи це можна розробити більш швидкий алгоритм (наприклад алгоритм пошуку А * в деяких випадках працює значно швидше ніж алгоритм Дейкстри). Такий підхід не завжди покращує час виконання алгоритму в найгіршому випадку, але в більшості реальних додатків алгоритм починає працювати швидше.

наближені алгоритми

Іноді навіть самий просунутий алгоритм з найбільш просунутою евристикою працює занадто повільно на найшвидшому комп'ютері. У таких випадках доводиться знижувати точність кінцевого результату. Замість того щоб намагатися отримати найкоротший шлях, можна обмежитися шляхом, який наприклад на 10% більше ніж найкоротший шлях.

Насправді є чимало важливих завдань, для яких відомі на сьогодні алгоритми видають оптимальний результат занадто повільно. Найбільш відома група з цих завдань називається NP (non-deterministic polynomial). Якщо завдання називається NP-повної або NP-важкою, то це означає, що ніхто не знає достатньо хорошого способу для отримання оптимального рішення. Крім того, якщо хтось розробить ефективний алгоритм для вирішення однієї NP-важкою завдання, то цей алгоритм можна буде застосувати до всіх NP-важких завдань.

Хорошим прикладом NP-важкою завдання є завдання комівояжера. Продавець хоче відвідати N міст, і він знає, скільки часу займає переміщення з одного міста в інший. Питання в тому наскільки швидко він зможе відвідати всі міста? Найшвидший з відомих алгоритмів для вирішення цього завдання є занадто повільним - і багато хто вважає, що так буде завжди - тому програмісти шукають досить швидкі алгоритми, що дають хороше рішення, але часто не оптимальне.

випадкові алгоритми

Ще один підхід, який застосовується для розв'язання деяких завдань, полягає в тому, щоб зробити алгоритм випадковим. Даний підхід не покращує час алгоритму в гіршому випадку, але досить часто добре працює в середньому випадку. Алгоритм швидкого сортування є хорошим прикладом використання рандомізації. У гіршому випадку, алгоритм швидкого сортування сортує групу елементів за O (N2), де N кількість елементів. Якщо в цьому алгоритмі використовувати рандомізацію, то шанси на найгірший випадок стають трохи малими, і в середньому випадку алгоритм швидкого сортування працює за час O (N * Log (N)). Інші алгоритми навіть в гіршому випадку гарантують час роботи O (N * Log (N)), проте вони повільніше в середньому випадку. Хоча обидва алгоритму мають час роботи пропорційний N * Log (N), алгоритм швидкого сортування має більш менший постійний коефіцієнт (constant factor) - тобто він вимагає C * N * Log (N), в той час як інші алгоритми вимагають більше 2 * C * N * Log (N) операцій.

Інший алгоритм, який використовує випадкові числа шукає медіану для групи чисел і його час роботи в середньому випадку становить O (N). Це набагато швидше в порівнянні з алгоритмом, який сортує числа і вибирає середнє, і працює за O (N * Log (N)). Існують детерміновані алгоритми (невипадкові) які дозволяють знайти медіану за час O (N), однак випадковий алгоритм простіше для розуміння і часто працює швидше цих детермінованих алгоритмів.

Основна ідея алгоритму пошуку медіани це вибрати серед чисел випадкове, і порахувати, скільки чисел в групі менше ніж вибране число. Припустимо, є N чисел, K з них менше або дорівнює обраному числу. Якщо K менше ніж половина N, тоді ми знаємо що медіана це (N / 2-K) -е число яке більше ніж випадково вибране число, так що ми відкидаємо K чисел менших або рівних випадковому числу. Тепер припустимо ми хочемо знайти (N / 2-K) -е найменше число, замість медіани. Алгоритм такий же, ми просто випадково вибираємо число і повторюємо описані кроки.

стиснення

Ще один клас алгоритмів призначений для стиснення даних. Цей алгоритм не має очікуваного результату (як наприклад, алгоритм сортування), але замість цього робиться оптимізація за деякими критеріями. У разі стиснення даних, алгоритм (наприклад, LZW) намагається зробити так щоб дані займали якнайменше байтів, але в той же час, щоб можна було розпаковувати їх до первісної форми. У деяких випадках цей тип алгоритмів використовує ті ж методи що і інші алгоритми, що призводить до хорошого результату, але неоптимальному. Наприклад, JPG і MP3 стискають дані таким чином, що кінцевий результат виходить більш низької якості, ніж оригінал, проте і розмір менше. MP3 стиск не зберігає кожну особливість оригінального аудіо файлу, але намагається зберегти достатньо деталей, щоб забезпечити прийнятну якість і в той же час значно скоротити розмір файлу. Формат JPG слід тим же принципом, але деталі істотно відрізняються, тому що метою є стиснення зображення, а не аудіо.

Навіщо потрібно знати всякі алгоритми

Щоб використовувати алгоритми належним чином, важливо знати всі згадані типи алгоритмів. Якщо вам доведеться розробляти важливу частину програмного забезпечення, то ви повинні бути в змозі оцінити швидкість роботи вашого алгоритму. Точність вашої оцінки залежить від того наскільки ви володієте аналізом часу виконання алгоритмів. Крім цього, необхідно знати деталі алгоритмів, що дозволить передбачати особливі випадки, в яких програма не працюватиме швидко, або буде давати неприйнятні результати.

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

Як приклад можна розглянути, як працюють мережеві комутатори. Комутатор має N підключених до нього кабелів, і приймає пакет даних, що надходять з цих кабелів. Комутатор повинен спочатку проаналізувати пакети, а потім відправити їх назад по правильному кабелю. Комутатор також як і комп'ютер працює в дискретному режимі - пакети відправляються дискретними інтервалами, а не безперервно. Швидкий комутатор прагне послати, як можна більше пакетів протягом кожного інтервалу інакше вони накопичаться і комутатор "впаде". Мета алгоритму відправляти максимальну кількість пакетів протягом кожного інтервалу, а також забезпечити порядок, при якому пакети, що прийшли раніше за інших відправлялися теж раніше інших. В цьому випадку виявляється, що для вирішення цього завдання підходить алгоритм відомий як "stable matching", хоча на перший погляд це може бути не очевидно. Такі зв'язки між завданням і рішенням можна виявити тільки за допомогою вже наявних алгоритмічних знань.

реальні приклади

Прикладів рішень реальних завдань вимагають новітніх алгоритмів предостатньо. Майже все, що ви робите на комп'ютері залежить від алгоритмів, які хтось дуже довго розробляв. Навіть найпростіших програм не існувало б без алгоритмів, які працюють "за сценою" керуючи пам'яттю і завантажуючи дані з жорсткого диска.

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

Алгоритм пошуку максимального потоку

Завдання пошуку максимального потоку полягає в тому, щоб за допомогою наявної мережі найкращим чином перемістити щось з одного місця в інше. Саме така проблема вперше виникла в 1950-х у зв'язку із залізничними коліями Радянського Союзу. США хотіли знати, як швидко Радянський Союз може підвозити матеріали до держав-сателітів в Східній Європі через свою мережу залізниць.

Кроме того США Хотіли знати якові часть рейок можна найбільш легко зніщіті щоб відрізаті держави-сателіті від решті Радянського Союзу. Виявилося, що ці два завдання тісно пов'язані і що рішення задачі пошуку максимального потоку також вирішує завдання про мінімальний розрізі, що, в кінцевому рахунку, дозволить з'ясувати найдешевший спосіб відрізати Радянський Союз від своїх супутників.

Перший ефективний алгоритм для пошуку максимального потоку був придуманий вченими Фордом і Фалкерсоном. Алгоритм згодом був названий алгоритмом Форда - Фалкерсона і є одним з найбільш відомих алгоритмів в області комп'ютерної науки. В останні 50 років алгоритм зазнав ряд поліпшень, що зробило його швидше (правда, деякі з цих поліпшень лякають своєю складністю).

Оскільки завдання було чітко поставлено, виявилося безліч різних застосувань. Алгоритм безпосередньо пов'язаний з Інтернетом, де важливо транспортувати максимум даних з однієї точки в іншу. Завдання також виникає в безлічі бізнес-процесів, і є важливою частиною дослідження операцій. Наприклад, якщо є N співробітників і N завдань, які повинні бути зроблені, але не кожен співробітник може впоратися з кожним завданням, то пошук максимального потоку видасть рішення, як призначити N співробітників на завдання таким чином, щоб кожна задача була виконана за умови що це можливо. Завдання Graduation з TopCoder SRM 200является хорошим прикладом завдання на пошук максимального потоку.

порівняння послідовностей

Багатьом кодерам за всю свою кар'єру жодного разу не доводилося реалізовувати алгоритм, який використовує динамічне програмування. Проте, динамічне програмування застосовується в ряді важливих алгоритмів. Один з алгоритмів це знаходження відмінностей між двома послідовностями, який більшість програмістів напевно використовували, хоча можливо і не розбиралися в ньому. Цей алгоритм обчислює мінімальну кількість вставок, видалень, редагувань необхідних для перетворення послідовність A в послідовність B.

Наприклад, розглянемо послідовності "AABAA" і "AAAB". Для перетворення першої послідовності в другу найпростіше, що потрібно зробити це видалити B в середині і змінити останню A на B. Цей алгоритм має безліч застосувань, включаючи деякі завдання пов'язані з ДНК і виявленням плагіату. Однак багато програмістів використовують його в основному для порівняння версій одного і того ж файлу з вихідним кодом. Якщо елементи послідовності це рядки в файлі, той цей алгоритм дозволяє дізнатися які рядки треба видалити, вставити, змінити щоб перетворити одну версію файлу в іншу.

Без динамічного програмування доводиться перебирати експоненціальне число перетворень, щоб перейти від однієї послідовності до іншої. Однак динамічне програмування скорочує час виконання алгоритму до O (N * M), де N і M кількість елементів в двох послідовностях.

Висновок

Скільки існує різних завдань, стільки існує і різних алгоритмів для їх вирішення. Проте є велика ймовірність того що завдання яку ви намагаєтеся вирішити в деякому сенсі схожа на іншу задачу. Розвиваючи глибоке розуміння широкого діапазону алгоритмів, ви зможете вибрати вірний алгоритм і застосувати його для вирішення завдання. Крім того рішення задач в змаганнях на TopCoder допоможе вам відточити свої навички в цій області. Багато з цих завдань здаються штучними і не реалістичними, але вони вимагають такого, ж набору алгоритмічних знань який потрібно кожен день в реальному світі.

ПОСИЛАННЯ по темі