最適化アルゴリズムを使用してネットワーク内で最短経路を見つけるアルゴリズム

Question

私はアルゴリズム設計とグラフ理論の主題には新しいです。私は数千のルータで構成された大規模なコンテンツベースのネットワークをシミュレートしています。ルーティングのために「逆方向パスで学習する」を使用しています。要求されたコンテンツ名とコンテンツは、フラッディングを使用してネットワーク内に伝播されます。ルーターは、ルーティングテーブル内の一致する名前を確認し、一致しない要求されたコンテンツ名と内容でルーティングテーブルに返信またはポピュレートします。アリのコロニー最適化、ヒルクライミングなどのような最適化アルゴリズムを使用すると、逆の経路で学習する代わりに経路効率が向上するでしょうか？

Answer 1

グラフが三角不等式を満たしている場合、つまり真理空間であるならば、最適の3/2であることが保証されていますので、christofides近似アルゴリズムを使用することをお勧めします。アリコロニー最適化のような他の発見的アルゴリズムは非常に高速で効率的ですが、あまり安全ではありません。アリコロニーの最適化（およびブルートフォースとdpソリューション）の良い例は、javascriptのGoogleマップtspソルバーです。私は空間充填曲線も良い近似であると確信しています。 zカーブまたはヒルベルトカーブを調べることができます。ヒルベルト曲線についての良い記事は、Nick spatial index quadtree hilbert curve blogまたは書籍「Hacker's delight」を参照してください。私は、単調n-aryグレイコードとハミルトニアンパスの構築について調べることをお勧めします。