SQL Serverは最短経路検索アルゴリズムを実装しています

これは去年の質問です。今日メールを整理していたら偶然見つけました。とても興味深いと思ったので書き留めておきました。

図1.

分析

RelationGraph テーブル内の Node フィールドと RelatedNode フィールド間の関係をよりわかりやすく説明するために、図 2 に示すようにグラフを使用して説明します。

図2.

図 2 では、ノードがどのように直接接続されているかが明確にわかります。また、ノード「p」からノード「j」へのいくつかの可能なパスも明確に確認できます。

上記から、2 番目の可能なパスは、最も少ない数のノードを通過することがわかります。

最初の問題を解決するために、私は2つの方法を参考にしました。

最初の方法は、

単一ソースの最短経路アルゴリズムであるダイクストラアルゴリズムを参照してください。このアルゴリズムの主な特徴は、開始点を中心にして、終了点に到達するまで層ごとに外側に拡張することです。

図3.

2番目の方法は、

最初の方法の改良は、図 4 に示すように、ノード「p」とノード「j」を中心として 2 つの円の外接点まで外側に拡張するマルチソースポイント法を使用することです。

図4.

成し遂げる

次に、SQL Server での実装方法について説明します。もちろん、ここで私が使用するのは、前述の 2 番目の方法で、「P」と「J」を起点として、中心から層ごとに外側に拡張します。

以下は、RelactionGraph テーブルにデータを作成して挿入するためのスクリプトです。

 TestDBを使用する
行く
object_id( 'RelactionGraph' ) がnullでない場合は、テーブル RelactionGraph を削除します。
テーブル RelactionGraph を作成します (ID int identity、Item nvarchar(50)、RelactionItemnvarchar(20)、制約 PK_RelactionGraph 主キー (ID))
行く
RelactionGraph(Item)include(RelactionItem) に非クラスター化インデックス IX_RelactionGraph_Item を作成します。
 RelactionGraph(RelactionItem)include(Item) に非クラスター化インデックス IX_RelactionGraph_RelactionItem を作成します。
行く
RelactionGraph (Item, RelactionItem) の値を挿入する
    ( 'a' 、 'b' )、( 'a' 、 'c' )、( 'a' 、 'd' )、( 'a' 、 'e' )、
    ( 'b' 、 'f' )、( 'b' 、 'g' )、( 'b' 、 'h' )、
    ( 'c' 、 'i' )、( 'c' 、 'j' )、
    ( 'f' 、 'k' )、( 'f' 、 'l' )、
    ( 'k' 、 'o' )、( 'k' 、 'p' )、
    ( 'お' 、 'い' )、( 'お' 、 'l' )
行く

ストアドプロシージャup_GetPathを書く

TestDBを使用する
行く
dbo.up_GetPathを実行します
        @Node = 'p' 、
 @関連ノード = 'j'  
行く

上記のストアドプロシージャは、主に 2 つの部分に分かれています。最初の部分は検索を実装する方法であり、2 番目の部分は戻り結果を構築する方法です。パート 1 のコードは、前の方法 2 に従って、@Node ノードと @RelatedNode ノードを介して外側のレイヤーを検索します。各検索で返されたノードは、一時テーブル #1 と #2 に保存されます。次に、一時テーブル #1 と #2 に接点があるかどうかが判断されます。接点がある場合は、最短パス (通過するノード数が最も少ない) が見つかったことを意味します。接点がない場合は、最大検索深度 (@MaxLevel smallint=100) に達するか、接点が見つかるまで、検索はループで続行されます。 100 層後に交差点が見つからない場合、検索は中止されます。ここで、検索可能な最大深度 @MaxLevel は、データ量が検索パフォーマンスに反比例するため、大量のデータによって発生する可能性のあるパフォーマンスの低下を制御するために使用されます。コードには、主に Node と RelatedNode を基準とした前方検索と後方検索についても記載されています。これらは相互参照オブジェクトであり、外向き検索に使用されます。

ストアドプロシージャの実行は次のとおりです。

必要に応じて@Nodeと@RelatedNodeに異なる値を割り当てることができます。

 TestDBを使用する
行く
 - 手順：
 object_id( 'up_GetPath' ) がnullでない場合 
    ドロッププロシージャ up_GetPath
行く
プロシージャ up_GetPath を作成する
（
    @Node nvarchar(50)、
    @関連ノード nvarchar(50)
 ）
として
ノーカウントをオンに設定
宣言する
    @level smallint =1, --現在の検索の深さ
    @MaxLevel smallint=100, --***検索可能な深さ
    @Node_WhileFlag ビット=1、 --@Nodeを中心に検索する場合、ループで検索するかどうかを決定するフラグとして使用されます
    @RelatedNode_WhileFlag ビット=1 --@RelatedNodeを中心に検索する場合、ループで検索するかどうかを決定するフラグとして使用されます
--直接関係のある2つのノードが見つかった場合は、直接戻ります
存在する場合(RelationGraph から 1 つを選択、(Node=@Node かつ RelatedNode=@RelatedNode)
または(Node=@RelatedNode And RelatedNode=@Node) )または @Node=@RelatedNode
始める
    convert(nvarchar(2000),@Node + ' --> ' + @RelatedNode) AsRelationGraphPath,convert(smallint,0) As StopCount を選択します。
戻る 
終わり
--
 if object_id( 'tempdb..#1' ) Is not null Drop Table #1 -- 一時テーブル#1は@Nodeを中心に外側に広がる各ノードのデータを格納する
if object_id( 'tempdb..#2' ) Is not null Drop Table #2 -- 一時テーブル#2には、@RelatedNodeを中心に外側に広がる各ノードのデータが格納されます。
テーブル#1を作成(
    ノード nvarchar(50),--相対ソースポイント
    関連ノード nvarchar(50), --相対ターゲット
    レベル smallint --depth
    ）
テーブル #2 を作成します (Node nvarchar(50),RelatedNode nvarchar(50),Level smallint)
 #1 ( ノード、関連ノード、レベル ) に挿入します
    select Node, RelatedNode, @level from RelationGraph a where a.Node =@Node union --Forward: @Node をソースクエリとして使用します
    select RelatedNode, Node, @level from RelationGraph a where a.RelatedNode = @Node --Reverse: @Node をターゲットとしてクエリを実行します
@Node_WhileFlag を sign(@@rowcount) に設定します。
 #2 ( ノード、関連ノード、レベル ) に挿入します
    select Node, RelatedNode, @level from RelationGraph a where a.Node =@RelatedNode union --Forward: @RelatedNode をソースクエリとして使用します
    select RelatedNode, Node, @level from RelationGraph a where a.RelatedNode = @RelatedNode -- 逆: @RelatedNode をターゲットとしてクエリを実行します
@RelatedNode_WhileFlag=sign(@@rowcount)を設定します
--RelationGraphテーブルに@Nodeまたは@RelatedNodeデータが見つからない場合は、後続のWhileプロセスを直接スキップします。
存在しない場合(#1 から 1 つを選択) または存在しない場合(#2 から 1 つを選択)
始める
While_Outに移動
終わり
while not exists(select 1 from #1 a inner join #2 b on b.RelatedNode=a.RelatedNode) --カットポイントが発生するかどうかを判断します
     かつ (@Node_WhileFlag|@RelatedNode_WhileFlag)>0 -- 検索が可能かどうかを判定する
     そして@level<@MaxLevel --深さを制御する
始める
@Node_WhileFlag >0 の場合
    始める
        #1 ( ノード、関連ノード、レベル ) に挿入します
             - フォワード
            a.Node、a.RelatedNode、@level+1 を選択
                RelationGraphから
                where exists(#1 から 1 を選択 where RelatedNode=a.Node And Level=@level) And
                    存在しません(Node=a.Node の場合、#1 から 1 つを選択)
            連合
             - 逆行する
            a.RelatedNode、a.Node、@level+1 を選択
                RelationGraphから
                where exists(#1 から 1 を選択 where RelatedNode=a.RelatedNode AndLevel=@level) And
                    存在しません(Node=a.RelatedNode の場合、#1 から 1 つを選択)
 @Node_WhileFlag を sign(@@rowcount) に設定します。
   終わり
@RelatedNode_WhileFlag > 0 の場合
    始める
        #2 ( ノード、関連ノード、レベル ) に挿入します
            - フォワード
            a.Node、a.RelatedNode、@level+1 を選択
                RelationGraphから
                where exists(#2 から 1 を選択 where RelatedNode=a.Node And Level=@level) And
                    存在しません(Node=a.Node の場合、#2 から 1 つを選択)
            連合
             - 逆行する
            a.RelatedNode、a.Node、@level+1 を選択
                RelationGraphから
                where exists(#2 から 1 を選択 where RelatedNode=a.RelatedNode AndLevel=@level) And
                    存在しません (Node=a.RelatedNode の場合、#2 から 1 つを選択)
 @RelatedNode_WhileFlag=sign(@@rowcount)を設定します
  終わり
    @level+=1 を選択
終わり
アウト中:
 --以下は、構築によって返される結果パスです
object_id( 'tempdb..#Path1' ) がnullでない場合は、テーブル #Path1 を削除します。
 object_id( 'tempdb..#Path2' ) がnullでない場合は、テーブル #Path2 を削除します。
 ;cte_path1 の場合
（
 a.Node、a.RelatedNode、Level を選択し、convert(nvarchar(2000)、a.Node+ ' -> ' +a.RelatedNode) AsRelationGraphPath、Convert(smallint,1) As PathLevel
 #1 から、存在する a があります (RelatedNode=a.RelatedNode である #2 から 1 つを選択)
すべて結合
b.Node、a.RelatedNode、b.Level を選択し、convert(nvarchar(2000)、b.Node+ ' -> ' +a.RelationGraphPath) を RelationGraphPath として変換し、Convert(smallint、a.PathLevel+1) を実行します。
 PathLevelとして
    cte_path1から
        内部結合 #1 b を b.RelatedNode=a.Node に結合
            b.レベル=a.レベル-1
 ）
 cte_path1 から #Path1 に * を選択します
;cte_path2 の場合
（
 a.Node、a.RelatedNode、Level を選択し、convert(nvarchar(2000)、a.Node) AsRelationGraphPath、Convert(smallint,1) As PathLevel
 #2 から、存在する a があります (RelatedNode=a.RelatedNode である #1 から 1 つを選択)
すべて結合
b.Node、a.RelatedNode、b.Level、convert(nvarchar(2000)、a.RelationGraphPath+ ' -> ' +b.Node) を RelationGraphPath として選択し、Convert(smallint、a.PathLevel+1) を実行します。
    cte_path2から
        内部結合 #2 b を b.RelatedNode=a.Node に結合
            b.レベル=a.レベル-1
 ）
 cte_path2 から #Path2 に * を選択します
;cte_result と
（
 a.RelationGraphPath+ ' -> ' +b.RelationGraphPath を選択 AsRelationGraphPath,a.PathLevel+b.PathLevel -1
 StopCount として、rank() over(order bya.PathLevel+b.PathLevel) として Result_row
    #Path1から
        #Path2 b を b.RelatedNode=a.RelatedNode に内部結合します。
            b.レベル=1
    ここで、a.Level=1
 ）
 Result_row=1 の cte_result から、異なる RelationGraphPath、StopCount を選択します。
行く

拡張機能

前の例は、都市のバス路線に拡張できます。2 つの停留所がある場合、これらの 2 つの停留所を通過する停留所が最も少ないバス路線を検索します。また、コミュニティ内の人間関係の検索にも拡張できます。たとえば、ある人が別の人と知り合いになりたい場合、そこにたどり着くまでに何人の人を直接通り抜ける必要がありますか。人と人とのつながりは、友人や親戚など直接的なつながりだけでなく、人と物とのつながりからも見つけられます。例えば、複数の作家が本を出版した場合、ある本の著者名簿から、共同で本を出版したというつながりがわかります。これは、2人が知り合った経緯を探す際の参考にもなります。この問題は非常に大きく複雑かもしれませんが、次のように拡張できます。

まとめ

ここでは、2 つのノード間のすべてのパスのうち、ノード数が最も少ないパスを見つけるだけです。実際のアプリケーションでは、これよりも複雑な状況に遭遇する可能性があります。他の環境やシナリオでは、長さ、時間、複数のノード、複数のスコープなどの情報が含まれる場合があります。いずれにしても、それを実装するには、一般的にいくつかの原則とアルゴリズムを参照する必要があります。

オリジナルリンク: http://www.cnblogs.com/wghao/archive/2013/04/23/3036965.html

【編集者のおすすめ】