|
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate ''c'' ("backtracks") as soon as it determines that ''c'' cannot possibly be completed to a valid solution.〔(【引用サイトリンク】 title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms )〕 The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of ''k'' queens in the first ''k'' rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned. Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test. Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog. Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s. The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility. ==Description of the method== The backtracking algorithm enumerates a set of ''partial candidates'' that, in principle, could be ''completed'' in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of ''candidate extension steps.'' Conceptually, the partial candidates are represented as the nodes of a tree structure, the ''potential search tree.'' Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further. The backtracking algorithm traverses this search tree recursively, from the root down, in depth-first order. At each node ''c'', the algorithm checks whether ''c'' can be completed to a valid solution. If it cannot, the whole sub-tree rooted at ''c'' is skipped (''pruned''). Otherwise, the algorithm (1) checks whether ''c'' itself is a valid solution, and if so reports it to the user; and (2) recursively enumerates all sub-trees of ''c''. The two tests and the children of each node are defined by user-given procedures. Therefore, the ''actual search tree'' that is traversed by the algorithm is only a part of the potential tree. The total cost of the algorithm is the number of nodes of the actual tree times the cost of obtaining and processing each node. This fact should be considered when choosing the potential search tree and implementing the pruning test. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Backtracking」の詳細全文を読む スポンサード リンク
|