backtracking

Also found in: Dictionary, Thesaurus, Medical, Wikipedia.

backtracking

[′bak‚trak·iŋ]

(computer science)

A method of solving problems automatically by a systematic search of the possible solutions; the invalid solutions are eliminated and are not retried.

backtracking

(algorithm)

A scheme for solving a series of sub-problems each of which may have multiple possible solutions and where the solution chosen for one sub-problem may affect the possible solutions of later sub-problems.

To solve the overall problem, we find a solution to the first sub-problem and then attempt to recursively solve the other sub-problems based on this first solution. If we cannot, or we want all possible solutions, we backtrack and try the next possible solution to the first sub-problem and so on. Backtracking terminates when there are no more solutions to the first sub-problem.

This is the algorithm used by logic programming languages such as Prolog to find all possible ways of proving a goal. An optimisation known as "intelligent backtracking" keeps track of the dependencies between sub-problems and only re-solves those which depend on an earlier solution which has changed.

Backtracking is one algorithm which can be used to implement nondeterminism. It is effectively a depth-first search of a problem space.

References in periodicals archive ?

CALL 09050 700 469 77P PER MIN ROI 1560 911 393 [euro]1.25 PER MIN PISCES FEBRUARY 20 - MARCH 20 Mercury is backtracking in your sign and making a bit of mischief so there are occasional flashes of stress over little but essential things that might disappear then reappear.

STARS WITH LYNNE EWART; Our Brilliant Astrologer Takes A Ook At What The Next Seven Days Hold For You

In addition to allowing greater computational efficiency, a multiple KDA organizes the data into independent tree structures, which is an advantage in a NN search when the number of backtracking is high.

A KD-tree-based nearest neighbor search for large quantities of data

"Backtracking [is] nice because it's very organized," he says." You organize it in such a way that you solve the problem in a specific order.

AI Association honors 'Classic Paper'

Mr Price told ministers at Commons question time: "Do you understand that in that community there is fear the Government may be backtracking on the scale of the project?"

Wales :Defence academy delayed

'This seems like another piece of backtracking by the First Minister.

Business project may be in danger

"We saw a significant backtracking at this summit in terms of real principles," says Michael Dorsey, a Sierra Club board member.

Rich vs. poor: not much sustainability at the World Summit. (Currents)

Backtracking inside the Beltway would add to the isthmus's dual challenges: slow growth and collapsing commodity prices.

Business Class. (Editor's Note)

This backtracking is best explained by a slow release of stress deep within the subduction zone, about 30 to 40 kilometers below Earth's surface, the researchers say.

Pacific Northwest stirred, not shaken

The International Monetary Fund and other donors have already suspended aid to Kenya because it suspects it of backtracking on its promised reforms.

US cracks its AGOA whip

WOLVERHAMPTON executives are backtracking on a suggestion that the course might use its extensive stabling and all-weather training facilities to become a self-contained racing unit during the foot and mouth crisis.

Crisis idea is discarded

While Steinberg seems conversant with most of the recent research supporting his provocative analysis of national backtracking on commitment to civil rights and their enforcement, he does leave some holes in his analysis.

Turning Back: The Retreat from Racial Justice in American Thought and Policy

Traipsing through its first months like a drunk in denial, unable to nominate an attorney general who was a) female and b) legal; mired in that gripping social issue rocking millions of American families--gays in the military; and backtracking on promises about Bosnia, China, and Haiti faster than you can say, "George Bush is a buffoon--we can do better," the Clintonites were in Gallup Poll free fall until they hired a Republican policy masseur.