Question

Backtracking search is not typically considered a heuristic search. However, it contains some elements which could make the approach considered a heuristic search. Examine both backtracking and heuristic search to compare and contrast the two approaches. Be sure to examine aspects of the backtracking search approach that would include it in and excluded it from a heuristic-based classification.

non complex nswers necessary

Answer 1

Backtracking Search

Backtracking is an algorithmic-method for taking care of issues recursively by attempting to assemble an answer steadily, one piece at a time, eliminating those arrangements that neglect to fulfill the limitations of the issue at any time of time. Or you can say, Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem .

The image below will help you clear the above definitions.

  

The backtrack recursive tree

HEURISTIC SEARCH

A Heuristic is a technique to solve a problem faster than classic methods, or to find an approximate solution when classic methods cannot. This is a kind of a shortcut as we often trade one of optimality, completeness, accuracy, or precision for speed. A Heuristic (or a heuristic function) takes a look at search algorithms. At each branching step, it evaluates the available information and makes a decision on which branch to follow. It does so by ranking alternatives. The Heuristic is any device that is often effective but will not guarantee work in every case.

Now to bring the contrast between these two approaches.

The Backtracking Heuristic (BH) methodology consists of constructing blocks of items by a combination of heuristics, that solve mathematical programming models and backtrack search algorithms to figure out the best heuristics and their best ordering. BH has been recently introduced in the literature in order to solve three-dimensional Knapsack Loading Problems, showing promising results. In the present Work, we apply the same methodology to solve constrained two-dimensional Guillotine cutting problems. In order to assess the potentials of this novel version also for cutting problems, we conducted computational experiments on a set of difficult and well-known benchmark instances.

The schematic representation of this algorithm is shown below

Explanation:-

Schematic representation of the backtracking heuristic to find most probable paths from a source concept s to a target t . (a) Assume a network with source and target concepts. For clarity, the nodes are ordered by their accessibility from s (leftmost nodes are most accessible, rightmost nodes least accessible). (b) As a first step in the backtracking process, we find the neighbors of the target t , leading in the direction of the source, that is, the neighbors of t with highest accessibility with respect to s . (c) The paths from the target are repeatedly expanded to include highly accessible nodes leading toward the source concept. Pruning of least probable paths keeps the growing set of paths to a workable size (not shown). (d) Most probable paths that arrive in the source (continuous lines) are considered as functional hypotheses linking the target to the source concept. Unfinished paths (dashed paths) continue being expanded until k paths between s and t have been found.

If you come across any doubt feel free to ask in the comments box below. I will be happy to help.

Thank You.

ALL THE BEST!.