Non-deterministic algorithm

What is non-deterministic algorithm?

A nondeterministic algorithm is an algorithm that can exhibit different behaviors  on different runs, as opposed to a deterministic algorithm which will always produce the same output for a given input going through the same outputs A concurrent algorithm can perform differently on different runs due to a race condition. 

While a deterministic algorithm only produces a single output of the same input even on several different runs, a non-deterministic algorithm will travel through various routes, allowing it to reach multiple different outcomes. Non-deterministic algorithms are useful for finding approximate solutions when an exact solution is far too difficult or expensive to derive using a deterministic algorithm

 Non-deterministic models are primarily used when the problem that the algorithm s is solving has multiple outcomes or when there is a single outcome that can be found by going down multiple paths, and each of the paths that could be followed is equally preferable. These outcomes are valid irrespective of the choices and decisions that the algorithm makes while running and making an attempt to solve the problem.

‍

What is the non-deterministic algorithm example?

One example of a non-deterministic algorithm is the execution of concurrent algorithms with race conditions, which can exhibit different outputs on different runs. Unlike a deterministic algorithm which travels a single path from input to output, a non-deterministic algorithm can take many paths, with some arriving at the same outputs, and others arriving at different outputs. This feature is mathematically used in non-deterministic computation models like the non-deterministic finite automaton.

‍

‍

A non-deterministic algorithm is capable of execution on a deterministic computer that has an unlimited number of parallel processors. A non-deterministic algorithm usually has two phases and output steps. The first phase is the guessing phase, which makes use of arbitrary characters to run the problem.

The second phase is the verifying phase, which returns true or false for the chosen string. Many problems can be conceptualized with help of non-deterministic algorithms including the unresolved problem of P vs NP in computing theory.

Non-deterministic algorithms are used in solving problems that allow multiple outcomes. Every outcome the non-deterministic algorithm produces is valid, irrespective of the choices made by the algorithm during execution.

If you’re looking at computational complexity theory, non-deterministic algorithms are the algorithms that, at each possible step, have the ability to allow for multiple continuations. To visualize this, imagine a person walking down a path, and every time they take a step, they need to decide which fork in the road they would want to take. They don’t arrive at a solution for every possible computational path, but are guaranteed to arrive at a correct solution for some path

In Gaming, non-deterministic algorithms are quite widely used. One of the most popular uses of non-deterministic behavior in gaming AI is when the game engine makes use of non-deterministic AI techniques to enable a non-player character (NPC) to learn the behavioral patterns, moves, and tactics of the player and then adapt to counter these moves and tactics. This is particularly useful in combat games to introduce an element of unpredictability and make the game more interesting. When these techniques are used, the player faces novel scenarios, instead of having to get bored having to deal with the NPC pulling off the exact same moves, sometimes even in the same sequence every single time the player plays that game. This can be used to keep the player hooked to the game and increase the game’s play-life.

‍

‍

What is the difference between deterministic & non-deterministic algorithm?

‍

‍

Deterministic algorithms

In a deterministic algorithm vs non deterministic algorithm, for a given particular input, the computer will always produce the same output going through the same states but in the case of a non-deterministic algorithm, for the same input, the compiler may produce different output in different runs. In fact, non-deterministic algorithms can’t solve the problem in polynomial time and can’t determine what is the next step. The non-deterministic algorithms can show different behaviors for the same input on different execution and there is a degree of randomness to it.

Deterministic algorithms can be summed to these three points:

• For a particular input, the computer will give always the same output.
• Can solve the problem in polynomial time.
• Can determine the next step of execution.

Non-deterministic algorithms

To implement a non-deterministic algorithm, we have a couple of languages like Prolog but these don’t have standard programming language operators and these operators are not a part of any standard programming languages.

Non-deterministic algorithms can be summed to these three points:

• For a particular input, the computer will give different outputs on different execution.
• Can’t solve the problem in polynomial time.
• Cannot determine the next step of execution due to more than one path the algorithm can take.

‍