The difference between branch and anchor and best first search

Question

I study the thread and the related and best search for my dissertation, but I have found many contradictions on the Internet about these two concepts. At first, I thought that the branch and the connected one only prune branches that end in an expensive solution (using heuristics) and do not prioritize the search (do simple DFS or BFS on the rest of the tree after trimming). However, later I found a lot of resources that say that BB also evaluates states and considers nodes with a higher rank (priority search). If so, what is the difference between BB and search in the first place?

Answer 1

The 2 concepts are related (sometimes they can be combined), but you should just focus on the fundamental differences between them, as their names show:

The branch and associated space explore the search space using branching on variables (= check variable values). This creates several subtasks, for example. Branching on a binary variable creates a problem in which the variable = 0 and a problem in which it is 1. Then you can continue and solve them recursively. A “limiting” aspect of the technique is to evaluate the estimates of the solutions that can be achieved in the subtask. If the subtask can only give bad solutions (compared to the previously found solution), you can safely skip exploring this part of the search space.

It’s best to first try to find a solution as quickly as possible by looking at the most interesting part of the search space (most interesting = rating). It does not break up the search space, but only tries to reach // the solution as quickly as possible.

Both approaches attempt to skip exploration of parts of the search space. Their use and effectiveness depends on the configuration of the problem. First of all, you need to specify the criterion "the most interesting solution to study," which can sometimes be difficult / impossible. A branch and a border are interesting only if the estimate that you can put on the subtasks makes sense / not too wide. It depends on the problem you are considering ...