动态规划算法是一种分而治之的算法,其应用之广泛,是刷题必备的理论。其过程如下:

  1. Characterize the structure of an optimal solution
  2. Recursively define the value of an optimal solution.
  3. Compute the value of anoptimal solution,typically in a bottom-up fashion.
  4. Construct an optimal solution from computed information.

斐波那契数列 (Fibonacci Sequence)

经典的fibonacci数列动态规划解法:

def fibonacci(n):
    assert n > 0
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n) + fibonacci(n+1)

上述代码问题在于,随着N的增大,展开的节点成指数级增长,很多的节点其实被重复计算了。解决的办法很简单,用一个字典记录之前的计算,下次遇到这种节点就不用再算了,直接取字典值就好,即用空间换时间:

fib = {1: 1, 2: 1}
def fibonacci(n):
    assert n > 0
    if n in fib:
        return fib[n]
    else:
        fib[n] = fibonacci(n-1) + fibonacci(n-2)
        return fib[n]

背包问题 (Knapsack Problem)

定义背包问题:

maximizei=1mpixisubject toi=1mwixiW,x{0,1}\begin{aligned} \text{maximize} \quad &\sum_{i=1}^m p_i' x_i\\ \text{subject to} \quad &\sum_{i=1}^mw_i' x_i \leq W, x \in \{0, 1\} \end{aligned}

我们设剩余nn个物品,剩余可用重量为WnW_n, 目前最大价值为PnP_n

  1. n=mn = mPn=0,Wn=WP_n = 0, W_n = W
  2. n=m1n = m - 1 时,

Pn=max{pn+1+Pn1,xn+1=1Pn1,xn+1=0P_n = \max \begin{cases} & p_{n+1} + P_{n-1}, & x_{n+1} = 1 \\ & P_{n-1}, & x_{n+1} = 0 \end{cases}

Wn={Wwn+1,xn+1=1Wn+1,xn+1=0W_n = \begin{cases} & W - w_{n+1}, \quad & x_{n+1} = 1 \\ & W_{n+1}, \quad & x_{n+1} = 0 \end{cases}

  1. n=0n = 0Wn<wnW_n < w_n 时,返回 PnP_n
p = [11,21,31,33,43,43,55,65]
w = [1,11,21,23,33,43,45,55]
W = 110
def knapsack(wn, pn, n):
    if wn < w[n-1] or n == 0:
        return pn
    else:
        p_choose = knap_sack(wn - w[n-1], pn + p[n-1], n-1)
        np_choose = knap_sack(wn, pn, n-1)

        if p_choose >= np_choose:
            return p_choose
        else:
            return np_choose

print(knapsack(W, 0, len(p)))

实验结果为151

为了保留搜索过程,我们用Binary Tree来解

class Node:
    def __init__(self, indices, z, w, parrent=None, left=None, right=None):
        self.parrent = parrent
        self.left = left # Choose Current
        self.right = right # Not Choose
        self.indices = indices 
        self.z = z # Current Value
        self.w = w # Current Weight Left
        
class Solution:
    p = [11,21,31,33,43,43,55,65]
    w = [1,11,21,23,33,43,45,55]
    W = 110

    assert len(p) == len(w)
    N = len(w)

    def build_tree(self, parrent):
        if len(parrent.indices) == 0:
            return
        else:
            index = parrent.indices[0]
            if parrent.w <= self.w[index]:
                return

            # Choose k[0]
            z = parrent.z + self.p[index]
            w = parrent.w - self.w[index]
            left_node = Node(parrent.indices[1:], z, w, parrent)
            
            # Not choose k[0]
            right_node = Node(parrent.indices[1:], parrent.z, parrent.w, parrent)

            parrent.left = left_node
            parrent.right = right_node

            self.build_tree(left_node)
            self.build_tree(right_node)

    def walk_tree(self, node):
        if node.left is None and node.right is None:
            if node.z > self.best.z:
                self.best = node
                return

        else:
            self.walk_tree(node.left)
            self.walk_tree(node.right)


    def print_path(self, node):
        if node.parrent is not None:
            if node.parrent.left == node:
                print("Choose ", node.parrent.indices[0], ", W left:", node.w, ", Current Price", node.z)
            elif node.parrent.right == node:
                print("Not Choose ", node.parrent.indices[0], ", W left:", node.w, ", Current Price", node.z)
            self.print_path(node.parrent)

    def solve(self):
        # Build the tree
        root = Node(list(range(self.N)), 0, self.W)
        self.build_tree(root)

        # Walk to find max
        self.best = root
        self.walk_tree(root)

        # Print result
        self.print_path(self.best)

八皇后问题 (Eight Queens Puzzle)

八皇后问题是指在国际象棋棋盘上放置8个皇后棋子,使得任意两个棋子之间不能互相攻击。
皇后棋子会攻击位于其同行,同列,以及同一条45度斜线上的所有棋子。
问题如出一辙,解法如下

import numpy as np
import random

class BoardNode:
    def __init__(self, board, last_place=None, queen_left=8, parrent=None, children=None):
        self.board = board
        self.parrent = parrent
        self.children = children
        self.queen_left = queen_left
        self.last_place = last_place

    def is_full(self):
        return self.board.sum() == 64

    def place_at(self, i, j):
        board = np.copy(self.board)
        board[i, :] = 1
        board[:, j] = 1

        for dx in range(-8, 8):
            if 0 <= i + dx < 8 and 0 <= j + dx < 8: 
                board[i+dx, j+dx] = 1
            if 0 <= i - dx < 8 and 0 <= j + dx < 8:
                board[i-dx, j+dx] = 1
        return board

    def places(self):
        if self.last_place is None:
            start_i = 0
        else:
            start_i = self.last_place[0]
        return [(i, j) for i in range(start_i, 8) for j in range(8) if self.board[i, j] != 1]

def print_board(board):
    out = ""
    for row in board:
        for x in row:
            if x == 0:
                out += " + "
            else:
                out += " X "
        out += " \n"
    print(out)
    return out


class EightQuees:
    solution = None
    count = 0
    board = np.zeros((8, 8), dtype=np.int)
    places = []

    def build_tree(self, node):
        if node.is_full():
            if node.queen_left == 0:
                self.solution = node
                self.count += 1
                print(self.count)

                self.places = []
                self.board = np.zeros((8, 8), dtype=np.int)
                self.print_node(self.solution)
                print_board(self.board)
                print(self.places)
            return


        elif node.queen_left > 0:
            for place in node.places():
                board = node.place_at(*place)
                child = BoardNode(board, place, node.queen_left-1, node)
                node.children = child
                self.build_tree(child)        
    
    def print_node(self, node):
        if node.last_place is not None:
            self.board[node.last_place] = 1
            self.places.append(node.last_place)
        if node.parrent is not None:
            self.print_node(node.parrent)

    def solve(self):
        root = BoardNode(np.zeros((8, 8), dtype=np.int))
        self.build_tree(root)

旅行商问题 (Traveling Salesman Problem)

给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。

用数学语言表达:

minimizei=0njincijxijsubject toxij{0,1}i=0,ijxij=1j=0,jixij=1\begin{aligned} \text{minimize}\quad & \sum_{i=0}^n\sum^n_{j\neq i} c_{ij}x_{ij}\\ \text{subject to} & \quad x_{ij} \in \{0, 1\}\\ &\sum_{i=0, i\neq j}x_{ij} = 1\\ &\sum_{j=0,j\neq i}x_{ij}=1 \end{aligned}

where cijc_{ij} represents path cost from city ii to jj, xij=1x_{ij}=1 represents path exists from city ii to jj and vice versa.

import numpy as np
import random

class Node:
    def __init__(self, unvisited, cost, last_city=None, first_city=None, parrent=None, children=None):
        self.unvisited = unvisited
        self.last_city = last_city
        self.first_city = first_city
        self.cost = cost
        self.parrent = parrent
        self.children = children
    
    def is_leaf(self):
        return len(self.unvisited) == 0
    
class TSP:
    solution = None
    cost = [
        [0, 3, 6, 7],
        [5, 0, 2, 3],
        [6, 4, 0, 2],
        [3, 7, 5, 0]
    ]
    cities = list(range(len(cost)))

    def print_path(self, node):
        cities = []
        print('Best cost:', node.cost)
        while node.parrent is not None:
            cities.append(node.last_city)
            node = node.parrent
        print(list(reversed(cities)))

    def walk_tree(self, node):
        if node.is_leaf():
            if node.cost < self.best.cost:
                self.best = node
                return
        else:
            for child in node.children:
                self.walk_tree(child)

    def build_tree(self, node):
        if node.is_leaf():
            return
        else:
            children = []
            for city in node.unvisited:
                c = 0 if node.last_city is None else self.cost[node.last_city][city] + node.cost
                first_city = city if node.first_city is None else node.first_city
                child = Node([x for x in node.unvisited if x != city], c, last_city=city, first_city=first_city, parrent=node)
                if child.is_leaf():
                    child.cost += self.cost[city][first_city]
                self.build_tree(child)
                children.append(child)
            node.children = children


    def solve(self):
        root = Node(self.cities, float('inf'))
        self.build_tree(root)
        self.best = root
        self.walk_tree(root)
        self.print_path(self.best)

最长公共子序列 (Longest Common Subsequence)

给定两个字符串 XXYY ,返回这两个字符串的最长公共子序列的长度。

设有二维数组f[i][j]f[i][j] 表示XXii位和YYjj位前的最长公共子序列长度,则

f[1][1]=S(1,1)f[i][j]=max{f[i1][j1]+S(i,j),f[i1][j],f[i][j1]}f[1][1] = S(1, 1)\\ f[i][j] = \max\{f[i-1][j-1] + S(i,j), f[i-1][j], f[i][j-1]\} \\

where

S(i,j)={1,X[i]=Y[j]0,X[i]Y[j]S(i, j) = \begin{cases} 1, X[i] = Y[j] \\ 0, X[i] \neq Y[j] \end{cases}

import numpy as np

class LCS:
    def solve(self, X, Y):
        nx = len(X)
        ny = len(Y)
        Z = np.zeros((nx, ny))

        for i in range(0, nx):
            for j in range(0, ny):
                if X[i] == Y[j]:
                    inc = Z[i-1, j-1] if i > 0 and j > 0 else 0
                    Z[i, j] = inc + 1
                else:
                    inc_x = Z[i-1, j] if i > 0 else 0
                    inc_y = Z[i, j-1] if j > 0 else 0
                    Z[i, j] = max(inc_x, inc_y)

        print(Z.max())