.可修編..可修編..可修編..可修編.- .可修編.- .可修編.一、算法的時間復雜性丁⑺)：利用某算法處理一個問題規模為門的輸入所需要的時間。空間：為了解求問題的實例而執行的計算步驟所需要額存空間(或字)數目，不包括用來存儲輸入的空間。算法空間復雜性不可能超過運行時間的復雜性。元運算:對于任何計算步驟，不管輸入數據或執行的算法，它的代價總是以一個時間常量為上界，則稱該計算步驟為元運算。基于比較的排序問題的最優算法：我們通常把在O(nlgn)時間用元素比較法排序的任何算法，稱為基于比較的排序問題的最優算法。一般來說，如果可以證明任何一個求解問題A的算法必定是。①2)那么我們把在O(f(n))時間求解任何問題人的任何算法都稱為問題人的最優算法。算法設計原則:正確性確定性清晰性。算法的要素：1.待解問題的描述2.算法設計的任務3.算法分析。二、關系運算：指的是用于檢驗兩個幾何對象的特定的拓撲空間關系的邏輯方法。兩步確定兩條線段是否相交：1.快速排斥實驗(矩形不相交)2.跨立實驗(判斷線段P1P2是否和Q1Q2跨立依據是：(P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)>=0.)判斷點是否在多邊形常用算法：1.射線法(又叫奇偶測試法)2.轉角法。線段在多邊形的一個重要條件是線段的兩個端點都在多邊形，第二個必要條件是線段和多邊形的所有邊都不交。線段在多邊形判斷步驟：1.先求出所有和線段相交的多邊形的頂點2.然后按照X-Y坐標排序(X坐標小的排在前面，對于X坐標相同的點，丫坐標小的排在前面，這種排序準則也是為了保證水平和垂直情況的判斷正確），這樣相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形，則該線段一定在多邊形。計算線段或直線與線段的交點：設一條線段為L0=P1P2,另一條線段或直線為L1=Q1Q2,要計算的就是10和11的交點：第一步：首先判斷10和11是否相交2.若11不平行與丫軸，則交點橫坐標為P1的橫坐標，代入到L1的直線方程中可以計算出交點縱坐標。第三步：若11平行于曠軸，則第四步：若10平行于*軸，有2種情況，第五步：若L1平行于*軸，則，第六步：若L1和10斜率均存在，則。中心點的計算：多邊形的中心點（又叫質心或重心）可以通過將多邊形分割成為三角形，求取三角形的中心點，然后將三角形的中心點加權求和取得。三點畫圓：算法關鍵是求取圓心和園半徑：第一步：求取圓心，第二步：求取半徑口，R=（（xa-xpL2+（ya-yp廠2）」/2。p是圓心。四、矢量線柵格化三種方法：八方向柵格化、全路徑柵格化、恒密度柵格化。矢量面格式向柵格面格式轉換又稱為多邊形填充，就是在矢量表示的多邊形邊界部的所有柵格點上賦以相應的多邊形編碼，從而形成柵格數據陣列。方法有：部點擴散算法（種子，八方向擴散）、射線算法和掃描算法、邊界代數算法（積分、拓撲）。柵格數據矢量化有4個基本步驟：1.邊界提取2.邊界線追蹤3.拓撲關系生成4.去除多余點及曲線圓滑。細化算法：柵格數據需要細化，以提取其中軸線，因為：1.中軸線是柵格數據曲線的標準化存儲形式2.實現細化是將柵格曲線矢量化的前提3.在有些算法中可以提高計算精度。細化算法可分兩大類：第一大類是基于距離變換，首先得到骨架像元，然后跟蹤距離變換圖中的“山脊線”，并將其作為中軸線；第二類是基于在不破壞柵格拓撲連通性的前提下，按對稱的原則刪除影像邊緣的柵格點。四例：1.用距離變換法搜尋中軸線（減細）2.最大數值計算法（丫值4、1）3.經典的細化算法4.邊緣跟蹤剝皮法.多邊形柵格轉矢量的雙邊界搜索算法：基本思想：通過邊界提取，將左右多邊形信息保存在邊界點上，每條邊界弧段由兩個并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號。具體步驟：1.邊界點和結點提取2.邊界線搜索與左右多邊形信息記錄3.多余點去除。多邊形柵格轉矢量的單邊界搜索算法：單邊界搜索算法時通過對傳統的區域跟蹤算法進行改進而形成的，傳統區域跟蹤算法中，對區域的描述由兩部分組成：區域外輪廓和部孔洞。單邊界搜索算法流程：1.跟蹤、搜索第一層所有的區域并記錄外輪廓和部孔洞信息2.根據跟蹤到的孔洞信息找出下一層中未跟蹤過的區域的外輪廓跟蹤起始點（即找出一個新區域）3.跟蹤找到的新區域并記錄其外輪廓和部孔洞信息4.重復23步，直到該層所有區域都已被跟蹤完畢5重復2到3步，直到整幅圖像所有區域都已被跟蹤完畢。五、道格拉斯-普克法優點是具有最小的線性位移，壓縮效果占優，缺點是需對整條曲線完成數字化后方能進行壓縮，且計算工作量較大。光欄法原理：它按照預先定義的一個扇形（“喇叭口”），根據曲線上各節點是在扇形外還是在扇形，決定節點是保留還是舍去。其優點是光欄法不僅算法嚴密，能按給定閾值保留曲線特征點，并按時處理，運算量小，占用存少。鏈式編碼：多邊形邊界可定義為：由某一原點開始并按某些基本方向確定的單位矢量鏈。（東0東南1東北7）游程長度編碼：游程指相鄰同值網格的數量，游程長度編碼結構是逐行將相鄰同值的網格合并，并記錄合并后網格的值及合并網格的長度，其目的是壓縮柵格數據量，消除數據間的冗余。塊式編碼：塊式編碼是將游程長度編碼擴大到二維的情況，把多邊形圍劃分成由像元組成的正方形，然后對各個正方形進行編碼。差分映射法：就是選擇某一參照值對有關柵格的屬性值進行求差運算，根據差值得到一個新的柵格數據層。（分行選取和全區選取）拓撲關系左轉算法描述如下：1.順序取一個結點作為起始結點，取完為止；取過該結點的方位角最小的未使用過的或僅使用一次，且使用過的方向與本次相反的弧段作為起始弧段。2.取這條弧段的另一個結點，找這個結點關聯的弧段集合中的本條弧段的下一條弧段，如果本條弧段是最后一條弧段，則取弧段集合的第一條弧段，作為下一條弧段。3.判斷是否回到起點，如果是，則形成了一個多邊形，記錄下它，并且根據弧段的方向，設置組成該多邊形的左右多邊形信息；否則轉2。4.取起始點上開始的，剛才所形成多邊形的最后一條邊作為新的起始弧段，轉2；若這條弧段已經使用過兩次，即形成了兩個多邊形，轉1。島的判斷問題算法如下：1.計算所有多邊形的面積2.分別對面積為正的多邊形和面積為負的多邊形排序，分別形成正多邊形和負多邊形集合。3.如果負多邊形集合的個數為1，結束程序；否則，從面積為正的多邊形集合中，順序取出一個多邊形，如果正多邊形已經都被訪問過，則程序結束。4.依次從負多邊形集合中取出負多邊形，判斷當前取出的正多邊形是否包含該多邊形，如果包含，就將該負多邊形加入當前取出的正多邊形中，形成復雜多邊形，設置負多邊形的組成弧段的拓撲信息，并從負多邊形集合中刪除該負多邊形。當所有負多邊形都被訪問一遍后轉3.六、直線方程的所有形式：P(t)=P0+tV=P0+t(Pi-P0)=(1-t)P0+tP1(y0-y1)x+(x1-x0)y+(x0y1-x1y0)=0。P(t)=(x0+tcos0,y0+tsine)點到直線距離計算公式：d(P,L)=((y0-y1)x+(x1-x0)y+(x0y1-x1y0))/((x1-x0廠2+(y1-y0廠2廠1/2.三角形面積計算公式:A=1/2*bh,A=1/2*absin0，A=(s(s-a)(s-b)(s-c))1/2,s=1/2*(a+b+c),A=1/4*(4a2b2-(a2+b2-c2)2)1/2 ，A=b2/2(cot 0+cotB ) 。A=1/2|v*w|=1/2|(v1-v0)(v2-v0)|,2A=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)。四邊形面積計算公式： A=((s-a)(s-b)(s-c)(s-d))1/2，A(v0v1v2v3)=|(v1-v0)*(v3-v0)|，A=(x1-x0)(y3-y0)-(x3-x0)(y1-y0)，A=1/2|(v2-v0)*(v3-v1)|,2A=(x2-x0)(y3-y1)-(x3-x1)(y2-y0)。任意二維平面多邊形面積計算方法與公式：A多邊『WA(A),\=APViVi+1注意：對于一個逆時針多邊形，當點P在邊ViVi+1的左邊，則A的面積是正的；相反，當點P在邊ViVi+1的右邊，并且位于多邊形外部，則\的面積是負的。如果是一個順時針多邊形，則符號相反，并且部的三角形面積為負的。七、空間索引：就是指依據空間對象的位置和形狀或空間對象之間的某種空間關系，按一定的順序排列的一種數據結構，其中包括空間對象的概要信息。B樹的定義：一個m階的8樹，或為空樹，或是為滿足下列特征的m叉樹。(1)樹中每個結點至多有m棵子樹；（2）若根結點不是葉子結點，則至少有兩顆子樹；（3）除根之外的所有非終端結點至少有舊⑵棵子樹；（4）所有的非葉結點中包含下列信息數據：（A0<Ki，Ai，Di>,<K2，A2，D2>,...,Kn，An，Dn>）式中Ki（i=1,2…n）為關鍵字，且K<Ki+1（i=0,…門）為指向子樹根節點的指針，且指針勺-1所指的子樹中所有結點的關鍵字均小于K（i=1,…n）；A所指的子樹in中所有結點的關鍵字均大于Kn;Dn為數據指針，指向關鍵字七所在的數據記錄。<（從口>稱為結點的一個元素。（5）所有的葉子結點都出現在同一層次上，并且不帶信息（可以看作是外部結點查詢失敗的結點，實際上這些結點不存在，指向這些結點的指針為空）。插入算法：設將元素小人口>插入8樹中。（1）首先在樹中查找人若查找到，算法結束（假定8樹中不容許有相同的關鍵字存在）。若沒有查到，設最后查到的結點為N。將關鍵字K插入結點N中，若結點N的元素的個數小于等于m-1,將A指向葉結點，插入結束，若結點N的元素關鍵字的個數為m,則需分裂結點N。（2）設插入關鍵字K后的結點情況如下：（A0<K1,A1,D1>,<K2,A2,D2>-.<Km,Am,Dm>）創建一新結點L，將N中的第[m/2+1以及其后的所有元素，共1^-g/2]個元素移入新結點L中。再將元素<K[m/2],A[m/2],D[m/2]>移出N,插入結點N的父結點。N的父結點還可能需要分裂，最壞的情況是分裂一直延續到根結點，最后產生新的根結點，樹高增加1。當插入操作引起了s個結點的分裂時，磁盤訪問的次數為h（讀取搜索路徑上的結點）+2s（回寫兩個分裂出的新結點）+1（回寫新的根結點或插入后沒有導致分裂的結點）。因此，所需要的磁盤訪問次數是卜+2$+1，最多可達3h+1。口樹的定義:設M為結點中單元的最大數目，m(1<=m<=M/2)為非根結點中單元個數的下限。(1)每個葉子結點包含的單元個數介于m與M之間，除非它同時是根結點。(2)每個葉子結點中的單元(I,SpatialObjectID仲，1是包含該n維空間對象的MBR,SpatialObjectID是該空間對象的ID。(3)每個非葉子結點的子結點樹介于m到M之間，除非它同時是跟結點。(4)每個非葉子的結點的單元(I，PointerToChild)中，I是包含子結點的MBR，PointerToChild是指向子結點的指針。通過該指針能訪問到子結點。(5)根結點最少有兩個字結點，除非它同時是葉子的結點。(6)所有的葉子結點都處于樹的同一層上。插入算法：新空間對象的插入操作：(1)為新的空間對象，尋找一個合適的葉子結點(2)將新的空間對象記錄到葉子的結點中，(3)調整樹的結構(4)生成新的根結點。選擇合適的葉子結點：(1)初始化(2)判斷是否為葉子結點(3)選擇合適的子樹。調整樹的結構：(1)初始化(2)判斷是否是根結點(3)調整父結點相應單元的I(4)根據需要進一步分裂父結點。常規四叉樹缺點：所占的外存空間比較大，原因在于它不僅要記錄每個結點值，還需記錄結點的一個前趨結點及四個后繼結點，以反映結點之間的聯系。對柵格數據進行運算時，還要作遍歷樹結點的運算。這樣就增加了操作的復雜性。線性四叉樹的基本思想和優缺點：線性四叉樹不像常規四叉樹那樣存儲樹中各個結點及其相互間關系，而是通過編碼四叉樹的葉結點來表示數據塊的層次和空間關系。葉結點都具有一個反映位置的關鍵字，亦稱位置碼，表示它所處位置。實質是把原來大小相等的柵格集合轉變成大小不等的正方形集合，并對不同尺寸和位置的正方形集合賦予一個位置碼。缺點：位置碼的位數決定分割的層數，圖形越復雜，分割的層數越多，相應的位置碼得位數亦越多，這種自上而下的分割方法需要大量重復運算，效率比較低。線性四又樹的編碼方法：基于深度和層次碼的線性四叉樹編碼；基于四進制的線性四叉樹編碼；四叉樹的十進制編碼。的概念：指的是完成一個任務所需要的具體步驟和方法。常用的算法有窮舉搜索法，遞歸法，回溯法，貪心法，分治法。算法設計的原則：正確性，確定性，清晰性。時間復雜性：去除了表示算法運行時間的函數中的低階項和首項系數，就稱度量算法的漸進運行時間。空間復雜性：為了求解問題實例而執行的計算步驟所需要的存空間數目，它不包括分配用來存儲輸入的空間.元運算：對于任何計算步驟，他的代價是以一個時間常量為上界，而不管輸入數據或執行的算法，這個計算步驟叫做元運算。(算術，比較，邏輯，賦值)最優算法：如果可以證明任何一個求解的問題人的算法必定是。8(n)),那么我們把在o(f(n))時間求解問題人的任何算法都稱為問題人的最優算法。關系運算是指用于檢驗兩個幾何對象的特定的拓撲空間關系的邏輯方法。判斷兩直線相交：1)快速排斥實驗，設以線段p1p2，Q1Q2為對角線的矩形不想交，則兩線段不相交。2）跨立實驗如果兩個線段相交，則一定跨立對方運用矢量乘法乘積小于零則位于兩邊。判斷點是不是在多邊形1）射線法，一條射線從點P開始，穿過多邊形的邊界的次數成為交點數目，當交點數目為偶數時，點在多邊形外部，不然在部。2）轉角發，多邊形環繞點P的次數成為環繞數，環繞數為零，在多邊形外部，不然在部。判斷線段是不是在多邊形：線段在多邊形的必要條件是兩個端點都在多邊形，線段和多邊形的所有邊都不交。如果多邊形的一個頂點和線段相交，還必須判斷兩個相鄰交點之間的線段是不是包含與多邊形部。計算線段或直線與線段的交點：第一步判斷兩條線是不是相交，如果不像交，沒有交點。第二到第五步分別判斷平行與X,Y軸的情況。第六步兩條線斜率都存在并且不為零。中心點的計算：重心（分割三角形，加權求的，權重為三角形面積站的多邊形面積比例）三點畫圓：求圓心P,求取圓的半徑。柵格數據向矢量格式的轉換步驟：1）邊界提取，采用高通濾波將柵格圖像二值化或者以特殊值標識邊界點。2）邊界線追蹤，對每個邊界弧段由一個結點向另一個結點搜索，通常對每個已知邊界點需沿除了進入方向的其他七個方向搜索下一個邊界，直到連成邊界弧段。3）拓撲關系生成，對于矢量表示得邊界弧段數據，判斷其與原圖上各多邊形的空間關系，以形成完整的拓撲結構并建立與屬性數據的聯系。4）去除多余點及曲線圓滑，由于搜索是逐個柵格進行的，必須去除由此造成的多余點記錄，以減少數據繁雜，搜索結果，曲線由于柵格精度的限制可能不夠圓滑，需要采用一定的插補算法進行光滑處理，常用的算法有線性迭代法，分段三次多項式插值法，正軸拋物線平均加權法。斜軸拋物線平均加權法，樣條函數插值法。多邊形柵格轉矢量的雙邊界搜索算法：思想是通過邊界提取，將左右多邊形信息保存在邊界點上，每條邊界弧段由兩個并行的邊界鏈組成，分別記錄該邊界弧段的左右多邊形編號。邊界線搜索采用2*2的柵格窗口，在每個窗口4個柵格數據的模式，可以唯一地確定下一個窗口的搜索方向和該弧段的拓撲關系，極大的加快了搜索速度，拓撲關系也很容易建立，步驟（1）邊界點和結點提取2）邊界線搜索與左右多邊形信息記錄3）多余點去除。單邊界搜索算法：對區域的描述由兩部分組成，區域外輪廓和部孔洞，確定外輪廓跟蹤起始點，對區域的外輪廓進行跟蹤和記錄，對區域部的所有孔洞進行掃描跟蹤和記錄。將圖像中的所有區域按包含關系分為若干層，每一層至少包含一個區域對象，流程：1搜索跟蹤第一層所有的區域并記錄外輪廓和部孔洞信息；2根據跟蹤到的空孔洞信息找出下一層中未跟蹤過的區域的外輪廓跟蹤起始點；3跟蹤找到的新區域并記錄其外輪廓和部孔洞信息4重復2，3步直到該層所有區域都已被跟蹤完畢5重復2-4步知道整幅圖像所有區域都已被跟蹤完畢。拓撲關系生成過程：1弧段處理，使整幅圖形中的所有弧段，除在端點處相交外沒有其他交點，即沒有相交或自相交的弧段2結點匹配，建立結點弧段關系3建立多邊形，以左轉算法或右轉算法跟蹤，生成多邊形，建立多邊形和弧段的拓撲關系4建立多邊形與多邊形的拓撲關系，調整弧段的左右多邊形標號，多邊形部標識號的自動生成。空間索引：是指依據空間對象的位置和形狀或空間對象之間的目中空間關系，按一定的順序排列的一種數據結構，其中包括空間對象的概要信息。8樹定義：一個M階的8樹1）樹中每個結點至多有乂棵子樹2）若根結點不是葉子節點。至少有兩棵子樹3）除根之外的所有非終端節點至少有乂/2（取整）棵子樹4）所有的非葉結點中包含（40,<K1,A1,D1>,…..<KN,AN,DN>）Ki為關鍵字，內為指針,Dn為數據指針5）所有的葉子節點都出現在同一層次上，并且不帶信息。口樹定義：1）每個葉子節點包含的單元個數介于m和M之間，除非它同時是根節點。2）每個葉子結點中的單元中，1是包含該n維空間對象的MBR,ID。3）每個葉子節點的子節點數介于m和M之間，除非它是根節點。4）每個非葉子節點的單元中，1是包含子節點的乂8口，POINTER是指向子節點的指針，通過該指針能訪問到子結點5）根節點最少有兩個子結點，除非它同時是葉子結點6）所有的葉子節點都處于樹的同一層上。算法的設計原則是正確性、確定性、清晰性。算法的復雜度包括算法的時間復雜度、算法的空間復雜度。￡06「八。￡6](1993)構造出一個由邊界、部、外部的點集組成的9—交空間關系模型(9皿)。折線段的拐向判斷方法可以直接由矢量叉積的性質推出。對于有公共端點的線段.1和P1P2，通過計算(P2-P產(P1-中的符號便可以確定折線段的拐向：若優-P0)x(P1-P0)>0,則P0P1在\點拐向右側后得到P1P2;若[-P0)x(P1-P0)<0,則P0P1在、點拐向左側后得到.2；若(、-P0)x(P1-P0)=0,則八.、、三點共線。在空間查詢中，最常用的兩種查詢是按屬性信息的要求來查詢定位空間位置和根據對象的空間位置查詢有關的屬性信息.。實現一種地圖投影點的坐標變換為另一種地圖投影點的坐標，就是要找出〕、=fi(9,八關系式，其方法有解析變換法、數值解析[y=f(S,Y)2變換法和數值變化法。設面狀物體的輪廓邊界由一個點的序列、(x1,y1),P2(x2,y2),…，TOC\o"1-5"\h\z\o"CurrentDocument"ciy% >S=_z^ii2_% y尸1i+1 i+1Pn(xn,4)表示，其面積為。軸線或邊界上的相鄰三點Pi_1、Pi,P」用右手螺旋法則判斷軸線(邊界)轉折點的凸凹性，若拇指向下，則2點左側為凸，右側為凹。在下面選項中，不屬于數據挖掘步驟的是(B)。人數據變換8數據分類C數據清理D知識表示有六種多項式時間算法最為常見，其關系為(D)。AO(1)<O(logn)<O(nlogn)<O(n)<O(n2)<O(n3).可修編..可修編..可修編..可修編..可修編.可修編.BO(1)<O(logn)<O(n)<O(n2)<O(nlogn)<O(n3)CO(1)<O(nlogn)<O(n)<O(logn)<O(n2)<O(n3)DO(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)我國現在采用的1980國家坐標系應用的是哪種地球橢球體參數(B)。人克拉索夫斯基橢球 B1975國際橢球CWGS-84系橢球 D1980國際橢球磁盤訪問次數是影響空間索引性能的關鍵指標，下面哪種空間索引方法是比較優秀的空間索引方法。(A)ACELL樹BR樹 CB+樹DR+樹(人)反映城市的帶狀延伸程度，帶狀延伸越明顯則延伸率越大，反映城市的離散程度越大。A伸延率8緊湊度C緊湊度指數口放射狀指數在矢量緩沖區的實現算法中對于雙線問題最簡單的方法是(C)。A凸角圓弧法B疊置算法C角平分線法D圓弧擬合法TOC\o"1-5"\h\z下圖按照前序遍歷的方法寫出結果。(A) 0、 勺、、Aa+b*c-d-e/f 0 /B-+a*b-cd/ef :一、cdCabcd-*+ef/-D沒有正確答案在下面選項中，不屬于數據挖掘算法的是苗)。

人聚類分析B疊置分析C人聚類分析B疊置分析C主成分分析D層次分析法下面關于點緩沖區邊界生成算法的敘述哪一條正確?(A)A等分的圓心角越小，步長越小，誤差越小；8等分的圓心角越大，步長越小，誤差越小；C等分的圓心角越大，步長越小，誤差越大；口等分的圓心角越小，步長越大，誤差越小。在下面選項中，不屬于8-樹的性質的是(D)。人多叉樹 8查找樹C平衡樹D二叉樹TOC\o"1-5"\h\z無向圖的鄰接矩陣是不對稱的。 (X)在多邊形的方向判斷中，多邊形邊界順時針方向稱為負方向。(x)同樣的一個算法可以用幾種不同的形式來描述，也可能存在幾種解決相同問題的算法。 ( )判斷圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩四邊的距離的最小值。 ( )網絡數據結構的基本組成部分和屬性是鏈和結點。 ( )所有元素存放在一片連續的存貯單元中，邏輯上相鄰的元素存放到計算機存仍然相鄰這種存儲方式是存儲方式。 (x)緊湊度是反映城市的緊湊程度，其中圓形區域被認為最緊湊，緊湊度為1。其它形狀的區域，其離散程度越小則緊湊度越低。 (x)緩沖區實現算法有矢量方法和柵格方法兩種。 ()對于塊式編碼來說，圖斑越碎，壓縮比越高。 (x)矢量數據的壓縮往往是不可逆的，數據壓縮后數據量變小了，但數據的精度不(X)(X)維述擴展的9交集模型關系非常復雜,通過對大量的空間關系進行歸納和分類,得出5種基本的空間關系，這5種關系定義為空間關系的最小集,他們具有哪些特征？（1）相互之間不能進行轉化；（2）能覆蓋所有的空間關系模式；（3）能應用于同維與不同維的幾何目標；（4）每一種關系對應于唯一的口￡-9皿矩陣；（5）任何其它的DE-9IM關系可以通過用這5種基本關系進行表達。簡述Dijkstra算法的步驟。（1）引進一個輔助向量口，它的每個分量口口]表示當前所找到的從起點丫巾到每個終點討的最短路徑的長度。假設用帶權的鄰接矩陣2m5來表示帶權有向圖，2^亂口口]表示弧＜vi,vj＞上的權值。若＜vi,3＞不連通，則arcs[i][j]=8。那么口口]的初值為：D[i]=arcs[m][i]vieV此外，將已找到的從丫巾出發的最短路徑的終點的集合記為$,它的初始狀態為空集。(2)選擇vj使得D[j]=Min{D[i]|vkV-S}Vj就是當前求得的一條從丫巾出發的最短路徑的終點。其中j為這條最短路徑的終點，將其加入到終點集合5,令5=50小(3)修改輔助向量口，即修改從丫巾出發到集合丫3上任一頂點丫卜可達的最短路徑長度。顯然，若口口]+2^5內的＜口的，則表明從丫巾出發，經過必到達丫卜的路徑更短。因此，如果口內+2^5口]的＜口的，則修改口的為D[k]=D[j]+arcs[j][k](4)重復操作第二步、第三步共憶1次。由此求得從丫到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。在動態緩沖區生成算法中主要是針對哪兩類特殊情況提出的？并寫出他們的生成方法。答：動態緩沖區生成是針對兩類特殊情況提出的：一類是流域問題：從流域上游的某一點出發沿流域下朔，河流的影響半徑或流域的輻射圍逐漸擴大；相反，則逐漸縮小。另一類是污染問題。污染源對鄰近對象的影響程度隨距離的增大而逐漸縮小。(一)對于流域問題，可以基于線目標的緩沖區生成算法，采用