貨物運(yùn)輸問(wèn)題

遞歸方程為：

更為一般形式的遞歸方程

看起來(lái)是不是像可以使用分治的策略實(shí)現(xiàn)，但是min里面子問(wèn)題太多了，只能使用動(dòng)態(tài)規(guī)劃的招了。

i,j是什么含義了？動(dòng)態(tài)規(guī)劃里i,j都是指的是問(wèn)題規(guī)模，對(duì)應(yīng)到貨物運(yùn)輸問(wèn)題指的是什么了？我們從數(shù)學(xué)上理解i,j是指數(shù)組arr = [1,2,3,4,5,6,7,8]兩邊的標(biāo)號(hào)，或者子問(wèn)題對(duì)應(yīng)的起始和終止標(biāo)號(hào)，類(lèi)似與快排里面的數(shù)組的標(biāo)號(hào)，實(shí)際問(wèn)題抽象為數(shù)組之后，就比較容易理解，在實(shí)際問(wèn)題里面i,j就非常不好理解，i,j是指的是子問(wèn)題的起始標(biāo)號(hào)和終止標(biāo)號(hào)。

不是動(dòng)態(tài)規(guī)劃里[i,j]指的是問(wèn)題規(guī)模嗎？這里怎么是子問(wèn)題的起始標(biāo)號(hào)和終止標(biāo)號(hào)，起始標(biāo)號(hào)和終止標(biāo)號(hào)實(shí)際上對(duì)應(yīng)的就是問(wèn)題的規(guī)模，j-i就是問(wèn)題規(guī)模，也就是使用了二維表示了一維的規(guī)模，快排里也可以不適用quick_sort(arr,p,q),直接使用quick_sort(left_or_right_arr)內(nèi)部直接使用的left_or_right_arr的0和end。要想原地操作就需要借助于p,q。

假如一個(gè)實(shí)際問(wèn)題已經(jīng)抽象成了一個(gè)數(shù)組問(wèn)題，就可以直接從數(shù)組的思路考慮，暫時(shí)忘記實(shí)際的問(wèn)題，從建立的模型考慮，這樣就可以回到熟悉的套路上來(lái)。

現(xiàn)在考慮如何實(shí)現(xiàn)：

m[i,j] = min{m[i,k-1] + m[k,j] } + w[i,j] i<k<=j；i ==j ,m[i,j] =0

代碼實(shí)現(xiàn)如下，這種動(dòng)態(tài)規(guī)劃，根據(jù)約束調(diào)價(jià)i<j,他掃描是沿著對(duì)角線(xiàn)方向掃描，對(duì)角線(xiàn)從左往右平移，直到掃描到右上角最后一個(gè)點(diǎn)，就是最終的解，時(shí)間復(fù)雜度為O(n^3)

# -*- coding: utf-8 -*- import numpy as np # 任意點(diǎn)到第一個(gè)點(diǎn)的和 def sum_(arr,n): b = [0]*(n+1) for i in range(1,n+1):b[i] = b[i-1] + arr[i-1] return b # 任意兩點(diǎn)之間的數(shù)組和 def weight_i_j(b,i,j):return b[j+1]-b[i]# m[i,j] = min{m[i,k-1] + m[k,j] } + w[i,j] i<k<=j,0<i<j<n+1 # i ==j ,m[i,j] =0def DynamicProgramming(arr):n = len(arr)b = sum_(arr,n)print(b)# 初始化，這個(gè)問(wèn)題初始化為i==j時(shí)為0，也就是對(duì)角線(xiàn)上均為0m = np.zeros((n,n),int)solution = np.full((n,n),-1)# 掃描的時(shí)候注意了，這種類(lèi)型的問(wèn)題，掃描順序不是從左到右，從上到下# 掃描的基準(zhǔn)是j-i的間距，沿著對(duì)角線(xiàn)往右上掃描，這里的i就是為j-i的長(zhǎng)度,掃描的最后就是# m[0,n-1],這個(gè)就是最后的解# i <j 所以間距為從1 到 n-1for r in range(1,n):# 沿著對(duì)角線(xiàn)往下走for i in range(n-r):j = i + r # 首先取第一個(gè)k = i+1m[i][j] = m[i][i] + m[i+1][j]# 用于解的追蹤solution[i][j] = i# 比較求最小的for k in range(i+2,j+1):temp = m[i][k-1] + m[k][j]if temp < m[i][j]:m[i][j] = tempsolution[i][j] = k-1# min{m[i,k-1] + m[k,j] } + w[i,j] m[i][j] += weight_i_j(b,i,j)return m,solutionarr = [1000,22,13,4,5000,86,57,18] print(arr) m,s = DynamicProgramming(arr) print(m) print(end='\n') print(s)runfile('D:/share/test/dp.py', wdir='D:/share/test') [1000, 22, 13, 4, 5000, 86, 57, 18] [0, 1000, 1022, 1035, 1039, 6039, 6125, 6182, 6200] [[ 0 1022 1070 1095 7134 12306 12563 12692][ 0 0 35 56 5095 10220 10420 10531][ 0 0 0 17 5034 10137 10337 10448][ 0 0 0 0 5004 10094 10294 10405][ 0 0 0 0 0 5086 5286 5397][ 0 0 0 0 0 0 143 236][ 0 0 0 0 0 0 0 75][ 0 0 0 0 0 0 0 0]][[-1 0 0 0 3 3 3 3][-1 -1 1 1 3 4 4 4][-1 -1 -1 2 3 4 4 4][-1 -1 -1 -1 3 4 4 4][-1 -1 -1 -1 -1 4 4 4][-1 -1 -1 -1 -1 -1 5 5][-1 -1 -1 -1 -1 -1 -1 6][-1 -1 -1 -1 -1 -1 -1 -1]]

四邊形不等式

結(jié)論

回到實(shí)際的問(wèn)題

代碼實(shí)現(xiàn)如下,實(shí)現(xiàn)的時(shí)候，只要把原來(lái)的i<k<=j,修改成s[i,j-1]<=k<=s[i+1,j]就可以了,時(shí)間復(fù)雜度為O(n^2)，加速算法有點(diǎn)問(wèn)題，s初始化都為0，那k不是只能取0嗎？程序還怎么走？

def DynamicProgrammingSpeed(arr):n = len(arr)b = sum_(arr,n)print(b)# 初始化，這個(gè)問(wèn)題初始化為i==j時(shí)為0，也就是對(duì)角線(xiàn)上均為0m = np.zeros((n,n),int)solution = np.full((n,n),0)# 掃描的時(shí)候注意了，這種類(lèi)型的問(wèn)題，掃描順序不是從左到右，從上到下# 掃描的基準(zhǔn)是j-i的間距，沿著對(duì)角線(xiàn)往右上掃描，這里的i就是為j-i的長(zhǎng)度,掃描的最后就是# m[0,n-1],這個(gè)就是最后的解# i <j 所以間距為從1 到 n-1for r in range(1,n):# 沿著對(duì)角線(xiàn)往下走for i in range(n-r):j = i + r # 利用四邊形不等式，把范圍縮小為s[i][j-1]到s[i+1][j]i1 = solution[i][j-1]j1 = solution[i+1][j]# 首先取第一個(gè)k = i1m[i][j] = m[i][i1-1] + m[i1][j]# 用于解的追蹤solution[i][j] = i1-1# 比較求最小的for k in range(i1+1,j1+1):temp = m[i][k-1] + m[k][j]if temp < m[i][j]:m[i][j] = tempsolution[i][j] = k-1# min{m[i,k-1] + m[k,j] } + w[i,j] m[i][j] += weight_i_j(b,i,j)return m,solution

總結(jié)

以上是生活随笔為你收集整理的算法优化：动态规划加速，货物运输问题，四边形不等式, 从O(n^2)到O(n^3)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。