optimization-checkpoint.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 图的遍历"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def BFS(graph, s):\n",
    "    queue = [] # \n",
    "    queue.append(s)\n",
    "    seen = set() # \n",
    "    while len(queue) > 0:\n",
    "        vertex = queue.pop(0)\n",
    "        nodes = graph[vertex]\n",
    "        for w in nodes:\n",
    "            if w not in seen:\n",
    "                queue.append(w)\n",
    "                seen.add(w)\n",
    "\n",
    "        # print(vertex)\n",
    "\n",
    "    print(seen)\n",
    "\n",
    "\n",
    "graph = {\n",
    "    \"A\": [\"B\", \"C\"],\n",
    "    \"B\": [\"A\", \"C\", \"D\"],\n",
    "    \"C\": [\"A\", \"B\", \"E\", \"D\"],\n",
    "    \"D\": [\"B\", \"C\", \"E\", \"F\"],\n",
    "    \"F\": [\"D\"],\n",
    "    \"E\": [\"C\", \"D\"],\n",
    "}\n",
    "\n",
    "BFS(graph, \"F\")\n",
    "#\n",
    "# def breadth_travel(root):\n",
    "#     \"\"\"利⽤队列实现树的层次遍历\"\"\"\n",
    "#     if root == None:\n",
    "#         return\n",
    "#     queue = []\n",
    "#     queue.append(root)\n",
    "#     while queue:\n",
    "#         node = queue.pop(0)\n",
    "#         print(node.elem)\n",
    "#         if node.lchild is not None:\n",
    "#             queue.append(node.lchild)\n",
    "#         if node.rchild != None:\n",
    "#             queue.append(node.rchild)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# dijkstra heap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq as hp\n",
    "import math\n",
    "\n",
    "graph = {\n",
    "\n",
    "    \"A\": {\"B\": 5, \"C\": 1},\n",
    "    \"B\": {\"A\": 5, \"C\": 2, \"D\": 1},\n",
    "    \"C\": {\"A\": 1, \"B\": 2, \"E\": 8, \"D\": 4},\n",
    "    \"D\": {\"B\": 1, \"C\": 4, \"E\": 3, \"F\": 6},\n",
    "    \"F\": {\"D\": 6},\n",
    "    \"E\": {\"C\": 8, \"D\": 3},\n",
    "}\n",
    "\n",
    "\n",
    "def init_distance(graph, s):\n",
    "    distance = {s: 0}\n",
    "    for key in graph:\n",
    "        if key != s:\n",
    "            distance[key] = math.inf\n",
    "    return distance\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<module 'heapq' from 'F:\\\\Installpath\\\\Anaconda3\\\\lib\\\\heapq.py'>\n",
      "{'A': 0, 'B': inf, 'C': inf, 'D': inf, 'F': inf, 'E': inf}\n",
      "seen:    {'A'}\n",
      "nodes:    dict_keys(['B', 'C'])\n",
      "change distance for B:    {'A': 0, 'B': 5, 'C': inf, 'D': inf, 'F': inf, 'E': inf}\n",
      "change distance for C:    {'A': 0, 'B': 5, 'C': 1, 'D': inf, 'F': inf, 'E': inf}\n",
      "seen:    {'A', 'C'}\n",
      "nodes:    dict_keys(['A', 'B', 'E', 'D'])\n",
      "change distance for B:    {'A': 0, 'B': 3, 'C': 1, 'D': inf, 'F': inf, 'E': inf}\n",
      "change distance for E:    {'A': 0, 'B': 3, 'C': 1, 'D': inf, 'F': inf, 'E': 9}\n",
      "change distance for D:    {'A': 0, 'B': 3, 'C': 1, 'D': 5, 'F': inf, 'E': 9}\n",
      "seen:    {'A', 'B', 'C'}\n",
      "nodes:    dict_keys(['A', 'C', 'D'])\n",
      "change distance for D:    {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'F': inf, 'E': 9}\n",
      "seen:    {'A', 'D', 'B', 'C'}\n",
      "nodes:    dict_keys(['B', 'C', 'E', 'F'])\n",
      "change distance for E:    {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'F': inf, 'E': 7}\n",
      "change distance for F:    {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'F': 10, 'E': 7}\n",
      "seen:    {'A', 'D', 'B', 'C'}\n",
      "nodes:    dict_keys(['A', 'C', 'D'])\n",
      "seen:    {'A', 'D', 'B', 'C'}\n",
      "nodes:    dict_keys(['B', 'C', 'E', 'F'])\n",
      "seen:    {'D', 'E', 'A', 'C', 'B'}\n",
      "nodes:    dict_keys(['C', 'D'])\n",
      "seen:    {'D', 'E', 'A', 'C', 'B'}\n",
      "nodes:    dict_keys(['C', 'D'])\n",
      "seen:    {'D', 'E', 'A', 'C', 'F', 'B'}\n",
      "nodes:    dict_keys(['D'])\n",
      "{'A': 0, 'B': 3, 'C': 1, 'D': 4, 'F': 10, 'E': 7}\n"
     ]
    }
   ],
   "source": [
    "def dijkstra(graph, s):\n",
    "    pqueue = []\n",
    "    hp.heappush(pqueue, (0, s)) #\n",
    "    print(hp)\n",
    "    seen = set()\n",
    "    distance = init_distance(graph, s)\n",
    "    print(distance)\n",
    "    while len(pqueue) > 0:\n",
    "        pair = hp.heappop(pqueue)\n",
    "        dist = pair[0] # \n",
    "        node = pair[1] #\n",
    "        seen.add(node)\n",
    "        print(\"seen:   \", seen)\n",
    "        nodes = graph[node].keys() # \n",
    "        print(\"nodes:   \", nodes)\n",
    "        #\n",
    "        for w in nodes:\n",
    "            if dist + graph[node][w] < distance[w]:\n",
    "                hp.heappush(pqueue, (dist + graph[node][w], w))\n",
    "                distance[w] = dist + graph[node][w]\n",
    "                print(f\"change distance for {w}:   \", distance)\n",
    "    return distance\n",
    "\n",
    "\n",
    "d = dijkstra(graph, \"A\")\n",
    "print(d)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# dijkstra 动态规划"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 3, 1, 4, 7, 10]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Inf = float('inf')\n",
    "Adjacent = [[0, 5, 1, Inf, Inf, Inf],\n",
    "            [5, 0, 2, 1, Inf, Inf],\n",
    "            [1, 2, 0, 4, 8, Inf],\n",
    "            [Inf, 1, 4, 0, 3, 6],\n",
    "            [Inf, Inf, 8, 3, 0, Inf],\n",
    "            [Inf, Inf, Inf, 6, Inf, 0]]\n",
    "Src, Dst, N = 0, 5, 6\n",
    "\n",
    "\n",
    "# 动态规划\n",
    "def dijstra(adj, src, dst, n):\n",
    "    dist = [Inf] * n  #\n",
    "    dist[src] = 0\n",
    "    book = [0] * n  # 记录已经确定的顶点\n",
    "    # 每次找到起点到该点的最短途径\n",
    "    u = src\n",
    "    for _ in range(n - 1):  # 找n-1次\n",
    "        book[u] = 1  # 已经确定\n",
    "        # 更新距离并记录最小距离的结点\n",
    "        next_u, minVal = None, float('inf')\n",
    "        for v in range(n):  # w\n",
    "            w = adj[u][v]\n",
    "            if w == Inf:  # 结点u和v之间没有边\n",
    "                continue\n",
    "            if not book[v] and dist[u] + w < dist[v]:  # 判断结点是否已经确定了\n",
    "                dist[v] = dist[u] + w\n",
    "                if dist[v] < minVal:\n",
    "                    next_u, minVal = v, dist[v]\n",
    "        # 开始下一轮遍历\n",
    "        u = next_u\n",
    "    print(dist)\n",
    "    return dist[dst]\n",
    "\n",
    "\n",
    "dijstra(Adjacent, Src, Dst, N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 模拟退火"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import division\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    " \n",
    "#define aim function\n",
    "def aimFunction(x):\n",
    "    y=x**3-60*x**2-4*x+6\n",
    "    return y\n",
    "x=[i/10 for i in range(1000)]\n",
    "y=[0 for i in range(1000)]\n",
    "for i in range(1000):\n",
    "    y[i]=aimFunction(x[i])\n",
    "\n",
    "plt.plot(x,y)\n",
    "plt.show()\n",
    "\n",
    "print('最小值',y.index(min(y)))   \n",
    "print(\"最优值\",x[400], min(y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T=1000 #initiate temperature\n",
    "Tmin=10 #minimum value of terperature\n",
    "x=np.random.uniform(low=0,high=100)#initiate x\n",
    "k=50 #times of internal circulation \n",
    "y=0#initiate result\n",
    "t=0#time\n",
    "while T>=Tmin:\n",
    "    for i in range(k):\n",
    "        #calculate y\n",
    "        y=aimFunction(x)\n",
    "        #generate a new x in the neighboorhood of x by transform function\n",
    "        xNew=x+np.random.uniform(low=-0.055,high=0.055)*T\n",
    "        if (0<=xNew and xNew<=100):\n",
    "            yNew=aimFunction(xNew)\n",
    "            if yNew-y<0:\n",
    "                x=xNew\n",
    "            else:\n",
    "                #metropolis principle\n",
    "                p=math.exp(-(yNew-y)/T)\n",
    "                r=np.random.uniform(low=0,high=1)\n",
    "                if r<p:\n",
    "                    x=xNew\n",
    "    t+=1\n",
    "#     print(t)\n",
    "    T=1000/(1+t)\n",
    "    \n",
    "print (x,aimFunction(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}