branch-bound

在 Go 语言中实现分支限界法（Branch and Bound）时，我们通常会处理组合优化问题，比如旅行商问题（TSP）或背包问题。下面我将提供一个简单的 Go 代码实现示例，解决旅行商问题（TSP），这将帮助你理解如何用分支限界法来减少搜索空间并找到最优解。

1. 旅行商问题（TSP）分支限界法的 Go 实现

在这个示例中，我们会使用分支限界法来求解经典的旅行商问题（TSP）。旅行商问题的目标是找到一个最短路径，经过每个城市一次，最后返回起始城市。

旅行商问题的分支限界法步骤：

1. 状态表示：每个状态表示当前城市、已经访问的城市、当前路径的总费用。
2. 下界计算：利用**最小生成树（MST）**等启发式算法来估算当前城市出发时剩余城市的最短路径的估计值。
3. 剪枝：如果某个分支的下界已经大于当前的最佳解，则不再继续探索。

代码实现：

package main

import (
	"fmt"
	"math"
	"sort"
)

// 城市之间的距离矩阵
var dist = [][]int{
	{0, 10, 15, 20, 25},
	{10, 0, 35, 25, 30},
	{15, 35, 0, 30, 5},
	{20, 25, 30, 0, 10},
	{25, 30, 5, 10, 0},
}

// 分支限界法中的状态表示
type State struct {
	currentCity   int
	visitedCities map[int]bool
	currentCost   int
	lowerBound    int
}

// 比较状态队列的优先级（通过lowerBound值）
type PriorityQueue []State

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].lowerBound < pq[j].lowerBound }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[0 : n-1]
	return x
}

// 计算从当前状态到目标城市的lowerBound估算（最小生成树估算）
func calculateLowerBound(state State) int {
	// 假设我们通过贪心算法计算剩余路径的最短距离
	// 这里只是示例，实际可以用更复杂的算法（例如最小生成树）。
	remainingCities := []int{}
	for i := 0; i < len(dist); i++ {
		if !state.visitedCities[i] {
			remainingCities = append(remainingCities, i)
		}
	}
	if len(remainingCities) == 0 {
		return 0
	}

	// 贪心策略：选择当前城市到未访问城市的最短距离
	minCost := 0
	for _, city := range remainingCities {
		minCost += dist[state.currentCity][city]
	}
	return minCost
}

// 分支限界法求解旅行商问题
func branchAndBoundTSP(startCity int) int {
	initialState := State{
		currentCity:   startCity,
		visitedCities: map[int]bool{startCity: true},
		currentCost:   0,
		lowerBound:    0, // 初始lower bound
	}

	// 优先队列（最小堆），按lowerBound排序
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, initialState)

	bestCost := math.MaxInt32

	// 开始分支限界法
	for pq.Len() > 0 {
		currentState := heap.Pop(pq).(State)

		// 如果所有城市都访问完，更新最佳解
		if len(currentState.visitedCities) == len(dist) {
			if currentState.currentCost < bestCost {
				bestCost = currentState.currentCost
			}
			continue
		}

		// 生成新的子问题：遍历未访问的城市，选择一个城市作为下一个城市
		for nextCity := 0; nextCity < len(dist); nextCity++ {
			if !currentState.visitedCities[nextCity] {
				// 计算从当前城市到下一个城市的路径
				newCost := currentState.currentCost + dist[currentState.currentCity][nextCity]
				// 更新新的状态
				newState := State{
					currentCity:   nextCity,
					visitedCities: cloneMap(currentState.visitedCities),
					currentCost:   newCost,
					lowerBound:    currentState.lowerBound + dist[currentState.currentCity][nextCity],
				}
				newState.visitedCities[nextCity] = true

				// 计算lowerBound
				newState.lowerBound += calculateLowerBound(newState)

				// 如果新的lowerBound小于当前最佳解，则继续探索
				if newState.lowerBound < bestCost {
					heap.Push(pq, newState)
				}
			}
		}
	}

	return bestCost
}

// 辅助函数：克隆map
func cloneMap(m map[int]bool) map[int]bool {
	copy := make(map[int]bool)
	for k, v := range m {
		copy[k] = v
	}
	return copy
}

func main() {
	// 从城市0出发
	startCity := 0
	result := branchAndBoundTSP(startCity)
	fmt.Printf("最短路径的总成本是: %d\n", result)
}

代码说明：

1. 状态表示 (State)：

   • currentCity: 当前所在的城市。
   • visitedCities: 一个 map，记录已经访问过的城市。
   • currentCost: 当前路径的总费用。
   • lowerBound: 当前状态的下界估算值，基于未访问城市的最短路径估算。

2. 优先队列 (PriorityQueue)：

   • 使用 Go 的 heap 包实现优先队列。根据 lowerBound 值对状态进行排序，保证每次优先扩展下界较小的分支。

3. 计算下界 (calculateLowerBound)：

   • 计算从当前城市出发，访问剩余未访问城市的最短路径估算。这里使用了一个简单的贪心策略，你可以根据实际需求替换为更精确的下界计算方法，如最小生成树（MST）。

4. 分支限界法的主逻辑 (branchAndBoundTSP)：

   • 初始化状态并将其推入优先队列。
   • 每次从队列中取出一个状态，检查是否完成所有城市的访问。
   • 对每个未访问的城市，计算到该城市的路径成本，并生成新的子问题状态。
   • 计算新的下界，并根据下界判断是否继续扩展这个分支。

5. 剪枝：

   • 如果某个状态的 lowerBound 大于当前已知的最佳解（bestCost），则不再继续扩展这个分支。

结果输出：

程序会输出最短路径的总成本，这是旅行商问题的最优解。

总结：

分支限界法通过构建一个搜索树，并在每个节点上计算下界来减少搜索空间。对于 TSP 问题，我们通过维护一个优先队列来按下界优先扩展节点，从而提高搜索效率。此实现展示了如何用分支限界法在 Go 语言中求解组合优化问题。