量化投资学习笔记44——基本数据结构算法总结3 回溯算法

开始看书，《你也能看得懂的python算法书》。
编程基础，链表等就略读了。
哈希算法是通过某种函数映射关系，将复杂的数据，映射成更加易于查找的形式。大多数情况下，哈希算法可以在常数时间内存储和查找这些数据。原理:利用哈希函数存储和查找数据。哈希算法存在冲突的情况，即不同的数据被映射到同一个位置。处理冲突的方法:链地址法。本质上是数组+链表。查找问题，首先想想能不能用哈希算法。
搜索问题的本质是试探问题的所有可能选择，按照特定规律和顺序，不断地去搜索答案，直到找到问题的解。有深度优先遍历算法和广度优先遍历算法。
回溯算法，采用试错的方法解决问题，当前步骤失败，返回上一个步骤，选择另一个方案继续试错。
贪心算法，总是选取局部最优的方案，直到获得最终解决。使用该算法，需要问题具有贪心选择性质，是指应用同一规则f，将原问题变为一个相似的但规模更小的子问题，后面的每一步都是当前看似最佳的选择。另外问题需要具有局部最优解。
动态规划算法将待求解问题拆分成一系列相互交叠的子问题，通过递推关系定义各子问题的求解策略，并随时记录子问题的解，最终获得原始问题的解，避免了对交叠子问题的重复求解。
在动态规划算法中有三要素，即最优子结构、边界和状态转移函数。最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到；边界是指问题最小子集的解；状态转移函数是指从一个阶段向另一个阶段过渡的具体模式，描述的是两个相邻子问题之间的关系。
最短路径算法，有迪可斯特朗算法、Floyd算法、A※算法。
用具体例子来看吧。
回溯算法（参考: https://zhuanlan.zhihu.com/p/93530380）
需要考虑三个问题：路径（已经做出的选择）、选择列表（当前可作的选择）、结束条件（到达决策树底层，无法再做选择的条件）
其框架为：

result = [ ]
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

例子：全排列问题。

# coding:utf-8
# 回溯算法


def permute(nums):
    results = []
    track = []
    backtrack(nums, track, results)
    return results
    
    
def backtrack(nums, track, results):
    if len(track) == len(nums):
        results.append(tuple(track))
        return
        
    for i in range(len(nums)):
        if nums[i] in track:
            continue
        # 选择
        track.append(nums[i])
        # 进入下一层决策树
        backtrack(nums, track, results)
        # 取消选择
        track.pop()


if __name__ == "__main__":
    # 全排列问题
    nums = [1, 2, 3]
    result = permute(nums)
    print(result)

时间复杂度是O(N!)，因为需要穷举整棵决策树。
再来看另一个例子，N皇后问题。
跟全排列类似，多了一个判断不合法的位置的函数。
参考:https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/

# N皇后问题
def  solveNQ(N):
    board = []
    for i in range(N):
        board.append([0]*N)
   
    results = []
    global n
    n = 0
    solveNQUtil(board, 0, N, results)
    # printSolution(results, N)
    return True
   
   
def printSolution(board, N):
    global n
    n += 1
    print("\n第{}个结果。\n".format(n))
    for i in range(N):
        for j in range(N):
            print(board[i][j], end = " ")
        print("\n")
       
       
def solveNQUtil(board, col, N, results):
    if col >= N:
        printSolution(board, N)
        return
       
    for i in range(N):
        if isSafe(board, i, col, N):
            board[i][col] = 1
            solveNQUtil(board, col+1, N, results)
            board[i][col] = 0
   
   
def isSafe(board, row, col, N):
    # 左侧的列
    for i in range(col):
        if board[row][i] == 1:
            return False
           
    # 左上对角线
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
           
    # 左下对角线
    for i, j in zip(range(row, N, 1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False
           
    return True

再来几个例子，数独问题。
9×9的格子，每行，每列以及每3×3格组成的宫里的数字都不相同。
参考这里:https://zhuanlan.zhihu.com/p/99218941

from datetime import datetime
# 数独的回溯解法
class sovSudoku:
    def __init__(self, board = []):
        self._b = board.copy()
        self._t = 0
        self._n = 0
       
    # 主循环，尝试x,y处的解答
    def trysxy(self, x, y):
        self._n += 1
        if self._b[x][y] == 0:
            pv = self.getPrem(x, y)
            for v in pv:
                self._t += 1
                if self.checkNotSame(x, y, v):
                    self._b[x][y] = v
                    nx, ny = self.getNext(x, y)
                    if nx == -1:
                        return True
                    else:
                        _end = self.trysxy(nx, ny)
                        if not _end:
                            self._b[x][y] = 0
                        else:
                            return True
           
    # 得到x, y处可以填的值
    def getPrem(self, x, y):
        prem = []
        rows = list(self._b[x])
        rows.extend([self._b[i][y] for i in range(9)])
        cols = set(rows)
        for i in range(1, 10):
            if i not in cols:
                prem.append(i)
        return prem
       
    # 检查每行每列和每个宫内是否有与b(x, y)相同的数字
    def checkNotSame(self, x, y, val):
        # 第x行
        for row_item in self._b[x]:
            if row_item == val:
                return False
        # 第y列
        for rows in self._b:
            if rows[y] == val:
                return False
        ax = x//3*3
        ab = y//3*3
        for r in range(ax, ax+3):
            for c in range(ab, ab+3):
                if self._b[r][c] == val:
                    return False
        return True
       
    # 得到下一个未填项
    def getNext(self, x, y):
        for ny in range(y+1, 9):
            if self._b[x][ny] == 0:
                return (x, ny)
        for row in range(x+1, 9):
            for ny in range(0, 9):
                if self._b[row][ny] == 0:
                    return (row, ny)
        return (-1, -1)
       
    def solve(self):
        if self._b[0][0] == 0:
            self.trysxy(0, 0)
        else:
            x, y = self.getNext(0, 0)
            self.trysxy(x, y)
           
            def updateSudo(self, cb):
                if len(cb) == 9 and len(cb[0] == 9):
                    self._b = cb
                else:
                    print("错误结果", len(cb), len(cb[0]))
                  
    def __str__(self):
        return '{0}{1}{2}'.format('[',',\n'.join([str(i) for i in self._b]),']')
       
    # 获得回溯次数
    def getTNum(self):
        return self._n

if __name__ == "__main__":
    # 数独问题
    s1 = [
            [8,0,0, 0,0,0, 0,0,0],
            [0,0,3, 6,0,0, 0,0,0],
            [0,7,0, 0,9,0, 2,0,0],
            [0,5,0, 0,0,7, 0,0,0],
            [0,0,0, 0,4,5, 7,0,0],
            [0,0,0, 1,0,0, 0,3,0],
            [0,0,1, 0,0,0, 0,6,8],
            [0,0,8, 5,0,0, 0,1,0],
            [0,9,0, 0,0,0, 4,0,0]
        ]
    begin = datetime.now()
    ss = sovSudoku(s1)
    ss.solve()
    print(datetime.now() - begin)
    print(ss)
    print(ss.getTNum())
   
    m = [
        [6, 0, 0, 1, 0, 0, 7, 0, 8],
        [0, 0, 0, 8, 0, 0, 2, 0, 0],
        [2, 3, 8, 0, 5, 0, 1, 0, 0],
        [0, 0, 0, 0, 4, 0, 0, 9, 2],
        [0, 0, 4, 3, 0, 8, 6, 0, 0],
        [3, 7, 0, 0, 1, 0, 0, 0, 0],
        [0, 0, 3, 0, 7, 0, 5, 2, 6],
        [0, 0, 2, 0, 0, 4, 0, 0, 0],
        [9, 0, 7, 0, 0, 6, 0, 0, 4]
    ]
    begin = datetime.now()
    ss = sovSudoku(m
    )
    ss.solve()
    print(datetime.now() - begin)
    print(ss)
    print(ss.getTNum())

现在来看另一个问题，0-1背包问题。
参考这里:https://www.cnblogs.com/xiaomangxie/p/10208441.html
有N件物品和一个容量为V的背包。第i件物品的价格（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
回溯法解决看这里:http://www.jeepxie.net/article/273672.html

# 背包问题
bestV = 0
curW = 0
curV = 0
bestx = None

def backtrack(i):
    global bestV,curW,curV,x,bestx
    if i >= n:
        if bestV < curV:
            bestV = curV
            bestx = x[:]
    else:
        if curW + w[i] <= c:
            x[i] = True
            curW += w[i]
            curV += v[i]
            backtrack(i+1)
            curW -= w[i]
            curV -= v[i]
        x[i] = False
        backtrack(i+1)

n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
x=[False for i in range(n)]
backtrack(0)
print(bestV)
print(bestx)