Backjumping Algorithm

Backjumping Algorithm

The backjumping algorithm is a relative of the backtracking algorithm; other notable relatives include backmarking, forward checking, domain annihilation, and graph-based backjumping, respectively. The generic backtracking algorithm, also known as the Simple Backtracking Algorithm purpose is to decide whether a specific branch of a tree will lead to the best solution before it navigates down to the leaf (child) nodes. (Dr. D. K. Gupta, April 5, 2003)The backjumping algorithm attempts to back jump to the source of a bad solution, rather than the sequential backtracking as executed by the backtracking algorithms.

The main purpose of the backjumping algorithm is to create a situation where the occurrence of a failure is not guaranteed to be within the last two consecutively assigned nodes, but more likely that the occurrence of the failure has occurred within the nodes of a more recent node. In the immanence of a dead-end node, the backjumping algorithm navigates back to the most recent node that is attached to the present and most immanent dead-end node. Another fascinating attribute of the backjumping algorithm is its migrational ability with various searching algorithms. (Steiner, 2000)Backjumping can be basically added with minimum overhead to all search algorithms that are at least partially employ linear-space search and where the underlying domains meet certain (not too strict) criteria.

Another fascinating attribute of the backjumping algorithm is its migrational ability with various searching algorithms. (Steiner, 2000)Backjumping can be basically added with minimum overhead to all search algorithms that are at least partially employ linear-space search and where the underlying domains meet certain (not too strict) criteria.

At a junior level course, a lot of the materials about backjumping algorithms are a bit difficult to understand. Especially to copulate it into a one to two page report. To effectively inform the reader about backjumping algorithms, a strong summary of the backtracking algorithms would be needed. And then various backjumping algorithms would need to be discussed separately. General research was done through the Google web site and the AltaVista web site, respectively.

Bibliography