Coping with Hardness Backtracking:suitable for those problems that exhibit good average time complexity.This methodology is based on a methodic examination of the implicit state space induced by the problem instance under study.In the process of exploring the state space of the instance,some pruning takes place. Randomized Algorithms:Based on the probabilistic notion of accuracy. a Approximation Algorithms:Compromise on the quality of solution in return for faster solutions
Coping with Hardness ◼ Backtracking: suitable for those problems that exhibit good average time complexity. This methodology is based on a methodic examination of the implicit state space induced by the problem instance under study. In the process of exploring the state space of the instance, some pruning takes place. ◼ Randomized Algorithms: Based on the probabilistic notion of accuracy. ◼ Approximation Algorithms: Compromise on the quality of solution in return for faster solutions
Backtracking In many real world problems,a solution can be obtained by exhaustively searching through a large but finite number of possibilities.Hence,the need arose for developing systematic techniques of searching,with the hope of cutting down the search space to possibly a much smaller space. Here,we present a general technique for organizing the search known as backtracking.This algorithm design technique can be described as an organized exhaustive search which often avoids searching all possibilities
Backtracking ◼ In many real world problems, a solution can be obtained by exhaustively searching through a large but finite number of possibilities. Hence, the need arose for developing systematic techniques of searching, with the hope of cutting down the search space to possibly a much smaller space. ◼ Here, we present a general technique for organizing the search known as backtracking. This algorithm design technique can be described as an organized exhaustive search which often avoids searching all possibilities
The 3-Coloring Problem Given an undirected graph G=(,E),it is required to color each vertex in Vwith one of three colors,say 1, 2,and 3,such that no two adjacent vertices have the same color.We call such a coloring legal;otherwise, if two adjacent vertices have the same color,it is illegal. A coloring can be represented by an n-tuple(G, G2,,Cn)such that c∈{1,2,3}，1≤kn. For example,(1,2,2,3,1)denotes a coloring of a graph with five vertices
The 3-Coloring Problem ◼ Given an undirected graph G=(V, E), it is required to color each vertex in V with one of three colors, say 1, 2, and 3, such that no two adjacent vertices have the same color. We call such a coloring legal; otherwise, if two adjacent vertices have the same color, it is illegal. ◼ A coloring can be represented by an n-tuple (c1 , c2 , …, cn ) such that ci{1, 2, 3}, 1in. ◼ For example, (1, 2, 2, 3, 1) denotes a coloring of a graph with five vertices
The 3-Coloring Problem There are 32 possible colorings (legal and illegal)to color a graph with n vertices. The set of all possible colorings can be represented by a complete ternary tree called the search tree. In this tree,each path from the root to a leaf node represents one coloring assignment. ■ An incomplete coloring of a graph is partia/if no two adjacent colored vertices have the same color. Backtracking works by generating the underlying tree one node at a time. If the path from the root to the current node corresponds to a legal coloring,the process is terminated (unless more than one coloring is desired)
The 3-Coloring Problem ◼ There are 3n possible colorings (legal and illegal) to color a graph with n vertices. ◼ The set of all possible colorings can be represented by a complete ternary tree called the search tree. In this tree, each path from the root to a leaf node represents one coloring assignment. ◼ An incomplete coloring of a graph is partial if no two adjacent colored vertices have the same color. ◼ Backtracking works by generating the underlying tree one node at a time. ◼ If the path from the root to the current node corresponds to a legal coloring, the process is terminated (unless more than one coloring is desired)
The 3-Coloring Problem If the length of this path is less than n and the corresponding coloring is partial,then one child of the current node is generated and is marked as the current node. If,on the other hand,the corresponding path is not partial,then the current node is marked as a dead node and a new node corresponding to another color is generated. If,however,all three colors have been tried with no success,the search backtracks to the parent node whose color is changed,and so on
The 3-Coloring Problem ◼ If the length of this path is less than n and the corresponding coloring is partial, then one child of the current node is generated and is marked as the current node. ◼ If, on the other hand, the corresponding path is not partial, then the current node is marked as a dead node and a new node corresponding to another color is generated. ◼ If, however, all three colors have been tried with no success, the search backtracks to the parent node whose color is changed, and so on