python算法設(shè)計(jì)和分析

計(jì)算機(jī)解決問(wèn)題的關(guān)鍵：設(shè)計(jì)出合適的算法算法設(shè)計(jì)和分析算法的質(zhì)量評(píng)價(jià)正確性：算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能；易讀性：算法應(yīng)易于閱讀和理解，以便于調(diào)試、修改和擴(kuò)充；穩(wěn)健性：當(dāng)環(huán)境發(fā)生變化（如遇到非法輸入）時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不正確的運(yùn)算結(jié)果；高效率：具有較高的時(shí)間和空間性能。Outline:§10.1枚舉法（查找問(wèn)題）§10.2遞歸程序設(shè)計(jì)§10.3排序問(wèn)題§10.4可計(jì)算性問(wèn)題枚舉法問(wèn)題求解中常用的一種算法設(shè)計(jì)方法。給定問(wèn)題P，如果知道P的可能解構(gòu)成一個(gè)有限集合S={s1,s2,s3,…,sn}，則可以逐一例舉每個(gè)si，檢驗(yàn)它是否確實(shí)是P的解?！鞍馘X白雞”問(wèn)題：假設(shè)公雞每只5元，母雞每只3元，小雞每3只1元。用100元錢買100只雞，問(wèn)公雞、母雞和小雞各買了多少只？x+y+z=1005x+3y+z/3=100枚舉法應(yīng)用一、不定方程的求解代碼：forxinrange(100):foryinrange(100):forzinrange(100):t=x+y+zm=5*x+3*y+z/3ift==100andm==100:print"x=",x,"y=",y,"z=",zforxinrange(100):foryinrange(100):forzinrange(100):t=x+y+zm=5*x+3*y+z/3

ift==100andm==100andz%3==0:print"x=",x,"y=",y,"z=",zx=0y=25z=75x=3y=20z=77x=4y=18z=78x=7y=13z=80x=8y=11z=81x=11y=6z=83x=12y=4z=84x=0y=25z=75x=4y=18z=78x=8y=11z=81x=12y=4z=84枚舉法應(yīng)用二、查找問(wèn)題問(wèn)題描述：在一個(gè)列表中查找某個(gè)值.defsearch(x,nums): #nums為一數(shù)值列表,x是一個(gè)數(shù)

#如果找到,返回x在列表中的位置

#否則返回-1Python本身就提供有關(guān)的功能:判斷：xinnums求位置：nums.index(x)>>>nums=[3,1,4,2,5]>>>x=4>>>search(4,nums)2>>>nums.index(4)2>>>nums.index(100)Traceback(mostrecentcalllast):File"<pyshell#3>",line1,in<module>nums.index(100)ValueError:100isnotinlistSuperprogrammer：自己來(lái)完成類似的功能，而且在尋找的數(shù)不在數(shù)列中時(shí)返回-1.（1）無(wú)序表的查找：一維表中的線性查找逐個(gè)檢查列表中的數(shù)據(jù).defsearch(x,nums):foriinrange(len(nums)):ifnums[i]==x:returnireturn–1nums=[3,1,4,2,5]>>>nums=[3,1,4,2,5]>>>x=4>>>search(4,nums)2>>>search(4,[10,11,12,13])-1無(wú)序表的查找：二維表中的線性查找defsearch2D(matrix,row,col,x):foriinrange(row):forjinrange(col):ifmatrix[i][j]==x:return(i+1,j+1)return-1

>>>search2D([[1,2,3],[4,5,6]],2,3,6)(2,3)>>>search2D([[1,2,3],[4,5,6]],2,3,7)-1特點(diǎn):容易實(shí)現(xiàn)適合無(wú)序數(shù)據(jù)列表不適合大數(shù)據(jù)量補(bǔ)充：二維列表的初始定義列表初始定義的兩種方法（初始值和多維）：myList=[0]*10#定義一個(gè)初始值皆為0的長(zhǎng)度為10的列表myList=[[0]*5]*6#定義一個(gè)初始值皆為0的6行*5列的二維列表myList=[0forxinrange(10)]

#定義一個(gè)初始值皆為0的長(zhǎng)度為10的列表myList=[[0forcolinrange(10)]forrowinrange(9)]#定義一個(gè)初始值皆為0的9行*10列的二維列表兩種定義方法本質(zhì)上不同：第一種（紫色）的定義是淺拷貝，第二種（藍(lán)色）的定義是深拷貝。淺拷貝（shallowcopy）是指源對(duì)象與拷貝對(duì)象共用一份實(shí)體，僅僅是引用的變量不同（名稱不同）。對(duì)其中任何一個(gè)對(duì)象的改動(dòng)都會(huì)影響另外一個(gè)對(duì)象。所以只在不改變對(duì)象值的情況下可用。深拷貝（deepcopy）是指源對(duì)象與拷貝對(duì)象互相獨(dú)立，其中任何一個(gè)對(duì)象的改動(dòng)都不會(huì)對(duì)另外一個(gè)對(duì)象造成影響。myList=[[0]*5]*6#定義一個(gè)初始值皆為0的6行*5列的二維列表foriinrange(5):myList[0][i]=iforiinrange(6):forjinrange(5):printmyList[i][j],printforiinrange(5):myList[2][i]=9foriinrange(6):forjinrange(5):printmyList[i][j],printmyList=[[0forcolinrange(5)]forrowinrange(6)]012340123401234012340123401234999999999999999999999999999999012340000000000000000000000000012340000099999000000000000000（2）

有序表的查找：二分查找猜數(shù)字：1-100（二分查找的思想）二分查找：

假設(shè)查找范圍為（low，high）

循環(huán)查找：

查看有序列表的中點(diǎn)數(shù)據(jù)nums[(low+high)/2]

找到：退出

else：根據(jù)情況接著找較大一半或較小一半，

即更新查找范圍（low、high）

循環(huán)退出條件：找到或未找到（此時(shí)low和high什么關(guān)系——終止條件）defsearch(x,nums):low,high=0,len(nums)-1

whilelow<=high:mid=(low+high)/2ifx==nums[mid]:returnmid

elifx<nums[mid]:high=mid-1else:low=mid+1return-1二分法——分而治之，特點(diǎn)就是把一個(gè)問(wèn)題的規(guī)模不斷縮小。#performbinarysearchforxinrangenums[low]tonums[high]mid=(low+high)/2iflow>high：xisnotinnumselifx<nums[mid]：performbinarysearchforxinrangenums[low]tonums[mid-1]else：

performbinarysearchforxinrangenums[mid+1]tonums[high]將一個(gè)大問(wèn)題簡(jiǎn)化為同樣形式的較小問(wèn)題第13章算法分析與設(shè)計(jì)§13.1枚舉法§13.2遞歸程序設(shè)計(jì)§13.3排序問(wèn)題§13.4可計(jì)算性問(wèn)題遞歸用途遞歸程序設(shè)計(jì)：將一個(gè)大問(wèn)題簡(jiǎn)化為同樣形式的較小問(wèn)題。在一個(gè)遞歸求解中，分解的子問(wèn)題與最初的問(wèn)題具有一樣的形式作為處理問(wèn)題的工具，遞歸技術(shù)是一種非常有力的工具。利用遞歸不但可以使得書寫復(fù)雜度降低，而且使程序看上去更加美觀遞歸調(diào)用：在一個(gè)函數(shù)中直接或間接地調(diào)用函數(shù)本身遞歸條件必須有遞歸終止的條件函數(shù)有與遞歸終止條件相關(guān)的參數(shù)，在遞歸過(guò)程中，決定終止條件的參數(shù)有規(guī)律地遞增或遞減

遞歸的標(biāo)準(zhǔn)模式有可對(duì)函數(shù)的入口（參數(shù)）進(jìn)行測(cè)試的基本情況

if(條件)return(不需要遞歸的簡(jiǎn)單答案);elsereturn(遞歸調(diào)用同一函數(shù))；基本情況典型的遞歸函數(shù)—階乘函數(shù)n!=1*2*3*4*…*(n-1)*n(n-1)!遞歸形式：遞歸終止條件計(jì)算階乘的遞歸函數(shù)deffact(n):ifn==0:return1else:returnn*fact(n-1)二分查找的遞歸算法二分查找的思想：在范圍list[low]到list[high]之間查找x取當(dāng)前范圍的中間數(shù)據(jù)m；如果m等于x或者m不存在則算法結(jié)束；如果x<m則在范圍list[low]到list[mid-1]之間查找x，否則在范圍list[mid+1]到list[high]之間查找x。涉及幾乎相同的操作二分查找的遞歸算法defBinSearch(x,nums,low,high):iflow>high:return-1#沒(méi)找著mid=(low+high)/2ifx==nums[mid]

returnmid

#找到了

elifx<nums[mid]:

returnBinSearch(x,nums,low,mid-1)

else:

returnBinSearch(x,nums,mid+1,high)defsearch(x,nums):#遞歸函數(shù)的調(diào)用

returnBinSearch(x,nums,0,len(nums)-1)切記不要忘了“return”遞歸函數(shù)的補(bǔ)充--數(shù)字旋轉(zhuǎn)方陣（蛇陣）數(shù)字旋轉(zhuǎn)方陣如右圖所示。編程輸出任意n*n的蛇陣。120191817162213231301532233362914423343528135242526271267891011初始矩陣的建立myList=[[0forcolinrange(n)]forrowinrange(n)]000000000000000000000000000000000000用遞歸的觀點(diǎn)看問(wèn)題先填最外圈，然后再填內(nèi)部的，填法同上，也是先填最外圈，再填內(nèi)部。根據(jù)上述思想，可以設(shè)計(jì)一個(gè)遞歸函數(shù)fill。該函數(shù)先填外圈，然后遞歸調(diào)用自己填內(nèi)部。函數(shù)接口：

fill(number,begin,size)number：表示要填入的起始數(shù)據(jù)

begin：表示要填的起始位置size：蛇陣的規(guī)模要生成一個(gè)6*6的蛇陣只要調(diào)用：fill(1,0,6)120191817162213231301532233362914423343528135242526271267891011Fill函數(shù)的設(shè)計(jì)思路：自上而下填最左列自左而右填最下行自下而上填最右列自右而左填最上行遞歸調(diào)用fillfill(number,begin,size)關(guān)鍵問(wèn)題：參數(shù)怎么變化（number,begin,size)

遞歸終止條件120191817162213231301532233362914423343528135242526271267891011關(guān)鍵問(wèn)題：

（1）遞歸終止條件

（2）參數(shù)怎么變化（number,begin,size)（1）遞歸終止條件：size==0:函數(shù)結(jié)束size==1：填寫最后一個(gè)數(shù)字，函數(shù)結(jié)束（2）參數(shù)變化：

規(guī)模減2，起始位置為原來(lái)的下一行下一列，填入的起始數(shù)字為填入一圈后的第一個(gè)數(shù)字。begin=begin+1size=size-2number在填寫數(shù)字時(shí)隨著改變120191817162213231301532233362914423343528135242526271267891011deffill(number,begin,size):

ifsize==0:return

elifsize==1:

myList[begin][begin]=numberreturnelse:foriinrange(begin,begin+size):#setthevalueofthecolfromtoptodown

myList[i][begin]=numbernumber=number+1foriinrange(begin+1,begin+size):#setthevalueoftherowfromlefttoright

myList[begin+size-1][i]=numbernumber=number+1foriinrange(begin+size-2,begin-1,-1):#setthevalueofthecolfromdowntotop

myList[i][begin+size-1]=numbernumber=number+1foriinrange(begin+size-2,begin,-1):#setthevalueoftherowfromrighttoleft

myList[begin][i]=numbernumber=number+1fill(number,begin+1,size-2)#開(kāi)始填內(nèi)圈120191817162213231301532233362914423343528135242526271267891011遞歸vs迭代(循環(huán))遞歸算法設(shè)計(jì)容易易讀效率略低迭代算法：用循環(huán)設(shè)計(jì)困難有的問(wèn)題沒(méi)有直觀的迭代算法效率高用迭代能實(shí)現(xiàn)的算法基本都能用遞歸來(lái)實(shí)現(xiàn)，反之亦然，當(dāng)然也有例外，如漢諾塔問(wèn)題遞歸經(jīng)典之作——漢諾塔問(wèn)題

印度古神廟中有三根柱子，第一根柱子上有64個(gè)直徑大小不同的金盤子，按照由大到小的次序排列。要求借助于第二根柱子將盤子全部移到第三根柱子。整個(gè)移動(dòng)過(guò)程符合三條規(guī)則：每次只能移動(dòng)一個(gè)盤子盤子只能在三根柱子之間移動(dòng)在移動(dòng)過(guò)程，三根柱子上的盤子必須保持大盤在下，小盤在上天神說(shuō)：“當(dāng)這64個(gè)盤子全部移到第三根柱子上時(shí)，世界末日就要到了”Hanoi塔問(wèn)題ABC目標(biāo)：利用輔助桿C，將A上的盤子全部移到B上規(guī)則：每次只能移動(dòng)一個(gè)盤子不允許大盤子放在小盤子上Hannoi塔n＝4（最開(kāi)始的情況）n＝4（完成情況）ABCABC

srcdstaux

srcdstauxHannoi塔第1步：從開(kāi)始的桿到輔助桿（src到aux）第2步：從開(kāi)始桿到目的桿（src到dst）srcdstauxABCABCHannoi塔第3步：從輔助桿到目的桿（aux到dst）第4步：從開(kāi)始的桿到輔助桿（src到aux）ABCABCHannoi塔第5步：從目的桿到開(kāi)始桿（dst到src）第6步：從目的桿到輔助桿（dst到aux）ABCABCHannoi塔第7步：從開(kāi)始桿到目的桿（src到dst）第8步：從開(kāi)始桿到目的桿（src到dst）ABCsrcdstauxABC

auxdstsrc1-8步就實(shí)現(xiàn)了兩個(gè)關(guān)鍵功能：

(1)把3個(gè)圓盤借助B桿從A移到C(2)最后一個(gè)盤從A移到B接下去的工作應(yīng)該是：（3）把C桿上的3個(gè)盤借助A移到B整個(gè)過(guò)程中，盤的個(gè)數(shù)不斷減少，桿子的作用會(huì)發(fā)生變化，其余處理形式一樣——遞歸解題思路最簡(jiǎn)單的情況，只有一個(gè)盤子：將盤子直接從A移到B大于一個(gè)盤子的情況：將除了最下面一個(gè)盤子外的所有盤子借助B桿從A移到C將最下面的盤子從A移到B將C上的盤子移到B終止條件ABCdef

moveTower(n,source,dest,temp):ifn==1:print“Movediskfrom”,source,“to”,dest,“.“#搬else:#3步走#先把n-1個(gè)塔轉(zhuǎn)移到輔助桿（temp）上，借助的是目標(biāo)桿（dest）

moveTower(n-1,source,temp,dest)#然后移動(dòng)最底下那根桿

moveTower(1,source,dest,temp)#把輔助桿上的移動(dòng)到目標(biāo)桿上

moveTower(n-1,temp,dest,source)第二個(gè)參數(shù):盤子原始棲息地第三個(gè)參數(shù):盤子最終棲息地第四個(gè)參數(shù):盤子借過(guò)的地方38Hanoi塔moveTower函數(shù)的應(yīng)用

defhanoi(n):

moveTower(n,"A","C","B")

>>>hanoi(3)

MovediskfromAtoC.

MovediskfromAtoB.

MovediskfromCtoB.

MovediskfromAtoC.

MovediskfromBtoA.

MovediskfromBtoC.

MovediskfromAtoC.第10章算法分析與設(shè)計(jì)§10.1查找問(wèn)題§10.2遞歸程序設(shè)計(jì)§10.3分治法（排序問(wèn)題）§10.4貪心法分治法思想是將難以處理的較大問(wèn)題分解為若干個(gè)較小的子問(wèn)題，然后分別解決這些子問(wèn)題，并從子問(wèn)題的解構(gòu)造出原問(wèn)題的解?！胺帧笔侵笇⒃瓎?wèn)題分解，“治”是指解決問(wèn)題?！胺种巍背朔侄沃倪^(guò)程，還有另一個(gè)特點(diǎn)——遞歸。當(dāng)我們將大問(wèn)題分解成子問(wèn)題后，經(jīng)常會(huì)發(fā)現(xiàn)子問(wèn)題與大問(wèn)題本質(zhì)上是相同的問(wèn)題，因此可以利用遞歸方法來(lái)設(shè)計(jì)算法。所以，分治法常常與遞歸法結(jié)合起來(lái)使用。分治法與排序問(wèn)題（1）選擇排序每次從剩下的數(shù)據(jù)中選擇最小值與剩余數(shù)據(jù)中的最前面一個(gè)值交換

[31,41,59,26,53,58,97,93]選擇排序?qū)嵗?1415926535897939397585331594126已正確定位9397585341593126已正確定位9397585359413126已正確定位主要任務(wù)：循環(huán)找最小值交換樸素策略：選擇排序def

selSort(nums):n=len(nums)

forbottominrange(n-1):

#循環(huán)n-2次

mp=bottom#初始bottom為迄今最小的索引位置

foriinrange(bottom+1,n):

#考慮其他值

ifnums[i]<nums[mp]:

mp=i

#新的迄今最小值的索引位置

nums[bottom],nums[mp]=nums[mp],nums[bottom]易實(shí)現(xiàn)，大數(shù)據(jù)量時(shí)效率低3141592653589793

(2)冒泡排序法從頭到尾比較相鄰的兩個(gè)元素，將小的換到前面，大的換到后面。經(jīng)過(guò)一趟比較，就把最大的元素交換到了最后一個(gè)位置。然后再?gòu)念^開(kāi)始到倒數(shù)第二個(gè)元素進(jìn)行第二趟氣泡……5730421968待冒泡的元素5304217689待冒泡的元素3042156789待冒泡的元素0321456789待冒泡的元素0213456789待冒泡的元素0123456789待冒泡的元素冒泡過(guò)程如果在一次起泡中沒(méi)有發(fā)生交換，則表示數(shù)據(jù)都已排好序，不需要再進(jìn)行起泡for(i=1;i<n;++i){

從元素0到元素n-i進(jìn)行起泡，最大的泡放入元素n-i；

if（沒(méi)有發(fā)生過(guò)數(shù)據(jù)交換）break;}怎么表示？defbubbleSort(nums):

n=len(nums)foriinrange(n-1):#對(duì)冒泡次數(shù)的循環(huán)

flag=False#每次循環(huán)flag被設(shè)為false，只要一次交換，flag就被設(shè)為true

forjinrange(n-1-i):

#內(nèi)循環(huán)，控制待冒泡的元素進(jìn)行兩兩比較

ifnums[j]>nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]flag=True#一旦發(fā)生過(guò)兩兩交換，就置為Trueifflag==False:break

#一趟冒泡中沒(méi)有發(fā)生交換，排序結(jié)束

defmain():myList=[45,67,76,54,34,55,90,23]bubbleSort(myList)printmyList冒泡排序源代碼特點(diǎn)：很容易實(shí)現(xiàn)，但大數(shù)據(jù)量時(shí)效率低(3)合并排序人們?cè)谕鎿淇伺频臅r(shí)候，經(jīng)常將手上的牌排成特定的順序，比如按花色或按大小排序。如果分到的牌不多，玩家一般用一只手將牌呈扇形握持，另一只手去整理排序。然而，如果玩的是用到兩三副牌的游戲，每個(gè)玩家分到的牌很多，那么玩家就會(huì)有手不夠大難以排序的煩惱。這時(shí)，如果旁邊坐著個(gè)觀戰(zhàn)者，玩家可以請(qǐng)這個(gè)觀戰(zhàn)者幫著拿一些牌，兩人分別將手中不多的牌進(jìn)行排序，然后再合并兩手牌以完成全部牌的排序?！喜⑴判虻幕舅枷耄ù髥?wèn)題分解成小問(wèn)題，分開(kāi)排序，再合并）無(wú)序的初始撲克牌集合分成二組分解的過(guò)程排好序的撲克牌集合合并的過(guò)程合并算法：兩個(gè)集合的最小值，較小者移出到新列表分治法：合并排序數(shù)據(jù)分成兩組或更多組，分別對(duì)各組排序，再把已有序的各組合并(merge)成完整有序列表。合并（merge）：定義一個(gè)新列表，比較兩組各自的第一個(gè)數(shù)據(jù)，小者輸出到新列表，由該組的下一個(gè)數(shù)據(jù)頂上來(lái)繼續(xù)比較。當(dāng)某組沒(méi)有數(shù)據(jù)，則將另一組整個(gè)輸出到新列表。defmerge(lst1,lst2,lst3):合并lst1、lst2到lst3whilelst1和lst2兩組都有數(shù)據(jù):

輸出兩組第一個(gè)數(shù)據(jù)的較小者至lst3

更新該組的第一個(gè)數(shù)據(jù)

while某組沒(méi)有數(shù)據(jù)了:

將另一組剩余數(shù)據(jù)輸出至lst3分而治之：合并排序合并排序中的合并過(guò)程實(shí)現(xiàn):defmerge(list1,list2,mergelist):

i,j,k=0,0,0#i,j為列表1和2的計(jì)數(shù)，k為列表3的計(jì)數(shù)n1,n2=len(list1),len(list2)whilei<n1andj<n2:#循環(huán)一直到某個(gè)列表為空iflist1[i]<list2[j]:#小者進(jìn)列表3，該列表的下一個(gè)值進(jìn)入下一次比較

mergelist[k]=list1[i]

i=i+1

else:

mergelist[k]=list2[j]

j=j+1

k=k+1

#列表3的下標(biāo)值

whilei<n1:#列表1還有未合并元素

mergelist[k]=list1[i]

i=i+1k=k+1whilej<n2:#列表2還有未歸并元素

mergelist[k]=list2[j]j=j+1k=k+1defmerge(list1,list2,mergelist):whilelen(list1)>0andlen(list2)>0:iflist1[0]<list2[0]:

mergelist.append(list1[0])dellist1[0]else:

mergelist.append(list2[0])dellist2[0]

mergelist.extend(list1)

mergelist.extend(list2)分而治之：合并排序的整體討論數(shù)據(jù)分成兩組或更多組，分別對(duì)各組排序，再把已有序的各組合并(merge)成完整有序列表。對(duì)各組排序可以利用遞歸：對(duì)每一組再次應(yīng)用分而治之的歸并排序。滿足遞歸的前提條件:基本情形：組中只有一個(gè)數(shù)據(jù)時(shí)無(wú)需遞歸;每次分組都使列表變小，最終會(huì)到達(dá)基本情形。偽代碼：

算法：對(duì)datalist執(zhí)行合并排序

輸入：無(wú)序的列表datalist

輸出：有序的列表datalist

將datalist一分為二：list1，list2

對(duì)list1進(jìn)行合并排序

對(duì)list2進(jìn)行合并排序合并list1和list2，結(jié)果放入datalist

合并排序的遞歸實(shí)現(xiàn)：def

mergeSort(nums):n=len(nums)ifn>1:m=n/2nums1,nums2=nums[:m],nums[m:]#分割

mergeSort(nums1)#對(duì)nums1進(jìn)行歸并排序，返回排好序的列表

mergeSort(nums2)

#對(duì)nums2進(jìn)行歸并排序，返回排好序的列表

merge(nums1,nums2,nums)#合并兩個(gè)排好序的列表，結(jié)果存于nums合并排序中的合并過(guò)程實(shí)現(xiàn):defmerge(list1,list2,mergelist):

i,j,k=0,0,0n1,n2=len(list1),len(list2)whilei<n1andj<n2:iflist1[i]<list2[j]:

mergelist[k]=list1[i]

i=i+1

else:

mergelist[k]=list2[j]

j=j+1

k=k+1

whilei<n1:

mergelist[k]=list1[i]

i=i+1k=k+1whilej<n2:

mergelist[k]=list2[j]j=j+1k=k+1第10章算法分析與設(shè)計(jì)§10.1查找問(wèn)題§10.2遞歸程序設(shè)計(jì)§10.3分治法（排序問(wèn)題）§10.4貪心法問(wèn)題的提出：需要在油庫(kù)A和加油站B、C、D、E、F、G、H之間修建輸油管道，圖中的虛線表示可能的管道鋪設(shè)路線，虛線旁標(biāo)注的數(shù)值表示所需鋪設(shè)的管道的長(zhǎng)度（千米）顯然沒(méi)有必要在所有可能路線上鋪設(shè)管道，而只需要各加油站直接或間接與油庫(kù)連通即可。假設(shè)人手和資金比較緊張，工程只能分批分期進(jìn)行，每期建設(shè)一條管道。我們?cè)撊绾我?guī)劃整個(gè)工程？圖論——最小生成樹(shù)方法（一）、盡可能快地使加油站投入使用，每一期工程都使一個(gè)加油站能夠供油。第一期必須在油庫(kù)A與某個(gè)加油站之間鋪設(shè)管道。找最短路徑。Prim算法：

從單一頂點(diǎn)開(kāi)始，在加權(quán)連通圖里搜索最小生成樹(shù)。即由此算法搜索到的邊子集所構(gòu)成的樹(shù)中，不但包括了連通圖里的所有頂點(diǎn)，且其所有邊的權(quán)值之和亦為最小。Prim算法：Step1、初始時(shí)所有地點(diǎn)標(biāo)記為不可通達(dá)Step2、選擇一個(gè)特定地點(diǎn)，標(biāo)記為可通達(dá)Step3、重復(fù)下列步驟，直至所有地點(diǎn)都被標(biāo)記為可通達(dá)：

選擇距離最近的兩點(diǎn)，其中一個(gè)地點(diǎn)是標(biāo)記可通達(dá)，另一個(gè)地點(diǎn)是不可通達(dá)。然后將這兩個(gè)點(diǎn)連接起來(lái)，并將原先不可通達(dá)的地點(diǎn)改為可通達(dá)_=float('inf')#正無(wú)窮defmain():

n=8#可讓用戶輸入Vertex=['A','B','C','D','E','F','G','H']graph=[[0,35,_,_,_,_,_,_],[35,0,15,_,_,_,_,_],[_,15,0,5,_,_,25,_],[_,_,5,0,_,_,_,_],[_,_,_,_,0,40,_,_],[_,_,_,_,40,0,_,10],[_,_,25,_,_,_,0,20],[_,_,_,_,_,10,20,0],]

#返回一個(gè)標(biāo)記兩兩之間是否聯(lián)通的列表

C=prim(graph,n)#接著開(kāi)始統(tǒng)計(jì)距離，打印線路

Result=[]

Total_dis=0foriinrange(n):forjinrange(n):if(1==C[i][j]):#兩地點(diǎn)連通

Result.append((Vertex[i],Vertex[j],graph[i][j]))

Total_dis=Total_dis+graph[i][j]print'FinalResult(totaldistance):%d'%(Total_dis)print'(P1,P2,dis)'printforrinResult:printrdefprim(graph,n):#flagsdenotingwhetherthevertexinconnectedornotflag=[False]*nflag[0]=True#initialconnectionmapconnection=[[0forcolinrange(n)]forrowinrange(n)]fornode_iterinrange(n-1):#有n-1條通路c_i=0c_j=0min_dis=_foriinrange(n):if(flag[i]):#是可通達(dá)點(diǎn)

forjinrange(n):dis_ij=graph[i][j]if(not(flag[j])anddis_ij<min_dis):#j為非可通達(dá)點(diǎn)min_dis=dis_ijc_i=ic_j=jflag[c_j]=Trueconnection[c_i][c_j]=1returnconnection方法（二）、不追求各加油站盡快投入使用，只想以最小的投資完成工程。這時(shí)的指導(dǎo)思想是，每一期工程都盡可能選擇當(dāng)前所有線路中最短的線路來(lái)鋪設(shè)管道，并確保最終能將油庫(kù)和所有加油站連通起來(lái)。Kruskal算法：

在加權(quán)連通圖里搜索最小生成樹(shù)，從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。Kruskal實(shí)現(xiàn)_=float('inf')defkruskal(graph,n):

#initialconnectionmapconnection=[[0forcolinrange(n)]forrowinrange(n)]fornode_iterinrange(n-1):c_i=0c_j=0min_dis=_foriinrange(n):forjinrange(n):dis_ij=graph[i][j]if(0==connection[i][j]and0==connection[j][i]\anddis_ij<min_disandi!=j):min_dis=dis_ijc_i=ic_j=jconnection[c_i][c_j]=1returnconnectiondefmain():n=8Vertex=['A','B','C','D','E','F','G','H']graph=[[0,35,_,_,_,_,_,_],[35,0,15,_,_,_,_,_],[_,15,0,5,_,_,25,_],[_,_,5,0,_,_,_,_],[_,_,_,_,0,40,_,_],[_,_,_,_,40,0,_,10],[_,_,25,_,_,_,0,20],[_,_,_,_,_,10,20,0],]C=kruskal(graph,n)Result=[]

Total_dis=0foriinrange(n):forjinrange(n):if(1==C[i][j]):

Result.append((Vertex[i],Vertex[j],graph[i][j]))

Total_dis=Total_dis+graph[i][j]print'FinalResult(totaldistance):%d'%(Total_dis)print'(P1,P2,dis)'print

forrinResult:printr貪心算法Prim算法和Kruskal算法都屬于貪心（貪婪）算法。貪心算法的特點(diǎn):

在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最