The two algorithms are similar in that they are both algorithms for searching on a spatial tree T. In general, the objective of branch bound method and backtracking method is different. The backtracking method obtains all the solutions satisfying the constraint conditions in T, while the objective of the branch bound method is to find a solution satisfying the constraint conditions, or to find the solution (optimal solution) that makes a certain objective function value reach the extreme value among the solutions satisfying the constraint conditions.

Branch bound algorithm

Essentially traversing the search space tree T with breadth first, only concerned with getting the optimal solution for a given function. If the algorithm finds a solution with a cost of n, when there is a partial solution, its cost > n, then the decomposition will not be extended to further explore its cost

The basic idea

Every active node has only one chance to be called an extension node. Once the active node becomes an extension node, all the son nodes will be generated at one time, and then the son nodes whose cost is greater than N will be deleted, and the remaining son nodes will exist as active nodes. This process is repeated until either an optimal solution is found or no active nodes exist

Pruning strategy

When searching for a node, it will first estimate the solution of the target (pre-estimation), and then determine whether to continue searching (the node with the least loss is selected for retrieval).

Commonly used method

Queue type (FIFO) branch bound method: using ordinary queues, nodes that are placed in the queue are taken out in breadth-first traversal order

Priority queue (PQ) branch bound method: the heap or queue sorted by priority using overwrite comparison is not first-in-first-out, it is the best first

Backtracking algorithm

In essence, it is a decision tree depth-first traversal problem, which uses an exhaustive approach, but it can avoid invalid search by adding pruning strategy in the process of implementation

The basic idea

Each node changes from an extended node to an inactive node only after traversing all the child nodes in turn. Key points: path (already made), choice list (currently available), end condition (reached the bottom of the decision tree, no more choices can be made)

Pruning strategy

  • Constraint function: Cut the invalid selection subtree that does not meet the constraint condition at the node that can produce sub-selection
    • Explicit constraint: Imposes direct constraints on the selection
    • Implicit constraint: To impose indirect constraints on choices through the interaction of other factors
  • Bounding function: Subtract subtrees that do not have the optimal solution (need to predict in advance or use estimates)

Back in the framework

recursive

# N Queen problem
result = []
def backtrack(Path, select list) :
    ifEnd conditions are met: result.add(path)return

    forchooseinSelect list: Make select backtrack(path, select list) unselectCopy the code

The iteration

def backtrack() :
	result = []
	ifThe end condition is not met:forchooseinSelection list:ifSatisfy constraint or limit condition: result.add(path)else: Continue searching downelse: Reaches the bottom, go back to the previous layer and select againCopy the code

A subset of the tree

# 0-1 knapsack problem [How many eligible subsets are there in a set of N numbers (pattern mining)]
def backtrack(Path, select list) :
	ifEnd conditions are met: result.add(path)else:
		forchooseinSelection list:ifSatisfies a constraint or bounding condition: backtrack(path, select list)# Go to the next levelCancel the choiceCopy the code

Arrange the tree

# Traveling Salesman problem
def backtrack(Path, select list) :
	ifEnd conditions are met: result.add(path)else:
		forchooseinSelection list: Make choicesifSatisfies a constraint or bounding condition: backtrack(path, select list)# Go to the next levelTo make a choiceCopy the code

Application of HUIM

Solution space

  • For subsets of all transaction items in the data set, tree structure is used to mine them

  • For all subsets of the item set, different algorithms use different subset tree structures

The constraint


u t i l i t y ( X ) p m i n U t i l utility(X) \ge minUtil

HUI-Miner

Idea: Use backtracking algorithm, depth traversal until the bottom, use branch bound function for each node, screen out unqualified nodes, avoid invalid retrieval

Pruning strategy: Use on border U (X ‘) or less ∑ (iu (X ‘, Ti) + ru (X ‘, Ti)) or less (iu (X, Ti) + ru (X, Ti)) U (X ‘), le, the sum (iu (X ‘, T_i) + ru (T_i), X ‘) \ le (iu (X, T_i) + ru (X, T_i)) U (X ‘) or less ∑ (iu (X ‘, Ti) + ru (X ‘, Ti)) or less (iu (X, Ti) + ru (X, Ti)), where X ⊆ \ subseteq X ‘X’ X X ⊆ X ‘

EFIM

Same as Hui-Miner

Pruning strategy: U (X ‘) or less su (X ‘) < lu (X ‘) < TWU TWU or less (X ‘) (X) U (X ‘) \ le su (X ‘) < lu (X ‘) < TWU (X ‘) \ le TWU U (X) (X ‘) or less su (X ‘) < lu (X ‘) < TWU TWU or less (X ‘) (X), In which X⊆X ‘X \subseteq X’X⊆X ‘

FHM

Idea: Take each unary item node as the root, and then use backtracking algorithm to carry out depth traversal

Pruning strategy: U ‘(X) = ∑ (iutils’ (X)) < ∑ (iutils (X) + rutils (X)) or less TWU TWU or less (X’) (X) u (X) = \ sum (iutils (X ‘)) < \ sum (iutils (X) + rutils (X)) \ le TWU (X ‘) \ le TWU u ‘(X) (X) = ∑ (iutils’ (X)) < ∑ (iutils (X) + rutils (X)) or less TWU TWU or less (X’) (X)

reference

  1. Labuladong: Detailed explanation of backtracking algorithm routines
  2. Dw 333: Recursion and iteration of backtracking algorithms
  3. Xiao Qiang DL: Branch bound method
  4. Yu Xing: backtracking method, branch limit method