В информатике , недетерминирован алгоритм является алгоритмом , который, даже тот же вход, может иметь различное поведение на различных трасс, в отличие от детерминированного алгоритма . Есть несколько способов, которыми алгоритм может вести себя по-разному от запуска к запуску. Параллельный алгоритм может выполняться по- разному на разных трассы из - за состояние гонки . Вероятностный алгоритм «S поведение зависит от генератора случайных чисел . Алгоритм, решающий задачу за недетерминированное полиномиальное времяможет выполняться с полиномиальным или экспоненциальным временем в зависимости от выбора, который он делает во время выполнения. Недетерминированные алгоритмы часто используются для поиска приближения к решению, когда точное решение было бы слишком дорого получить с помощью детерминированного.
Это понятие было введено Робертом В. Флойдом в 1967 году [1].
Используйте [ редактировать ]
Часто в теории вычислений термин «алгоритм» относится к детерминированному алгоритму . Недетерминированный алгоритм отличается от своего более известного детерминированного аналога своей способностью достигать результатов, используя различные пути. Если детерминированный алгоритм представляет единственный путь от входа к результату, недетерминированный алгоритм представляет один путь, ведущий ко многим путям, некоторые из которых могут приводить к одному и тому же выходу, а некоторые - к уникальным выходам. Это свойство математически зафиксировано в «недетерминированных» моделях вычислений, таких как недетерминированный конечный автомат . В некоторых сценариях все возможные пути могут выполняться одновременно.
При проектировании алгоритмов часто используются недетерминированные алгоритмы, когда проблема, решаемая алгоритмом, по своей сути допускает несколько результатов (или когда существует один результат с несколькими путями, по которым результат может быть обнаружен, каждый в равной степени предпочтительнее). Важно отметить, что каждый результат недетерминированного алгоритма действителен, независимо от того, какой выбор алгоритм делает во время работы.
В теории вычислительной сложности недетерминированные алгоритмы - это алгоритмы, которые на каждом возможном шаге могут допускать множественные продолжения (представьте себе человека, идущего по тропинке в лесу, и каждый раз, когда он шагает дальше, он должен выбирать, на какой развилке дороги он хочет принять). Эти алгоритмы не приводят к решению для каждого возможного вычислительного пути; однако они гарантированно придут к правильному решению для некоторого пути (т.е. человек, идущий через лес, может найти свою хижину, только если он выберет некоторую комбинацию «правильных» путей). Выбор можно интерпретировать как догадки в процессе поиска .
Большое количество проблем можно концептуализировать с помощью недетерминированных алгоритмов, включая самый известный нерешенный вопрос в теории вычислений, P vs NP .
Реализация недетерминированных алгоритмов с детерминированными [ править ]
Один из способов имитировать алгоритм недетерминированной N используя алгоритм детерминированного D является обработкой множеств состояний N как состояния D . Это означает, что D одновременно отслеживает все возможные пути выполнения N (см. Конструкцию powerset для этого метода, используемого для конечных автоматов ).
Другой - рандомизация , которая состоит в том, что все варианты выбора определяются генератором случайных чисел . Результат называется вероятностным детерминированным алгоритмом.
См. Также [ править ]
Ссылки [ править ]
- ^ Роберт W.Floyd (октябрь 1967). «Недетерминированные алгоритмы». Журнал ACM . 14 (4): 636–644. DOI : 10.1145 / 321420.321422 .
Дальнейшее чтение [ править ]
- Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). MIT Press. ISBN 978-0-262-03384-8.
- «Недетерминированный алгоритм» . Национальный институт стандартов и технологий . Проверено 7 июля 2013 года .
- «Недетерминированные алгоритмы» . Компьютерные науки Нью-Йоркского университета . Проверено 7 июля 2013 года .
