BCS401 Algorithms Module-5: Backtracking

Study Notes

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.

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.

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.

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.

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.

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.