Недетерминированный алгоритм

Эта статья о недетерминизме в компьютерном программировании . Для недетерминизма в теории сложности вычислений см. Недетерминированную модель вычислений .

В компьютерном программировании — недетерминированный алгоритм это алгоритм , который даже для одних и тех же входных данных может демонстрировать различное поведение при разных запусках, в отличие от детерминированного алгоритма . Существует несколько причин, по которым алгоритм может вести себя по-разному от запуска к запуску. Параллельный алгоритм может работать по-разному при разных запусках из-за состояния гонки . Поведение вероятностного алгоритма зависит от генератора случайных чисел . Алгоритм, который решает задачу за недетерминированное полиномиальное время, может работать за полиномиальное или экспоненциальное время в зависимости от выбора, который он делает во время выполнения. Недетерминированные алгоритмы часто используются для поиска приближения к решению, когда получение точного решения с использованием детерминированного решения было бы слишком дорогостоящим.

Это понятие было введено Робертом Флойдом в 1967 году.

Используйте

Часто в теории вычислений термин «алгоритм» относится к детерминированному алгоритму . Недетерминированный алгоритм отличается от своего более знакомого детерминированного аналога способностью достигать результатов, используя различные маршруты. Если детерминированный алгоритм представляет собой один путь от входа к результату, то недетерминированный алгоритм представляет собой один путь, ведущий к множеству путей, некоторые из которых могут привести к одному и тому же выходу, а некоторые из которых могут прийти к уникальным результатам. Это свойство математически фиксируется в «недетерминированных» моделях вычислений, таких как недетерминированный конечный автомат . В некоторых сценариях все возможные пути могут работать одновременно.

При разработке алгоритмов недетерминированные алгоритмы часто используются, когда проблема, решаемая алгоритмом, по своей сути допускает несколько результатов (или когда существует один результат с несколькими путями, с помощью которых результат может быть обнаружен, каждый из которых одинаково предпочтителен). Важно отметить, что каждый результат, который дает недетерминированный алгоритм, действителен, независимо от того, какой выбор алгоритм делает во время работы.

В теории сложности вычислений недетерминированные алгоритмы — это алгоритмы, которые на каждом возможном шаге могут допускать множественные продолжения (представьте себе, что человек идет по тропинке в лесу, и каждый раз, когда он делает шаг дальше, он должен выбрать, какую развилку дороги он хочет взять). Эти алгоритмы не позволяют найти решение для каждого возможного вычислительного пути; однако они гарантированно придут к правильному решению для некоторого пути (т. е. человек, идущий по лесу, может найти свою хижину только в том случае, если он выберет некоторую комбинацию «правильных» путей). Выбор можно интерпретировать как догадку в процессе поиска .

Большое количество проблем можно концептуализировать с помощью недетерминированных алгоритмов, включая самый известный нерешенный вопрос в теории вычислений, P против NP .

алгоритмов с

Один из способов симулировать недетерминированный алгоритм N с помощью детерминированного алгоритма D рассматривать наборы состояний N как состояния D. — Это означает, что D одновременно отслеживает все возможные пути выполнения N (см. построение набора мощности для этого метода, используемого для конечных автоматов ).

Другой метод — рандомизация , который заключается в том, что все варианты выбора определяются генератором случайных чисел . Результат называется вероятностным детерминированным алгоритмом.

См. также

• Недетерминированная машина Тьюринга
• Недетерминированное программирование

Дальнейшее чтение

• Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). МТИ Пресс. ISBN  978-0-262-03384-8 .
• «Недетерминированный алгоритм» . Национальный институт стандартов и технологий . Проверено 7 июля 2013 г.
• «Недетерминированные алгоритмы» . Информатика Нью-Йоркского университета . Проверено 7 июля 2013 г.