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