chapter6-conclusion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 递推\n",
    "### 挑战：剑客的秘密"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def secret(n):\n",
    "    \"\"\"剑客秘密，输入挥剑次数n，求解出分割平面的数量\"\"\"\n",
    "    result = 1 # n=0，没有挥剑，平面为一整块\n",
    "    step = 1\n",
    "    while step <= n: \n",
    "        result += step # 每一次都在上一次结果上累加\n",
    "        step += 1 #  到下一步\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for i in range(0, 10):\n",
    "    print(secret(i), end=',')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def knight_tour(n, m, dest_x, dest_y):\n",
    "    map_arr = [] # 记录坐标的值\n",
    "    for i in range(m): # 初始化棋盘，所有点为(0,0)\n",
    "        map_arr.append([(0,0)]*n)\n",
    "    model = [(2,1),(2,-1),(1,2),(1,-2)] #四种步伐的变化\n",
    "    map_arr[dest_x][dest_y]=(-1,-1) # 标记为终点\n",
    "    print_tmp(map_arr) # 打印寻找路径的过程\n",
    "    for i in range(n-1, 0 , -1):\n",
    "        for j in range(m-1, 0, -1):\n",
    "            if map_arr[i][j][0] != 0:\n",
    "                for k in range(4):\n",
    "                    if (n > i-model[k][0] >= 0 and m > j-model[k][1] >= 0):\n",
    "                        # 判读坐标点是否在棋盘上，如果在则记录其下一个位置\n",
    "                        map_arr[i-model[k][0]][j-model[k][1]]= (i,j)\n",
    "        print_tmp(map_arr) # 打印寻找路径的过程\n",
    "    result = [] # 记录路径结果\n",
    "    if map_arr[0][0] == (0,0): \n",
    "        # 若骑士坐标上没有下一步的坐标值，说明没有方法可以达到终点\n",
    "        print('没有可行路径')\n",
    "    else:\n",
    "        x = 0\n",
    "        y = 0\n",
    "        result = [(0,0)]\n",
    "        while map_arr[x][y] != (-1,-1): #没有到终点，继续寻找下一步的坐标\n",
    "            x, y = map_arr[x][y] # 更新下一步坐标\n",
    "            result.append((x,y))\n",
    "    return result\n",
    "\n",
    "def print_tmp(arr):\n",
    "    \"\"\"打印棋盘当前情况\"\"\"\n",
    "    for line in arr:\n",
    "        for p in line:\n",
    "            if p==(0,0): #初始值\n",
    "                print('-', end=' ')\n",
    "            elif p==(-1,-1): #终点\n",
    "                print('O', end=' ')\n",
    "            else: # 骑士可以走的点\n",
    "                print('x', end=' ')\n",
    "        print()\n",
    "    print('-----------------')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "knight_tour(7,7,3,6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 递归\n",
    "### 斐波那契数列 递归和递推"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibonacci_recu(n):\n",
    "    \"\"\"递归求解斐波那契数列\"\"\"\n",
    "    if n <= 1: #递归返回条件\n",
    "        return n  # 递归返回值是一个正数  \n",
    "    else: \n",
    "        # 目的是求解第n项的值\n",
    "        return fibonacci_recu(n - 1) + fibonacci_recu(n - 2) \n",
    "\n",
    "def fibonacci(n):\n",
    "    \"\"\"递推求解斐波那契数列\"\"\"\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    # 递推公式的初始值\n",
    "    fn1 = 0\n",
    "    fn2 = 1\n",
    "    step = 2   # 大于1递推公式才生效\n",
    "    resutl = 0 # 记录结果\n",
    "    while step <= n: # 计算到第ｎ项的值才退出循环\n",
    "        result = fn1+fn2 # 从n-1,n-2两项推导出第ｎ项的值\n",
    "        fn1=fn2    # 更新n-2项为n-1项\n",
    "        fn2=result # 更新n-1项为n项\n",
    "        step += 1  # 下一项 \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 对比两个函数输出\n",
    "for i in range(10):\n",
    "    print(fibonacci_recu(i), fibonacci(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def secret_recu(n):\n",
    "    \"\"\"用递归方式求解剑客的秘密\"\"\"\n",
    "    if n == 0: # 递归返回条件\n",
    "        return(1) # 递归返回值是一个正整数 \n",
    "    # 目的是求解第n项的值\n",
    "    return (secret_recu(n-1) + n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 对比两个函数输出\n",
    "for i in range(0, 10):\n",
    "    print(secret(i), secret_recu(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class QueensQuestion(object):\n",
    "    def __init__(self):\n",
    "        self.result_count = 0\n",
    "\n",
    "    def main_func(self, n):  # 矩阵为n行n列\n",
    "        \"\"\"求解8皇后问题主函数\"\"\"\n",
    "        self.result_count = 0 # 初始化统计结果为0\n",
    "        self.position([-1] * n, 0, n) # 皇后初始位置为-1,代表未放置\n",
    "\n",
    "    def is_valid(self, col, row):\n",
    "        # 判断位置是否符合要求\n",
    "        if len(set(col[:row + 1])) != len(col[:row + 1]): \n",
    "            # 检查皇后的列是否有相同的，set()寻找唯一值，若两者个数一样，说明没有相同数值在列表中。\n",
    "            return False\n",
    "        for i in range(row): #检查对角线\n",
    "            if i - col[i] == row - col[row]:\n",
    "                # 检查“\\”斜线上，坐标差相同则表示在同一斜线上\n",
    "                return False\n",
    "            if i + col[i] == row + col[row]:\n",
    "                # 检查\"/\"斜线上，坐标和相同则表示在同一斜线上\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def position(self, col, row, n):  # row:当前行，col:每一行皇后的位置 n:总行数\n",
    "        if row == n:  #到最后一行，也就是所有皇后都安排好位置\n",
    "            self.print_result(col, n) # 打印结果\n",
    "            return # 返回，不保留结果，结果已经输出到屏幕上。\n",
    "\n",
    "        for row_position in range(n):\n",
    "            col[row] = row_position   # 遍历皇后所在列的位置\n",
    "            if self.is_valid(col, row): # 如果位置符合要求，设置下一个皇后位置\n",
    "                self.position(col, row + 1, n)\n",
    "\n",
    "    def print_result(self, col, n):\n",
    "        \"\"\"打印皇后在棋盘上的位置\"\"\"\n",
    "        self.result_count += 1 # 统计可行结果\n",
    "        print(col) #输出每行皇后所在列\n",
    "        # 在屏幕上输出棋盘上的皇后位置\n",
    "        for row in range(n):\n",
    "            for column in range(n):\n",
    "                if col[row] == column: # 找到皇后所在列位置\n",
    "                    print(\" Q\", end=' ')\n",
    "                else:# 棋盘其他地方\n",
    "                    print(\" -\", end=' ')\n",
    "            print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "q = QueensQuestion() # 实例化对象\n",
    "q.main_func(4) # 求解８个皇后的位置（当然ｎ可以是任意正整数）\n",
    "q.result_count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 分治算法\n",
    "### 挑战：小孩的作业真麻烦"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class HomeworkQuestion(object):\n",
    "    \"\"\"帮忙检查小孩作业\"\"\"\n",
    "    \n",
    "    def __init__(self, n, m=None):\n",
    "        self.temp = [] # 作为栈记录一个结果\n",
    "        self.result = [] #  把所有解存储起来\n",
    "        self.n = n # 需要拆解的数\n",
    "        if m:\n",
    "            self.m = m # 也可以自定义最少拆解值\n",
    "        else:\n",
    "            self.m = n -1  # 最少拆解的数值默认设为1\n",
    "    \n",
    "    def main_func(self):\n",
    "        # 主函数\n",
    "        self.formula_split(self.n, self.m)\n",
    "    \n",
    "    def formula_split(self, n, m):\n",
    "        if m == 0: # 不能再拆分，返回上一层\n",
    "            return\n",
    "        if n == 0: # 分解结束，返回结果\n",
    "            # 把结果保存，直接保存，会保持地址，后面temp的变化会引起结果的变化\n",
    "            self.result.append(self.temp.copy()) \n",
    "            return\n",
    "        if n < m: # n比ｍ小，互换两者\n",
    "            m = n\n",
    "        self.temp.append(m) # 结果中加入m，下面是包含m的情况\n",
    "        self.formula_split(n-m, m) # n-m 继续拆解\n",
    "        self.temp.pop() # 从结果中移除m，以下是不包含m的情况\n",
    "        self.formula_split(n, m-1) # 继续拆分m-1情况\n",
    "    \n",
    "    def print_result(self):\n",
    "        # 在屏幕上整洁地展示结果\n",
    "        for r in self.result:\n",
    "            print(\"{}={}\".format(self.n, \"+\".join([str(i) for i in r])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "q = HomeworkQuestion(4)\n",
    "q.main_func()\n",
    "print(len(q.result))\n",
    "q.print_result()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 动态规划\n",
    "\n",
    "### 重复子问题-查表法\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class FibonacciDp(object):\n",
    "    \"\"\"用动态规划求解斐波那契数列\"\"\"\n",
    "    def __init__(self, n):\n",
    "        self.n = n # 返回数列长度\n",
    "        self.result = [None] * (n+1) # 初始化保存子问题解的列表\n",
    "    \n",
    "    def main_func(self):\n",
    "        # 主函数，计算前n项的值并输出结果\n",
    "        self.fibonacci(self.n)\n",
    "        print(\"斐波那契数列前%d项的是：\" % self.n, self.result)\n",
    "    \n",
    "    def fibonacci(self, n):\n",
    "        # 递归求解\n",
    "        if n == 0 or n == 1: #第一项和第二项的值\n",
    "            self.result[n] = n\n",
    "        # 首先查表，若没有解再去求解，若有解直接返回\n",
    "        if self.result[n] is None:\n",
    "            self.result[n] = self.fibonacci(n-1) + self.fibonacci(n-2)\n",
    "        return self.result[n] # 存在解，直接返回"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "f = FibonacciDp(8)\n",
    "f.main_func()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 重复子问题-制表法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class FibonacciDp2(object):\n",
    "    \"\"\"用动态规划求解斐波那契数列\"\"\"\n",
    "    def __init__(self, n):\n",
    "        self.n = n # 返回数列长度\n",
    "        self.fib = [0] * (n+1) # 初始化斐波那契数列\n",
    "\n",
    "    def fibonacci(self):\n",
    "        # 递推方式求解\n",
    "        self.fib[1] = 1\n",
    "        for i in range(2 , self.n+1):\n",
    "            # 自下而上求解每一项的值\n",
    "            self.fib[i] = self.fib[i-1] + self.fib[i-2]\n",
    "        print(\"斐波那契数列前%d项的是：\" % self.n, self.fib)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "f = FibonacciDp2(8)\n",
    "f.fibonacci()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：荒野求生"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def backpack_recu(W , w , v , n):\n",
    "    \"\"\"用分治算法思想来写递归函数求解背包最大价值\"\"\"\n",
    "    if n == 0 or W == 0 : # 递归退出条件：没有物品，或者承重最大值W为0\n",
    "        return 0 # 都是返回0\n",
    "    # 分解问题\n",
    "    if (w[n-1] > W):\n",
    "         # 若第n件物品的重量大于W，只能选择第一种情况，不放入第n个物品\n",
    "        return backpack_recu(W , w , v , n-1) \n",
    "    else:\n",
    "        # 比较放入第n个物品和不放入第n个物品两个价值比较\n",
    "        v1 = v[n-1] + backpack_recu(W-w[n-1], w , v , n-1) # 放入第n个物品\n",
    "        v2 = backpack_recu(W , w , v , n-1) # 不放入第n个物品\n",
    "        return max(v1,v2) # 合并结果取最大价值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def backpack_dp(W, w, v, n):\n",
    "    \"\"\"动态规划算法思想来解决问题\"\"\"\n",
    "    # 初始化数组dp保存子问题的解\n",
    "    dp = [[0 for wi in range(W + 1)] \n",
    "            for i in range(n + 1)] \n",
    "    for i in range(n + 1):\n",
    "        for wi in range(W + 1):\n",
    "            # 没有物品，或者承重最大值W为0\n",
    "            if i == 0 or wi == 0: \n",
    "                dp[i][wi] = 0 # 最大价值为0\n",
    "            elif w[i - 1] <= wi:\n",
    "                # 比较放入第n个物品和不放入第n个物品两个价值比较\n",
    "                v1 = v[i - 1] + dp[i - 1][wi - w[i - 1]] # 放入第n个物品\n",
    "                v2 = dp[i - 1][wi] # 不放入第n个物品\n",
    "                dp[i][wi] = max(v1,v2) # 取最大价值\n",
    "            else:\n",
    "                # 若第n件物品的重量大于W，只能选择第一种情况，不放入第n个物品\n",
    "                dp[i][wi] = dp[i - 1][wi]\n",
    "    res = dp[n][W] # 最大值必然在这里 \n",
    "    print(\"动态规划求解结果，背包在最大负重{}kg,能装下的最大价值为{}\".format(W, res))\n",
    "    \n",
    "    wt = W # 避免改变输入，用wt表示最大承受重量\n",
    "    includ_pack = [] # 记录放进背包的物品\n",
    "    for i in range(n, 0, -1): \n",
    "        if res <= 0: # 如果最大价值为0，可退出循环，已经找到所有结果\n",
    "            break\n",
    "        # 根据分析，若结果来自 v[i - 1] + dp[i - 1][wi - w[i - 1]]这里，必定包含此物品\n",
    "        # 反之，来自dp[i - 1][wi]，则不包含此物品\n",
    "        if res == dp[i - 1][wt]:\n",
    "            continue\n",
    "        else:\n",
    "            includ_pack.append(w[i - 1]) # 包含此物品\n",
    "            # 求解的逆过程\n",
    "            res = res - v[i - 1]  # 去掉该物品的价值\n",
    "            wt = wt - w[i - 1] # 去掉该物品的重量\n",
    "    # 输出解决方案\n",
    "    for val in includ_pack:\n",
    "        item_id = w.index(val)\n",
    "        print(\"放入编号{}物品,\\t重量为{}kg,\\t价值为{}\".format(item_id+1, val, v[item_id]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "val = [10,30,60,85,100] # 物品价值\n",
    "wt = [5,8,10,15,20] # 物品重量\n",
    "W = 40 # 背包最大负重\n",
    "n = len(val) # 物品数量\n",
    "print(\"分治算法求得最大价值为：\",backpack_recu(W, wt, val, n)) # 分治算法求解\n",
    "backpack_dp(W, wt, val, n) # 动态规划求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def homework_dp(N, M=None):\n",
    "    \"\"\"用动态规划求整数n的分割形式有多少种\"\"\"\n",
    "    if not M: # 默认最大分割数为N-1\n",
    "        M = N - 1\n",
    "    elif M > N: # 最大分割数是N\n",
    "        M = N\n",
    "    # 初始化二维数据记录子问题解\n",
    "    dp=[[0 for i in range(N + 1)] for j in range(N + 1)] \n",
    "    for n in range(0, N + 1):\n",
    "        for m in range(0, N + 1):\n",
    "            if n==0 and m==0: # 关系6\n",
    "                dp[n][m] = 1\n",
    "                continue\n",
    "            if n==0: # 关系1\n",
    "                dp[n][m] = 1\n",
    "                continue\n",
    "            if m==0: # 关系2\n",
    "                dp[n][m] = 0\n",
    "                continue\n",
    "            if n < m: # 关系4\n",
    "                dp[n][m] = dp[n][n]\n",
    "            elif n == m: # 关系5\n",
    "                dp[n][m] = 1 + dp[n][m-1]\n",
    "            else: # 关系3\n",
    "                dp[n][m] = dp[n-m][m] + dp[n][m-1]\n",
    "    print(dp[N][M]) # 输出最终结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = 10\n",
    "homework_dp(n) # 动态规划算法\n",
    "q = HomeworkQuestion(n) # 分治算法\n",
    "q.main_func()\n",
    "print(len(q.result))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 贪心算法\n",
    "### 挑战：埃及分数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math \n",
    "def egyptian_fraction(n, d): \n",
    "    print(\"用埃及分数表示{}/{} =\".format(n, d), end = \" \") \n",
    "    result = [] # 保存埃及分数的分母，分子都是1，不用保存\n",
    "    while n != 0: # 剩余部分为0表示已经得到全部答案 \n",
    "        x = math.ceil(d / n) # 相除，向下取整\n",
    "        result.append(x) # 保存埃及分数的分母\n",
    "        # 求解剩余部分的分子和分母\n",
    "        n = x * n - d  \n",
    "        d = d * x \n",
    "    # 输出结果\n",
    "    for i, di in enumerate(result): \n",
    "        if i != len(result) - 1:\n",
    "            print(\" 1/{} +\" .format(di), end = \" \") \n",
    "        else: # 最后一个\n",
    "            print(\" 1/{}\".format(di))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "egyptian_fraction(6, 14)\n",
    "egyptian_fraction(11, 12) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：超级收银员"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def super_cashier(n, money):\n",
    "    print(\"找零钱{}元需要用到：\".format(n))\n",
    "    # 初始化结果，找零使用每一种货币的数量, 默认数量为0\n",
    "    result = dict(zip(money, [0]*len(money)))\n",
    "    i_money = 0\n",
    "    while n !=0: # 剩余部分为0表示已经得到全部答案\n",
    "        if n - money[i_money] >=0:\n",
    "            n = n - money[i_money]\n",
    "            # 记录此货币需要的数量增加1\n",
    "            result[money[i_money]] += 1 \n",
    "        else:\n",
    "            i_money += 1 # 换下一种货币\n",
    "    # 输出结果\n",
    "    for key, val in result.items():\n",
    "        if val > 0: # 只输出用的货币\n",
    "            print(\"{}元{}张\".format(key, val))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "super_cashier(36, [20,10,5,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 挑战：贪心算法求解荒野求生"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def backpack_greedy(W , w , v , n):\n",
    "    items = [] # 初始化物品信息\n",
    "    for i in range(n):\n",
    "        item = {\n",
    "            \"id\": i+1,# 物品编号\n",
    "            'weight': w[i], # 重量\n",
    "            'value': v[i], # 价值\n",
    "            'v/w': v[i]/w[i], # 主要是求解单位重量的价值\n",
    "        }\n",
    "        # 按照单位重量的价值由大到小排序\n",
    "        if len(items) == 0: # 若列表为空，直接添加进去\n",
    "            items.append(item)\n",
    "        else:\n",
    "            insert_i = 0 # 找到合适的位置插入\n",
    "            while insert_i<len(items):\n",
    "                if items[insert_i]['v/w'] <= item['v/w']:\n",
    "                    break\n",
    "                else:\n",
    "                    insert_i += 1\n",
    "            items.insert(insert_i, item)\n",
    "    print(\"贪心算法求解结果\")\n",
    "    total_val = 0 # 放进背包的物品总价值\n",
    "    for item in items: # 遍历所有物品看是否能放下\n",
    "        if W - item['weight'] >= 0: # 如果能放下\n",
    "            W = W - item['weight'] # 背包的最大负重就要减去该物品\n",
    "            total_val += item['value'] # 总价值添加此物品价值\n",
    "            # 输出添加物品的信息\n",
    "            print(\"放入编号{}物品，重量为{}，价值为{}\".format(\n",
    "                item[\"id\"],\n",
    "                item[\"weight\"],\n",
    "                item[\"value\"]\n",
    "            ))\n",
    "    return total_val # 返回结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "val = [10,20,30] # 物品价值\n",
    "wt = [5,12,20] # 物品重量\n",
    "W = 20 # 背包最大负重\n",
    "n = len(val) # 物品数量\n",
    "backpack_dp(W, wt, val, n) # 动态规划求解\n",
    "print(\"贪心算法求得最大价值为：\", backpack_greedy(W, wt, val, n)) # 贪心算法求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "val = [10,30,60,85,100] # 物品价值\n",
    "wt = [5,8,10,15,20] # 物品重量\n",
    "W = 40 # 背包最大负重\n",
    "n = len(val) # 物品数量\n",
    "backpack_dp(W, wt, val, n) # 动态规划求解\n",
    "print(\"贪心算法求得最大价值为：\", backpack_greedy(W, wt, val, n)) # 贪心算法求解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 穷举\n",
    "### 挑战：韩信点兵问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def count_soldier():\n",
    "    \"\"\"穷举算法求解\"\"\"\n",
    "    total = 1000\n",
    "    while total <=1100: # 枚举范围\n",
    "        # 可行解条件：3人一排，多2人，5人一排，多4人，7人一排，多6人\n",
    "        if (total % 3 == 2) and (total % 5 == 4) and (total % 7 == 6):\n",
    "            print(\"士兵人数\",total)\n",
    "        total += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "count_soldier()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###  极大极小值算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "class MinMaxAlgo(object):\n",
    "    def __init__(self, scores):\n",
    "        self.scores = scores\n",
    "        # 根据完全二叉树性质，求决策树深度，也是算法的递归最大深度\n",
    "        self.max_depth = math.log(len(scores), 2)\n",
    "    \n",
    "    def main_func(self):\n",
    "        # 程序主函数\n",
    "        print(\"最终决策: \", self.minimax(0, 0, True))\n",
    "        \n",
    "    def minimax(self, current_depth, node_index, is_max_turn): \n",
    "        # 递归结束条件: 到达决策最大深度 \n",
    "        if current_depth == self.max_depth:  \n",
    "            return self.scores[node_index]\n",
    "        if is_max_turn: # 我方行动，获取最大值\n",
    "            # 从下面一层中返回的值挑选最大值\n",
    "            return max(\n",
    "                self.minimax(current_depth + 1, node_index * 2, False), # 左结点\n",
    "                self.minimax(current_depth + 1, node_index * 2 + 1, False) # 右结点\n",
    "            ) \n",
    "\n",
    "        else: # 对方行动，从下层返回的值挑选最小值\n",
    "            return min(\n",
    "                self.minimax(current_depth + 1, node_index * 2, True),  \n",
    "                self.minimax(current_depth + 1, node_index * 2 + 1, True)\n",
    "            )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "scores = [7,4,2,9,12,6,25,10]\n",
    "algo = MinMaxAlgo(scores)\n",
    "algo.main_func()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Alpha-Beta剪枝算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "MAX, MIN = 1000, -1000 # 定义正负无穷值\n",
    "class AlphaBetaAlgo(object):\n",
    "    def __init__(self, scores):\n",
    "        self.scores = scores\n",
    "        self.max_depth = math.log(len(scores), 2)\n",
    "    \n",
    "    def main_func(self):\n",
    "        # 程序主函数\n",
    "        # alpha极大值初始化为Min，只要小于所有决策的价值就可以\n",
    "        # beta极小值初始化为Max，只要大于所有决策的价值就可以\n",
    "        print(\"最终决策: \", self.minimax(0, 0, True, alpha=MIN, beta=MAX))\n",
    "    \n",
    "    def minimax(self, current_depth, node_index, is_max_turn, alpha, beta):\n",
    "        if current_depth == self.max_depth:\n",
    "            return self.scores[node_index]\n",
    "        if is_max_turn: # 我方行动，获取最大值,可修改alpha值\n",
    "            best = MIN # 初始化当前极大值\n",
    "            # 依次访问左右子结点\n",
    "            for i in range(0, 2): \n",
    "                val = self.minimax(current_depth + 1, node_index * 2 + i, False, alpha, beta)\n",
    "                best = max(best, val) # 取极大值 \n",
    "                alpha = max(alpha, best) # 是否修改alpha值\n",
    "                if beta <= alpha: # 是否符合剪枝条件\n",
    "                    print(\"beta={},alpha={},可以剪枝\".format(beta, alpha))\n",
    "                    break # 若符合忽略此结点以下的所有子结点\n",
    "            return best\n",
    "        else: # 对方行动，挑选最小值,可修改beta值\n",
    "            best = MAX # 初始化当前极大值\n",
    "            # 依次访问左右子结点\n",
    "            for i in range(0, 2):\n",
    "                val = self.minimax(current_depth + 1, node_index * 2 + i, True, alpha, beta)\n",
    "                best = min(best, val) # 取极小值\n",
    "                beta = min(beta, best) # 是否修改beta值\n",
    "                if beta <= alpha: # 是否符合剪枝条件\n",
    "                    print(\"beta={},alpha={},可以剪枝\".format(beta, alpha))\n",
    "                    break\n",
    "            return best"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "algo = AlphaBetaAlgo([7,4,2,9])\n",
    "algo.main_func()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "algo = AlphaBetaAlgo([7,4,2,9,12,6,25,10])\n",
    "algo.main_func()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最佳优先搜索算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bfs_path(graph, start, target):\n",
    "    def find_min_path(queue):\n",
    "        # 估计函数：寻找代价最小的路径\n",
    "        temp_queue = [] # 记录每条路径的总代价\n",
    "        for path in queue:\n",
    "            total = 0\n",
    "            for node in path:\n",
    "                total += node[1]\n",
    "            temp_queue.append(total)\n",
    "        # 寻找最小代价的路径\n",
    "        path_index = 0\n",
    "        for i in range(len(temp_queue)):\n",
    "            if temp_queue[i] < temp_queue[path_index]:\n",
    "                path_index = i\n",
    "        # 返回此路径，并且在优先队列移除\n",
    "        return queue.pop(path_index)\n",
    "    visited = [] # 保存已经访问的结点\n",
    "    # 优先队列来保存访问结点的成本，初始值为开始位置\n",
    "    priority_queue = [[(start,0)]]\n",
    "    # 特殊情况，开始位置与目标位置相同\n",
    "    if start == target:\n",
    "        return \"开始位置就是目标位置\"  \n",
    "    while priority_queue: # 尝试所有可能，直到队列为空\n",
    "        print('优先队列:', priority_queue)\n",
    "        # 选择优先队列里的一条路径\n",
    "        path = find_min_path(priority_queue)\n",
    "        node = path[-1]\n",
    "        if node[0] not in visited: # 没有访问过\n",
    "            neighbours = graph[node[0]] # 获取这个结点的邻接结点\n",
    "            for neighbour in neighbours:\n",
    "                # 遍历所有邻接结点，创建新的路径添加到优先队列里面\n",
    "                if neighbour[0] not in visited:\n",
    "                    new_path = list(path)\n",
    "                    new_path.append(neighbour)\n",
    "                    if neighbour[0] == target:\n",
    "                        return new_path\n",
    "                    priority_queue.append(new_path)\n",
    "            visited.append(node[0]) # 结点已经访问\n",
    "    # 没有找到路径\n",
    "    return \"两个结点没有路径相连\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "graph = {\n",
    "    \"A\": [(\"B\",3), (\"D\",2), (\"G\",12)],\n",
    "    \"B\": [(\"A\",3), (\"H\",9)],\n",
    "    \"C\": [(\"D\",4),(\"F\",3)],\n",
    "    \"D\": [(\"A\",2), (\"C\",4), (\"E\",5)],\n",
    "    \"E\": [(\"D\",5),(\"F\",1)],\n",
    "    \"F\": [(\"C\",3),(\"E\",1)],\n",
    "    \"G\": [(\"A\",12)],\n",
    "    \"H\": [(\"B\",9)],\n",
    "}\n",
    "print(\"求解得到路径:\", bfs_path(graph, \"A\", \"F\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A*算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "MAX = 1000 # 充当无穷大\n",
    "class Graph(object):\n",
    "    def __init__(self, graph):\n",
    "        self.graph = graph \n",
    "\n",
    "    def get_neighbors(self, v):\n",
    "        return self.graph[v]\n",
    "\n",
    "    def h(self, n):\n",
    "        # 估价函数，我们简化了这个函数，假设每个结点的距离为1\n",
    "        H = {\n",
    "            'A': 1,\n",
    "            'B': 1,\n",
    "            'C': 1,\n",
    "            'D': 1,\n",
    "            'E': 1,\n",
    "            'F': 1,\n",
    "            'G': 1,\n",
    "            'H': 1,\n",
    "        }\n",
    "        return H[n]\n",
    "\n",
    "    def a_star_algorithm(self, start_node, target_node):\n",
    "        # A*算法主程序\n",
    "        open_list = set([start_node]) # 在开放列表中，是结点已被访问，但邻接的结点未被访问\n",
    "        closed_list = set([]) # 那是结点已访问，邻接的结点也都全部访问\n",
    "        g = {} # 记录所有结点到开始结点的距离，若没有记录就当成无穷大\n",
    "        g[start_node] = 0 # 开始结点与自身距离为零\n",
    "        parents = {} # 记录结点的邻接结点\n",
    "        parents[start_node] = start_node # 第一个结点为开始结点\n",
    "\n",
    "        while len(open_list) > 0: # 直到开放列表为空，跳出循环\n",
    "            n = None\n",
    "            for v in open_list: # 寻找f（n）的最小值\n",
    "                if n == None or g.get(v,MAX) + self.h(v) < g.get(n,MAX) + self.h(n):\n",
    "                    n = v\n",
    "            if n == None: # 找不到下一个结点，证明路径不存在\n",
    "                print('两个结点没有路径相连')\n",
    "                return None\n",
    "            print(\"挑选结点:\", n)\n",
    "            # 如果到达目标结点，开始重建回路\n",
    "            if n == target_node:\n",
    "                reconst_path = []\n",
    "                while parents[n] != n: # 直到找到开始结点，跳出循环\n",
    "                    reconst_path.append(n)\n",
    "                    n = parents[n]\n",
    "                reconst_path.append(start_node) # 补充开始结点\n",
    "                reconst_path.reverse() # 翻转列表\n",
    "                print('最佳路径为: {}'.format(reconst_path))\n",
    "                return reconst_path\n",
    "\n",
    "            # 遍历该结点的所有邻接结点\n",
    "            for (neighbor_node, value) in self.get_neighbors(n):\n",
    "                if neighbor_node not in open_list and neighbor_node not in closed_list:\n",
    "                    # 该结点不在开放列表和关闭列表，则加入开放列表\n",
    "                    open_list.add(neighbor_node)\n",
    "                    parents[neighbor_node] = n # 记录其父亲结点，便于构建路径\n",
    "                    g[neighbor_node] = g[n] + value # 记录此结点到开始结点的代价\n",
    "                else:\n",
    "                    # 新的路径代价比原来小则更新路径\n",
    "                    if g[neighbor_node] > g[n] + value: \n",
    "                        parents[neighbor_node] = n\n",
    "                        g[neighbor_node] = g[n] + value\n",
    "                        # 如果该结点在关闭列表，让他重新回到开放列表\n",
    "                        if neighbor_node in closed_list:\n",
    "                            closed_list.remove(neighbor_node)\n",
    "                            open_list.add(neighbor_node)\n",
    "            open_list.remove(n) # 所有邻接结点访问完，移除该结点\n",
    "            closed_list.add(n) # 放到关闭列表\n",
    "        # 尝试所有可能后，若没有找到路径，说明不存在\n",
    "        print('两个结点没有路径相连')\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "graph_list = {\n",
    "    \"A\": [(\"B\",3), (\"D\",2), (\"G\",12)],\n",
    "    \"B\": [(\"H\",9)],\n",
    "    \"D\": [(\"C\",4), (\"E\",5)],\n",
    "    \"C\": [(\"F\",3)],\n",
    "    \"E\": [(\"F\",1)],\n",
    "}\n",
    "graph = Graph(graph_list)\n",
    "graph.a_star_algorithm('A', 'F')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 遗传算法\n",
    "\n",
    "### 挑战：吊死鬼游戏"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "GENES = 'abcdefghijklmnopqrstuvwxyz'  # 基因\n",
    "\n",
    "class Individual(object): \n",
    "    '''此类代表种群中的个体'''\n",
    "    def __init__(self, target, chromosome=None):\n",
    "        self.target = target\n",
    "        if chromosome: # 个体染色体，也就是所猜的单词解\n",
    "            self.chromosome = chromosome\n",
    "        else: # 若没有，创建一个随机的染色体\n",
    "            self.chromosome = self.create_gnome()\n",
    "        self.fitness = self.cal_fitness()  # 此个体的适用能力值\n",
    "\n",
    "    @classmethod # 修饰符对应的函数不需要实例化，不需要 self 参数，但第一个参数需要是表示自身类的 cls 参数\n",
    "    def mutated_genes(cls):\n",
    "        # 基因突变，也就是从a-z中随机挑选一个字母\n",
    "        global GENES \n",
    "        gene = random.choice(GENES) \n",
    "        return gene\n",
    "\n",
    "    def create_gnome(self):\n",
    "        # 初始化个体基因\n",
    "        gnome_len = len(self.target) # 根据目标单词长度随机构建一个字符串\n",
    "        return [self.mutated_genes() for _ in range(gnome_len)]\n",
    "\n",
    "    def mate(self, parent, mutation=0.1):\n",
    "        # 进行繁衍，产生新一代\n",
    "        child_chromosome = [] # 后代染色体\n",
    "        p1_proba = (1 - mutation) / 2 # 取得父母基因概率是一样\n",
    "        for p1, p2 in zip(self.chromosome, parent.chromosome):\n",
    "            # 遍历父母每一个基因，通过一定概率随机获取父母其中一方的基因，还有0.1概率发生变异\n",
    "            prob = random.random() #获取一个0-1的随机数\n",
    "            if prob < p1_proba: # 一半概率选择选择p1\n",
    "                child_chromosome.append(p1) \n",
    "            elif prob < p1_proba*2: # 一半概率选择选择p2\n",
    "                child_chromosome.append(p2) \n",
    "            else: # 剩下1-probability概率发生基因突变\n",
    "                child_chromosome.append(self.mutated_genes()) \n",
    "        # 创建一个新个体，并返回\n",
    "        return Individual(self.target, chromosome=child_chromosome) \n",
    "\n",
    "    def cal_fitness(self): \n",
    "        # 计算适应能力值，记录正确的字符数量\n",
    "        fitness = 0\n",
    "        for gs, gt in zip(self.chromosome, self.target): \n",
    "            if gs == gt: fitness+= 1\n",
    "        return fitness\n",
    "\n",
    "class GeneticAlgorithm(object):\n",
    "    '''遗传算法'''\n",
    "    def __init__(self, target, population_size=100,\n",
    "                 proba_elitism=10, proba_crossover=50,\n",
    "                 mutation=0.1, max_generation=100):\n",
    "        self.population_size = population_size  # 种群大小\n",
    "        self.target = target  # 目标单词\n",
    "        self.proba_elitism = proba_elitism  # 精英模式的比例\n",
    "        self.proba_crossover = proba_crossover  # 交配概率\n",
    "        self.mutation = mutation  # 突变概率\n",
    "        self.max_generation = max_generation  # 最大进化代数，也就是循环最多次数\n",
    "        self.found = False  # 初始化时没有找到最优解\n",
    "        self.generation = 1  # 当前进化的世代，创世纪是1\n",
    "        self.population = []  # 种群,初始化为空\n",
    "    \n",
    "    def init_population(self):\n",
    "        # 初始化第一代个体\n",
    "        for _ in range(self.population_size):\n",
    "            self.population.append(Individual(self.target))\n",
    "\n",
    "    def main(self):\n",
    "        # 主函数\n",
    "        self.init_population() # 产生第一代个体\n",
    "        # 若没有找到答案，并且没有达到最大进化代数，继续下一代演化\n",
    "        while not self.found and self.generation < self.max_generation: \n",
    "            # 按照适应能力排序-内置排序法\n",
    "            self.population = sorted(self.population, key = lambda x:x.fitness, reverse=True)\n",
    "            # 一旦发现有适应值和目标长度一样，说明我们找到这个单词\n",
    "            if self.population[0].fitness == len(self.target): \n",
    "                self.found = True\n",
    "                break\n",
    "            # 记录下一代个体\n",
    "            new_generation = []\n",
    "            # 精英模式，选择前10%的个体进入下一代\n",
    "            s = int((self.proba_elitism*self.population_size)/100) \n",
    "            new_generation.extend(self.population[:s]) \n",
    "            # 90%的个体是通过上一代的交配得到\n",
    "            s = int(((100 - self.proba_elitism)*self.population_size)/100)\n",
    "            # 前50%有繁衍下一代的个体数量\n",
    "            num_crossover =  int(self.proba_crossover * self.population_size / 100)\n",
    "            for _ in range(s):\n",
    "                # 前50%的个体可以有繁衍权力，在这些个体中随机挑选两个\n",
    "                parent1 = random.choice(self.population[:num_crossover])  \n",
    "                parent2 = random.choice(self.population[:num_crossover])\n",
    "                child = parent1.mate(parent2, mutation=self.mutation) # 进行繁衍\n",
    "                new_generation.append(child) # 得到新的一代个体\n",
    "            self.population = new_generation # 新一代的个体代替上一代的\n",
    "            print(\"第{}代\\t单词: {}\\t适应值: {}\".format(\n",
    "                self.generation, \n",
    "                \"\".join(self.population[0].chromosome), \n",
    "                self.population[0].fitness)) \n",
    "            self.generation += 1 # 记录进化的代数\n",
    "        print(\"第{}代\\t单词: {}\\t适应值: {}\".format(\n",
    "            self.generation, \n",
    "            \"\".join(self.population[0].chromosome),\n",
    "            self.population[0].fitness))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ga = GeneticAlgorithm('generation')\n",
    "ga.main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ga = GeneticAlgorithm('generation', population_size=400, proba_crossover=40, mutation=0.15)\n",
    "ga.main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 挑战：定制旅游路线规划师"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 创建基本要素和方法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "class City(object):\n",
    "    \"\"\"城市\"\"\"\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "    \n",
    "    def distance(self, city):\n",
    "        # 计算两个城市的距离,使用欧拉距离，也就是两个坐标的直线距离\n",
    "        dx = abs(self.x - city.x)\n",
    "        dy = abs(self.y - city.y)\n",
    "        return np.sqrt((dx ** 2) + (dy ** 2))\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"({},{})\".format(self.x, self.y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "def generate_city(n):\n",
    "    # 用于生成随机城市，返回两种形式的表达\n",
    "    # city_list：一种是城市坐标列表\n",
    "    # distances_array：一种是城市与城市间的距离矩阵\n",
    "    city_list = []\n",
    "    for i in range(n):\n",
    "        city_list.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))\n",
    "    distances_array = np.array([[np.linalg.norm(city_list[i].distance(city_list[j]))\n",
    "                                 for i in range(n)]\n",
    "                                for j in range(n)])\n",
    "    return city_list, distances_array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 方案一：穷举算法求解问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import permutations #生成全排列\n",
    "def enumeration_algo(city_list):\n",
    "    # 穷举所有路径，求解最短路径\n",
    "    solutions = permutations(city_list) # 返回结果是一个迭代器\n",
    "    optimal_cost = float(\"Inf\") # 初始化为无穷大\n",
    "    optimal_path = None # 记录最短路径访问城市的顺序\n",
    "    try:\n",
    "        while True:\n",
    "            s = next(solutions) # 用next()获取迭代器的一个值\n",
    "            total_disctance = 0 # 初始化此路径的总距离\n",
    "            for i in range(1, len(s)-1):\n",
    "                total_disctance += s[i-1].distance(s[i])\n",
    "            total_disctance += s[-1].distance(s[0])\n",
    "            # print(\"路线距离：\", total_disctance)\n",
    "            if total_disctance < optimal_cost: # 如果比最短路径小，则更新\n",
    "                optimal_cost = total_disctance\n",
    "                optimal_path = s\n",
    "    except StopIteration:\n",
    "        # 迭代器结束\n",
    "        print(f\"最短路径: {round(optimal_cost, 3)}\")\n",
    "        for i, city in enumerate(optimal_path):\n",
    "            if i == len(optimal_path) - 1: # 最后一个城市，需要在后面补上第一个城市\n",
    "                print(f\"{city}->{optimal_path[0]}\")\n",
    "            else:\n",
    "                print(city, end = '->')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "city_list, distances_array = generate_city(4) # 随机生成4个城市地点\n",
    "enumeration_algo(city_list)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 方案二：动态规划解决商旅问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dp_algo(distances_array):\n",
    "    n = len(distances_array) # 城市数量\n",
    "    all_points_set = set(range(n)) # 为城市编号\n",
    "    # cost-key：键值代表当前状态，它是一个队列，包含两个参数（已访问结点集合,最后一个访问结点）\n",
    "    # cost-value：值代表了到达该状态的最优解，它是一个队列，有两个参数（路径距离，倒数第二个访问结点）\n",
    "    cost = {}\n",
    "    # 它的元素是一个队列，包含两个参数（已经访问过的结点，最后一个访问结点），也就是cost的键值\n",
    "    queue = [] # 开放队列保存将要访问的状态\n",
    "    for i in range(n):\n",
    "        # 初始状态就是只一个结点，距离为0，没有倒数第二个结点用None表示 \n",
    "        cost[(tuple([i]), i)] = tuple([0, None])\n",
    "        queue.append((tuple([i]), i))\n",
    "    while queue:\n",
    "        prev_visited, prev_last_point = queue.pop(0) # 获取一个入口，开始搜索\n",
    "        prev_dist, _ = cost[(prev_visited, prev_last_point)]\n",
    "        # 排除已经访问的结点，剩下将要访问的结点\n",
    "        to_visit = all_points_set.difference(set(prev_visited))\n",
    "        for new_last_point in to_visit:\n",
    "            # 遍历所有未访问结点\n",
    "            new_visited = tuple(sorted(list(prev_visited) + [new_last_point]))\n",
    "            # 添加新结点后，更新路径距离\n",
    "            new_dist = prev_dist + distances_array[prev_last_point][new_last_point]\n",
    "            if (new_visited, new_last_point) not in cost:\n",
    "                # 如果没有在cost找到，添加新的元素\n",
    "                cost[(new_visited, new_last_point)] = (new_dist, prev_last_point)\n",
    "                # 把新状态添加进去\n",
    "                queue += [(new_visited, new_last_point)]\n",
    "            else:\n",
    "                # 如果已经有存在cost表中，看是否获得更小的代价，若有则更新值\n",
    "                if new_dist < cost[(new_visited, new_last_point)][0]:\n",
    "                    cost[(new_visited, new_last_point)] = (new_dist, prev_last_point)\n",
    "    # 通过cost表回溯最优路径和计算最短路程\n",
    "    return retrace_optimal_path(cost, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def retrace_optimal_path(cost, n):\n",
    "    points_to_retrace = tuple(range(n)) # 未访问城市数量，初始值为总城市数量\n",
    "    path_key = None # 记录最短距离的状态键值\n",
    "    optimal_cost = float('inf') # 记录最短路径值\n",
    "    for k, v in cost.items():\n",
    "        # 是否为遍历所有城市的状态的解\n",
    "        if k[0] == points_to_retrace:\n",
    "            if v[0] < optimal_cost:\n",
    "                optimal_cost = v[0]\n",
    "                path_key = k\n",
    "    last_point = path_key[1] # 键值的第二个值是最后访问的城市\n",
    "    next_to_last_point = cost[path_key][1] # 找到倒数第二个访问的结点\n",
    "    optimal_path = [last_point] # 记录最优路径\n",
    "    points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))\n",
    "    while next_to_last_point is not None: # 还存在未访问城市，继续循环\n",
    "        last_point = next_to_last_point\n",
    "        path_key = (points_to_retrace, last_point) # 构建键值\n",
    "        next_to_last_point = cost[path_key][1] # 找到上一个城市\n",
    "        optimal_path = [last_point] + optimal_path # 添加到最优路径\n",
    "        # 更新未访问城市\n",
    "        points_to_retrace = tuple(sorted(set(points_to_retrace).difference({last_point})))\n",
    "    return optimal_path, optimal_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "citys, distances_array = generate_city(4) # 有4个城市\n",
    "optimal_path, optimal_cost = dp_algo(distances_array)\n",
    "print(\"========动态规划==========\")\n",
    "print(f\"最短路径: {round(optimal_cost, 3)}\")\n",
    "for i, key in enumerate(optimal_path):\n",
    "    if i == len(citys) - 1: # 最后一个城市，需要在后面补上第一个城市\n",
    "        print(f\"{citys[key]}->{citys[optimal_path[0]]}\")\n",
    "    else:\n",
    "        print(citys[key], end = '->')\n",
    "print(\"========穷举算法==========\")\n",
    "enumeration_algo(citys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 方案三：遗传算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import random, operator\n",
    "import matplotlib.pyplot as plt\n",
    "def generate_city(n):\n",
    "    # 用于生成随机城市，返回两种形式的表达\n",
    "    # city_list：一种是城市坐标列表\n",
    "    # distances_array：一种是城市与城市间的距离矩阵\n",
    "    city_list = []\n",
    "    for i in range(n):\n",
    "        city_list.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))\n",
    "    distances_array = np.array([[np.linalg.norm(city_list[i].distance(city_list[j]))\n",
    "                                 for i in range(n)]\n",
    "                                for j in range(n)])\n",
    "    return city_list, distances_array\n",
    "\n",
    "class GeneticAlgorithm(object):\n",
    "    \"\"\"遗传算法解决旅行者问题\"\"\"\n",
    "    def __init__(self, city_list, population_size,\n",
    "        elite_size, mutation_rate, generations):\n",
    "        self.city_list = city_list # 城市列表\n",
    "        self.population_size = population_size # 种群大小\n",
    "        self.elite_size = elite_size # 精英模式数量\n",
    "        self.mutation_rate = mutation_rate # 变异的概率\n",
    "        self.generations = generations # 进化的总代数\n",
    "        self.progress = [] # 记录每一代的最优结果\n",
    "\n",
    "    def init_population(self):\n",
    "        # 创建一个种群\n",
    "        population = []\n",
    "        for i in range(self.population_size):\n",
    "            route = random.sample(self.city_list, len(self.city_list))\n",
    "            population.append(route)\n",
    "        return population\n",
    "\n",
    "    def fitness(self, route):\n",
    "        # 计算个体的适应能力值\n",
    "        path_distance = 0 # 路径的总距离\n",
    "        for i in range(0, len(route)):\n",
    "            from_city = route[i]\n",
    "            if i + 1 < len(route):\n",
    "                to_city = route[i + 1]\n",
    "            else:\n",
    "                to_city = route[0]\n",
    "            path_distance += from_city.distance(to_city)\n",
    "        distance = path_distance\n",
    "        # 距离越长，适应能力值越小，因此用路径长度的倒数作为适应能力值\n",
    "        return 1 / float(distance)\n",
    "\n",
    "    def rank_routes(self, population):\n",
    "        # 适应能力值排名\n",
    "        fitness_results = {}\n",
    "        for i in range(0, len(population)):\n",
    "            fitness_results[i] = self.fitness(population[i])\n",
    "        return sorted(fitness_results.items(), key = operator.itemgetter(1), reverse = True)\n",
    "\n",
    "    def selection(self, population, population_ranked):\n",
    "        # 根据适应能力值挑选个体进入杂交处理\n",
    "        mating_pool = []  # 记录被挑选的个体\n",
    "        df = pd.DataFrame(np.array(population_ranked), columns=[\"Index\", \"Fitness\"])\n",
    "        # 通过这个方法，把适应能力值归一化后，变成一个按排名的分数\n",
    "        df['cum_sum'] = df.Fitness.cumsum()\n",
    "        df['cum_perc'] = 100 * df.cum_sum / df.Fitness.sum()\n",
    "        for i in range(0, self.elite_size):\n",
    "            # 精英模式\n",
    "            mating_pool.append(population[population_ranked[i][0]])\n",
    "        for i in range(0, len(population_ranked) - self.elite_size):\n",
    "            # 剩下的按轮盘赌选择\n",
    "            pick = 100 * random.random() # 每次生成一个（0到1）随机数\n",
    "            for i in range(0, len(population_ranked)):\n",
    "                if pick <= df.iat[i, 3]: # 看落在那个区间，选择该个体\n",
    "                    mating_pool.append(population[population_ranked[i][0]])\n",
    "                    break\n",
    "        return mating_pool\n",
    "\n",
    "    def breed_population(self, mating_pool):\n",
    "        # 杂交处理\n",
    "        def breed(parent1, parent2):\n",
    "            # 父母杂交，创建新的一代\n",
    "            child_p1 = [] # 来自parent1的基因\n",
    "            child_p2 = [] # 来自parent2的基因\n",
    "            gene_A = int(random.random() * len(parent1))\n",
    "            gene_B = int(random.random() * len(parent1))\n",
    "            start_gene = min(gene_A, gene_B)\n",
    "            end_gene = max(gene_A, gene_B)\n",
    "            # 随机抽取parent1一段基因\n",
    "            for i in range(start_gene, end_gene):\n",
    "                child_p1.append(parent1[i])\n",
    "            for item in parent2:\n",
    "                # 剩下的都来自parent2\n",
    "                if item not in child_p1:\n",
    "                    child_p2.append(item)\n",
    "            child = child_p1 + child_p2\n",
    "            return child\n",
    "\n",
    "        children = [] # 记录下一代个体\n",
    "        length = len(mating_pool) - self.elite_size\n",
    "        pool = random.sample(mating_pool, len(mating_pool)) # 打乱顺序\n",
    "        for i in range(0, self.elite_size):\n",
    "            # 精英模式，直接进入下一代\n",
    "            children.append(mating_pool[i])\n",
    "        for i in range(0, length):\n",
    "            child = breed(pool[i], pool[len(mating_pool) - i - 1])\n",
    "            children.append(child)\n",
    "        return children\n",
    "\n",
    "    def mutate_population(self, population):\n",
    "        # 基因突变处理\n",
    "        def mutate(individual):\n",
    "            for index_city1 in range(len(individual)):\n",
    "                if (random.random() < self.mutation_rate):\n",
    "                    # 若个体（路径）发生变异，随机挑选两个城市交换位置\n",
    "                    index_city2 = int(random.random() * len(individual))\n",
    "                    city1 = individual[index_city1]\n",
    "                    city2 = individual[index_city2]\n",
    "                    individual[index_city1] = city2\n",
    "                    individual[index_city2] = city1\n",
    "            return individual\n",
    "\n",
    "        mutated_population = []\n",
    "        for index_population in range(0, len(population)):\n",
    "            mutated_population.append(mutate(population[index_population]))\n",
    "        return mutated_population\n",
    "\n",
    "    def next_generation(self, current_generation):\n",
    "        # 生成下一代\n",
    "        population_ranked = self.rank_routes(current_generation) # 计算排名\n",
    "        mating_pool = self.selection(current_generation, population_ranked) # 挑选个体繁衍\n",
    "        children = self.breed_population(mating_pool) # 杂交处理\n",
    "        new_generation = self.mutate_population(children) # 基因突变处理\n",
    "        return new_generation # 最后返回新的一代种群\n",
    "\n",
    "    def run(self):\n",
    "        # 算法调用的入口\n",
    "        population = self.init_population()\n",
    "        self.progress.append(1 / self.rank_routes(population)[0][1])\n",
    "        print(\"第一代最短路径: \" + str(self.progress[0]))\n",
    "        for i in range(0, self.generations):\n",
    "            population = self.next_generation(population)\n",
    "            self.progress.append(1 / self.rank_routes(population)[0][1])\n",
    "        print(\"最后一代最短路径: \" + str(1 / self.rank_routes(population)[0][1]))\n",
    "        index_best_route = self.rank_routes(population)[0][0]\n",
    "        return population[index_best_route]\n",
    "\n",
    "    def draw_progress(self):\n",
    "        plt.plot(self.progress)\n",
    "        plt.ylabel('Distance')\n",
    "        plt.xlabel('Generation')\n",
    "        plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "input_size = 15\n",
    "citys, distances_array = generate_city(input_size)\n",
    "ga = GeneticAlgorithm(city_list=citys, population_size=50, elite_size=5, mutation_rate=0.01, generations=80)\n",
    "t = time.time()\n",
    "result = ga.run()\n",
    "runtime = round(time.time() - t, 3)\n",
    "print('遗传算法运行时间', runtime)\n",
    "t = time.time()\n",
    "optimal_path, optimal_cost = dp_algo(distances_array)\n",
    "print(f\"最短路径: {round(optimal_cost, 3)}\")\n",
    "runtime = round(time.time() - t, 3)\n",
    "print('动态规划运行时间', runtime)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}