Write short notes on Backtracking strategy Tractable and Intractable Problem

Question

Write short notes on  Backtracking strategy Tractable and Intractable Problem

Bipin Tiwari · Accepted Answer

Backtracking is a technique based on algorithm to solve problem. It uses recursive calling to find the solution by building a solution step by step increasing values with time. It removes the solutions that doesn’t give rise to the solution of the problem based on the constraints given to solve the problem. Backtracking algorithm is applied to some specific types of problems, Decision problem used to find a feasible solution of the problem. Optimisation problem used to find the best solution that can be applied. Enumeration problem used to find the set of all feasible solutions of the problem. In backtracking problem, the algorithm tries to find a sequence path to the solution which has some small checkpoints from where the problem can backtrack if no feasible solution is found for the problem. b)Tractable and Intractable Problem Tractable Problem: A problem that is solvable by a polynomial-time algorithm. The upper bound is polynomial. Here are examples of tractable problems (ones with known polynomial-time algorithms): – Searching an unordered list – Searching an ordered list – Sorting a list – Multiplication of integers (even though there’s a gap) – Finding a minimum spanning tree in a graph (even though there’s a gap) Intractable Problem: a problem that cannot be solved by a polynomial-time algorithm. The lower bound is exponential. From a computational complexity stance, intractable problems are problems for which there exist no efficient algorithms to solve them. Most intractable problems have an algorithm that provides a solution, and that algorithm is the brute-force search. This algorithm, however, does not provide an efficient solution and is, therefore, not feasible for computation with anything more than the smallest input. Examples Towers of Hanoi: we can prove that any algorithm that solves this problem must have a worst-case running time that is at least 2n − 1. * List all permutations (all possible orderings) of n numbers.

Write short notes on

Backtracking strategy

Tractable and Intractable Problem

Leave your Answer:

Hits Counter

Question

Write short notes on Backtracking strategy Tractable and Intractable Problem

Leave your Answer:

Write short notes on

Backtracking strategy

Tractable and Intractable Problem