国产自产21区,亚洲97,免费毛片网,国产啪视频,青青青国产在线观看,国产毛片一区二区三区精品

專利名稱：最低成本路徑搜索裝置及其使用的最低成本路徑搜索方法
技術領域：
本發(fā)明涉及一種最低成本路徑搜索裝置以及該裝置所使用的一種最低成本路徑搜索方法，更具體地說，本發(fā)明涉及一種用于在網(wǎng)絡中搜索從入口節(jié)點到出口節(jié)點之間的最低成本路徑的方法。
現(xiàn)有技術通常公知的Dijkstra方法就是這種類型的最低成本路徑搜索方法。Dijkstra方法為一個出口節(jié)點僅搜索一個最低成本路徑。
Dijkstra方法是一種被廣泛地用作解決最短路徑問題的數(shù)學編程方法，而最短路徑問題則是與網(wǎng)絡有關的一種典型的優(yōu)化問題。這種方法能夠解決從一源節(jié)點到一目標節(jié)點間尋找最短路徑的最短路徑問題。
在這種情況下，通過利用優(yōu)化原理就可從數(shù)學上獲得最短路徑，在此原理中，從一源節(jié)點到一目標節(jié)點間的最短路徑在一特定節(jié)點上被分成兩部分，從而使由分割產(chǎn)生的兩個路徑中的每一個在集合中都地變成最短路徑。就是說，Dijkstra方法從一個空集合開始進行處理，一次找到多個最短路徑節(jié)點中的一個，以增加最短路徑子集的元素，并最終為全部節(jié)點找出最短路徑。
在“將內(nèi)部交叉成本考慮在內(nèi)的一種公路網(wǎng)絡中的路由搜索方法及其采用多媒體在路由導引系統(tǒng)中的應用”一文(日本信息處理學會，1992年7月，vol.33，No.7的第970-979頁)中說明了另一種用于對全部路徑按照成本升序進行搜索的方法。該出版物中所述的方法將搜索期間所找到的路徑保存起來，以用于對全部路徑的搜索。
上述搜索方法首先產(chǎn)生一個鏈接轉(zhuǎn)換列表，一輸入-輸出列表以及一成本差列表，并利用這些列表生長出一個到目標點的最低成本路徑樹。
但是，在傳統(tǒng)方法中，采用Dijkstra方法，為一個出口節(jié)點僅搜索出一個最低成本路徑。因此，就不可能按照成本的升序搜索出多個路徑。
生長出一個最低成本路徑的方法要對全部路徑進行搜索。因而，這就需要大量的存儲空間，以用來在搜索期間保存路徑。另一個問題在于，在搜索開始之前，不能確定所需的存儲空間量。具體來說，在一個含有很多分支的拓撲結構中，要保存的路徑在有些情況下不能被保存。在這種情況下，一個要尋找的路徑就不能被包含在有結果的搜索中，從而導致不能按照成本的順序來獲取路徑。
發(fā)明概述本發(fā)明的一個目的是，提供一種最低成本路徑搜索裝置以及一種能夠解決上述問題的最低成本路徑搜索方法，在有限量的存儲空間中按照成本升序為每個出口節(jié)點搜索任意數(shù)目的最低成本路徑，并能快速執(zhí)行路徑搜索。
根據(jù)本發(fā)明的最低成本路徑搜索裝置是一種能夠在網(wǎng)絡中搜索從入口節(jié)點到出口節(jié)點之間的最低成本路徑的最低成本路徑搜索裝置。這種最低成本路徑搜索裝置包括成本預估裝置，用于預先估計從一個中間節(jié)點到出口節(jié)點的成本；路徑生成裝置，用于為中間路徑生成從入口節(jié)點到中間節(jié)點的多個路徑，每個路徑都延伸至與該中間節(jié)點相鄰的一個節(jié)點；路徑存儲裝置，用于從路徑生成裝置生成的路徑中選出要保存的路徑，并同時控制多個要保存的路徑；路徑選擇裝置，用于從路徑保存裝置所保存的路徑中選出一個最佳路徑；以及路徑輸出單元，用于在路徑存儲裝置中沒有保存路徑時輸出獲取的路徑。
根據(jù)本發(fā)明的最低成本路徑搜索方法是一種能夠在網(wǎng)絡中搜索從入口節(jié)點到出口節(jié)點之間的最低成本路徑的最低成本路徑搜索方法。這種最低成本路徑搜索方法包括以下各步驟預先估計從一個中間節(jié)點到出口節(jié)點的成本；為中間路徑生成從入口節(jié)點到中間節(jié)點的多個路徑，每個路徑都延伸至與該中間節(jié)點相鄰的一個節(jié)點；從路徑生成裝置生成的路徑中選出要保存的路徑，同時控制多個要保存的路徑；從保存的路徑中選出一個最佳路徑；以及在沒有路徑保存時輸出獲取的路徑。


通過以下的詳細說明并參考附圖，本發(fā)明的上述及其它目的、特征和優(yōu)點將變得更加易于理解，在附圖中圖1是顯示本發(fā)明一個實施例中的一種最低成本路徑搜索裝置的結構的框圖；圖2是顯示本發(fā)明實施例中最低成本路徑搜索方法的操作的流程圖；圖3是顯示圖1所示路徑存儲單元的操作的流程圖；圖4是顯示了可用于根據(jù)本發(fā)明實施例的一種拓撲結構的例子的框圖；圖5是顯示利用Dijkstra方法對圖4所示拓撲結構計算出來的估計成本的框圖。
以下將參考附圖對本發(fā)明的一些實施例進行詳細說明。優(yōu)選實施例說明[第一實施例]圖1是顯示根據(jù)本發(fā)明第一個實施例的一種最低成本路徑搜索裝置的結構的框圖。參考圖1，本實施例中的這種最低成本路徑搜索裝置包括成本預估裝置1，路徑生成裝置2，路徑存儲單元3，路徑選擇裝置4，路徑輸出單元5以及存儲單元6。
成本預估裝置1估計從一個中間節(jié)點到所有出口節(jié)點的所有成本。路徑生成裝置2生成從當前搜索路徑到一相鄰節(jié)點間的路徑。路徑存儲單元3檢查路徑生成裝置2所生成的路徑并為終端節(jié)點在存儲單元6中保存多達預定數(shù)目的路徑。
路徑選擇裝置4從保存在所有中間節(jié)點和入口節(jié)點的項目之內(nèi)的路徑中選出一個路徑，該路徑尚未被選取，而且其路徑成本與最低估計成本之和最小。路徑輸出單元5輸出保存在出口節(jié)點中的路徑，作為搜索結果。在這種情況下，路徑輸出單元5按照成本的升序輸出與其為各個出口節(jié)點預備的路徑數(shù)相同的路徑。
圖2是顯示本實施例中所述的最低成本路徑搜索方法的操作的流程圖。圖3是顯示圖1所示路徑存儲單元3的操作的流程圖。以下將參考圖1-圖3對本實施例中所使用的最低成本路徑搜索方法進行說明。
首先，成本預估裝置1估計出從一個中間節(jié)點到所有出口節(jié)點的成本(圖2中的步驟S1)。在這種情況下，成本預估裝置1為各個中間節(jié)點保存了從該節(jié)點到出口節(jié)點的節(jié)點估計成本的最小值，作為最小估計成本。成本的估計按照以下三種方式之一(1)允許搜索方法的用戶輸入一個成本，(2)利用諸如Dijkstra的方法計算出最小成本，該方法是一種被廣泛用于解決網(wǎng)絡中最短路徑問題的數(shù)學編程方法，以及(3)輸入一個固定值。
接下來，路徑生成裝置2生成一個延伸至當前搜索路徑的一個相鄰節(jié)點的路徑(圖2中的步驟S2)。在初始路徑的生成過程中，路徑生成裝置2利用入口節(jié)點作為當前搜索路徑來執(zhí)行路徑生成。
路徑存儲單元3首先檢查路徑生成裝置2所生成的路徑(圖3中的步驟S11)。在路徑檢查期間，路徑存儲單元3將檢查一個路徑是否經(jīng)過同一節(jié)點兩次或更多次。
如果一個路徑經(jīng)過了同一節(jié)點兩次或更多次，則路徑存儲單元3將拒絕并舍棄該路徑(圖3中的步驟S12)。如果一個路徑?jīng)]有經(jīng)過同一節(jié)點兩次或更多次，則路徑存儲單元3將接納該路徑并檢查保存在存儲單元6中的路徑數(shù)目(圖3中的步驟S13)。當檢查路徑數(shù)目時，路徑存儲單元3將檢查保存在路徑的終端節(jié)點項目中的路徑數(shù)。應該注意，在存儲單元6中為各個節(jié)點保存著預定數(shù)目的路徑，而且該數(shù)目對拓撲結構中的所有節(jié)點都是恒定的。
如果存在一個或多個空閑項，路徑存儲單元3將保存路徑的路由，和作為路徑成本的該路徑上的鏈路通過成本(圖3中的步驟S14)。如果沒有空閑項，則路徑存儲單元3將舍棄具有最大成本的路徑(圖3中的步驟S15)。當舍棄最大成本路徑時，路徑存儲單元3將舍棄保存在路徑終端節(jié)點項目中的最大成本路徑。
在舍棄了一個保存在終端節(jié)點項目中的路徑之后，路徑存儲單元3在最終空閑項目中保存入新路徑的路由和路徑成本。路徑存儲單元3對路徑生成裝置2所生成的全部路徑重復執(zhí)行上述操作(圖3中的步驟S11-S16)。
路徑選擇裝置4從為所有中間節(jié)點和入口節(jié)點保存在存儲單元6內(nèi)的路徑中選出一個路徑，以作為當前搜索路徑，該路徑尚未被選取，而且其路徑成本與最低估計成本之和最小(圖2中的步驟S5)。如果這樣一個路徑被成功選出(圖2中的步驟S5)，則控制將返回至步驟S2以生成一個路徑。
如果不能選出這樣一個路徑，則控制轉(zhuǎn)到路徑輸出單元5，以將保存在出口節(jié)點項目中的路徑輸出，作為搜索結果(圖2中的步驟S6)，然后路徑搜索結束。在上述路徑搜索操作中，與存儲單元6中各個節(jié)點的預定路徑數(shù)目相同的路徑被按照成本的升序而為出口節(jié)點輸出。
圖4是顯示本實施例中所使用的拓撲結構的一個例子的框圖。圖5是顯示利用Dijkstra方法對圖4所示拓撲結構計算出來的估計成本的框圖。以下將參考圖1、圖4和圖5對本實施例中所使用的最低成本路徑搜索方法的操作進行說明。
在圖4中，入口節(jié)點由a表示，出口節(jié)點由b和c表示，中間節(jié)點則由A、B、C、D和E表示。鏈路旁的數(shù)字代表了通過成本。例如，當經(jīng)過節(jié)點a與節(jié)點A之間的鏈路時需要成本“1”。應該注意，本例中，在各個節(jié)點項目中可以保存多達兩個路徑。
首先，成本預估裝置1計算出從各個中間節(jié)點到各個出口節(jié)點的估計成本，并保存最小估計成本。例如，圖5顯示了利用Dijkstra方法產(chǎn)生的估計結果。在第一個路徑的生成中，路徑生成裝置2通過以入口節(jié)點a作為當前搜索路徑，將路徑延伸至與入口節(jié)點a相鄰的節(jié)點A而生成路徑a→A。
路徑存儲單元3檢查路徑a→A。沒有經(jīng)過同一節(jié)點兩次或多次的路徑a→A被接納。路徑存儲單元3檢查已保存的路徑的數(shù)目，并發(fā)現(xiàn)在路徑終端節(jié)點A的項目中沒有保存路徑。因此，路徑存儲單元3將路徑a→A和路徑成本“1”保存在存儲單元6的節(jié)點A項目中。
由于只有路徑a→A被保存在節(jié)點A的項目中，并且該路徑尚未被選取，所以路徑選擇裝置4將選擇該路徑作為當前搜索路徑，并將控制返回給路徑生成裝置2。
在第二個路徑的生成中，路徑生成裝置2以路徑a→A作為當前搜索路徑，生成三個路徑，a→A→B、a→A→C和a→A→a。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點a兩次的路徑a→A→a，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→B(路徑成本＝4)和a→A→C(路徑成本＝2)分別保存在節(jié)點B和節(jié)點C的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點B的項目中的路徑a→A→B(路徑成本+最低估計成本＝6)和保存在節(jié)點C的項目中的路徑a→A→C(路徑成本+最低估計成本＝5)。所以路徑選擇裝置4選擇路徑a→A→C(因其路徑成本與最低估計成本之和最小)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
在第三個路徑的生成中，路徑生成裝置2以路徑a→A→C作為當前搜索路徑生成三個路徑，a→A→C→E、a→A→C→B和a→A→C→A。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點A兩次的路徑a→A→C→A，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→C→E(成本值＝6)和a→A→C→B(成本值＝3)分別保存入節(jié)點E和節(jié)點B的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點B的項目中的路徑a→A→B(路徑成本+最低估計成本＝6)和路徑a→A→C→B(路徑成本+最低估計成本＝5)以及保存在節(jié)點E的項目中的路徑a→A→C→E(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4選擇路徑a→A→C→B(因其路徑成本與最低估計成本之和最小)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
在第四個路徑的生成中，路徑生成裝置2以路徑a→A→C→B作為當前搜索路徑生成四個路徑，a→A→C→B→c、a→A→C→B→D、a→A→C→B→A以及a→A→C→B→C。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點A兩次的路徑a→A→C→B→A和經(jīng)過節(jié)點C兩次的路徑a→A→C→B→C，并舍棄這兩個路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→C→B→c(成本值＝5)和a→A→C→B→D(成本值＝4)分別保存在節(jié)點c和節(jié)點D的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點B的項目中的路徑a→A→B(路徑成本+最低估計成本＝6)、保存在節(jié)點E的項目中的路徑a→A→C→E(路徑成本+最低估計成本＝7)以及保存在節(jié)點D的項目中的路徑a→A→C→B→D(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4選擇路徑a→A→B(因其路徑成本與最低估計成本之和最小)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
在第五個路徑的生成中，路徑生成裝置2以路徑a→A→B作為當前搜索路徑生成四個路徑，a→A→B→c、a→A→B→D、a→A→B→A以及a→A→B→C。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點A兩次的路徑a→A→B→A，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→B→c(成本值＝6)、a→A→B→D(成本值＝5)和路徑a→A→B→C(成本值＝5)分別保存在節(jié)點c、節(jié)點D和節(jié)點C的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點C的項目中的路徑a→A→B→C(路徑成本+最低估計成本＝8)、保存在節(jié)點E的項目中的路徑a→A→C→E(路徑成本+最低估計成本＝7)以及保存在節(jié)點D的項目中的路徑a→A→B→D(路徑成本+最低估計成本＝8)。所以路徑選擇裝置4選擇路徑a→A→C→E(因其路徑成本與最低估計成本之和最小)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
路徑a→A→C→B→D和路徑a→A→C→E具有相同的分值(路徑成本+最低估計成本＝7)。當兩個路徑具有相同的分值時，路徑選擇裝置4將選擇它們中間的一個。
在第六個路徑的生成中，路徑生成裝置2以路徑a→A→C→E作為當前搜索路徑生成三個路徑，a→A→C→E→b、a→A→C→E→D及a→A→C→E→C。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點C兩次的路徑a→A→C→E→C，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→C→E→b(路徑成本＝7)保存在節(jié)點b的項目中。
另一方面，對要保存在節(jié)點D的項目之中的路徑a→A→C→E→D來說，路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)節(jié)點D已保存有最高成本的兩個節(jié)點，因此它將舍棄最大成本路徑。在這種情況下，路徑存儲單元3對a→A→C→B→D(路徑成本＝4)、a→A→B→D(路徑成本＝5)以及a→A→C→E→D(路徑成本＝9)進行比較，舍棄最大成本路徑a→A→C→E→D，并將其它兩個節(jié)點保存在節(jié)點D的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點C的項目中的路徑a→A→B→C(路徑成本+最低估計成本＝8)以及保存在節(jié)點D的項目中的路徑a→A→C→B→D(路徑成本+最低估計成本＝7)和路徑a→A→B→D(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4選擇路徑a→A→C→B→D(路徑成本+最低估計成本＝7)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
在第七個路徑的生成中，路徑生成裝置2以路徑a→A→C→B→D作為當前搜索路徑生成兩個路徑，a→A→C→B→D→B和a→A→C→B→D→E。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點B兩次的路徑a→A→C→B→D→B，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→C→B→D→E(路徑成本＝7)保存在節(jié)點E的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點C的項目中的路徑a→A→B→C(路徑成本+最低估計成本＝8)、保存在節(jié)點E的項目中的路徑a→A→B→D→E(路徑成本+最低估計成本＝8)以及保存在節(jié)點D的項目中的路徑a→A→B→D(路徑成本+最低估計成本＝8)。所以路徑選擇裝置4選擇路徑a→A→B→C(因其路徑成本與最低估計成本之和最小)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
路徑a→A→B→C、路徑a→A→C→B→D→E以及路徑a→A→B→D具有相同的分值(路徑成本+最低估計成本＝8)。當兩個路徑或更多路徑具有相同的分值時，路徑選擇裝置4將選擇它們中間的一個。
在第八個路徑的生成中，路徑生成裝置2以路徑a→A→B→C作為當前搜索路徑生成三個路徑，a→A→B→C→B、a→A→B→C→E以及a→A→B→C→A。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點B兩次的路徑a→A→B→C→B以及經(jīng)過節(jié)點A兩次的路徑a→A→B→C→A，并舍棄這兩個路徑。
對要保存入節(jié)點E的項目中的路徑a→A→B→C→E來說，路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)節(jié)點E已保存有最高成本的兩個節(jié)點，因此它將舍棄最大成本路徑。在這種情況下，路徑存儲單元3對a→A→C→E(路徑成本＝6)、a→A→C→B→D→E(路徑成本＝7)以及a→A→B→C→E(路徑成本＝9)進行比較，舍棄最大成本路徑a→A→B→C→E，并將其余兩個節(jié)點保存在節(jié)點E的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點E的項目中的路徑a→A→C→B→D→E(路徑成本+最低估計成本＝8)和保存在節(jié)點D的項目中的路徑a→A→B→D(路徑成本+最低估計成本＝8)。所以路徑選擇裝置4選擇路徑a→A→B→D(因其路徑成本與最低估計成本之和最小)作為當前搜索路徑，并將控制返回給路徑生成裝置2。
路徑a→A→C→B→D→E和路徑a→A→B→D具有相同的分值(路徑成本+最低估計成本＝8)。當兩個路徑或更多路徑具有相同的分值時，路徑選擇裝置4將選擇它們中間的一個。
在第九個路徑的生成中，路徑生成裝置2以路徑a→A→B→D作為當前搜索路徑生成兩個路徑，a→A→B→D→B和a→A→B→D→E。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點B兩次的路徑a→A→B→D→B，并舍棄該路徑。
路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)節(jié)點E已保存有最高成本的兩個節(jié)點，因此它將舍棄最大成本路徑。在這種情況下，路徑存儲單元3對a→A→C→E(路徑成本＝6)、a→A→C→B→D→E(路徑成本＝7)以及a→A→B→D→E(路徑成本＝8)進行比較，舍棄最大成本路徑a→A→B→D→E，并將其余兩個節(jié)點保存在節(jié)點E的項目中。
現(xiàn)在，未被選出且保存在入口節(jié)點和中間節(jié)點的各項之中的路徑是保存在節(jié)點E的項目中的路徑a→A→C→B→D→E(路徑成本+最低估計成本＝8)所以路徑選擇裝置4選擇該路徑作為當前搜索路徑，并將控制返回給路徑生成裝置2。
在第十個路徑的生成中，路徑生成裝置2以路徑a→A→C→B→D→E作為當前搜索路徑生成三個路徑，a→A→C→B→D→E→b、a→A→C→B→D→E→D以及a→A→C→B→D→E→C。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點C兩次的路徑a→A→C→B→D→E→C和經(jīng)過節(jié)點D兩次的路徑a→A→C→B→D→E→D，并舍棄這兩個路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后將路徑a→A→C→B→D→E→b(路徑成本＝8)保存在節(jié)點b的項目中。在入口節(jié)點和中間節(jié)點的各項之中沒有未被選出且保存的路徑，所以控制前進到路徑輸出單元5。
路徑輸出單元5輸出保存在節(jié)點b的項目中的兩個路徑a→A→C→E→b和a→A→C→B→D→E→b以及保存在出口節(jié)點c的項目中的兩個路徑a→A→C→B→c和a→A→B→c。上述操作按照成本的升序各為出口節(jié)點b和出口節(jié)點c輸出兩個路徑。
如上所述，當搜索期間將路徑保存在中間節(jié)點和出口節(jié)點的項目中時，通過利用有限數(shù)目的路徑來選擇要保存的路徑，就可允許在有限的存儲量中為各個出口節(jié)點獲取指定數(shù)目的按成本升序排列的最低成本路徑。另外，在搜索期間，通過預先估計路徑成本并通過對用于一個路徑的項目數(shù)進行限制以縮窄搜索范圍，就可實現(xiàn)路徑的快速搜索。[第二實施例]接下來將對本發(fā)明第二實施例中的一種最低成本路徑搜索方法進行說明。第二實施例中的最低成本路徑搜索方法與第一實施例中所述方法的不同之處在于，其所保存路徑的數(shù)目以及路徑存儲單元3進行路徑選擇的處理過程中選擇路徑的方法是不同的。除此之外，第二實施例中的最低成本路徑搜索方法與第一實施例中的方法相類似。其裝置配置也與第一實施例相類似。
在第二實施例中，可被保存的路徑數(shù)在整個拓撲結構中都是恒定的。這種設計上的改動允許為所有出口節(jié)點按照成本升序獲取任何數(shù)目的路徑。以下將對第二實施例的操作進行說明。應注意，第二實施例中的成本估計和路徑生成與第一實施例中的情況完全相同。
第二實施例中的路徑存儲單元3首先檢查路徑生成裝置2所生成的各個路徑。在路徑檢查期間，路徑存儲單元3將檢查是否有路徑經(jīng)過同一節(jié)點兩次或更多次，如果一個路徑經(jīng)過了同一節(jié)點兩次或更多次，則路徑存儲單元3將拒絕并舍棄該路徑。
如果一個路徑?jīng)]有經(jīng)過同一節(jié)點兩次或更多次，則路徑存儲單元3將接納該路徑并檢查已被保存的路徑的數(shù)目。當檢查路徑數(shù)目時，路徑存儲單元3將檢查保存在整個拓撲結構中的路徑數(shù)。如果存在一個或多個空閑項目，則路徑存儲單元3進行路徑保存，即，保存路徑的路由以及路徑成本與最低估計成本之和。
如果沒有空閑項目，則路徑存儲單元3將舍棄最大成本路徑。在舍棄最大路徑成本時，路徑存儲單元3將舍棄包含該路徑本身和該路徑的終端節(jié)點的項目中所保存的路徑之一，在入口節(jié)點與中間節(jié)點當中，其路徑成本和最低估計成本總和為最大的路徑。當舍棄完一個路徑之后，路徑存儲單元3將把路由以及路徑成本與最低估計成本之和保存在最終空出的項目中。對于路徑生成裝置2所生成的全部路徑，重復執(zhí)行該操作。
本實施例中，路徑選擇裝置4從保存在整個拓撲結構的多個路徑中選擇出一個路徑以作為當前搜索路徑，該路徑的終端節(jié)點為入口節(jié)點或中間節(jié)點，其路徑成本與最低估計成本之和為最小。所選取的路徑被從存儲單元6中刪除。如果選取這樣一個路徑，控制將返回至路徑生成裝置2。如果不能選取這樣一個路徑，則控制將前進至路徑輸出單元5。
本實施例中，路徑輸出單元5可輸出一些保存在整個拓樸結構中的其終端節(jié)點是一個出口節(jié)點的路徑以作為搜索結果，然后結束路徑搜索。如上所述，本實施例中的路徑搜索操作在整個拓撲結構中按照成本的升序輸出預定數(shù)目的路徑。
接下來將參考圖4所示的一個拓撲結構例子，對本實施例中的最低成本路徑搜索方法進行說明。可以看到，在該例子中拓撲結構可保存多達四個路徑。
首先，成本預估裝置1執(zhí)行與第一實施例中相同的操作。如果本實施例中使用的是Dijkstra方法，則它將產(chǎn)生如圖5所示的結果。在第一個路徑的生成中，路徑生成裝置2以入口節(jié)點a作為當前搜索路徑，通過將路徑延伸至與入口節(jié)點a相鄰的節(jié)點A而生成一個路徑a→A。
路徑存儲單元3檢查路徑a→A。由于它并未經(jīng)過同一節(jié)點兩次或更多次，所以路徑a→A被接納。路徑存儲單元3檢查已保存路徑的數(shù)目并發(fā)現(xiàn)在整個拓撲結構中沒有保存路徑。因此，路徑存儲單元3將把路徑a→A以及路徑成本“1”與最低估計成本“4”的總和“5”保存在節(jié)點A的項目之中。
由于在整個拓撲結構中只保存了路徑a→A，而且該路徑的終端節(jié)點(節(jié)點A)是一個中間節(jié)點，所以路徑選擇裝置4從存儲單元6中刪除此路徑，并以該路徑作為當前搜索路徑，將控制返回給路徑生成裝置2。
在第二個路徑的生成中，路徑生成裝置2以路徑a→A作為當前搜索路徑生成三個路徑a→A→B、a→A→C及a→A→a。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點a兩次的路徑a→A→a，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后保存路徑a→A→B(路徑成本+最低估計成本＝6)和路徑a→A→C(路徑成本+最低估計成本＝5)。
現(xiàn)在，已保存的路徑是路徑a→A→C(路徑成本+最低估計成本＝5)和a→A→B(路徑成本+最低估計成本＝6)。所以路徑選擇裝置4將路徑成本與最低估計成本之和最小的路徑a→A→C從存儲單元6中刪除，并以該路徑作為當前搜索路徑，將控制返回給路徑生成裝置2。
在第三個路徑的生成中，路徑生成裝置2以路徑a→A→C作為當前搜索路徑生成三個路徑a→A→C→A、a→A→C→B及a→A→C→E。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點A兩次的路徑a→A→C→A，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后保存路徑a→A→C→B(路徑成本+最低估計成本＝5)和路徑a→A→C→E(路徑成本+最低估計成本＝7)。
現(xiàn)在，已保存的路徑是路徑a→A→C→B(路徑成本+最低估計成本＝5)、路徑a→A→B(路徑成本+最低估計成本＝6)以及路徑a→A→C→E(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4將路徑成本與最低估計成本之和最小的路徑a→A→C→B從存儲單元6中刪除，并以該路徑作為當前搜索路徑，將控制返回給路徑生成裝置2。
在第四個路徑的生成中，路徑生成裝置2以路徑a→A→C→B作為當前搜索路徑生成四個路徑a→A→C→B→A、a→A→C→B→C、a→A→C→B→c以及a→A→C→B→D。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點A兩次的路徑a→A→C→B→A和經(jīng)過節(jié)點C兩次的路徑a→A→C→B→C，并舍棄這兩個路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后保存路徑a→A→C→B→c(路徑成本+最低估計成本＝5)和路徑a→A→C→B→D(路徑成本+最低估計成本＝7)。
現(xiàn)在，已保存的路徑是路徑a→A→C→B→c(路徑成本+最低估計成本＝5)、路徑a→A→B(路徑成本+最低估計成本＝6)、路徑a→A→C→E(路徑成本+最低估計成本＝7)以及路徑a→A→C→B→D(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4將路徑成本與最低估計成本之和最小且其終端節(jié)點是一個中間節(jié)點的路徑a→A→B從存儲單元6中刪除，并以該路徑作為當前搜索路徑，將控制返回給路徑生成裝置2。
在第五個路徑的生成中，路徑生成裝置2以路徑a→A→B作為當前搜索路徑生成四個路徑a→A→B→A、a→A→B→C、a→A→B→c以及a→A→B→D。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點A兩次的路徑a→A→C→B→A，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中沒有空閑的項目，因此需舍棄最大成本路徑。
在這種情況下，路徑存儲單元3對路徑a→A→C→E(路徑成本+最低估計成本＝7)、路徑a→A→C→B→D(路徑成本+最低估計成本＝7)、路徑a→A→B→C(路徑成本+最低估計成本＝8)以及路徑a→A→B→D(路徑成本+最低估計成本＝8)進行比較。由于另一個已保存路徑a→A→C→B→c(路徑成本+最低估計成本＝5)以及現(xiàn)在要保存的路徑a→A→B→c(路徑成本+最低估計成本＝6)的終端節(jié)點是一個出口節(jié)點，所以它們不會被舍棄。
因此，只有兩個候選路徑得到保存。而其余的路徑a→A→B→C(路徑成本+最低估計成本＝8)和路徑a→A→B→D(路徑成本+最低估計成本＝8)則會作為最大成本路徑被舍棄。
現(xiàn)在，已保存的路徑是路徑a→A→C→B→c(路徑成本+最低估計成本＝5)、路徑a→A→B→c(路徑成本+最低估計成本＝6)、路徑a→A→C→E(路徑成本+最低估計成本＝7)以及路徑a→A→C→B→D(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4將路徑成本與最低估計成本之和最小且其終端節(jié)點是一個中間節(jié)點的路徑a→A→C→E從存儲單元6中刪除，并以該路徑作為當前搜索路徑將控制返回給路徑生成裝置2。路徑a→A→C→E和路徑a→A→C→B→D具有相同的分值(路徑成本+最低估計成本＝7)。當兩個路徑具有相同的分值時，路徑選擇裝置4將選擇其中之一。
在第六個路徑的生成中，路徑生成裝置2以路徑a→A→C→E作為當前搜索路徑生成三個路徑a→A→C→E→C、a→A→C→E→b以及a→A→C→E→D。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點C兩次的路徑a→A→C→E→C，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中沒有空閑的項目，因此需舍棄最大成本路徑。
在這種情況下，路徑存儲單元3對路徑a→A→C→B→D(路徑成本+最低估計成本＝7)和路徑a→A→C→E→D(路徑成本+最低估計成本＝12)進行比較。由于其余的已保存路徑a→A→C→B→c(路徑成本+最低估計成本＝5)和路徑a→A→B→c(路徑成本+最低估計成本＝6)的終端節(jié)點以及現(xiàn)在要保存的路徑a→A→C→E→b(路徑成本+最低估計成本＝6)的終端節(jié)點都是一個出口節(jié)點，所以它們不會被舍棄。
因此，只有一個候選路徑得到保存。而其余的路徑a→A→C→E→D(路徑成本+最低估計成本＝12)則會作為最大成本路徑被舍棄。
現(xiàn)在，已保存的路徑是路徑a→A→C→B→c(路徑成本+最低估計成本＝5)、路徑a→A→B→c(路徑成本+最低估計成本＝6)、路徑a→A→C→E→b(路徑成本+最低估計成本＝7)以及路徑a→A→C→B→D(路徑成本+最低估計成本＝7)。所以路徑選擇裝置4將路徑成本與最低估計成本之和最小且其終端節(jié)點是一個中間節(jié)點的路徑a→A→C→B→D從存儲單元6中刪除，并以該路徑作為當前搜索路徑，將控制返回給路徑生成裝置2。
在第七個路徑的生成中，路徑生成裝置2以路徑a→A→C→B→D作為當前搜索路徑生成兩個路徑a→A→C→B→D→E和a→A→C→B→D→B。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點B兩次的路徑a→A→C→B→D→B，并舍棄該路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后保存路徑a→A→C→B→D→E(路徑成本+最低估計成本＝8)。
現(xiàn)在，已保存的路徑是路徑a→A→C→B→c(路徑成本+最低估計成本＝5)、路徑a→A→B→c(路徑成本+最低估計成本＝6)、路徑a→A→C→E→b(路徑成本+最低估計成本＝7)以及路徑a→A→C→B→D→E(路徑成本+最低估計成本＝8)。所以路徑選擇裝置4將路徑成本與最低估計成本之和最小且其終端節(jié)點是一個中間節(jié)點的路徑a→A→C→B→D→E從存儲單元6中刪除，并以該路徑作為當前搜索路徑，將控制返回給路徑生成裝置2。
在第八個路徑的生成中，路徑生成裝置2以路徑a→A→C→B→D→E作為當前搜索路徑生成三個路徑a→A→C→B→D→E→C、a→A→C→B→D→E→b以及a→A→C→B→D→E→D。路徑存儲單元3檢查這些路徑，拒絕經(jīng)過節(jié)點C兩次的路徑a→A→C→B→D→E→C以及經(jīng)過節(jié)點D兩次的路徑a→A→C→B→D→E→D，并舍棄這兩個路徑。路徑存儲單元3檢查路徑的數(shù)目，發(fā)現(xiàn)在存儲單元6中有空閑的項目，然后保存路徑a→A→C→B→D→E→b(路徑成本+最低估計成本＝8)。
現(xiàn)在，已保存的路徑是路徑a→A→C→B→c(路徑成本+最低估計成本＝5)、路徑a→A→B→c(路徑成本+最低估計成本＝6)、路徑a→A→C→E→b(路徑成本+最低估計成本＝7)以及路徑a→A→C→B→D→E→b(路徑成本+最低估計成本＝8)。由于沒有其終端節(jié)點是一中間節(jié)點的已保存路徑，所以路徑選擇裝置4將把控制返回給路徑輸出單元5。
路徑輸出單元5輸出四個已保存的路徑a→A→C→B→c、a→A→B→c、a→A→C→E→b和a→A→C→B→D→E→b。本實施例中，上述操作例如按照成本的升序輸出了來自全部出口節(jié)點的指定數(shù)目的路徑。
根據(jù)本發(fā)明所述的最低成本路徑搜索裝置以及這種裝置所使用的最低成本路徑搜索方法具有以下優(yōu)點。即，當在網(wǎng)絡中對從一入口節(jié)點到出口節(jié)點之間的最低成本路徑進行搜索時，根據(jù)本發(fā)明所述的裝置和方法能夠預先估計從出口節(jié)點到各中間節(jié)點的成本、通過延伸至與一中間節(jié)點相鄰的節(jié)點而生成一個從一節(jié)點到一中間節(jié)點的路徑、在對要保存的路徑數(shù)目進行控制的同時從所生成的路徑中選擇一個或多個要保存的路徑、從已保存的路徑中選出最佳路徑、并在當沒有已保存路徑的情況下輸出該路徑。這種方法允許在有限的存儲量中為各個出口節(jié)點快速獲取指定數(shù)目的按成本升序排列的最低成本路徑。
盡管以上是參考特定的優(yōu)選實施例對本發(fā)明進行說明的，但是應該理解，本發(fā)明的主題思想并不限于這些具體實施例。相反，本發(fā)明主題思想包含了各種變換、修改和替代，它們都包含在權利要求的精神和范圍之內(nèi)。
權利要求
1.一種最低成本路徑搜索裝置，用于在網(wǎng)絡中搜索從入口節(jié)點到出口節(jié)點之間的最低成本路徑，上述最低成本路徑搜索裝置包括成本預估裝置，用于預先估計從中間節(jié)點到出口節(jié)點的成本；路徑生成裝置，用于為中間路徑生成從入口節(jié)點到中間節(jié)點的多個路徑，每個路徑都延伸至與該中間管理相鄰的一個節(jié)點；路徑存儲裝置，用于從所述路徑生成裝置生成的路徑中選出要保存的路徑，并能同時控制多個要保存路徑的數(shù)目；路徑選擇裝置，用于從所述路徑存儲裝置所保存的路徑中選出一個最佳路徑；以及路徑輸出單元，用于在當所述路徑存儲裝置中沒有保存路徑時輸出獲取的路徑。
2.如權利要求1所述的最低成本路徑搜索裝置，其中，上述成本預估裝置利用一個外部輸入的成本作為估計成本。
3.如權利要求1所述的最低成本路徑搜索裝置，其中，上述成本預估裝置利用一種作為數(shù)學編程方法的Dijkstra方法來計算一個最低成本。
4.如權利要求1所述的最低成本路徑搜索裝置，其中，上述成本預估裝置利用預設的固定值作為估計成本。
5.如權利要求1所述的最低成本路徑搜索裝置，其中，上述路徑存儲裝置限制了每個節(jié)點的要保存的路徑的數(shù)目。
6.如權利要求1所述的最低成本路徑搜索裝置，其中，上述路徑存儲裝置限制了對所有節(jié)點的要保存的路徑的數(shù)目。
7.一種在網(wǎng)絡中搜索從入口節(jié)點到出口節(jié)點之間的最低成本路徑的最低成本路徑搜索方法，上述最低成本路徑搜索方法包括以下各步驟成本估計步驟，預先估計從中間節(jié)點到出口節(jié)點的成本；路徑生成步驟，為中間路徑生成從入口節(jié)點到中間節(jié)點的多個路徑，每個路徑都延伸至與該中間節(jié)點相鄰的一個節(jié)點；路徑選擇步驟，從所述路徑生成裝置生成的路徑中選出要保存的路徑，同時控制多個要保存的路徑；從保存的路徑中選出一個最佳路徑的步驟；以及在沒有路徑保存時輸出獲取的路徑的步驟。
8.如權利要求7所述的最低成本路徑搜索方法，其中，上述成本估計步驟利用一個外部輸入的成本作為估計成本。
9.如權利要求7所述的最低成本路徑搜索方法，其中，上述成本估計步驟利用一種作為數(shù)學編程方法的Dijstra方法來計算一個最低成本。
10.如權利要求7所述的最低成本路徑搜索方法，其中，上述成本估計步驟利用預設的固定值作為估計成本。
11.如權利要求7所述的最低成本路徑搜索方法，其中，上述路徑選擇步驟限制了要為每個節(jié)點保存的路徑的數(shù)目。
12.如權利要求7所述的最低成本路徑搜索方法，其中，上述路徑選擇步驟限制了為所有節(jié)點保存的路徑的數(shù)目。
全文摘要
在步驟S1的成本估計步驟中,估計出從中間節(jié)點到所有出口節(jié)點的成本,并且在步驟S2的生成步驟中,通過將當前搜索路徑延伸至一相鄰路徑而生成各個路徑。在步驟S3的路徑存儲步驟中,對生成的路徑進行檢查,如果在存儲單元中有空閑項,則保存該路徑。在步驟S4的路徑選擇步驟中,存儲單元中保存在所有中間節(jié)點和入口節(jié)點的項目中的一個尚未被選擇的路徑被選擇作為當前搜索路徑,該路徑的路徑成本與最低估計成本之和最小。在步驟S6的路徑輸出步驟中,將保存在出口節(jié)點中的路徑作為搜索結果輸出。
文檔編號G01C21/34GK1350244SQ0113679
公開日2002年5月22日 申請日期2001年10月25日 優(yōu)先權日2000年10月25日
發(fā)明者曾我健二 申請人:日本電氣株式會社