Недетермінований алгоритм
В інформатиці, недетермінований алгоритм це алгоритм, який передбачає декілька шляхів обробки одних і тих самих вхідних даних, без будь-якого уточнення який саме варіант буде обраний.
Використання
Часто в теорії алгоритмів, термін «algorithm» вказує на детермінований алгоритм. Недетермінований алгоритм відрізняється від свого відомішого двійника можливістю отримання результату декількома різними шляхами. Детермінований алгоритм передбачає єдиний шлях від вхідних даних до виходу, тоді як деякі шляхи виконання недетермінованого алгоритму можуть привести до однакового результату, а деякі до особливих результатів. Ці властивості описано математично в «недетермінованій» моделі обчислень, відомій як недетермінований автомат.
В розробці алгоритмів, недетерміновані алгоритми часто використовуються, коли задача, що розв'язується за допомогою алгоритму за своєю суттю дозволяє багато виходів (або коли існує один вихід з багатьма шляхами через які він може бути знайдений, при чому всі шляхи однаково добрі). Важливо, що кожен вихід недермінованого алгоритму правильний, незалежно від шляхів обраних алгоритмом під час виконання.
В теорії складності обчислень, недетермінований алгоритм є таким, що на кожному можливому кроці може бути декілька продовжень (уявіть людину, що простує лісом, кожного кроку вона повинна прийняти рішення, який шлях їй обрати далі). Такі алгоритми не видають розв'язок для кожного шляху обчислень; однак, вони гарантують отримання вірного розв'язку певним шляхом (наприклад, людина, що простує лісом може знайти свою хату, якщо обере певну комбінацію правильних шляхів). Вибори можна тлумачити припущення в процесі пошуку.
Велика кількість задач може бути осмислена через недетерміновані алгоритми, включно з найвідомішими нерозв'язаними питаннями в теорії обчислень, P = NP.
Реалізація недетермінованого алгоритму за допомогою детермінованого
Одним шляхом відтворення недетермінованого алгоритму N із детермінованим алгоритмом D це трактувати набір станів алгоритму N як стани D. Тобто D одночасно відслідковує всі можливі шляхи виконання N (дивись Детермінування скінченного автомата для використання цього прийому для скінченного автомата).
Другий шлях це ймовірнісний алгоритм. Результат називається ймовірнісний детермінований алгоритм.
Приклади
Приклад 1: Список покупок
Уявімо список покупок: список товарів для покупки.
Це можна осмислити двома способами:
- Як вказівку купити всі ці товари в будь-якому порядку. Це недетермінований алгоритм.
- Як вказівку купити всі ці товари в даному порядку. Це детермінований алгоритм.
Приклад 2: Сортування злиттям
Припустимо ми маємо набір речей (скажімо, 300 студентських робіт), які необхідно відсортувати (скажімо, за номерами студентів).
Один з алгоритмів для цього (що зветься сортування злиттям) наступний:
- розбити набір на дві приблизно рівних частини
- відсортувати обидві половини сортуванням злиттям (тобто рекурсивно)
- злити результати
Елементи можуть бути унікально відсортовані, якщо критерій сортування завжди визначає повний порядок; тобто номери студентів унікальні, але якщо сортувати іспити за прізвищами студентів і два студенти мають однакове прізвище, результат сортування залишається невизначеним. В таких випадках, сортування злиттям завжди буде видавати один з можливих вірних впорядкувань, але який саме, залишається невідомим, тобто алгоритм недермінований.
Приклад 3: Кістякове (покривальне) дерево
На вході неорієнтований зв'язний граф. Неорієнтований граф це набір вершин які можуть бути або не бути з'єднані ребрами. Підграф графа містить підмножину його вершин і ребер. Граф з'єднує дві вершини, якщо можна пройти по ребрах з одної вершини до іншої. Шлях в графі це найменший підграф, що з'єднує дві його вершини. Граф є зв'язним якщо він з'єднує всі свої вершини.
Алгоритм: допоки ребро можна видалити так, що граф залишається зв'язним, видалити це ребро.
Вихід: кістякове (покривальне) дерево, це такий підграф, який є деревом, що з'єднує всі вершини.
Кожен граф (який є зв'язним і не є деревом) має кілька кістякових дерев, тобто ми знов маємо приклад коли задача за своєю суттю дозволяє декілька вірних розв'язків, і обраний алгоритм видає один з них, але навряд чи ці розв'язки повторюватимуться.
Приклад 4: Тест простоти
Задача: дане натуральне число більше від одиниці, визначити чи є це число простим.
Недетерміністичний алгоритм наступний:
- Взяти будь-яке ціле k таке, що 2 ≤ k ≤ √(n).
- Якщо k є дільником n, зупинитись з відповіддю ні; інакше зупинитися з відповіддю не відомо.
Видно, що алгоритм не завжди дає корисну відповідь, але ніколи не дає хибної відповіді.
Цей алгоритм недетермінований, він видає повну відповідь не завжди, а тільки при певній комбінації виборів. Це є прикладом пошукового типу недетермінованого алгоритму.