《算法設計與分析》課件第5章

第5章回溯法5.1回溯法的基本原理

5.2

n皇后問題

5.3子集和數(shù)問題

5.4

0-1背包問題

5.5著色問題

習題 5.1回溯法的基本原理

回溯法(backtracking)是一種系統(tǒng)地搜索問題解的方法。為了實現(xiàn)回溯，首先需要為問題定義一個解空間(solutionspace)，這個空間必須至少包含問題的一個解(可能是最優(yōu)

的)。在一般的情況下，我們會將問題的解表示成一個向量X＝(x1,x2,…,xn)，其中元素xi∈Si。通常，需要找出滿足某一約束條件且使某一規(guī)范函數(shù)取最大值(或最小值)的解向量。這樣的一個向量可能表示一種排列，其中xi表示排列的第i個元素,或者表示對于給定集合S，xi為真，當且僅當?shù)趇個元素在集合Si中。我們稱滿足問題約束條件的解為可行解(feasiblesolution)?；厮菟惴ㄒ淮螖U展一個元素。在回溯算法的每一步中，假定我們已經(jīng)構造了問題的部分解，如問題解向量的前k個元素，k≤n。通過這個部分解(x1,x2,…,xk)，我們要構造第k+1個位置上可能的候選解集合Sk+1，然后通過在向量最后添加另一元素來對當前解進行擴展，以得到更長的一個部分解。在對部分解進行擴展之后，我們必須檢查到目前為止的解是否是問題的一個解，如果是問題的解，則輸出；否則，我們需要檢查這個部分解是否可以繼續(xù)擴展成為問題的解。如果可以，則進行遞歸調(diào)用并繼續(xù)這一過程；如果不可以繼續(xù)擴展，則從x中刪除最后添加的元素，并再嘗試這個位置是否存在另一元素。然而，在某些點上，Sk+1可能為空，即不存在合法的方式對當前解進行擴展。如果是這樣，我們必須進行回溯(backtrack)，用Sk中的下一候選解代替xk，即部分解中的最后一項。這就是回溯方法的由來，過程BACKTRACKING描述了這一思想。BACKTRACKING(X)

1 計算解X的第一個元素的候選集合S1

2 k

1

3 while

k>0do//擴展

4

while

Sk

do//第k個元素的候選解不空

5

xk

Sk中的下一元素

6

Sk

Sk–{xk}

7

ifX=(x1,x2,…,xk)是問題的解

8

then輸出

9 k

k+1

10 計算解X的第k個元素的候選集合Sk

11

k

k

–1//回溯

12 return回溯法構造了問題部分解的一棵樹，樹中的每個結點都是問題的一個部分解。如果結點y是由結點x直接擴展的，那么x與y之間有一條邊。我們可以從部分解所構成的樹來更深

刻地理解回溯的本質(zhì)，因為解的構造過程正好對應于深度優(yōu)先遍歷樹的過程。將回溯過程看做深度優(yōu)先搜索，自然會產(chǎn)生這個基本算法的遞歸過程BACKTRACKING-DFS。BACKTRACKING-DFS(X,k)

1 ifX=(x1,x2,…,xk)是問題的解，

2 then輸出

3 else

4

k

k+1

5 計算解X的第k個元素的候選集合Sk

6

while

Sk

do//第k個元素的候選解不空

7 xk

Sk中的下一元素

8 Sk

Sk–{xk}

9 BACKTRACKING-DFS(X,k)

10 return

1.子集樹的構造

當所給的問題是從n個元素的集合中找出滿足某種性質(zhì)的子集時，相應的解空間樹稱為子集樹(subsettree)。在組合優(yōu)化問題求解中，常常用到子集樹的概念。例如，對于n個

元素的整數(shù)集{1,2,…,n}，n=1時，只有兩個子集，即{}和{1}；n=2時，有4個子集；n=3時，有8個子集。每增加一個新元素，都使子集個數(shù)加倍，因此對于n個元素，有2n個子集。又例如，0-1背包問題對應的解空間就是一棵子集樹,樹中所有結點都可能成為問題的一個解。子集樹中至多有2n個葉結點。n=3時,子集樹如圖5-1所示。因此，任何算法遍歷子集樹所需的運行時間為Ω(2n)。圖5-1

0-1背包問題的子集樹(n=3)為了構造所有2n個子集，我們可以建立一個有n個單元的數(shù)組或向量，其中xi的值或為真或為假,表明xi是否屬于某個給定子集。利用回溯算法中候選解的表示可得，Sk=(true,false)。當k≥n時，X是問題的解。

利用狀態(tài)空間表示法，回溯算法在構造集合{1,2,3}的子集過程中將產(chǎn)生以下部分解序列：

{1}→{1,2}→{1,2,3}*→{1,2,－}*→{1,－}→{1,－,3}*→{1,－,－}*→{1,－}→{1}→{－}→{－,2}→{－,2,3}*→{－,2,－}*→{－,－}→{－,－,3}*→{－,－,－}*→{－,－)→{－}→{}其中，“*”表示完整子集,部分解中的“－”表示這個位置不選。第i個位置為真，則用i自身表示。

通過這個例子，我們能夠更好地理解回溯的過程。集合{1,2,3}的子集樹如圖5-2所示。圖5-2集合{1,2,3}的子集樹

2.排列樹的構造

當所給的問題是從n個元素的集合中找出滿足某種性質(zhì)的排列時，相應的解空間樹稱為排列樹(permutationtree)。

這樣的計算給出了一種合適的表示方式。為了構造出所有n!種排列，可以設一個具有n個元素的數(shù)組。第k個位置的候選解的集合就是那些不在前k－1個元素的部分解中出現(xiàn)的元素集合，因此，Sk={1,2,…,n}－X。當k=n+1時，向量X

就是問題的解。通過這種表示方法，將按照如下次序產(chǎn)生{1,2,3}的排列：

{1}→(1,2)→{1,2,3}*→{1,2}→{1}→{1,3}→{1,3,2}*

→{1,3}→{1}→{}→{2}→{2,1}→{2,1,3}*→{2,1}→{2}→{2,3}→{2,3,1}*→{2,3}→{2}→{}→{3}→{3,1}→{3,1,2}*→{3,1}→{3}→{3,2}→{3,2,1}*→{3,2}→{3}→{}

3.搜索樹的構造

枚舉出給定圖中從源點s到t的所有路徑要比列出所有排列或者子集的問題更復雜一些。不像上述的例子，沒有關于頂點或者邊個數(shù)的函數(shù)可用作計算問題解的顯式公式，這是

因為路徑的個數(shù)取決于給定圖的結構。

由于到t的所有路徑的開始點相同，因此S1={A}。第2個位置上候選解的集合是那些滿足(A,v)為圖中邊的結點集合。因此，對于路徑上的從一結點到另一結點的遍歷過程，可以利用邊定義合法步。一般而言，Sk+1由還未在部分解中出現(xiàn)的相鄰的頂點集組成。當xk=t時，輸出問題的解。我們必須設置解向量X的大小為n，盡管大多數(shù)路徑可能會比n小。圖5-3所示的搜索樹(searchingtree)給出了給定圖中從頂點A開始的所有路徑。樹中的結點按照深度優(yōu)先搜索編號。圖5-3從頂點A開始的所有簡單路徑的搜索樹 5.2

n皇后問題

1.8皇后問題

我們給棋盤上的行和列從1到8編號，同時也給皇后從1到8編號。由于每一個皇后應放在不同的行上，不失一般性，假設皇后i放在第i行上，因此8皇后問題可以表示成8元組(x1,x2,…,x8)，其中xi(i=1,2,…,8)表示皇后i所放置的列號。這種表示法的顯式約束條件是Si={1,2,3,4,5,6,7,8}，i=1,2,…,8。在這種情況下，解空間由88個8元組組成，而隱式約束條件是沒有兩個xi相同(即所有皇后必須在不同列上)，且滿足不存在兩個皇后在同一條對角線上。加上隱式約束條件，問題的解空間可進一步減小。此時，解空間大小為8!，因為所有解都是8元組的一個置換。圖5-4表示了8皇后問題的一個解。圖5-4

8皇后問題的一個解我們可以用一棵樹表示8皇后問題的解空間。由于8皇后問題的解空間為8!種排列，因此我們將要構造的這棵樹實際上是一棵排列樹。為了簡單起見，圖5-5只給出了n=4時問題的一種可能樹結構。這棵樹有24個葉子結點，樹中結點按照深度優(yōu)先搜索編號，樹中的邊表示xi可能取的值。假定樹的根為第1層，樹中第1層到第2層的邊上的數(shù)字表示x1可能取的值。最左邊的子樹包含x1=1的所有解，最左子樹的左子樹包含x1=1且x2=1的所有解。第i層到第i+1層的邊上表示xi可能取的值。因此，從根結點到葉子結點的所有路徑定義了問題的解空間。圖5-5

4皇后問題解空間的樹結構圖5-6表示4皇后問題回溯時的部分狀態(tài)空間樹。圖中一個結點一旦被限界函數(shù)殺死，則用B做上記號。圖5-6具有限界函數(shù)的4皇后問題的部分狀態(tài)空間樹

2.n皇后問題及回溯算法

我們可以很容易地將8皇后問題推廣到n皇后問題(n-queenproblem)，即找出n×n的棋盤上放置n個皇后并使其不能互相攻擊的所有解。設X=(x1,x2,…,xn)表示問題的解，其中xi表示第i個皇后放在第i行所在的列數(shù)。由于不存在兩個皇后位于同一列上，因此xi互不相同。設有兩個皇后分別位于棋盤(i,j)和(k,l)處，如果兩個皇后位于同一對角線上，則

表明它們所在的位置應該滿足：i－j=k－l或i+j=k+l。綜合這兩個等式可得，如果兩個皇后位于同一對角線上，那么它們的位置關系一定滿足|j－l|=|i－k|。下面的算法N-QUEEN給出n皇后問題的所有解。N-QUEEN(n)

1 x[1]

0 //第1個皇后的列位置初始化

2 k

1 //當前行

3 whilek>0do

4

x[k]

x[k]+1 //到下一列

5

while

x[k]

n¬PLACE(k)do

6 x[k]

x[k]+1

7

if

x[k]

n //找到一個位置

8 thenif

k=n //測試是否為問題的解

9

thenoutput(X)//輸出解

10

elsek

k+1//轉下一行，即給下一個皇后找位置

11 x[k]

0 //初始化當前皇后列取值

12 elsek

k–1 //回溯

13 return第1～2行進行初始化。第3行的while循環(huán)表示對所有行執(zhí)行循環(huán)體，計算xk值。在第5～6行的while循環(huán)中，對于每一個xk值，調(diào)用PLACE過程測試它的合法性,即尋找滿足約束條件的xk值。第7行中，如果找到一個放置位置，則進一步測試所求(x1,x2,…,xk)是否為問題的解，這只需判斷k是否等于n即可。如果是問題的解，則輸出(第9行),否則通過賦值語句將k值增加1,繼續(xù)外層while循環(huán)。如果第7行的條件為假，則表明不存在合法的xk值，此時將k值減1(第12行)，進行回溯。

PLACE過程如下：

PLACE(k)

1 i

1

2 whilei<k

do

3

if(x[i]=x[k]or

abs(x[i]

–x[k])=abs(i–k)//同一列或同一對角線有兩個皇后

4

thenreturnfalse

5

i

i+1

6 returntrue

PLACE過程檢測到目前為止的第k個皇后所在的列數(shù)xk,是否與前k－1個皇后所在列xi(1≤i≤k－1)在同一列或在同一對角線上(第3行)。如果這些條件都不違反，則返回true，否則返回false。

5.3子集和數(shù)問題

1.子集和數(shù)問題及回溯算法

子集和數(shù)問題(subset-sumproblem)是指給定n個互不相同的正整數(shù)pi(1≤i≤n)及一個正數(shù)S,要求找出∑pi為S的所有子集。我們稱這種表示法為變長元組表示法，如圖5-7所示。圖中結點按照廣度優(yōu)先搜索編號。在第i層與第i+1層的邊上表示pi被選中時的下標，最左邊的子樹表示選中p1的所有子集，根的第2棵子樹則確定了選中p2但不選p1的所有子集，其中黑色結點表示答案結點。圖5-7子集和數(shù)問題變長元組表示法的子集樹結構我們可以用另一種形式表示子集和數(shù)問題。解的子集用n元組(x1,x2,…,xn)表示，其中每個xi∈{0,1}，1≤i≤n。如果pi未被選中，則xi為0，否則xi為1。這種表示法稱為定長元組表示法。利用這種表示法，上述解又可表示為(1,1,0,0,1,0)、(1,0,1,1,0,0)和(0,0,1,0,0,1)。圖5-8表示了子集和數(shù)定長元組表示法的子集樹結構。圖中結點按照深度優(yōu)先搜索編號。在第i層與第i+1層的邊上表示pi被選中時的下標，最左邊的子樹表示選中p1的所有子集，根的第2棵子樹則確定了選中p2但不選p1的所有子集，黑色結點表示答案結點。圖5-8子集和數(shù)問題定長元組表示法的子集樹結構對于子集和數(shù)問題定長元組表示法，產(chǎn)生它的任一子結點是較容易的。對于第i層上的一個結點，它的左孩子為xi=1，右孩子為xi=0。假定pi按照非降次序排列，限界函數(shù)可設計為

這兩個條件保證算法SUBSET-SUM可以找到問題的解。SUBSET-SUM(S,p,s,k,r) //前k－1個xi值已確定

1 x[k]

1 //生成左孩子

2 ifs+p[k]=S //如果條件為真，表明找到解

3 thenoutputx1,x2,…,xk,0,…,0//輸出問題解

4 elseifs+p[k]

+p[k+1]

S //測試遞歸調(diào)用的條件

5 thenSUBSET-SUM(S,p,s+p[k],k+1,r－p[k]) //前k個xi值已確定,且xk

1

6 ifs+r–p[k]

Sands+p[k+1]

S //生成右孩子

7 then

x[k]

0

8

SUBSET-SUM(S,p,s,k+1,r－p[k])//前k個xi值已確定，且xk

0

9 return

2.子集和數(shù)問題算法示例

圖5-9顯示本小節(jié)例子n=6，(p1,p2,p3,p4,p5,p6)=(5,10,12,13,15,18)，S=30，運行算法SUBSET-SUM后，所生成狀態(tài)空間樹的部分結果。初始時，s=0，k=1，r= 圖5-9算法SUBSET-SUM所生成狀態(tài)空間樹的一部分回溯法的一般執(zhí)行步驟如下：

(1)定義一個解空間，它包含問題的解。

(2)用適于搜索的方式組織該空間。

(3)用深度優(yōu)先法搜索該空間，利用限界函數(shù)來避免移動到不可能產(chǎn)生解的子空間。

5.4

0-1背包問題

1.0-1背包問題及回溯算法示例

再次考慮0-1背包問題(0-1knapsackproblem)。某商店有n個物品，第i個物品價值為vi，重量(或稱權值)為wi，其中vi和wi為非負數(shù)。背包的容量為W，W為一非負數(shù)。目標是如何選擇裝入背包的物品，使裝入背包的物品總價值最大?？蓪⑦@個問題形式描述為

約束條件為我們使用定長元組表示法。如果在結點Z處，已經(jīng)確定了xi的值，1≤i≤k,則可在條件0≤xi≤1下，用第4章中的貪心算法求解結點Z處的解作為限界函數(shù)BOUND，k+1≤i≤n。

BOUND(cv,cw,k,W)//k:上次去掉的物品

1 b

cv//cv:當前價值總量

2 c

cw//cw:當前背包占用權值

3 fori

k+1to

n

4

doc

c+w[k]

5

if

c<W

6 then

b

b+v[i]

7 elsereturn(b+(1–(c–W)/w[i])v[i])第1～2行進行初始化。第3～7行的while循環(huán)計算背包獲得的價值。第7行中1－(c－W)/wi表示最后放入背包的物品比例。

由算法BT-KNAPSACK可見，只有在經(jīng)過一系列左孩子結點之后，才需要調(diào)用限界過程BOUND。

BT-KNAPSACK(W,n,w,v,fw,fv,X)

1 cw

cv

0//cw：背包當前已用權值，cv：背包當前總價值

2 k

1

3 fv

–1//fv：背包的最大值，初始化為–1

4 do

5

while

k

nandcw+w[k]

W

do//測試物品k是否可以放入背包

6 cw

cw+w[k]//修改當前背包已用權值cw

7 cv

cv+v[k]//修改當前背包總價值cv

8 y[k]

1//做左孩子結點的移動

9 k

k+1//繼續(xù)考慮下一個物品

10

if

k>n//如果所有物品考慮過(退出循環(huán)后)

11

then

fv

cv//復制這個解產(chǎn)生的總價值

12 fw

cw//復制這個解所占背包權值

13 k

n

14 X

Y//更新解

15

else

y[k]

0//最后放入背包中的物品k不合適，去掉

16

whileBOUND(cv,cw,k,W)

fvdo17

while

k

0andy[k]

1do

18

k

k–1//找最后放入背包的物品

19

if

k=0

20

thenreturn//算法返回

21

y[k]

0//做右孩子結點的移動

22

cw

cw–w[k]//修改當前背包占用權值

23

cv

cv–v[k]//修改當前背包總價值

24

k

k+1

25 whiletrue圖5-10顯示了由算法BT-KNAPSACK所生成的狀態(tài)空間樹。這棵樹的第i層和第i+1層之間的邊上表示yi的取值，1表示沿左孩子結點的移動，0表示沿右孩子結點移動。結點內(nèi)的數(shù)值分別表示權值cw和價值cv。注意，右孩子結點的權值和價值與其父結點相同，在此略去。根及右孩子結點外的值為該處結點的上界。左孩子結點的上界與父結點相同。算法BT-KNAPSACK中的變量fv在結點A、B、C以及D處被更新，在對fv更新的同時更新解X。算法返回時，fv=159，X=(1,1,1,0,1,1,0,0)。圖5-10由算法BT-KNAPSACK所生成的狀態(tài)空間樹

2.改進算法

我們可以對算法BT-KNAPSACK做進一步改進。由于vi(1≤i≤n)是整數(shù)，因此BOUND值向下取整是一個更好的限界函數(shù)，如果這樣，圖5-10中的結點E和F就不需要擴展，從而進一步減少生成結點數(shù)。對BOUND算法也可進行改進，使得算法BOUND不必重復算法BT-KNAPSACK中第5～9行的工作。改進的算法如下：IMPROVED-BOUND(cv,cw,k,W,vcv,wcw,i)

1 vcv

cv//cv:當前價值總量

2 wcw

cw//cw:背包剩余可用量

3 fori

k+1to

n

4

do

if

wcw+w[i]

W

5

thenwcw

wcw+w[i]

6 vcv

vcv+v[i]

7 y[k]

1

8

elsereturn(vcv+(W–wcw)(v[i]

/w[i]))IMPROVED-BT-KNAPSACK(W,n,w,v,fw,fv,X)

1 cw

cv

0 //cw：背包當前權值，cv：背包當前總價值

2 k

0

3 fv

–1 //fv：背包的最大值，初始化為–1

4 do

5

whileIMPROVED-BOUND(ccv,ccw,k,W,vcv,wcw,i)

fp

do

6

while

k

0andy[k]

1do

7

k

k–1//找最后放入背包的物品

8

if

k=0

9 thenreturn//算法返回

10

y[k]

0 //做右孩子結點的移動

11

cw

cw–w[k] //修改當前背包權值12

cv

cv–v[k] //修改當前背包總價值

13

ccv

vcv

14

ccw

wcw

15

k

j

16

if

k>n//如果所有物品考慮過(退出第5行的循環(huán)后)

17 then

fv

cv//復制這個解產(chǎn)生的總價值

18

fw

cw//復制這個解所占背包權值

19

k

n

20

X

Y//更新解

21 else

y[k]

0//最后放入背包中的物品k不合適，去掉

22 while(1)

5.5著色問題

若一個圖已經(jīng)畫在曲面S上而任何兩條邊都不相交，則稱該圖被嵌入(embedded)曲面S內(nèi)。如果一個圖被嵌入一個平面內(nèi)，則稱它是可平面的。嵌入到平面內(nèi)的圖稱為平面圖(planargraph)。例如，圖5-11為一個可平面圖和它的一種嵌入。圖5-11一個可平面圖和它的一種嵌入給定圖G=(V,E)和k種顏色，設計算法來給出這個圖的所有k可著色方案，否則輸出該圖不是k可著色的。假定用鄰接矩陣Adj［1..n,1..n］表示圖G。如果(i,j)是圖G中的一條邊，那么Adj［i,j］=1；否則，Adj［i,j］=0。因為解的構造過程正好對應深度優(yōu)先遍歷樹的過程，因此可把回溯過程看做深度優(yōu)先搜索，對5.1節(jié)描述的BACKTRACKING-DFS稍作修改，就可得圖的k著色算法K-COLORING。其中，顏色用正整數(shù)1,2,…,k表示，(x1,x2,…,xn)表示解向量。算法產(chǎn)生的狀態(tài)空間樹中，除根所在層之外，每一層有k個結點，表示xi有k種顏色可用。樹的高度為n+1。第i層與第i+1層之間的邊上表示xi可用的顏色。算法K-COLORING產(chǎn)生一個圖的所有k著色解。K-COLORING(i,k)

1 fori

1to

n

do

2 x[i]

0//初始化

3 do

4 GENERATE-COLOR(i,k)

5 if

x[i]=0thenbreak//退出dowhile循環(huán)

6 if

i=n

7 thenoutput(X)

8 elseGENERATE-COLOR(i+1,k)

9 whiletrue

10 return//算法返回GENERATE-COLOR(i,k)

1 do

2 x[i]

(x[i]+1)mod(k+1)//已用掉i-1種顏色

3 ifx[i]=0return//未找到顏色，算法返回

4 for

j

1to

n

do

5 ifAdj[i,j]&x[i]=x[j]

6 thenbreak//退出for循環(huán)

7 ifj=n+1

8 thenreturn//為x[i]找到一種顏色，算法返回

9 while(1)//試圖找另一種顏色圖5-12(a)給出了4個頂點的平面圖，圖5-12(b)給出了由算法K-COLORING(1,3)生成的所有可能的3著色。圖5-12算法K-COLORING示例

習題

5-1解釋術語：狀態(tài)空間、答案狀態(tài)、活結點、E結點、死結點和限界函數(shù)。

5-2旅行商問題(travellingsalesmanproblem)。旅行商問題的基本描述為：某旅行商要到若干村莊售貨，各村莊之間的路程是給定的。為了提高效率，旅行商決定從所在商店

出發(fā)，到每個村莊售一次貨，然后返回村商店。問他應選擇一條什么路線才能使所走的總路程最短。形式描述為：給定有向圖G=(V,E)，邊成本為cij，且如果(i,j)∈E，則cij>0，否則cij=∞。令|V|=n，假定n>1。G的一條周游路線包含V中每個頂點的一個有向環(huán)。周游路線的成本是此路線上所有邊上的成本和。求旅行商問題的具有最小成本的周游路線。

(1)將旅行商問題的解空間組織成一棵樹。

(2)編寫一個回溯算法，搜索旅行商問題的所有解(可行排列)。

5-3裝箱問題(binpacking)。有一批共n個集裝箱要裝上兩艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且滿足 。裝箱問題要求確定，是否有一個合理的裝載方案可將這n個集裝箱裝上這兩艘輪船。試設計該問題的回溯算法，并分析問題的復雜度。

5-4給定無向圖G=(V,E)，如果U

V，且對任意u，v∈U，有(u,v)∈E，則稱U是G的一個完全子圖。G的完全子圖U是G的一個團，當且僅當U不包含G的更大完全子圖。G的最大團是指G中所含頂點數(shù)最多的團。試設計求最大團問題的回溯算法。

5-5最小頂點覆蓋問題(minimumvertex-coverproblem)。給定無向圖G＝(V,E)，當且僅當對于G中的每一條邊(u,v)∈E，u或v在U中時，G的頂點子集U是一個頂點覆蓋

(vertexcover),U中頂點的個數(shù)是覆蓋的大小,U中頂點個數(shù)最少的覆蓋為最小覆蓋。在圖5-12(a)中，{1,3}是大小為2的一個頂點覆蓋。試設計求最小覆蓋問題的回溯算法，并分析算法的運行時間。

5-6機器設計問題。某機器由n個部件組成，每一個部件可從m個供應商那里購得。設wij是從供應商j那里購得的零件i的重量，cij為該零件的成本。試設計一個回溯算法，給出總成本不超過c的最小重量機器設計，并分析算法的復雜度。

5-7網(wǎng)絡設計問題。輸油網(wǎng)絡問題可表示為一個加權有向無環(huán)圖G,G中有一個稱為源點的頂點s。從s出發(fā)，汽油被輸送到圖中的其他頂點。s的入度為0，每一條邊上的權給出了它所連接的兩點間的距離。網(wǎng)絡中的油壓是距離的函數(shù)，隨著距離的增大而減小。為了保證整個輸油網(wǎng)絡正常工作，需要維持網(wǎng)絡中的最低油壓Pmin，為此