Недетерминированные алгоритмы: поведение и применение
Nondeterministic algorithm
Недетерминированные алгоритмы в программировании: поведение зависит от запуска, случайности или условий гонки. Различия в результатах при одинаковых данных.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм, поведение и результат которого могут зависеть от запуска.
Algorithm whose behavior and output may depend on the run
nondeterminism in computer programming
В компьютерном программировании недетерминированный алгоритм — это алгоритм, который, даже при одинаковом входном значении, может демонстрировать разное поведение при разных запусках, в отличие от детерминированного алгоритма. Существует несколько причин, по которым алгоритм может вести себя по-разному от запуска к запуску. Параллельный алгоритм может выполняться по-разному из-за возникновения состояния гонки. Поведение вероятностного алгоритма зависит от генератора случайных чисел. Алгоритм, решающий задачу за недетерминированное полиномиальное время, может выполняться за полиномиальное или экспоненциальное время в зависимости от выбора, сделанного в процессе выполнения. Недетерминированные алгоритмы часто используются для поиска приближенного решения, когда точное решение было бы слишком дорогостоящим для получения с помощью детерминированного алгоритма. Данное понятие было введено Робертом В. Флойдом в 1967 году.
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different runs due to a race condition. A probabilistic algorithm's behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution. The nondeterministic algorithms are often used to find an approximation to a solution, when the exact solution would be too costly to obtain using a deterministic one. The notion was introduced by Robert W. Floyd in 1967.
Использование
Часто в вычислительной теории термин "алгоритм" относится к детерминированному алгоритму. Недетерминированный алгоритм отличается от более привычного детерминированного аналога своей способностью достигать результатов различными путями. Если детерминированный алгоритм представляет собой единственный путь от входных данных к результату, то недетерминированный алгоритм представляет собой один путь, расходящийся на множество путей, некоторые из которых могут привести к одному и тому же результату, а другие – к уникальным результатам. Это свойство математически отражено в "недетерминированных" моделях вычислений, таких как недетерминированный конечный автомат. В некоторых случаях допускается одновременное выполнение всех возможных путей. При разработке алгоритмов недетерминированные алгоритмы часто используются, когда решаемая ими задача по своей природе допускает несколько возможных результатов (или когда существует единственный результат, к которому можно прийти по множеству равноценных путей). Важно отметить, что любой результат, выдаваемый недетерминированным алгоритмом, является допустимым, независимо от выбора, сделанного алгоритмом в процессе работы. В теории вычислительной сложности недетерминированные алгоритмы – это алгоритмы, которые на каждом шаге могут иметь несколько вариантов продолжения (представьте человека, идущего по тропинке в лесу, и на каждом шагу ему приходится выбирать, какую развилку выбрать). Эти алгоритмы не гарантируют нахождение решения по каждому возможному пути вычислений, однако гарантируют нахождение правильного решения хотя бы по одному из путей (то есть, человек в лесу сможет найти свою хижину, только выбрав определенную комбинацию "правильных" развилок). Выбор можно рассматривать как предположение в процессе поиска. Многие задачи можно представить в виде недетерминированных алгоритмов, включая самый известный нерешенный вопрос в теории вычислений – вопрос о равенстве классов P и NP.
Often in computational theory, the term "algorithm" refers to a deterministic algorithm. A nondeterministic algorithm is different from its more familiar deterministic counterpart in its ability to arrive at outcomes using various routes. If a deterministic algorithm represents a single path from an input to an outcome, a nondeterministic algorithm represents a single path stemming into many paths, some of which may arrive at the same output and some of which may arrive at unique outputs. This property is captured mathematically in "nondeterministic" models of computation such as the nondeterministic finite automaton. In some scenarios, all possible paths are allowed to run simultaneously. In algorithm design, nondeterministic algorithms are often used when the problem solved by the algorithm inherently allows multiple outcomes (or when there is a single outcome with multiple paths by which the outcome may be discovered, each equally preferable). Crucially, every outcome the nondeterministic algorithm produces is valid, regardless of which choices the algorithm makes while running. In computational complexity theory, nondeterministic algorithms are ones that, at every possible step, can allow for multiple continuations (imagine a person walking down a path in a forest and, every time they step further, they must pick which fork in the road they wish to take). These algorithms do not arrive at a solution for every possible computational path; however, they are guaranteed to arrive at a correct solution for some path (i. e., the person walking through the forest may only find their cabin if they pick some combination of "correct" paths). The choices can be interpreted as guesses in a search process. A large number of problems can be conceptualized through nondeterministic algorithms, including the most famous unresolved question in computing theory, P vs NP.
Реализация недетерминированных алгоритмов с детерминированными
Один из способов моделирования недетерминированного алгоритма N с помощью детерминированного алгоритма D — рассматривать множества состояний N как состояния D. Это означает, что D одновременно прослеживает все возможные пути вычисления N (см. построение множества степеней для применения этого метода к конечным автоматам). Другой способ — рандомизация, при которой все выборы определяются генератором случайных чисел. Результат называется вероятностным детерминированным алгоритмом.
One way to simulate a nondeterministic algorithm N using a deterministic algorithm D is to treat sets of states of N as states of D. This means that D simultaneously traces all the possible execution paths of N (see powerset construction for this technique in use for finite automata). Another is randomization, which consists of letting all choices be determined by a random number generator. The result is called a probabilistic deterministic algorithm.