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

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

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

Это понятие было введено Роберт В. Флойд в 1967 г.[1]

Использовать

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

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

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

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

Реализация недетерминированных алгоритмов с детерминированными

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

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

Смотрите также

использованная литература

  1. ^ Роберт Флойд (октябрь 1967). «Недетерминированные алгоритмы». Журнал ACM. 14 (4): 636–644. Дои:10.1145/321420.321422.

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