Scribd
Upload
53 views6 pages

Non Deterministic Algorithms

Non-deterministic algorithms can produce different outcomes for the same input across different runs, unlike deterministic algorithms which yield a single output. They are useful in solving problems with multiple possible solutions, such as the Subset Sum Problem and the Traveling Salesman Problem. These algorithms rely on guessing and checking various possibilities to find a valid solution, highlighting their non-deterministic nature.

Uploaded by

naresh20_mca
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
53 views6 pages

Non Deterministic Algorithms

Non-deterministic algorithms can produce different outcomes for the same input across different runs, unlike deterministic algorithms which yield a single output. They are useful in solving problems with multiple possible solutions, such as the Subset Sum Problem and the Traveling Salesman Problem. These algorithms rely on guessing and checking various possibilities to find a valid solution, highlighting their non-deterministic nature.

Uploaded by

naresh20_mca
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Non-deterministic algorithms

• 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.
• A nondeterministic algorithm is an algorithm that exhibits different
behaviors on different runs, as opposed to a deterministic
algorithm.
• Non-deterministic algorithms are used in solving problems which
allow multiple outcomes.
• Unlike a deterministic algorithm which produces only a single
output for the same input even on different runs, a non-
deterministic algorithm travels in various routes to arrive at the
different outcomes.
example
• Subset Sum Problem: Given a set of positive integers and a target sum,
determine whether there is a subset of the integers that adds up exactly to
the target sum.
• Nondeterministic Algorithm:
• Guess a subset of integers from the given set.
• Check if the sum of the guessed subset equals the target sum.
• If it does, accept the guess and output the subset.
• If it doesn't, guess another subset and repeat steps 2-3 until either a subset
that sums to the target is found or all possible subsets have been checked.
• In this algorithm, the process of guessing subsets is nondeterministic
because there's no systematic way to decide which subsets to try first. The
algorithm relies on a series of guesses and checks to eventually find a
solution. The nondeterminism arises from the guessing process rather than
any randomness inherent in the algorithm itself.
example
• Traveling Salesman Problem (TSP): Given a list of cities and the
distances between each pair of cities, find the shortest possible
route that visits each city exactly once and returns to the original
city.
• Nondeterministic Polynomial (NP) Algorithm:
• Guess a permutation of the cities to form a potential tour.
• Check if the guessed tour is valid (i.e., it visits each city exactly
once).
• If it is valid, calculate the total distance of the tour.
• If the total distance is shorter than the current best-known
solution, update the best-known solution.
• Repeat steps 1-4 until all possible permutations have been checked.

You might also like