3

問題の背景

私は現在、AntColonySystemアルゴリズムのフレームワークを開発しています。私は、彼らが適用された最初の問題である巡回セールスマン問題（TSP）でそれらを試すことから始めようと思いました。タスクにはC＃を使用します。

すべてのTSPインスタンスは、各エッジに関連付けられた2つの異なる重みを持つ完全な無向グラフで構成されます。

質問

これまで、隣接リスト表現のみを使用してきましたが、それらはまばらなグラフにのみ推奨されることを読みました。私はデータ構造に関して最も知識のある人ではないので、無向の完全グラフを実装するための最も効率的な方法は何でしょうか？

必要に応じて、追加の詳細を提供できます。

お時間をいただきありがとうございます。

アップデート

重量の明確化。各エッジには、次の2つの値が関連付けられます。

  1. 2つの都市間の距離（d（i、j）= d（j、i）両方向に同じ距離）
  2. その特定の端にアリによって沈着したフェロモンの量

オペレーション。グラフで実行する操作の簡単な要約：

  • 各ノードについて、その特定のノードのアリは、すべての入射エッジに関連付けられた値を反復処理する必要があります

問題の明確化

アリコロニー最適化アルゴリズムは、TSPが最初に適用された場所であるため、TSPを「解決」できます。「解決」とは、メタヒューリスティック最適化と呼ばれるアルゴリズムファミリーの一部であり、最適な解決策を返すことを保証するものではないためです。

当面の問題について：

  • 各アリは記憶を持っているので、アリはツアーを完了する方法を知っています。
  • アリが都市を訪れるたびに、その都市を記憶に保存します。
  • アリが新しい都市への訪問を検討するたびに、アリはその記憶を検索し、そのエッジがすでに訪問した都市に到達しない場合にのみ、発信エッジを選択します。
  • アリが選択できるエッジがなくなると、ツアーが完了します。この時点で、アリが作成したツアーを、その記憶をさかのぼって遡ることができます。

研究記事の詳細：アリの巣システムの記事

効率に関する考慮事項

メモリよりも実行時間（速度）の方が気になります。

4

2 に答える 2

2

まず、隣接リストと行列の一般的なガイドがここにあります。 ただし、これは非常に低レベルで具体的ではない議論であるため、まだ知らないことは何も教えてくれないかもしれません.

要点は次のとおりです。「ノード i とノード j の間のエッジの距離またはフェロモン レベルを正確に知る必要がある」という質問に答える必要があることがよくある場合は、おそらく行列形式が必要です。 、その質問は O(1) 時間で回答できるためです。

ノードに隣接するエッジを反復処理する必要があると言及していますが、ここで巧妙さと繊細さが必要になる場合があります。反復の順序を気にしない場合は、データ構造を気にしません。順序に深く関心があり、前もって順序を知っていて、それが決して変わらない場合は、おそらくこれを隣接リストに直接コーディングできます。たとえば、フェロモンの濃度を最大または最小にしたい場合は、優先キューなど、さらに構造化されたものを試してみてください。それは本当にあなたがしている操作の種類に依存します。

最後に、メモリよりも速度に関心があるとおっしゃっていますが、使用するグラフ表現の数は明確ではありません。1つだけなら、本当に気にしません。しかし、各アリがグラフの独自の表現を作成している場合、思った以上に気にするかもしれません。隣接リストを使用すると、不完全なグラフ表現を持ち運ぶことができます。その反面、アリが最前線を探索しているときは、表現を構築するのに時間がかかるということです。

最後に、完全なグラフと TSP を扱っているとおっしゃっていることは承知していますが、これらのルーチンをおそらくグラフ上の他の問題に適応させる必要があるかどうか、もしそうなら どうするかについて考える価値はあります。

私は隣接リストやさらに多くの構造に傾倒していますが、クリーンで鮮明な答えが見つかるとは思いません。

于 2012-06-18T17:16:45.843 に答える
1

あなたは完全なグラフを持っているので、最良の表現は2D配列になると思います。

public class Edge
{
//change types as appropriate
  public int Distance {get;set;}
  public int Pheromone {get;set;}
}


int numNodes;
Edge[,] graph = new Edge[numNodes,numNodes];
for(int i = 0; i < numNodes; i++)
{
  for(int j = 0; j < numNodes; j++)
  {
    graph[i][j] = new Edge();
    //initialize Edge
  }
}

多くのノードがあり、このグラフのインデックスでノードを「覚えていない」場合は、aNodeをグラフのインデックスにマップするディクショナリがあると便利な場合があります。また、逆ルックアップを使用することも役立つ場合があります (ここでは aListが適切なデータ構造です。これにより、ノードのインデックスに基づいて Node オブジェクトを取得できます (各ノードについて多くの情報を保存する必要がある場合)。グラフ内のそのノード。

于 2012-06-08T15:55:29.230 に答える