python笔试题奥特曼打怪兽_2019阿里校招测评题，光明小学完全图最短路径问题(python实现)...
題目：光明小學的小朋友們要舉行一年一度的接力跑大賽了，但是小朋友們卻遇到了一個難題：設計接力跑大賽的線路，你能幫助他們完成這項工作么？
光明小學可以抽象成一張有N個節點的圖，每兩點間都有一條道路相連。光明小學的每個班都有M個學生，所以你要為他們設計出一條恰好經過M條邊的路徑。
光明小學的小朋友們希望全盤考慮所有的因素，所以你需要把任意兩點間經過M條邊的最短路徑的距離輸出出來以供參考。
你需要設計這樣一個函數：
res[][] Solve( N, M, map[][]);
注意：map必然是N * N的二維數組，且map[i][j] == map[j][i]，map[i][i] == 0，-1e8 <= map[i][j] <= 1e8。（道路全部是無向邊，無自環）2 <= N <= 100, 2 <= M <= 1e6。要求時間復雜度控制在O(N^3*log(M))。
map數組表示了一張稠密圖，其中任意兩個不同節點i,j間都有一條邊，邊的長度為map[i][j]。N表示其中的節點數。
你要返回的數組也必然是一個N * N的二維數組，表示從i出發走到j，經過M條邊的最短路徑
你的路徑中應考慮包含重復邊的情況。
一 、求解
先來說一下求解這一題的思路，這個問題的本質就是M步無向圖的最短路徑遍歷，一般求解最短路徑問題，我們首先想到的就是采用遞歸實現。
已知有N個節點，求解從節點i到節點j之間的M步的最短路徑問題，我們可以把M步分解成1步和M-1步：
1、假設存在節點k，且k節點不同于節點i,節點j，第一步求解節點i到節點k之間的1步最短路徑
2、剩下M-1步，可以看做求解節點k到節點j之間的M-1步最短路徑問題
3、當k取不同值時，我們會得到多個距離值，選取最小的一個距離值
#-*- coding: utf-8 -*-
"""Created on Fri Aug 3 08:54:35 2018
@author: zy"""
importnumpy as npdefSolve(maps,M):'''由N個節點兩兩連接組成路徑，選取從節點i->節點j之間的最短M條路徑
param:
maps:二維數組，由兩兩節點之間的路徑長度組成
M:表示所經過的路徑個數'''
'''輸入校驗'''
if notisinstance(maps,(list,np.ndarray)):raise ValueError('輸入參數maps數據類型必須是list或者numpy.array')if len(maps.shape) != 2:raise ValueError('輸入參數maps為二維數組')if maps.shape[0] != maps.shape[1]:raise ValueError('輸入二維數組maps行數和列數要求一致')#計算節點的個數
N =maps.shape[0]if N<2 or N>100:raise ValueError('輸入二維數組maps行數必須在2~100之間')if M<2 or M>1E6:raise ValueError('輸入參數N的值必須在2~1e6之間')#輸入二維數組數值校驗
for i inrange(N):for j inrange(i,N):if maps[i][j] !=maps[j][i]:raise ValueError('輸入二維數組maps必須是對稱的')if maps[i][j] < -1e8 or maps[i][j] > 1e8:raise ValueError('二維數組maps的元素值必須在-1e8~1e8之間')if i==j:if maps[i][j] !=0:raise ValueError('二維數組maps的對角元素值必須是0')#用于保存i->j的路徑值
res =np.zeros_like(maps)#計算節點i->j的最短路徑
for i inrange(N):for j inrange(i,N):
res[i][j]=MinPath(maps,M,i,j)
res[j][i]=res[i][j]returnresdefMinPath(maps,M,i,j):'''計算i->j的最短路徑'''
#遞歸終止條件
if M == 1:returnmaps[i][j]'''計算i->j的最短路徑'''N=maps.shape[0]#用于保存i->j的可能路徑長度
length =np.zeros(N)#遍歷從k->j的最短路徑
for k inrange(N):if k != i and k !=j:#k->j的M-1條最短路徑 + i->k的一條路徑
length[k] = MinPath(maps,M-1,k,j) +maps[i][k]#進行排序，過濾掉為0的值
length =np.sort(length)for i inlength:if i !=0:returniif __name__ == '__main__':#maps = np.array([[0,2,3],[2,0,1],[3,1,0]])
maps = np.array([[0,2,3,4],
[2,0,1,3],
[3,1,0,2],
[4,3,2,0]
])
M= 3result=Solve(maps,M)print(result)
二、時間復雜度分析
我們來分析一下該算法的時間復雜度。
先來分析一下遞歸函數MinPath(maps,M,i,j):
1、函數的規模為M
2、當規模是1時，函數結束
3、假設T(M)表示規模為M的問題所需要的步驟數
算法的遞歸方程為：T(M) = (N-2)T(M - 1) +3N+6
注釋：3N+6表示規模毎減少一次，所做的步驟數
if M==1: 1次
N=maps.shape[0] 1次
length = np.zeros(N) 1次
for k in range(N): N次
if k != i and k != j: N次
+maps[i][k] 當i==j時 N-1次，否則N-2次 我們取N-2次
length =np.sort(length) 1次
最后的for循環 2次或者4次 我們取4次
迭代展開：T(M) = (N-2)T(M - 1) + 3N+6
=(N-2)[(N-2)T(M-2) + 3N + 6] + 3N+6
=(N-2)2T(M-2) + (N-2)(3N+6) + 3N+6
=(N-2)3T(M-3) + (N-2)2(3N+6) + (N-2)(3N+6) + 3N+6
=....
=(N-2)(M-1) + (N-2)(M-2)(3N+6)+...+3N+6
=(N-2)(M-1) + [(N-2)(M-1)(3N+6) - 3N-6]/(N-3)
= O((N-2)(M-1))
Solve函數中遞歸函數循環的次數為N(1+N)/2，所以算法的復雜度為O(N2(N-2)(M-1))。并沒有滿足題目的要求，更好的求解方法我還沒有想到，有了解的大佬可以告訴小弟。
參考文章：
總結
以上是生活随笔為你收集整理的python笔试题奥特曼打怪兽_2019阿里校招测评题，光明小学完全图最短路径问题(python实现)...的全部內容，希望文章能夠幫你解決所遇到的問題。
