分支定界搜索以及 Python 中的示例和实现

作者

我们将尝试了解本文中的一种启发式搜索技术。启发式技术是确定几种替代方案中哪一种最有效实现特定目标的标准。分支定界搜索也称为统一成本搜索。

什么是分支定界搜索算法？

分支定界是一种用于组合、离散和一般数学优化问题的搜索算法。它与回溯类似，因为它同样实现了状态空间流来表示问题的解决方案。

然而，它可能更适合尝试解决优化问题，并且仅解决最小化问题，而不是最大化问题。从统计学上来说，分支定界算法从 NP-Hard 问题的整个可能性搜索空间中找到最佳解决方案。

分支定界搜索如何工作？

在分支定界搜索策略中，生成一个成本函数（用 g(X) 表示），通过使用一系列运算符，为从起始节点到当前节点 X 的路径分配累积成本。最便宜的价格已经发现的路径在搜索空间生成过程的每一步都会扩展，直到达到目标状态。

分支定界搜索也称为统一成本搜索，因为它扩展了最低成本部分路径。例如，在旅行商问题中，从起点到当前节点X的实际行驶距离可以表示为g(X)。

算法步骤

Input: START and GOAL states
Local Variable: OPEN, CLOSED, NODE, SUCCs, FOUND
Output: Yes or No
 
Method:
Initialise FOUND = false
while(OPEN is not NULL and FOUND = false) do
{
  remove the top element from OPEN list and call it NODE
  if NODE is the goal node then FOUND = true
  else
  {
    put NODE in CLOSED list:
    find SUCCs of NODE. if any,and compute thier 'g' values and store them in OPEN list:
    sort all the nodes in the OPEN list based on their cost - function values.
 }
}end while loop
if FOUND = true then return Yes otherwise return No.

如果所有运算符的 g(X) = 1，则分支定界方法将退化为简单的广度优先搜索。人工智能认为它与深度优先和广度优先一样有害。如果我们添加动态规划，我们可以通过消除冗余路径来改善这一点。

我们注意到，该方法通常需要创建解决方案并评估其功效。可以使用任何技术来得出答案，并且可以在测试中使用启发式方法。以下是用于开发和测试策略的算法的基本结构。

start
  Generate possible solutions
  Test if it is a goal
  If not go to start else quit
end

品牌和绑定搜索算法的实际应用

为了更清楚地理解这个概念，让我们尝试使用分支定界算法来实现 8 个难题。下面给出问题描述。

一块 3 x 3 的棋盘，有 8 个图块（每个图块的数字范围为 1 到 8），并提供一个空白空间。目标是利用空闲空间来排列图块上的数字，使它们与最终的排列相匹配。四个相邻的（左、右、上、下）图块可以滑入可用区域。

例如

初始状态

为了避免在不包括答案节点的子树中搜索，通常可以使用成本函数的近似来加速对答案节点的搜索。然而，它没有使用回溯方法，而是进行 BFS 式搜索。

基本上，分支定界涉及三种不同类型的节点。

  1. 活动节点是一个生成的节点，其子节点尚未生成。
  2. E 节点（一个活动节点）的子节点现在正在接受检查。或者换句话说，E节点是当前正在扩展的节点。
  3. 不再进一步开发或检查的已创建节点称为死节点。死节点已经扩展了它的所有子节点。

成本函数：在搜索树中，每个节点X都有相应的成本。可以使用成本函数找到下一个E节点。成本最低的 E 节点是下一个。成本函数的定义是

C(X) = g(X) + h(X)

在哪里
   C(X) 有时也称为“f”。
   g(X) = 从根到达当前节点的成本
   h(X) = 从 X 到达答案节点的成本。
树

在 Python 中实现分支限界搜索算法

import copy
from heapq import heappush, heappop
  
# we have defined 3 x 3 board therefore n = 3..
n = 3
  
# bottom, left, top, right
row = [ 1, 0, -1, 0 ]
col = [ 0, -1, 0, 1 ]
  
 
class priorityQueue:
 
    def __init__(self):
        self.heap = []
  
    # Inserts a new key 'k'
    def push(self, k):
        heappush(self.heap, k)
  
    # remove minimum element
    def pop(self):
        return heappop(self.heap)
  
    # Check if queue is empty
    def empty(self):
        if not self.heap:
            return True
        else:
            return False
  
class node: 
    def __init__(self, parent, mat, empty_tile_pos,
                 cost, level):
                       
        # parent node of current node
        self.parent = parent
  
        # matrix
        self.mat = mat
  
        # position of empty tile
        self.empty_tile_pos = empty_tile_pos
  
        # Total Misplaced tiles
        self.cost = cost
  
        # Number of moves so far
        self.level = level
  
 
    def __lt__(self, nxt):
        return self.cost < nxt.cost
  
# Calculate number of non-blank tiles not in their goal position
def calculateCost(mat, final) -> int:
      
    count = 0
    for i in range(n):
        for j in range(n):
            if ((mat[i][j]) and
                (mat[i][j] != final[i][j])):
                count += 1               
    return count
  
def newNode(mat, empty_tile_pos, new_empty_tile_pos,
            level, parent, final) -> node:
                  
    new_mat = copy.deepcopy(mat)
    x1 = empty_tile_pos[0]
    y1 = empty_tile_pos[1]
    x2 = new_empty_tile_pos[0]
    y2 = new_empty_tile_pos[1]
    new_mat[x1][y1], new_mat[x2][y2] = new_mat[x2][y2], new_mat[x1][y1]
  
    # Set number of misplaced tiles
    cost = calculateCost(new_mat, final)
    new_node = node(parent, new_mat, new_empty_tile_pos,
                    cost, level)
    return new_node
  
#print the N x N matrix
def printMatrix(mat):  
    for i in range(n):
        for j in range(n):
            print("%d " % (mat[i][j]), end = " ")  
        print()
 
def isSafe(x, y):
    return x >= 0 and x < n and y >= 0 and y < n
  
 
def printPath(root):  
    if root == None:
        return
      
    printPath(root.parent)
    printMatrix(root.mat)
    print()
  
 
def solve(initial, empty_tile_pos, final):
    pq = priorityQueue()
  
    # Create the root node
    cost = calculateCost(initial, final)
    root = node(None, initial,
                empty_tile_pos, cost, 0)
 
    pq.push(root)
  
    while not pq.empty():
        minimum = pq.pop()
  
        # If minimum is the answer node
        if minimum.cost == 0:
              
            # Print the path from root to destination;
            printPath(minimum)
            return
  
        # Produce all possible children
        for i in range(4):
            new_tile_pos = [
                minimum.empty_tile_pos[0] + row[i],
                minimum.empty_tile_pos[1] + col[i], ]
                  
            if isSafe(new_tile_pos[0], new_tile_pos[1]):
                  
                # Create a child node
                child = newNode(minimum.mat,
                                minimum.empty_tile_pos,
                                new_tile_pos,
                                minimum.level + 1,
                                minimum, final,)
  
                # Add child to list of live nodes
                pq.push(child)
  
# Driver Code
# 0 represents the blank space
# Initial state
initial = [ [ 2, 8, 3 ],
            [ 1, 6, 4 ],
            [ 7, 0, 5 ] ]
  
# Final State
final = [ [ 1, 2, 3 ],
          [ 8, 0, 4 ],
          [ 7, 6, 5 ] ]
  
# Blank tile position during start state
empty_tile_pos = [ 2, 1 ]
  
# Function call
solve(initial, empty_tile_pos, final)

输出

输出

概括

在本文中，我们学习了最有效的算法之一，称为分支定界搜索。该搜索算法有助于解决许多常见问题，如 N 皇后问题、0-1 背包问题、旅行商问题等。该算法根据问题中提供的条件在每种情况下进行一点修改，但基本思想搜索方法与前面解释的相同。