Go猜想录
大道至简,悟者天成
排列类DFS

摘要

  • 排列类搜索的隐式图模型
  • 排列类搜索的时间复杂度和适用条件
  • 通过排列类搜索看搜索与多重循环的区别
  • 著名的NP问题:TSP问题(旅行商问题)
    • DFS的解法
    • 状态压缩型动态规划
    • 随机化算法

什么是排列式搜索?

问题的模型是求出一个集合中所有元素的满足某个条件的排列
排列和组合的区别是排列是有顺序的
[1,2,3] 和 [3,2,1] 是同一个组合但不是同一个排列

排列的搜索树

             _
       /     |     \
      1      2      3
     / \    / \    / \
    12 13  21 23  31 32

15 · 全排列

求出给定没有重复的输入集的所有排列
[1,2,3] 有 6 个排列

/**
 * @param nums: A list of integers.
 * @return: A list of permutations.
 *          we will sort your return value in output
 */
// Permute 生成所有可能的排列组合
func Permute(nums []int) [][]int {
	var results [][]int
	if nums == nil {
		return results
	}

	visited := make([]bool, len(nums))
	dfs(nums, visited, []int{}, &results)
	return results
}

// dfs 递归生成排列组合
// 递归的定义
func dfs(nums []int,
	visited []bool,
	permutation []int,
	results *[][]int) {

	// 递归的出口
	if len(permutation) == len(nums) {
		// 深拷贝当前排列并添加到结果集中
		temp := make([]int, len(permutation))
		copy(temp, permutation)
		*results = append(*results, temp)
		return
	}

	// 递归的拆解
	for i := 0; i < len(nums); i++ {
		if visited[i] {
			continue
		}
		// 添加当前数字到排列中,并标记为已访问
		permutation = append(permutation, nums[i])
		visited[i] = true
		// 递归继续生成排列
		dfs(nums, visited, permutation, results)
		// 回溯,移除最后一个数字,并标记为未访问
		visited[i] = false
		permutation = permutation[:len(permutation)-1]
	}
}

时间复杂度

O(n! * n)
DFS时间复杂度通用公式:O(方案总数 * 构造每个方案的时间)

递归 vs 循环

递归实现搜索的本质是实现了按照给定参数来决定循环层数的一个多重循环
递归实现的搜索=n重循环,n由输入决定

816 · 旅行商问题

著名的NP问题:TSP问题

排列式搜索的典型代表
Traveling Salesman Problem
又称中国邮路问题

5种解法

  1. 暴力 DFS
  2. 暴力 DFS + 最优性剪枝(pruning)
  3. 状态压缩动态规划
  4. 随机化算法- 使用交换调整策略
  5. 随机化算法- 使用反转调整策略

一个题掌握四种算法:

  1. 排列式搜索 Permutation Style DFS
  2. 最优性剪枝算法 Optimal Pruning Algorithm
  3. 状态压缩动态规划 State Compression Dynamic Programming
  4. 随机化算法 Randomization Algorithm
    • 又称为遗传算法 Genetic Algorithm,模拟退火算法 Simulated Annealing

暴力搜索

package dfs

import (
	"math"
)

// Result 用于存储最小费用
type Result struct {
	minCost int
}

// NewResult 创建一个新的 Result 实例,并初始化 minCost 为一个较大值
func NewResult() *Result {
	return &Result{
		minCost: math.MaxInt32,
	}
}

// minCost 计算访问所有城市的最小费用
func minCost(n int, roads [][]int) int {
	graph := constructGraph(roads, n)
	visited := make(map[int]bool)
	result := NewResult()
	visited[1] = true

	travel(1, n, visited, 0, graph, result)

	return result.minCost
}

// dfs 深度优先搜索遍历城市
func travel(
	city int,
	n int,
	visited map[int]bool,
	cost int,
	graph [][]int,
	result *Result) {

	// 如果所有城市都已访问,更新最小费用
	if len(visited) == n {
		if cost < result.minCost {
			result.minCost = cost
		}
		return
	}

	for i := 1; i < len(graph[city]); i++ {
		if visited[i] {
			continue
		}
		visited[i] = true
		travel(i, n, visited, cost+graph[city][i], graph, result)
		delete(visited, i)
	}
}

// constructGraph 构造图的邻接矩阵
func constructGraph(roads [][]int, n int) [][]int {
	graph := make([][]int, n+1)
	for i := range graph {
		graph[i] = make([]int, n+1)
		for j := range graph[i] {
			graph[i][j] = math.MaxInt32
		}
	}

	for _, road := range roads {
		a, b, c := road[0], road[1], road[2]
		graph[a][b] = min(graph[a][b], c)
		graph[b][a] = min(graph[b][a], c)
	}

	return graph
}

// min 返回两个整数中的较小值
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

剪枝优化

// 0 .... i-1 i ..... -1 city
// 比较 (i-1,i) + (-1,city) 和 (i-1,-1) + (i,city)
// 相当于中间部分(i,-1)翻转
func hasBetterPath(graph [][]int, path []int, city int) bool {
	pathLength := len(path)
	for i := 1; i < pathLength; i++ {
		path_i_1 := path[i-1]
		path_i := path[i]
		path_last := path[pathLength-1]

		if graph[path_i_1][path_i]+graph[path_last][city] >
			graph[path_i_1][path_last]+graph[path_i][city] {
			return true
		}
	}
	return false
}

package dfs

import "math"

type Result2 struct {
	minCost int
}

func NewResult2() *Result {
	return &Result{minCost: 1000000}
}

func minCost2(n int, roads [][]int) int {
	graph := constructGraph(roads, n)
	visited := make(map[int]bool)
	path := []int{1}
	result := NewResult()
	visited[1] = true

	travel2(1, n, path, visited, 0, graph, result)

	return result.minCost
}

func travel2(city int, n int, path []int, visited map[int]bool, cost int, graph [][]int, result *Result) {
	if len(visited) == n {
		result.minCost = int(math.Min(float64(result.minCost), float64(cost)))
		return
	}

	for i := 1; i < len(graph[city]); i++ {
		if visited[i] {
			continue
		}
		if hasBetterPath(graph, path, i) {
			continue
		}
		visited[i] = true
		path = append(path, i)
		travel2(i, n, path, visited, cost+graph[city][i], graph, result)
		path = path[:len(path)-1]
		visited[i] = false
	}
}

func constructGraph2(roads [][]int, n int) [][]int {
	graph := make([][]int, n+1)
	for i := range graph {
		graph[i] = make([]int, n+1)
		for j := range graph[i] {
			graph[i][j] = 100000
		}
	}

	for _, road := range roads {
		a, b, c := road[0], road[1], road[2]
		if graph[a][b] > c {
			graph[a][b] = c
		}
		if graph[b][a] > c {
			graph[b][a] = c
		}
	}

	return graph
}

func hasBetterPath(graph [][]int, path []int, city int) bool {
	pathLength := len(path)
	for i := 1; i < pathLength; i++ {
		path_i_1 := path[i-1]
		path_i := path[i]
		path_last := path[pathLength-1]

		if graph[path_i_1][path_i]+graph[path_last][city] >
			graph[path_i_1][path_last]+graph[path_i][city] {
			return true
		}
	}
	return false
}

状态压缩动态规划

O (2^n * n^2)
要求的不是具体路径,而是最小值

随机化算法

随机化一个初始方案
通过一个调整策略调整到局部最优值
在时间限制内重复上述过程直到快要超时

使用交换调整策略

使用反转调整策略


知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。