Java スパニングツリー構造ポイント間の最短経路アルゴリズム

まずは二分木についてお話しましょう。二分木は、各ポイントが 2 つのポイントに接続されているツリー構造です。下に行くほどポイントの数が増え、形が木のように見えるため、二分木と呼ばれます。二分木は、データ構造で高速検索、リソースの節約、効率の向上に使用されます。 2点間の経路は1つだけなので計算は必要ありません。もちろん、次のアルゴリズムを使用して計算することもできます。

バイナリツリー図:

二分木の変形である多分岐木について説明します。名前が示すように、各ポイントは N 個のポイントに接続できます。同様に、2 点間の経路も 1 つしかないため、計算する必要はありません。もちろん、次のアルゴリズムを使用して計算することもできますが、これも非常に困難です。

図に示すように:

スパニングツリーは、マルチブランチツリーの変形です。各ノードは N 個のノードに接続されています。上、下、左、右のいずれであるかは関係ありません。混乱しています。最終的な結果は、いずれかのノードを切断しても、他のノードを接続するパスが残ることです。

図に示すように:

このグラフは最小全域木に属します。スレッドの状況は極めて混沌として複雑になる可能性があります。以下はテストに使用したグラフです。完全な全域木ではありませんが、マルチフォークと全域木の中間です。

ルーティングテーブルの概念について説明しましょう。実際のネットワーク構造は、上記のテスト図に似ています。あるマシンから別のマシンに情報を送信するには、最短パスを見つける必要があります (もちろん、実際には考慮する必要がある予期しない状況が多数ありますが、これは最も基本的な状況にすぎません)。実際、なぜ自分のマシンで計算しなければならないのか、と私は思います。ルーティングテーブルを保存するだけでも、非常に多くのスペースを占有します。他のユーザーに情報を送信する必要があるたびに、隣接するノードを見つけて、最終目的地までのパスコストを尋ね、最小のものを選択して送信します。全員が次のステップを尋ね、最終的には必ず最終目的地に到達できます。さらに、ローカルマシンは次のホップが誰であるかを知るだけでよく、ルーティング情報全体を保存する必要はありません。

まあ、このマシンで計算しないといけないので、ちょっとお見せしますね。

考え方は同じで、段階的に何をすべきかを尋ねます。

（パス情報の追加とルーティング情報の削除の計算原理はコードの後半で示します）

まず、パス情報をすべて記述する必要がありますね。コンピューターに画像を渡して、それを理解させるだけではだめです (将来的には、さらなる技術開発によって可能になるかもしれません)。

文章で説明すると、簡単に言えば、点 * 別の隣接する点 * それらの間のコストとなります。

たとえば、この図では、2 つのポイント間のコストが 1 であると仮定します。

A*B*1

1*C*1 です

双方向接続なので、

1 点

1 位

したがって、このアルゴリズムは、片方向の接続がある場合でも計算できます。

これらの接続情報を文字列配列に保存します。

例えば: String[] s = {"A*B*1", "B*A*1", "B*A*1", "C*A*1"}

順番は関係ありません。好きなようにしてください。

2 番目のステップはキーポイントです。上記のアイデアを使用して、最初からステップごとに検索します。各ポイントについて、それに直接接続されているすべてのポイント (もちろん、質問するポイントを除く) に質問します。最終目的地に到達するにはどのくらいのコストがかかりますか? 最終結果は、終了ポイントからステップごとに前方に計算し、最小のものを保持し、その他を破棄することです。典型的な反復思考。すべて 1 回の反復で完了します。

まず、以下のように使いやすいようにstring[]をリストにします。

注意すべき点が 1 つあります: 重要!!! 重複がある可能性があります。

次のような状況があります: A は E への最短経路を望んでいます。

A が B に質問し、B が C に質問し、C が D に質問し、D が再度 B に質問する場合があります。

したがって、通過したポイントを保存するための別のリストが必要です。検索するたびに過去を振り返ることはなく、以前に表示されたポイントに戻ることもありません。

今回見つけたルートが最短ではないかもしれないと心配しないでください。すべてのルートを一度ずつ通るので、最終的にはすべてのルートを一緒に通った後、間違いなく最短になります。

では、アルゴリズムを見てみましょう。リスト (すべてのパス情報を保存)、ポイント (それ自体)、宛先を渡し、次のホップポイント (通話のコストを含む) を計算します。

もちろん、このアルゴリズムは最適ではありません。繰り返し計算が行われ、最初に見つかったものを見つけるために最短経路が選択されます（そのポイントに行くたびにこの経路を取らないようにランダムに作成し、他の経路も負荷を分散できるようにする必要があります）。

参考用ですので、お気軽にご連絡ください。

JAVAバージョン:

(ベクトルはリストです)

公共 クラスFindNextRout {
プライベートベクターal;
プライベート文字列sourcePort;
プライベート文字列destPort;
プライベート文字列 nextPort;
パブリックFindNextRout(ベクトル al、文字列 sourcePort、文字列 destPort) { 
 これ.al = al; 
  .sourcePort = sourcePort;です。 
 これは.destPort = destPort;
 次のルート();
 } 
 パブリック文字列getNextPort() { 
  nextPortを返します。
 } 
 公共  void NextRout() { 
 整数a = - 1 ;
 文字列 rout = "" ; 
  for (オブジェクト項目: al) {
 ArrayList all =新しいArrayList();
 文字列[] ss = (item + "" ).split( "\\*" );
 すべてを追加します(ss[ 0 ]); 
  if (sourcePort.equals(ss[ 0 ])) { 
  if (ss[ 1 ].equals(destPort)) { 
  int b = Integer.parseInt(ss[ 2 ]); 
  b < a || a == - 1の場合
 a = b;
 次ポート = ss[ 1 ];
 }
 }それ以外{ 
  int b = getLeastCost(all, ss[ 1 ], destPort); 
  int c = b + Integer.parseInt(ss[ 2 ]); 
  b != - 1の場合
  (a == - 1 )の場合{
 a = c;
 次ポート = ss[ 1 ];
 }それ以外{ 
 もし（c < a）{
 a = c;
 次ポート = ss[ 1 ];
 }
 }
 }
 }
 }
 } 
   
 } 
   
 公共  int getLeastCost(ArrayList all、String sourcePort、String destPort) { 
 整数a = - 1 ; 
  if (!all.contains(sourcePort)) {
 すべてを追加します(ソースポート); 
  for (オブジェクト項目: al) {
 文字列[] ss = (item + "" ).split( "\\*" ); 
  if (sourcePort.equals(ss[ 0 ])) { 
  ss[ 1 ]を含む場合
  if (ss[ 1 ].equals(destPort)) { 
  int b = Integer.parseInt(ss[ 2 ]); 
  b < a || a == - 1の場合
 a = b;
 }
 }それ以外{ 
  int b = getLeastCost(all, ss[ 1 ], destPort); 
  int c = b + Integer.parseInt(ss[ 2 ]); 
  b != - 1の場合
  (a == - 1 )の場合{
 a = c;
 }それ以外{ 
 もし（c < a）{
 a = c;
 }
 }
 }
 }
 }
 }
 } 
   
 } 
 を返します。
 }
 }

Python バージョン: (Python に翻訳してくれた Zhang Dongfang に感謝します)

 os、sysをインポート
ツールのインポートから*
クラスFindNextAddress:
 def __init__(自己、 宛先アドレス 、 UI ):
試す：
自己.nextAddress = UI.routeTable[destAddress]
 #アドレスがルートテーブルにあるかどうかを確認します 
 #UI.addline('試してみる')  
を除外する：
 #UI.addline('ex1')  
自分.UI = UI
自己.sourceAddress = UI.address
自己.destAddress = 宛先アドレス
自己.tool = tool()
 #UI.addline(宛先アドレス)  
 #UI.addline('ex2')  
自己.nextAddress =自己.findNextAddress()
 # アドレスがルートテーブルにない場合は、ルートを再計算します。  
 #UI.addline(自己.nextAddress)  
 #UI.addline('ex3')  
 def getNextAddress(自己):
戻る 自己.nextAddress
 #送信元から送信先までの次のアドレスを見つける 
 def findNextAddress(自己):
 a=- 1  
 tempNextAddress = ''  
アイテムの 自己.UI.routeInfo:
 #self.UI.addline(item+" //// アイテム")  
すでにパス済み=[]
結果 = item.split( '*' )
自己.tool.addItemInList(すでにパス、結果[ 0 ])
もし 自己.sourceAddress == 結果 [ 0 ]:
結果[ 1 ] == self .destAddressの場合:
 b = int(結果[ 2 ])
 b<aまたはa==- 1 の場合:
 a=b
 tempNextAddress = 結果[ 1 ]
それ以外：
 b = self.getLeastCost (alreadyPass,result[ 1 ], self.destAddress ) です。
 c=b+int(結果[ 2 ])
 b != - 1 の場合:
 a==- 1 の場合:
 a=c
 tempNextAddress = 結果[ 1 ]
それ以外：
 c<aの場合:
 a=c
 tempNextAddress = 結果[ 1 ]
 tempNextAddressを返す
#最も適切なパスを取得する 
 def getLeastCost( self 、 alreadyPass 、 sourceAddress 、 destAddress ):
 a=- 159判定=自己.tool.search(alreadyPass,sourceAddress)
判定がFalseの場合:
自己.tool.addItemInList(すでにパス、ソースアドレス)
アイテムの 自己.UI.routeInfo:
結果 = item.split( '*' )
 sourceAddress==result[ 0 ]の場合:
判断 =自己.tool.search(alreadyPass,結果[ 1 ])
判定がFalseの場合:
結果[ 1 ] == 宛先アドレスの場合:
 b = int(結果[ 2 ])
 b<aまたはa==- 1 の場合:
 a=b
それ以外：
 b = self .getLeastCost(alreadyPass,result[ 1 ],destAddress)
 c=b+int(結果[ 2 ])
 b!=- 1の場合:
 a == - 1 の場合 またはc<a:
 a=c
返す

さて、次にパス情報が変更になった場合にどうするかについて説明します。

パス情報が変更されました。簡単に言えば、ルーティングテーブル全体を削除して再計算します。これをルーティングテーブルの更新と呼びます。

パスが更新されると、コンピュータはどの部分が更新されたかを直接確認できず、どのポイントを計算することもできません。コンピュータは、すべてを再度確認する必要があります。確認したので、再計算しても違いがないため、すべて削除することができます。ルーティングテーブルを使用する場合、どの宛先に行きたいかを計算し、計算を保存します。次回必要になったときに、保存した情報にジャンプするだけです。必要ない場合は、無視します。このように、すべての宛先が一度に送信されていない場合は、パス情報が更新されます。使用されていない宛先はまったく計算されず、計算する必要もありません。これにより、コンピューターリソースを節約できます。

オリジナルリンク: http://www.cnblogs.com/kevinGuo/archive/2011/12/07/2278702.html

【編集者のおすすめ】