維特比演算法說白了就是動態規劃實現最短路徑，只要知道「動態規劃可以降低復雜度」這一點就能輕松理解維特比演算法
維特比演算法是一個特殊但應用最廣的動態規劃演算法，利用動態規劃，可以解決任何一個圖中的最短路徑問題。而維特比演算法是針對一個特殊的圖——籬笆網路的有向圖（Lattice )的最短路徑問題而提出的。 它之所以重要，是因為凡是使用隱含馬爾可夫模型(Hidden Markov Model，HMM)描述的問題都可以用它來解碼，包括今天的數字通信、語音識別、機器翻譯、拼音轉漢字、分詞等。——《數學之美》 ps 多處摘錄此書，不再贅述。
籬笆網路有向圖的特點是同一列節點有多個，並且和上一列節點交錯地連接起來。同一列節點代表同一個時間點上不同的狀態的並列，大概因為這種一列一列整齊的節點和交錯的邊很像籬笆而得名。
假設上圖每一列分別有n1……nn個節點，如果不使用動態的話，那麼計算復雜度就是O(n1*n2……nn)。
而維特比演算法的精髓就是，既然知道到第i列所有節點Xi{j=123…}的最短路徑，那麼到第i+1列節點的最短路徑就等於到第i列j個節點的最短路徑+第i列j個節點到第i+1列各個節點的距離的最小值。
這是一句大白話，所謂中文偽碼。
分析一下復雜度，假設整個籬笆有向圖中每一列節點最多有D個（也就是圖的寬度為D），並且圖一共有N列，那麼，每次計算至多計算D*D次（從i列的D個節點中挑一個計算到i+1列D個節點的距離）。至多計算N次。那麼復雜度驟減為O（ND2），遠遠小於窮舉O（DN）。
Ⅱ 求助python的最短路徑問題
這是一個深州前度優先搜索演算法（Deepth First Search, DFS）
演算法核心是不斷遞歸，直到找到目標，入隊一種可能方案，return返回上一遞歸，再次嘗試以當前點開始計算有沒有其他方案，如有則繼續遞歸並入隊，如沒有則再次return
簡單來說就是這樣的結構：
def dfs(position, value):
# position 傳參位置，value 傳參到現在的計算結果
if 到達目標:
判斷value是否比最短路徑短
return value
else:
for x in position的所有可能下一路徑:
if x在路徑列表中:
# 不能有重復路徑，變成回環
continue
else:
獲取路徑x的值
改變position
入告跡檔隊 dfs(new_position, value+x
這個代碼用的是襪亂字典存儲每個點可到達的點以及路程
然後深度優先搜索
不懂再追問
Ⅲ 如何用python在arcgis中編寫程序，求兩點的最短路徑
你是想學PYTHON編程還是只是想只得到這個PYTHON文件。可以給你提供一條簡潔的途徑用modelbuilder來實現，將多個SHP文件拖入進去，再把MERGE工具拖進去，雙擊modelbuilder中的merge工具框設置，再雙擊output dataset框設置輸出。然後將這些shp文件用倒數第二個按鈕添加鏈接的功能將他們一個個與merge工具框鏈接起來。最後點擊model-export-to srcipt-python 就會輸出一個python文件，可以用記事本打開查看裡面的代碼。
Ⅳ 如何使用QGIS裡面的python編程求最優路線
題主：
你的問題描述不是很詳盡。
比如，你所說的最短路徑，是直線還是沿道路的最短路徑。如果是後者這個稍微麻煩些，並需要補充路網數據。如是直線距離最短，那麼，你所需求的是以最短路徑走訪完所有農戶（以居委會為起點），還是每戶至居委會的距離最短（兩點間直線距離）。還有就是GIS文件的屬性表和你的EXCEL表格的關系...
所以，如你題中所說，建議你現在做的有以下幾件事：
①明確要目標到底是什麼，就如上面所說的一樣；
②對於每一戶（包括居委會），你還需獲取其坐標（X/Y），這個在GIS軟體中易獲取；
③將excel數據連接至屬性表中。
最後，你這個項目要解決的問題有Dijkstra、Floyd、A*等演算法可用。但是具體用哪一種還需根據問題進行優選...
希望對你有所幫助！！！
Ⅳ python 的 networkx 的中有沒有 函數 可以直接取出與 某一個點（node）所相連的所有邊的個數
path=nx.all_pairs_shortest_path(G) #調用多源最短路徑演算法，計算圖G所有節點間的磨檔最短路徑
print path[0][2] #輸出節點0、2之間的最短路徑瞎喚亂序列：鏈悉 [0, 1, 2]
Ⅵ Python數據分析在數學建模中的應用匯總（持續更新中！）
1、Numpy常用方法使用大全（超詳細）
1、Series和DataFrame簡單入門
2、Pandas操作CSV文件的讀寫
3、Pandas處理DataFrame，Series進行作圖
1、Matplotlib繪圖之屬性設置
2、Matplotlib繪制誤差條形圖、餅圖、等高線圖、3D柱形圖
1、層次分析法（AHP）——算數平均值法、幾何平均值法、特徵值法（Python實現，超詳細注釋）
2、Python實現TOPSIS分析法（優劣解距離法）
3、Python實現線性插值和三次樣條插值
4、Python實現線性函數的擬合演算法
5、Python實現統計描述以及計算皮爾遜相關系數
6、Python實現迪傑斯特拉演算法和貝爾曼福特演算法求解最短路徑
Ⅶ 如何用python實現《多社交網路的影響力最大化問題分析》中的演算法
經過一周，現已初步完成，其中多出代碼不夠美觀以及效率不高，還請指點
# _*_ coding:utf-8 _*_
# ==================================================================================
#
# Description: Influence Maximization on Multiple Social Networks
#
# ==================================================================================
import matplotlib.pyplot as plt
import networkx as nx
import heapq
#總圖
G = nx.DiGraph()
def load_graph(file):
'''
載入文件為列表格式,並得到G,畫出圖結構
'''
#將總列表設成全局格式
global gllist
#迭代文件中每個元素
with open(file) as f:
lines = f.readlines()
mylist = [line.strip().split() for line in lines]
gllist = []
#將字元串型轉換為整型
for i in mylist:
gllist.append(i[:-2]+map(lambda x: float(x), i[-2:]))
print '初始全局列表:'
print gllist
drawlist=[]
#提取二維列表mylist每行前三個元素,賦給新的列表drawlist
for i in range(len(mylist)):
drawlist.append([])
for j in range(3):
drawlist[i].append(mylist[i][j])
#將列表drawlist載入為有向加權圖
G.add_weighted_edges_from(drawlist)
nx.draw(G, with_labels=True, width=1, node_color='y', edge_color='b')
plt.show()
print 'G圖中所有節點:',G.nodes()
print 'G圖中所有邊:',G.edges()
print '\n'
def get_self_node(gllist, target=None):
'''
獲取目標節點的自傳播節點,返回selflist並包含目標節點
'''
#初始化自傳播節點列表
selflist = [target]
#存放已傳播節點列表
haslist = []
flag = 0
while (flag != 0):
flag = 0
for target in selflist:
if target not in haslist:
for i in range(len(gllist)):
#判斷二維列表中,每行第三個元素是否為1,若為1，則為自傳播節點
if ((gllist[i][0] == target)or(gllist[i][1]==target))and(gllist[i][3]==1.0):
if gllist[i][0] == target:
if gllist[i][1] not in haslist:
selflist.append(gllist[i][1])
haslist.append(gllist[i][1])
flag += 1
else:
if gllist[i][0] not in haslist:
selflist.append(gllist[i][0])
haslist.append(gllist[i][0])
flag += 1
#去除重復元素
haslist = set(haslist)
selflist = set(selflist)
#去除重復元素
selflist = set(selflist)
return selflist
def longest_path(gllist,source=None,target=None):
'''
獲取起始點到實體的最大路徑集合,返回為longestpath列表
'''
longestpath = []
newlist = []
for i in range(len(gllist)):
newlist.append([])
for j in range(3):
newlist[i].append(gllist[i][j])
#構建圖結構
G1 = nx.DiGraph()
#添加帶權有向邊
G1.add_weighted_edges_from(newlist)
#獲取目標節點的所有自傳播街邊,並存入selflist中
selflist = get_self_node(gllist, target)
max_path = 0
val_path = 1
#獲取初始節點到目標節點及目標節點的自傳播節點的最大路徑
for v in selflist:
if v != source:
#遍歷兩點之間所有路徑,並進行比對
for path in nx.all_simple_paths(G1,source=source,target=v):
#判斷路徑後兩個元素是否為相同實體（如：b1->b2）
if is_self_transmit_node(path[-2], v) == 0:
for i in range(0, len(path)-1):
val_path *= G1.get_edge_data(path[i], path[i+1])['weight']
if max_path < val_path:
max_path = val_path
val_path = 1
#若目標節點為起始節點則直接跳出
else: continue ############ 有待商榷 ##############
longestpath.append(max_path)
#返回初始節點到實體的最大路徑
return longestpath
def is_self_transmit_node(u, v):
'''
判斷目標節點不為起始節點的自傳播點
'''
flag = 0
#獲得起始節點的所有自傳播點
selflist = get_self_node(gllist, v)
for x in selflist:
if u == x:
flag = 1
return flag
def single_strong_infl(longestpath):
'''
計算起始點到實體的傳播概率（影響強度）,返回影響強度stronginfl
'''
temp = 1
for x in longestpath:
temp *= 1-x
stronginfl = 1-temp
return stronginfl
def all_strong_infl(G):
'''
獲得每個節點對實體的影響概率
'''
allstrong = [] #初始化所有節點的加權影響范圍列表
gnodes = [] #初始化節點列表
tempnodes = [] #初始化臨時節點列表
gnodes = G.nodes()
for u in gnodes:
strong = 0 #存儲初始節點對每個實體的影響范圍加權，初始化為0
#重置臨時節點列表
tempnodes = G.nodes()
for v in tempnodes:
#非自身節點
if u != v:
#判斷目標節點不為起始節點的自傳播點
if is_self_transmit_node(v, u) == 0:
#獲取起始節點到實體間最大加權路徑，並存入longestpath
longestpath = longest_path(gllist, u, v)
#去除已遍歷目標節點的所有自傳播節點
renode = get_self_node(gllist, v)
for x in renode:
if x != v:
tempnodes.remove(x)
#計算起始節點到實體間傳播概率（影響強度）
stronginfl = single_strong_infl(longestpath)
strong += stronginfl
#添加單個節點到所有實體的加權影響范圍
allstrong.append([u, round(strong, 2)])
#返回每個節點到所有實體的加權影響范圍
return allstrong
#output allstrong : [['a1', 2.48], ['a2', 1.6880000000000002], ['b1', 0.7], ['b2', 0], ['c1', 0], ['d2', 0.6]]
def uS_e_uppergain(u, ev, S):
'''
獲取節點u在集合S的基礎上對實體ev的影響增益, 傳入候選節點,上界gain(u|S, ev)
'''
#獲取目前實體的所有自傳播節點
selflist = get_self_node(gllist, ev)
stronglist = []
#遍歷自傳遍節點
for v in selflist:
'''
判斷節點v是否存在種子集合S中
其中v為單個節點,如v(ev, Gi)
S為種子節點集合,如['a1','a2','b1','b2','c1','d2']
'''
if v in S:
ppSv = 1
else:
longestpath = []
#遍歷種子集合
for s in S:
#初始化路徑權值與最大路徑權值
val_path = 1
max_path = 0
#遍歷兩點之間所有路徑，並進行比對
for path in nx.all_simple_paths(G,source=s,target=v):
#判斷路徑後兩個元素是否為相同實體（如：b1->b2）
if is_self_transmit_node(path[-2], v) == 0:
for i in range(0, len(path)-1):
val_path *= G.get_edge_data(path[i], path[i+1])['weight']
if max_path < val_path:
max_path = val_path
#重置路徑權值為1
val_path = 1
#將最大加權路徑存入longestpath列表
longestpath.append(max_path)
#得到上界pp(S,v)的影響概率,上界pp(S,v)
ppSv = single_strong_infl(longestpath)
stronglist.append(ppSv)
#得到上界pp(S,ev)的影響概率,上界pp(S,ev)
ppSev = single_strong_infl(stronglist)
#獲取pp(u,ev)
ppuev = single_strong_infl(longest_path(gllist, u, ev))
#計算上界gain(u|S，ev)
uSevgain = (1 - ppSev) * ppuev
return uSevgain
def uppergain(u, emu, ems, S):
'''
在已有種子集合S的基礎上,求得節點u的影響增益上界,
其中傳進參數ems為二維列表,如[['a1',2.48],['a2',1.688]],S則為['a1','a2']
'''
uSgain = 0.0
#遍歷emu得到列表形式,得到如['a1',2.48]形式
for ev in emu:
#判斷節點是否存在種子集合中
if ev[0] in S:
uSgain += uS_e_uppergain(u, ev[0], S)
else:
uSgain += ev[1]
#返回上界gain(u|S)
return uSgain
def bound_base_imms(G, k):
'''
完全使用影響增益上界的方式選擇top-k個種子節點的過程
'''
#初始化emu,H,初始化ems=空集,S=空集
Htemp = []
Htemp = all_strong_infl(G)
H = []
#遍歷Htemp=[['a1',2.48],['a2',1.688]],得到如['a1',2.48]形式
for x in Htemp:
#逐個獲取二維列表中每一行，形式為['a1',2.48,0]
H.append([x[0],x[1],0])
emu = []
emu = all_strong_infl(G)
ems = []
S = []
for i in range(k):
#提取堆頂元素,tnode的形式為['a1',2.48,0]
tnode = heapq.nlargest(1, H, key=lambda x: x[1])
#將[['b2', 3.1, 0]]格式改為['b2', 3.1, 0]格式
tnode = sum(tnode, [])
while (tnode[2] != i):
gain = 0.0
#獲取節點u的影響增益上界
gain = uppergain(tnode, emu, ems, S)
#賦值影響范圍
tnode[1] = gain
#修改status
tnode[2] = i
#對堆進行排序
H = heapq.nlargest(len(H), H, key=lambda x: x[1])
#獲取堆頂元素
tnode = heapq.nlargest(1, H, key=lambda x: x[1])
tnode = sum(tnode, [])
#添加node到種子集合
S.append([tnode[0]])
#更新ems,添加新節點及節點對每個實體的影響范圍加權
ems.append([tnode[0], tnode[1]])
#刪除堆頂元素
H.remove(tnode)
print ems
return sum(S, [])
if __name__=='__main__':
#大小為k的種子集合S
k = 60
#載入文件數據,得到圖G和初始列表gllist
load_graph('test.txt')
#完全使用影響增益上界值的計算過程函數,列印種子集合S
print '種子集合:',bound_base_imms(G, k)
test.txt
a1 b1 0.2 0
a1 c1 0.8 0
a2 b2 0.4 0
a2 d2 1 0
b1 c1 0.7 0
c2 a2 0.8 0
d2 b2 0.6 0
a1 a2 1 1
a2 a1 0.1 1
....
a1 l1 0.5 0
a1 m1 0.5 0
a1 q1 0.5 0
a1 v1 0.5 0
a1 z1 0.5 0
a1 s1 0.5 0
a1 w1 0.5 0
a1 u1 0.5 0
其中前兩列為傳播實體，第三列為實體間傳播概率，最後一列為0代表同一網路傳播，為1代表網路間自傳播。
下來要進行優化：
1.採用獨立級聯模型，設置閾值
2.將最大路徑改為最短路徑，利用log
Ⅷ Python中networkx中shortest_path使用的是哪一種最短路徑方法
不全是。依據傳入的參數決定調用哪種演算法。
看源碼：至少涉及了dijkstra、廣乎灶度優先/深度優先演算法。
ifsource歲遲扮isNone:
iftargetisNone:
##Findpathsbetweenallpairs.
ifweightisNone:
paths=nx.all_pairs_shortest_path(G)
else:
paths=nx.all_pairs_dijkstra_path(G,weight=weight)
else:
##Findpathsfromallnodesco-accessibletothetarget.
旦桐directed=G.is_directed()
ifdirected:
G.reverse(=False)
ifweightisNone:
paths=nx.single_source_shortest_path(G,target)
else:
paths=nx.single_source_dijkstra_path(G,target,weight=weight)
#.
fortargetinpaths:
paths[target]=list(reversed(paths[target]))
ifdirected:
G.reverse(=False)
else:
iftargetisNone:
##.
ifweightisNone:
paths=nx.single_source_shortest_path(G,source)
else:
paths=nx.single_source_dijkstra_path(G,source,weight=weight)
else:
##Findshortestsource-targetpath.
ifweightisNone:
paths=nx.bidirectional_shortest_path(G,source,target)
else:
paths=nx.dijkstra_path(G,source,target,weight)
Ⅸ 一道演算法題，用python初始化一顆二叉樹並求解其最短路徑的值
二叉樹演算法，可能按照你的需求不是很多：
下面是我用的一個，不過你可以借鑒一下的：
# -*- coding: cp936 -*-
import os
class Node(object):
"""docstring for Node"""
def __init__(self, v = None, left = None, right=None, parent=None):
self.value = v
self.left = left
self.right = right
self.parent = parent
class BTree(object):
"""docstring for BtTee """
def __init__(self):
self.root = None
self.size = 0
def insert(self, node):
n = self.root
if n == None:
self.root = node
return
while True:
if node.value <= n.value:
if n.left == None:
node.parent = n
n.left = node
break
else:
n = n.left
if node.value > n.value:
if n.right == None:
n.parent = n
n.right = node
break
else:
n = n.right
def find(self, v):
n = self.root # http://yige.org
while True:
if n == None:
return None
if v == n.value:
return n
if v < n.value:
n = n.left
continue
if v > n.value:
n = n.right
def find_successor(node):
'''查找後繼結點'''
assert node != None and node.right != None
n = node.right
while n.left != None:
n = n.left
return n
def delete(self, v):
n = self.find(v)
print "delete:",n.value
del_parent = n.parent
if del_parent == None:
self.root = None;
return
if n != None:
if n.left != None and n.right != None:
succ_node = find_successor(n)
parent = succ_node.parent
if succ_node == parent.left:
#if succ_node is left sub tree
parent.left = None
if succ_node == parent.right:
#if succ_node is right sub tree
parent.right = None
if del_parent.left == n:
del_parent.left = succ_node
if del_parent.right == n:
del_parent.right = succ_node
succ_node.parent = n.parent
succ_node.left = n.left
succ_node.right = n.right
del n
elif n.left != None or n.right != None:
if n.left != None:
node = n.left
else:
node = n.right
node.parent = n.parent
if del_parent.left == n:
del_parent.left = node
if del_parent.right == n:
del_parent.right = node
del n
else:
if del_parent.left == n:
del_parent.left = None
if del_parent.right == n:
del_parent.right = None
def tranverse(self):
def pnode(node):
if node == None:
return
if node.left != None:
pnode(node.left)
print node.value
if node.right != None:
pnode(node.right)
pnode(self.root)
def getopts():
import optparse, locale
parser = optparse.OptionParser()
parser.add_option("-i", "--input", dest="input", help=u"help name", metavar="INPUT")
(options, args) = parser.parse_args()
#print options.input
return (options.input)
if __name__ == '__main__':
al = [23, 45, 67, 12, 78,90, 11, 33, 55, 66, 89, 88 ,5,6,7,8,9,0,1,2,678]
bt = BTree()
for x in al :
bt.insert(Node(x))
bt.delete(12)
bt.tranverse()
n = bt.find(12)
if n != None:
print "find valud:",n.value