python简述回溯法求解旅行商问题的步骤 回溯算法 python

回溯法-经典算法-Python

简介：

回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。

但当探索到某一步时，发现原先选择并不优或达不到目标(剪枝函数)，就退回一步重新选择。

函数中先确定必要的参数，再写递归函数(函数内，如果在函数外需要注意全局变量传递的问题)，最后再调用，否则可能会出现调用在声明前的错误。

递归函数的编写注意事项：

一、参数的选取，回溯需要哪些参数，因为是函数内的函数，因此不用考虑全局变量的传递问题。

二、结束条件，到什么时候终止，如果写错了，很容易造成无限递归。

三、如果递归不成功，是否需要重置状态。

快捷键：Ctrl + Home 快速回到页面顶端查看目录，点击锚点，快速定位到算法。

老鼠走迷宫

题目概述：给定一个二维数组，最外层是围墙，全为 1，里面 0 表示可以通行，寻找一条从左上角[0,0]到右下角的可行路线[n-1,n-1]。

解题思路：老鼠往四个方向探索，如果其中一个走不通，则退回来走另一个方向。

进阶：如果迷宫中有多条路径，显示所有路径，对代码进行简单修改即可。

endI,endJ,success = n-1,n-1,0

for i in range(len(maze)):

for j in range(len(maze[0])):

visit(i,j)

return success

def visit(i, j):

maze[i][j] = 1#走过了

if i == endI and j == endJ:

success = 1#进阶这里保存路径。

if success != 1 and maze[i][j+1]==0: visit(i,j+1)#右

if success != 1 and maze[i+1][j]==0: visit(i+1,j)#下

if success != 1 and maze[i][j-1]==0: visit(i,j-1)#左

if success != 1 and maze[i-1][j]==0: visit(i-1,j)#上

#用来显示路径,从这个点往四个方向走下去走不出去，置回为0.

if success != 1:#进阶这里不用判断

maze[i][j] = 0

return success

统计小岛的最大面积

题目概述：二维数组，统计1连续的最大面积

解题思路：

以下先介绍三种简单排序：冒泡排序、选择排序、插入排序。

'''冒泡排序

选择理由：稳定，与原位置偏离不远。

基本思想：正宗的冒泡排序，j 其实从后往前走的，不过我们比较喜欢，从下标0开始嘛，效果一样，但是要知道。默认有增加一个状态判断，如果某趟没有进行过交换，则直接结束。

时间复杂度：最好O(n)，最差O(n2), 平均O(n2)

空间复杂度：O(1)

'''

def BobleSort(li):

n = len(li)

for i in range(n-1):#定义几趟排序n-1，最后一趟不比较

state = False

for j in range(n-1-i):#每趟排序的比较次数

if li[j] > li[j+1]:

li[j],li[j+1] = li[j+1],li[j]

state = True

if not state:

return li

return li

'''简单插入排序

选择理由：稳定，基本有序。

基本思想:从第一个元素开始，不断整理顺序。

时间复杂度：最好O(n)，最差O(n2),平均O(n2)

空间复杂度：O(1)

'''

def InsertSort(li):

for i in range(1, len(li)):#定义趟数n-1

tempi = li[i]; j = i

while j > 0 and tempi < li[j-1]:#for就显示不出来优势了

li[j] = li[j-1]#后面的值上移

j -= 1

li[j] = tempi

'''简单选择排序

选择理由：不稳定，很无序，与原位置偏离较远。

基本思想:后面找到最小的值后再来交换，比冒泡排序的优点是不用交换那么多次[可能也是唯一的优点吧]。

时间复杂度：无论好差平均都是O(n2)

空间复杂度：O(1)

'''

def SelectSort(li):

for i in range(len(li)-1):#定义趟数n-1

minIndex = i

for j in range(i+1,len(li)):#定义每趟排序的比较次数

if li[minindex] > li[j]:

minindex = j

if minindex != i:

li[i],li[minindex] = li[minindex],li[i]

前面三种最差都是O(n2)，经过后人的不断努力，研究，速度才得以提升。排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加快排序的速度。以下介绍几种进阶排序：希尔排序、堆排序、归并排序、快速排序、计数排序

'''希尔排序-缩小增量排序

选择理由：不稳定，适合基本无序的序列，内部使用了简单插入排序。

基本思想:我们比较的元素可以再远一点，即所谓的增量，等距的一些元素先排序，再逐渐过渡到整个数组，最后的增量肯定是 1，检查还有哪些没有排好序。

时间复杂度：最差O(n2)，最好平均不确定(增量的选择很关键，有很多研究)

空间复杂度：O(1)

'''

import random

def ShellSort(li):

def shellInsert(li, d):#使用的是直接插入排序

n = len(li)

for front in range(d, n):

rear = front - d

temp = li[front]

while rear >= 0 and li[rear] > temp:

li[rear+d] = li[rear]

rear -= d

if li[front] != temp:

li[rear+d] = temp

n = len(li)

if n = 1:

shellInsert(li, d)

d //= 2

return li

#测试

li = [x for x in range(10)]

random.shuffle(li)

print(li)

print(ShellSort(li))

'''堆排序

选择理由：简单选择排序没有很好利用第一次比较的结果，因此改进为堆排序,不稳定。

基本思想:建堆：从最后一个非叶子节点开始调整到根节点；

大顶堆：将最大值移动到根节点，父节点：一定比所有的子节点都大

小顶堆：将最小值移动到根节点，父节点：一定比所有的子节点都小

排序：从根节点取出数放在最后面n-1次。这里并不直接使用数，而是用数组模拟树结构，数组到树的转换，下标从 0 开始，节点若存在父节点则下标为 n//2，若有子节点则左子节点下标为 2*n+1，右子节点下标为 2*n+2.

时间复杂度：最好-最差-平均都是：O(nlogn)这就很厉害了！

空间复杂度：O(1)

堆排序经典应用：

1. 三角形的最大周长：给定一个长度数组，返回三条构成三角形的最大周长。

解题思路：不一定要将数组全部排序，构造大顶堆，边排序边判断两边之和大于第三边即可。

'''

def heapadjust(li, root, end):

leaf = root*2+1

tmp = li[root]

while leaf li[leaf]:#比较两个子节点

leaf += 1

#迭代后不是和父节点比较，因为我没有交换，和保存父节点值的tmp比较

if li[leaf] > tmp:

li[root] = li[leaf]# 将父节点替换成新的子节点的值，这里就完成了转换。

root = leaf# 赋坐标，为下一步迭代做好准备，子节点变成父节点

leaf = root*2+1#寻找子节点的子节点

else:

break

li[root] = tmp# 将转换的值赋给最终移动到的地方。

def heapsort(li):

n = len(li)

# 创建堆，和下面排序不同的是，我们转换的范围永远是整个数组n-1

for not_leaf in range(n//2-1, -1, -1):#下标从零开始。

heapadjust(li, not_leaf, n-1)

# 挨个出数，创建堆已经完成了第一次排序

for end in range(n-1, -1, -1):

li[end],li[0] = li[0],li[end] # 将最后一个值与父节点交互位置

heapadjust(li, 0, end-1)

'''归并排序-分治递归的思想,代码为二路归并

选择理由：稳定，一般用于总体无序，但各子项相对有序。

基本思想:将列表分成几部分，两两合并。

时间复杂度：最好-最差-平均都是：O(nlogn)这就很厉害了！

空间复杂度：O(n)

归并排序经典应用：

1. 排序链表：

解题思路:递归归并

经典考察三个知识点：归并排序，找中间节点，合并链表

'''

def MergeSort(li):

#合并左右子序列函数

def merge(li, left, mid, right):

temp = [] #中间数组

i = left#左段子序列起始

j = mid + 1#右段子序列起始

while i= li[key]:

right -= 1

while left < right and li[left] = right:

return

mid = partition(li, left, right)

quicksort(li, left, mid-1)

#优化3：减少递归栈空间的使用，使用迭代

#while循环加上left = mid + 1

quicksort(li, mid+1, right)

#主函数

n = len(li)

if n 1:

p = A.index(tail)#当前乱序的最大值的坐标

if p != 0:

num = p + 1

self.nreverse(A, num)

res.append(num)

self.nreverse(A, tail)

res.append(tail)

tail -= 1

return res

'''距离相等的条形码

题目概述：数组中相同的数字不能相连。[1,1,1,2,2,2]

解题思路:按照数量多少先进行排序，然后按奇偶填充。

'''

def rearrangeBarcodes(barcodes):

counter = dict(collections.Counter(barcodes))

#按出现次数统计元素

sortedCounter = sorted( counter, key=lambda k: 0 - counter[k])

barcodes = []

#重新排序

for i in sortedCounter:

barcodes += [i] * counter[i]

arrangedBarcodes = [None for _ in range(len(barcodes))]

#间隔插入

arrangedBarcodes[::2] = barcodes[:len(arrangedBarcodes[::2])]

arrangedBarcodes[1::2] = barcodes[len(arrangedBarcodes[::2]):]

return arrangedBarcodes

'''距离顺序排列矩阵单元格

题目概述：给定矩阵中的一个坐标，按曼哈顿距离排列矩阵中其余的坐标。

曼哈顿距离：|r1 - r2| + |c1 - c2|

解题思路：利用空间换时间的想法，构造距离空间。

'''

def allCellsDistOrder(R, C, r0, c0):

ans = []

dic = {}

for i in range(R):

for j in range(C):

diff = abs(i-r0)+abs(j-c0)

print(diff)

if diff not in dic:

dic[diff] = [[i,j]]

else:

dic[diff].append([i,j])

for i in range(R+C):

if i in dic.keys():

ans.extend(dic[i])

return ans