[アーティクル]
08/19/2015

この記事は機械翻訳されたものです。

テストの実行

タブーアルゴリズムと最大クリーク (機械翻訳)

James McCaffrey 今月のコラムでは、グラフの最大クリーク問題に高度なソリューションを紹介します。どのようなタブーのアルゴリズムと呼ばれるソリューションを使用し、設計およびこれらのアルゴリズムをテストする方法について説明します。最大クリーク問題のアイデアは、すべてが互いに接続されているグラフのノードの最大のグループを見つけることです。図 1 に、簡単なグラフを見てください。グラフには、9 ノードと 13 のエッジがあります。グラフは、加重ではない (端を関連付けられている優先順位がない) および無向 (すべてのエッジは双方向です)。ノード 2、4 および 5 はサイズの 3 つの派閥を形成します。最大クリーク、ノード 0、1、3、4、サイズ 4 のクリークのフォームです。

Graph for a Tabu Maximum Clique Algorithm
1 グラフはタブー最大クリーク抽出アルゴリズムの図します。

最大クリーク問題のいくつかの理由は、興味深いものです。それは、簡単なグラフから明らかではないが図 1、最大クリーク問題のコンピューター科学で最もチャレンジングな 1 つです。それは多く重要な実用的な問題は人々のノードを表すメッセージまたは関係のエッジを表す社会ネットワーク通信解析などで発生します。貪欲アルゴリズムなどの技術問題を使用して重要なタブーのアルゴリズムは、高度なプログラミングテクニック。あなた個人のライブラリで最大クリーク問題への解決策を持つ実用的な役に立つツールをすることができます、使用するアルゴリズムを理解する新しい技術はあなたの技術セットを追加できます。

これは、3 番目の列を使用して高度なコーディングとテスト技法しますが、この列を説明するために、最大クリーク問題を直接参照せずに前の 2 つ読み取れることシリーズです。 10 月のコラム、」グラフ構造と最大派閥」(msdn.microsoft.com/magazine/hh456397)、私はグラフデータ構造をメモリに保持するための効率的なデータ構造をコーディングする方法を説明します。 11 月のコラム、「貪欲アルゴリズムと最大派閥」(msdn.microsoft.com/magazine/hh547104）、比較的単純なアルゴリズムを使用して難しい最大クリーク問題への解決策を見つけることができます記載されて。

非公式の用語では、貪欲アルゴリズムは、単純な不完全な問題を解決するは困難を開始し、繰り返しソリューションを改善するために最善の方法を探しますアルゴリズムです。いくつかの停止の状態に到達するまでこのプロセスが繰り返されます。どのようにまで、貪欲アルゴリズムは通常に欠点がある:、繰り返し繰り返し、同じソリューションが生成されます。タブーのアルゴリズムは、この弱点に対処する設計されています。 Word のタブーは、時々タブー、禁じられて意味を綴った。簡単な言葉で、タブーアルゴリズム、禁止されたデータの一覧を維持します。アルゴリズムの処理の一部は、いくつかの時間を禁止するまでデータを過ぎたタブーを使用する許可されていません。簡単な利用形態をタブーアルゴリズム、固定時間を禁止します。高度なタブーアルゴリズム、アルゴリズムを実行中禁止時間を動的に適応します。

図 2 最大クリーク問題への適用はタブーアルゴリズムの重要なアイデアを示していて、この列の内容を示しています。

Tabu Maximum Clique Demo Run
図 2 タブー最大クリークデモの実行

私は、1 つのように対応するグラフをメモリに読み込むを開始するコンソールアプリケーションがある図 1。ファイルは、DIMACS と呼ばれる標準のグラフのファイル形式を使用します。デザインとコーディングの効率のグラフデータ構造自体は重要な問題です。私は私の 10 月のコラムでグラフのデータ構造体のコードを説明しました。

アルゴリズムによってランダムに 1 つのノードを選択して、クリーク、ノードの初期化を開始します。アルゴリズム、繰り返しを見つけるし、クリークのサイズが増加する、最適なノードを追加しようとします。私は、後で最適なノードを意味を説明します。アルゴリズムを追加するノードを見つけることができない場合は、クリークからを削除するのには、最適なノードを検索しようとします。内部的には、アルゴリズムは最後の時間は各ノードは現在のソリューションのクリークに移動または、派閥から外に移動に覚えています。アルゴリズムでこの情報を使用しての追加を禁止するまたは最近削除ノードが一定の時間を使用します。これは、アルゴリズムのタブーの一部です。

しょっちゅう進捗状況が良い (より大きい) クリークで行われていない場合、アルゴリズム自体が再起動します。アルゴリズムはサイレントモードで以前見ているソリューション (派閥) を格納します。アルゴリズムでは、ソリューション履歴情報を使用して禁止時間を動的に適応します。アルゴリズムが、同じソリューションが発生を保持する場合は、使用されてから最近使用されたノードを阻止するために、禁止する時間が長くなります。アルゴリズムは、同じソリューションを参照してくださいしない場合より大きなプールノードを選択するの禁止時間が減少します。これはタブーアルゴリズムの適応の一部です。

1 つ以上の停止条件を指定する必要がありますので、貪欲アルゴリズムが使用されている、ほとんどの状況で最適なソリューション、不明です。アルゴリズムは停止状態に達するが、最善の解決策が表示されます。

以下のセクションでは、私はあなたのスクリーンショットを生成するコード歩くよ図 2。完全なソースコードは code.msdn.microsoft.com/mag201112TestRun。この列は、中間レベルのプログラミングスキル C 家族言語または Visual Basic が必要です。NET 言語。 C# の場合は、使用しますが、場合、F # または Python など別の言語も非常に苦労せずにリファクタリングすることができますので、私は、コードを書いています。

プログラムの全体的な構造

示すように、プログラムの全体構造図 2 で図 3。わかりやすくするため、静的メソッドを使用して、1 つのコンソールアプリケーションでのすべてのコードを配置することを決めたが、クラスライブラリに、コードの部分をモジュール化して、オブジェクト指向のアプローチを使用する必要があります。プログラムを見て疑いがあるかもしれないよりも少ない複雑です図 3 ほとんどの方法の短いヘルパーメソッドであるため。

図 3 の全体のプログラムの構造

using System;
using System.Collections.Generic; // List<int>
using System.Text; // StringBuilder
using System.IO; // FileStream
using System.Collections; // Hashtable
namespace TabuMaxClique
{
  class TabuMaxCliqueProgram
  {
    static Random random = null;
    static void Main(string[] args) { ...
}
    static List<int> FindMaxClique(MyGraph graph, int maxTime,
      int targetCliqueSize) { ...  }
    static List<int> MakePossibleAdd(MyGraph graph,
      List<int> clique) { ...
}
    static bool FormsALargerClique(MyGraph graph,
      List<int> clique, int node) { ...
}
    static int GetNodeToAdd(MyGraph graph,
      List<int> allowedAdd, List<int> possibleAdd) { ...
}
    static int GetNodeToDrop(MyGraph graph, List<int> clique,
      List<int> oneMissing) { ...
}
    static List<int> MakeOneMissing(MyGraph graph,
      List<int> clique) { ...
}
    static List<int> SelectAllowedNodes(List<int> listOfNodes,
      int time, int prohibitPeriod, int[] lastMoved) { ...
}
    static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
      int bestSize, Hashtable history, int time, int prohibitPeriod,
      ref int timeProhibitChanged) { ...
}
    static string ListAsString(List<int> list) { ...
}
    private class CliqueInfo
    {
      // ...
}
  }
  public class MyGraph
  {
    // ...
private class BitMatrix
    {
      // ...
}
  }
} // ns

プログラム 2 つの高度なクラスと各これらのクラスのヘルパーサブクラスをしています。クラス TabuMaxCliqueProgram には、Main メソッドとサブクラス CliqueInfo は、以前見たクリークソリューションの履歴を維持するために使用されると共に、すべてのアルゴリズムロジックが含まれます。クラス MyGraph は、効率的なグラフ表現をカプセル化し、サブクラス BitMatrix は、隣接性情報ノードは凝縮形式で格納するために使用が含まれています。名前、クラススコープの Random オブジェクトランダム、ランダムなノードにクリークを初期化するがある場合を追加または削除する複数の最適なノードに使用です。

いくつかの WriteLine ステートメントと try catch コードの削除では、Main メソッドです。

Console.WriteLine("\nBegin tabu algorithm maximum clique demo\n");
string graphFile = "..
\\..
\\DimacsGraph.clq";
MyGraph graph = new MyGraph(graphFile, "DIMACS");
int maxTime = 50;
int targetCliqueSize = graph.NumberNodes;
List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
Console.WriteLine("\nSize of best clique found = " + maxClique.Count);
Console.WriteLine(ListAsString(maxClique));

グラフは、プログラム定義の MyGraph オブジェクトとして表されます。グラフは、DIMACS ファイルの形式を使用して、外部のテキストファイルから読み込まれます。 MyGraph の主要なメソッドは、AreAdjacent は、2 つのノードが接続されている場合に true です。私は maxTime 貪欲アルゴリズムは絶対停止条件を確立するために 50 のイテレーションを設定します。これは人工的に小さいです。通常実際最大クリーク問題では、最大時間は 1,000 に 100,000 の範囲内です。 2 番目の停止条件を確立するために targetClique のサイズを設定; クリークのグラフでは、同じ数のノードが見つかった場合は、最大の派閥が発見されている必要があります。ほとんどの作業は、貪欲、適応のタブーアルゴリズムを使用して、最大の可能なクリークを検索するには、FindMaxClique メソッドによって行われます。ヘルパーメソッド ListAsString が単に <int> リストの文字列表現を作成します。オブジェクト。

FindMaxClique メソッド

FindMaxClique メソッドは、説明しますいくつかのヘルパーメソッドを呼び出します。高レベルの擬似コードでは、FindMaxClique アルゴリズムで指定した図 4。擬似コードは、わかりやすくするためのいくつかの重要な詳細を葉しますが、アルゴリズムの要点を示します。

図 4 適応タブー最大クリーク抽出アルゴリズム

initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
  if there are nodes which can be added
    get list of allowed nodes
    if there are allowed nodes to add
      find best node to add and add to clique
      mark added node as recently used
      record current clique
 else
   get list of allowed nodes to drop
   if there are allowed nodes which can be dropped
     find best node to drop and drop from clique
     mark dropped node as recently used
     record current clique
 else
   select a random node to drop and drop from clique
   mark dropped node as recently used
   record current clique
 if lack of progress
   restart algorithm
  update list of candidate nodes
  update prohibit time
end loop
return largest clique found
The FindMaxClique method definition begins:
static List<int> FindMaxClique(MyGraph graph, int maxTime,
  int targetCliqueSize)
{
  List<int> clique = new List<int>();
  random = new Random(1);
  int time = 0;
  int timeBestClique = 0;
  int timeRestart = 0;
  int nodeToAdd = -1;
  int nodeToDrop = -1;
...

ローカルクリークオブジェクトは、現在のソリューションのクリークです。ランダムなオブジェクトは、1 の任意のシード値をインスタンス化されます。時間変数、アルゴリズムのメインの処理ループのカウンターです。 TimeBestClique と timeRestart 変数が不足しているかどうかは、進行中のアルゴリズム自体を再起動することができますのでを決定に使用されます。進む :

int prohibitPeriod = 1;
int timeProhibitChanged = 0;
int[] lastMoved = new int[graph.NumberNodes];
for (int i = 0; i < lastMoved.Length; ++i) {
  lastMoved[i] = int.MinValue;
}
Hashtable history = new Hashtable();
...

禁止期間は、1 に初期化されます。つまり、— 最初に、少なくとも — ノードは、アルゴリズムで使用されています。後は、1 つの時間のイテレーションを使用できません。 0 の値を使用していた場合は、効果なしの時間をすべて禁止するでしょう。研究が最高の価値を固定禁止時間を問題から問題に変化を示しているとそのアプローチを用いる問題を禁止するには固定値ほとんどタブーのアルゴリズムを使用が。アルゴリズムの実行中は更新を禁止する時間を提示、適応手法前のソリューションの歴史に。私はこの手法の適応のタブーを呼び出すが反応性または動的手法いくつかの研究論文を呼び出します。

LastMoved 配列を使用して、ノードの許可または任意の時点で禁止されているかどうかを確認します。配列のインデックスを表すノード、および配列の対応する値 (追加または削除) に、ノードが移動された最終時間です。 LastMoved 配列を使用して、明示的に許可されているノードの一覧を作成する必要が排除する (または、同等、禁止のノード)。私は lastMoved に int 型のすべてのセルを初期化します。私は後で場合は、ノードを特定できるように MinValue を決して使用されています。

歴史の Hashtable オブジェクトは、以前見たソリューション派閥のコレクションを保持します。ハッシュテーブル内の各項目は後で詳細に説明する CliqueInfo オブジェクトです。私は、非ジェネリックの Hashtable オブジェクトの代わりに、汎用の Dictionary オブジェクトを使用した可能性があります。 FindMaxClique を続けています。

int randomNode = random.Next(0, graph.NumberNodes);
clique.Add(randomNode);
List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...

ランダムノードに、グラフから、現在のソリューションの派閥を初期化します。アルゴリズムによって最高 (最大) クリーク解を追跡するには、bestClique リストのインスタンスを作成します。次は来る。

List<int> possibleAdd = MakePossibleAdd(graph, clique);
List<int> oneMissing = MakeOneMissing(graph, clique);
...

MakePossibleAdd メソッドは、クリークのサイズを大きくには、現在のクリークに 1 が追加できるすべてのノードのリストを構築します。他の言葉では、メソッドのクリークではないが、クリークでのすべてのノードに接続されているノードの一覧を作成します。この possibleAdd リストの 0 の数がある可能性があるまたは禁止されているノードを含めることができます。 MakePossibleAdd は、ヘルパーメソッド FormsALargerClique を呼び出します。

MakeOneMissing メソッドは、すべて 1 つの現在のクリークでノードが接続されているすべてのノードの一覧を構築します。それは明らかではないが、このようなリストを維持私は後で説明する、ノードには、現在クリークを削除するには、最高のノードが決定する巧妙な方法を作成ことが判明します。メインの処理ループを開始します。

while (time < maxTime && bestSize < targetCliqueSize)
{
  ++time;
  bool cliqueChanged = false;
...

メインの処理ループのイテレーションの最大数に達したとき、またはターゲットクリークサイズの最善の解決策が見つかった場合は終了します。 CliqueChanged 変数を使用して、あなたが表示されます、追加とノードを削除すると、分岐ロジックを制御します。許可のノードを追加するには、ロジックが表示されます図 5。

図 5 は許可されたノードを追加するロジック

if (possibleAdd.Count > 0) {
  List<int> allowedAdd = SelectAllowedNodes(possibleAdd, time,
    prohibitPeriod, lastMoved);
  if (allowedAdd.Count > 0) {
    nodeToAdd = GetNodeToAdd(graph, allowedAdd, possibleAdd);
    clique.Add(nodeToAdd);
    lastMoved[nodeToAdd] = time;
    clique.Sort();  cliqueChanged = true;
    if (clique.Count > bestSize) {
      bestSize = clique.Count;
      bestClique.Clear();
      bestClique.AddRange(clique);
      timeBestClique = time;
    }
  }
}

アルゴリズムは、現在のクリークのサイズが増加するすべてのノードがあるかどうかを調べます。したがって、メソッド SelectAllowedNodes を許可されているノードの一覧作成かどうか — は、ない tabu — 追加できるノードの一覧から。

キーの行 SelectAllowedNodes のです。

if (time > lastMoved[currNode] + prohibitPeriod)
  result.Add(currNode); // Allowed

CurrNode possibleAdd リスト内のノードの 1 つです。ロジックは、ノードを禁止する期間を過ぎている、ノードが最後に使用された十分な時間 elaspsed 以来かどうかを調べます。場合は、ノードの allowedAdd ノードの一覧に追加されます。

今、メソッドが許可されているし、クリークのサイズが増加するすべてのノードがある場合にクリークを追加するには、最高のノードも GetNodeToAdd が決定します。最高のノードはノードな allowedAdd リストからです possibleAdd リスト内のノードに接続します。アイデアは、アルゴリズムの次の反復処理に追加するノードを見つけることのほとんどチャンスを与えるが、ノードを追加することです。最も possibleAdd 内のノードに接続が関連付けられている allowedAdd リスト内の複数のノードがあります。場合は、タイのノードの 1 つがランダムに選択されます。最高のノードを追加した後、現在のクリークソリューション私は後で説明する理由のために並べ替えられます。ノードを削除するコードです。

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    List<int> allowedInClique = SelectAllowedNodes(clique, time,
      prohibitPeriod, lastMoved);
    if (allowedInClique.Count > 0) {
      nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
      clique.Remove(nodeToDrop);
      lastMoved[nodeToDrop] = time;
      clique.Sort();  cliqueChanged = true;
    }
  }
}
...

アルゴリズム、ノードを追加できない場合は、バックトラックは、次の反復処理に追加する新しいノードはソリューションを得られると期待を許可されているノードを削除しようとします。現在のクリークでのノードの一覧はタブーされていないノードを取得するには、SelectAllowedNodes メソッドによってフィルター処理されます。 GetNodeToDrop の最高の oneMissing ノードの一覧を使用してを削除するのにはこれらのノードを選択します。

PossibleAdd ノードの一覧で最大の増加になります現在のクリークは、許可されたノードにドロップする勧めします。これを行う方法の 1 つは実際には、現在の派閥から削除して、結果の possibleAdd リストのサイズを計算、許可リストに各ノードをテストすることです。すべて 1 つの現在のクリークでノードが接続されているノードの一覧を使用して、はるかに効率的なアプローチです。ノードの oneMissing リスト、リストは次のとおり使用できます。許可されたクリークノード内の各ノードをスキャンし、oneMissing リストのノードの数を notconnected クリークノードにはカウントします。最低許容クリークリスト内のノードのノードに接続、oneMissing のリストをドロップするのに最適なノードです。この最小接続のノードをドロップ、ドロップのノードに接続されていない、oneMissing リスト内のすべてのノード今完全にクリークでの残りのノードに接続され、possibleAdd の新しいノードをそのために。

この時点で、ロジックでは、それが許可されているノードを追加または、許可されているノードを削除することが可能でしょう。自体を unstick するには、アルゴリズムでは、現在の派閥から、ランダムなノードを削除します。

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    nodeToDrop = clique[random.Next(0, clique.Count)];
    clique.Remove(nodeToDrop);
    lastMoved[nodeToDrop] = time;
    clique.Sort();
    cliqueChanged = true;
  }
}
...

次に、進歩の欠如されている場合、その場合を参照してくださいするアルゴリズムチェック自体再起動します。

int restart = 100 * bestSize;
if (time - timeBestClique > restart && time - timeRestart > restart) {
  timeRestart = time;
  prohibitPeriod = 1;
  timeProhibitChanged = time;
  history.Clear();
...

再起動の変数は、改善がない、または最後の再起動以降を許可する回数です。ここで、現在のベストソリューションサイズの 100 倍の値を使用します。再起動間隔のために使用する値がよく理解されていないし、代替しようとする可能性があります。 (私はダミーの値を 2 以上の再起動でスクリーンショットを生成するために使用図 2)。私は使用する値も私の実践、しかしきました。再起動する場合は、アルゴリズム禁止時間をリセットし、見られているソリューション派閥を保持する歴史のハッシュテーブルを消去します。アルゴリズムがまだ歴史のハッシュテーブルを更新していないことに注意してください。再起動コードただし、ときノードいた最後に追加またはソリューションクリークから削除に関する情報を格納、lastVisited 配列をリセットしません。次は来る。

int seedNode = -1;
List<int> temp = new List<int>();
for (int i = 0; i < lastMoved.Length; ++i) {
  if (lastMoved[i] == int.MinValue) temp.Add(i);
}
if (temp.Count > 0)
  seedNode = temp[random.Next(0, temp.Count)];
else
  seedNode = random.Next(0, graph.NumberNodes);
...

ソリューションクリーク決して前に使用されています。ノードを再シードするにはアルゴリズムを試みます。いくつかの未使用のノードがある場合は、1 つがランダムに選択されます。未使用のノードがない場合は、ランダムなノードが選択されます。ランダムなノードを使用するのではなく、未踏の代替少なくとも最近移動されたノードを選択します。再起動コードは次の終了します。

...
clique.Clear();
  clique.Add(seedNode);
}

FindMaxClique ラップを開設する、メイン処理ループのように。

...
possibleAdd = MakePossibleAdd(graph, clique);
    oneMissing = MakeOneMissing(graph, clique);
    prohibitPeriod = UpdateProhibitPeriod(graph, clique, bestSize,
      history, time, prohibitPeriod, ref timeProhibitChanged);
  } // Main processing loop
  return bestClique;
}

PossibleAdd と oneMissing のリストが再生成されます。代替補助データ構造を維持し、それらをゼロから再作成するのではなくこれら 2 つのリストを更新することです。 UpdateProhibitPeriod メソッドはタブーアルゴリズムの適応の一部の重要なコンポーネントであり、私はすぐに説明します。

以前のソリューションを思い出し

メソッド UpdateProhibitPeriod では、以前に見られるソリューションのハッシュテーブルを使用して動的に増減が禁止します。ソリューションに示します <int> クリークであることを思い出してください。ノードはすべて互いに接続されます。しかし、私も、ソリューションが最後に見られた時刻を格納する必要があります。したがって、クリークソリューションをカプセル化して、最後の時間それ見られた CliqueInfo のクラスとして図 6。

図 6 CliqueInfo クラス

private class CliqueInfo
{
  private List<int> clique;
  private int lastSeen;
  public CliqueInfo(List<int> clique, int lastSeen)
  {
    this.clique = new List<int>();
    this.clique.AddRange(clique);
    this.lastSeen = lastSeen;
  }
  public int LastSeen
  {
    get { return this.lastSeen; }
    set { this.lastSeen = value; }
  }
  public override int GetHashCode()
  {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < clique.Count; ++i) {
      sb.Append(clique[i]);
      sb.Append(" ");
    }
    string s = sb.ToString();
    return s.GetHashCode();
  }
  public override string ToString()
  {
    string s = "";
    for (int i = 0; i < clique.Count; ++i)
      s += clique[i] + " ";
      return s;
  }
}

CliqueInfo 項目をソリューション履歴 Hashtable オブジェクトに追加されるため、カスタムの GetHashCode ハッシュ関数が必要であるがあります。カスタムハッシュ関数を書いては驚くほど込み入っています、全体の列に関するすべての問題を徹底的に検討が必要になります。この状況では、私は、最も単純な使用 — しますが、ない、最も効率的な — のアプローチ。スペースで区切られたクリーク分野では、ノードの文字列表現を作成し、組み込みの String.GetHashCode を使用します。たとえば、ノード、クリークを含まれる場合 {3 5 8}、生成する「3 5 8」 (空白) をし、その文字列からハッシュコードを生成します。それは 1 つの派閥があることではないので派閥は常に、並べ替えられた順序で維持をリコール {3 5 8} と別の派閥 {8 3 5}。私は clique ので、ノードの間にスペースを配置 {3 5 8} {3 58} クリークから区別されます。

更新の期間を禁止します。

メソッド UpdateProhibitPeriod 適応増加または以前見たクリークのソリューションに基づいて禁止時間が減少します。このメソッドを開始します。

static int UpdateProhibitPeriod(MyGraph graph, List<int> clique,
  int bestSize, Hashtable history, int time, int prohibitPeriod,
  ref int timeProhibitChanged)
{
  int result = prohibitPeriod;
  CliqueInfo cliqueInfo = new CliqueInfo(clique, time);
.
.
.

メソッドが、現在の禁止時間と同じになることを禁止する時間が返されます。現在クリークと現在の時刻を保持して、CliqueInfo オブジェクトはインスタンス、次のよう。

if (history.Contains(cliqueInfo.GetHashCode())) {
  CliqueInfo ci = (CliqueInfo)history[cliqueInfo.GetHashCode
  int intervalSinceLastVisit = time - ci.LastSeen;
  ci.LastSeen = time;
  if (intervalSinceLastVisit < 2 * graph.NumberNodes - 1) {
    timeProhibitChanged = time;
    if (prohibitPeriod + 1 < 2 * bestSize) return prohibitPeriod + 1;
    else return 2 * bestSize;
  }
}
else history.Add(cliqueInfo.GetHashCode(), cliqueInfo);
...

コードを確認する前に、CliqueInfo オブジェクトの形式で、現在のクリークソリューションが見られているかどうかします — 歴史ハッシュテーブルのクリークですか？現在のクリークの前に見られている場合は、クリークを見てどのくらいの時間それ以来、アルゴリズムを計算します。この間隔が短い場合は、禁止時間 (上限に) インクリメントされます。このアイデアは、現在の派閥を見たので非常に長くされていないため、アルゴリズム重複するソリューション生成していることです。禁止時間を増加した場合より多くのタブーのノードがある、したがって少ないノード、重複クリークソリューションを生成する可能性を低減できます。現在のクリークソリューションを前に見たされていない場合は、それが歴史のハッシュテーブルに追加されます。

「十分な短い「間隔は、以下 1 つのグラフ内のノード数が 2 倍です。これは、禁止時間に加算するタイミングを決定する使用されます。ここで使用する最高値最大クリーク抽出の研究の別の未解決の問題です。「上限」禁止時間は、サイズの 2 倍現在の最も有名なソリューションです。最高の上限値は、おそらく今では、別のオープンな研究の質問を推測することができますです。

この時点では、いずれか、現在クリーク前に見たされていないクリーク前に見られているが禁止時間に加算するために必要な間隔の大きさではなかった。したがって、アルゴリズム今禁止期間タブーノードの数を減らすし、順番に複数のノードを追加または削除する、アルゴリズムを与える許可されるノードの数を増やすが減少することができるかどうか確認します。

...
if (time - timeProhibitChanged > 10 * bestSize) {
    timeProhibitChanged = time;
    if (prohibitPeriod - 1 > 1)
      return prohibitPeriod - 1;
    else
      return 1;
  }
  else {
    return result; // no change
  }
} // UpdateProhibitTime

明示的に現在の派閥を見た"比較的"久しぶり以来かどうか確認するではなく、アルゴリズム直接禁止期間が最後に変更された時刻を調べることによって現在の派閥を見てどのくらいの時間以来、確認します。もう一度、最高の価値を「比較的長い」は明確に理解されていません。現在の最適なソリューションの 10 倍のサイズの値を使用します。禁止時間 1 以下をドロップできないことに注意してください。

多くの研究

最大クリーク問題研究結果は、パフォーマンスおよびソリューション品質の両方を考慮すると、貪欲なアプローチ、適応タブー機能を最高の全体的な結果を与えることをお勧めします。 DIMACS 難しいグラフクリークベンチマーク問題のセットを作成する研究組織です。ここ DIMACS、特に難しい問題 (C2000.9) と、コードすばやく (2 秒未満)、クリークの 77 の最も有名なソリューションのサイズの 1.5% 以内であるサイズ 76 が見つかりましたに対して提示するコードを実行します。

いくつかのポイントで、この列は、私は研究結果、最大クリーク問題に言及しました。この研究に興味があるなら、次によって書かれた論文のための Web 検索をお勧め: r. Battiti ら、w. Pullan ら。 k. 片山ら。これら 3 つの著者とその同僚のいくつかの論文は私のプライマリ参照されました。

有望な未踏領域ここで発表した最大クリーク抽出アルゴリズムの高原の検索と呼ばれるもののいくつかのフォームを組み込むことです。最大クリーク抽出アルゴリズム最初非タブーノードを現在のクリークのソリューションに追加しようことを思い出してください。それは可能ではない場合は、アルゴリズムが現在クリークソリューションからノードを削除します。高原の検索のアイデアクリークではなくノードを交換することができます現在のクリークソリューションで 1 つのノードを見つけることです。この現在のクリークのサイズを増加しないが、それのクリークでは、いずれかサイズ doesn't。

Dr.James McCaffrey作品は Volt Information Sciences Inc.、ここで彼は管理技術ソフトウェアエンジニアトレーニングを働いて、Microsoft ワシントン州レドモンドキャンパス。彼は、Internet Explorer、MSN サーチなど、いくつかの Microsoft 製品で働いています。博士。 McCaffrey の著者である」。NET Test Automation Recipes」』 (Apress、2006年）と達することができる jammc@microsoft.com。

この記事のレビュー、次の技術的な専門家に感謝： Paul Koch、 Dan Liebling、 Ann Loomis Thompson と Shane Williams