BCS401 Algorithms Module-5: Backtracking

Backtracking

• Backtracking involves an exhaustive search technique, generating all potential solutions to identify those meeting specific criteria.
• It constructs solutions incrementally, evaluating each partial solution to see if it can still lead to a valid complete solution.
• Backtracking is implemented using a state-space tree, representing choices made during the solution process.
• Nodes in the state-space tree are characterized as promising (potentially valid solutions) or non-promising (unable to lead to a complete solution).
• Backtracking commonly employs a depth-first search approach to explore potential solutions thoroughly before reverting to previous steps when dead ends are encountered.
• A complete solution can be found and returned, or the algorithm can continue searching for additional solutions if required.

N-Queens Problem

• The N-Queens problem tasks one with placing N queens on an N x N chessboard such that no two queens threaten each other.
• The backtracking algorithm positions queens row by row, trying various column placements while adhering to rules of no shared rows, columns, or diagonals.
• For example, solving the 4-Queens problem demonstrates backtracking by exploring different placements and reverting upon dead ends until a valid configuration is achieved.
• Solutions for n ≥ 4 can be found in linear time, with symmetry in board arrangements also leveraged to explore alternative solutions.

Sum of Subsets Problem

• The objective is to determine a subset of a set A = {a1,..., an} of n positive integers that totals to a given integer d.
• An instance example includes finding subsets of A = {1, 2, 5, 6, 8} summing to d = 9, which has the solutions {1, 2, 6} and {1, 8}.
• Sorting elements of the set aids in efficient solution finding and subset evaluation.

Decision vs Optimization Algorithms

• Optimization problems aim to find the best solution (e.g., minimal weight in traveling salesman).
• Decision problems focus on answering binary questions (e.g., whether a Hamiltonian cycle exists within a weight limit).
• Many problems exist in both forms, enabling transformation from decision to optimization.

NP-Complete and NP-Hard Problems

• P represents decision problems solvable by deterministic algorithms in polynomial time.
• NP refers to decision problems solvable by nondeterministic algorithms in polynomial time, implying P ⊆ NP.
• A problem is NP-complete if it belongs to NP, and every problem in NP is polynomially reducible to it, making it the hardest within NP.
• An illustration of an NP-complete problem is the CNF-satisfiability problem, where boolean variables must be assigned true/false to validate an expression.
• NP-hard problems are those that do not need to be solvable in polynomial time but are at least as hard as NP-complete problems.
• If any NP-complete problem can be solved in polynomial time, all NP problems can be solved in polynomial time, leading to the conjecture whether P = NP.

Additional Notes

• The relationship between P, NP, NP-Complete, and NP-Hard is fundamental in understanding computational complexity.
• The halting problem illustrates an NP problem that isn't NP-complete, emphasizing the complexities in categorizing problems within these classifications.
• Research continues into whether finding a polynomial-time solution for one NP-complete problem implies polynomial-time solutions for all NP problems.