測試回合

發行項
07/23/2015

窮盡演算法與最大團

詹姆斯 McCaffrey

在本月的專欄中，我將提供圖表的最大 clique 問題的解決方案。方案使用了稱為窮盡的演算法，並且要探討如何設計和測試這些演算法。最大 clique 問題的概念是要連線至另一個圖形中尋找節點的最大的群組。請看一下簡單的圖形，在圖 1。圖形有九個節點和 13 的邊緣。圖表] 是 unweighted (有無邊緣相關聯的優先順序) 和 undirected (所有邊緣都是雙向)。節點 2、 4 和 5 形成大小為 3 的 clique。最大的 clique 是 0、 1、 3 和 4，而形成四個大小的 clique 節點所設定。

圖 1 圖形窮盡的最大值 Clique 演算法

最大 clique 問題有趣的是幾個原因。雖然這不是明顯的簡單圖表中的圖 1，最大 clique 問題是最具挑戰性電腦科學中其中一個項目。在這類的社交網路通訊分析，其中節點代表人員，而邊緣代表訊息或關聯性的許多重要應用程式，它便會發生。和最大 clique 問題助方案窮盡的演算法，也就是為電腦科學領域的基本技巧。

非正式的說，窮盡演算法會是一種演算法，以簡單、不完整的解決方案，困難的問題來開頭，而再反覆查看有改進解決方案的最佳方式。處理程序會重複出現，某些停止條件為止。[圖 2 說明最大 clique 問題的重要的想法，並讓我討論方向，本文將告訴您。

[圖 2 窮盡的最大值 Clique 示範執行

我有一個主控台應用程式，首先會載入記憶體的對話方塊相對應顯示在圖表圖 1。設計與撰寫有效率的圖形資料結構是在本身是重大的問題。我會說明圖形資料結構的程式碼在 [我的上一篇專欄 (msdn.microsoft.com/magazine/hh456397)。演算法第一次定時，會選取單一節點，在這個案例的節點 2，而且會初始化具有該節點的 clique。接下來，演算法會尋找最佳的節點將新增至 clique。如果您參考圖 1，您會看到只有兩個節點 4 和 5，將會形成較大的 clique。我將說明最佳的節點代表的意義短時間內。

選取演算法，並會將節點加入 4 clique，clique 現在是 {2，4}。此時，圖表] 中，第 5，將會放大 clique，所以演算法選取 5] 節點，並將它加入至 clique 沒有只有一個節點。現在會增加大小的 clique 沒有節點可用。從 [希望可以加入新的、不同的節點，會讓進度 clique 演算法卸除的最佳的節點。同樣地，我解釋移轉「最佳」的途徑。從 clique，演算法會卸除節點 4。您可以藉由查看圖形中看到，還有沒有辦法進度。這種情況常會使用窮盡演算法，因此一定要有一個方法來獲得超出 dead-end 的解決方案。

演算法只追蹤多久之後已進行的進度，也就是 clique，以使用較大的發現。在一段時間沒有進度之後, 會重新啟動的演算法，本身。Clique 為清除狀態。這次演算法隨機挑選節點 3 做為初始的節點。使用相同的反覆程序來找出最佳的節點加入或卸除，演算法最後會探索 {0、 1、 3，4} 的最大的 clique。在大部分的問題，使用窮盡演算法的地方，無法識別的最佳化解決方案，所以演算法會繼續，直到符合某個停止條件為止。如此一來，演算法會設定為 20 次反覆運算後停止。此時，找到的最佳 clique 隨即出現。

在 [章節中，我將引導您完成的程式碼所產生的螢幕擷取畫面， 圖 2。完整原始程式碼位於 code.msdn.microsoft.com/mag201110TestRun (本篇文章中會使用相同的程式碼，從上個月)。本文假設您有中繼層級的程式設計技能與 c 家族語言或 vb.NET 的語言。我所使用的 C#，不過我倒是寫了程式碼，讓您可以重整成其他語言，而不需太大的困難，如果您想。

整個程式結構

所示的程式的整體結構圖 2 ] 所示圖 3。程式會對系統、 System.Collections.Generic (clique 表示為型別清單 <int>)、 System.IO (適用於從文字檔載入來源圖表) 和 System.Collections (程式定義的 MyGraph 類別會使用 BitArray 類別) 的命名空間中的相依性。重新命名的主要類別從 Visual Studio 範本產生的程式 GreedyMaxCliqueProgram 來使文字更明確。初始化並重新 clique 設定為 [隨機的節點，並中斷您的姓名，多個最佳節點加入或卸除時，我會使用名為「隨機」的類別範圍 Random 物件。

[圖 3 整體程式結構

using System;
using System.Collections.Generic;
using System.IO;
using System.Collections;
 
namespace GreedyMaxClique
{
  class GreedyMaxCliqueProgram
  {
    static Random random = null;
 
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin greedy maximum clique demo\n");
 
        string graphFile = "..
\\..
\\DimacsGraph.clq";
        Console.WriteLine("Loading graph into memory");
        Console.WriteLine("Graph loaded and validated\n");
        MyGraph graph = new MyGraph(graphFile, "DIMACS");
 
        int maxTime = 20;
        int targetCliqueSize = graph.NumberNodes;
 
        List<int> maxClique = FindMaxClique(graph, maxTime,
          targetCliqueSize);
        Console.WriteLine("\nMaximum time reached");
        Console.WriteLine("\nSize of best clique found = " +
          maxClique.Count);
 
        Console.WriteLine("\nBest clique found:");
        Console.WriteLine(ListAsString(maxClique));
 
        Console.WriteLine("\nEnd greedy maximum clique demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    } // Main
 
    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> possibleAdd)
    {
      // ...
}
 
    static int GetNodeToDrop(MyGraph graph, List<int> clique,
      List<int> oneMissing)
    {
      // ...
}
 
    static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
    {
      // ...
}
 
    static string ListAsString(List<int> list)
    {
      // ...
}
  } // class Program
 
  public class MyGraph
  {
    // ...
}
} // ns

程式定義的 MyGraph 物件是以圖形表示。圖形會載入來自外部的文字檔案中，會使用名為 DIMACS 的標準檔案格式。 MyGraph 的主要方法是 AreAdjacent，則傳回 true，如果兩個節點所連接。我將 maxTime 設定為 20，若要設定窮盡演算法絕對的停止條件。我設定 targetCliqueSize 來建立第二個的停止條件；如果找不到具有相同數目的節點的圖表] 中的 clique，最大的 clique 必須找到。

FindMaxClique 方法

所有的工作方式是 FindMaxClique，使用窮盡的演算法來搜尋的最大的可能 clique 的方法。 FindMaxClique 會呼叫數個 helper 方法，我將詳細說明。我架構程式使用靜態方法，但您可能想要重構程式碼，我在這裡提出完整物件導向的方法。 FindMaxClique 方法不斷重複運算直到其中兩個的停止條件符合，則會傳回找到的最佳 clique。則程式定義會包含內嵌的 MyGraph 類別，這是上個月的發行項的主旨。

在高層次的虛擬程式碼，FindMaxClique 演算法是：

initialize clique with a single node
get list of candidate nodes to add
loop until stop condition met
  if there are nodes that can be added
    find best node to add and add to clique
  else
    find best node to drop and drop from clique
 
  if lack of progress
    restart algorithm
 
  update list of candidate nodes
end loop
return largest clique found

FindMaxClique 方法定義開頭：

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;
...

本機的 clique 物件是目前的 clique。我將個體化 Random 物件使用任意的種子值為 1。時間的變數是迴圈計數器變數中。因為它是不連續的是很好的替代名稱「刻度」。我追蹤時找到目前的最佳 clique 及上次重新啟動，若要控制何時重新啟動將會發生的時間。我會將空值為-1 指派給新增節點和拖放節點的變數中：

int randomNode = random.Next(0, graph.NumberNodes);
Console.WriteLine("Adding node " + randomNode);
clique.Add(randomNode);
...

大於或等於 x，而且小於 y，Random.Next(x,y) 方法會傳回值。設定 x = 0，而 y = NumberNodes，將隨機節點中 0 到 8 (含)，如範例中的圖表：

List<int> bestClique = new List<int>();
bestClique.AddRange(clique);
int bestSize = bestClique.Count;
timeBestClique = time;
...

[BestClique] 清單用來追蹤此演算法的搜尋期間找到的最大 clique 的複本。我可以使用方便的 AddRange 方法來將項目複製到 bestClique 中目前的 clique。 BestSize 變數是用來以方便使用。 TimeBestClique 用來決定是否的演算法會重新啟動電腦：

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

MakePossibleAdd 的 helper 方法會檢查目前的 clique，並建構可以逐一加入至 clique 的單位來放大 clique 的所有節點的清單。這份清單是最佳的節點將新增至 clique 的對象的來源。 MakeOneMissing 的 helper 方法有一點技巧。方法會建構一份所有已連線至目前的 clique 中的某個節點的節點。如您所見，此 oneMissing 清單用來決定最佳的節點從 clique 中卸除。現在，我開始主要處理迴圈：

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

如同先前所解釋，窮盡演算法通常會需要一個以上的停止條件。此處如果超出最大反覆運算次數，或目前的 clique 的大小符合目標大小會終止迴圈。 CliqueChanged 變數用來控制分支邏輯之間加入節點拖放節點。我可以省略此變數並使用如果。.其他 控制結構，而不是個別的 如果。.然後陳述式，但如此一來，分支的控制變數的使用使程式碼都可以輕易地讀取及修改，請在 [我的看法：

if (possibleAdd.Count > 0) {
  nodeToAdd = GetNodeToAdd(graph, possibleAdd);
  Console.WriteLine("Adding node " + nodeToAdd);
  clique.Add(nodeToAdd);
  clique.Sort();
  cliqueChanged = true;
  if (clique.Count > bestSize) {
    bestSize = clique.Count;
    bestClique.Clear();
    bestClique.AddRange(clique);
  }
} // add
...

我會檢查以確定至少一個節點，可以加入至 clique，並接著呼叫 GetNodeToAdd 的 helper 方法。這個方法會掃描 possibleAdd 清單中的節點清單，並傳回最佳的節點，以新增 (我將說明 GetNodeToAdd 時，會出現狂承諾的說明「最佳」)。這個節點會加入至目前的 clique。此時我 clique，因為排序演算法中，稍後我需要搜尋 clique，而如果 clique 進行排序時，我還可以使用快速的二進位搜尋，而非線性搜尋。新的 clique 進行檢查以確定是否為較佳比目前的最佳 clique 的 (大)。

接下來要：

if (cliqueChanged == false) {
  if (clique.Count > 0) {
    nodeToDrop = GetNodeToDrop(graph, clique, oneMissing);
    Console.WriteLine("Dropping node " + nodeToDrop);
    clique.Remove(nodeToDrop);
    clique.Sort();
    cliqueChanged = true;
  }
} // drop
...

如果無法增加目前的 clique 的大小，演算法會嘗試從 clique 拖放節點。 Helper 方法 GetNodeToDrop 會選取最佳的節點，以從 clique 中卸除:

int restart = 2 * bestSize;
if (time - timeBestCliqueFound > restart &&
  time - timeLastRestart > restart) {
   Console.WriteLine("\nRestarting\n");
   timeLastRestart = time;
   int seedNode = random.Next(0, graph.NumberNodes);
   clique.Clear();
   Console.WriteLine("Adding node " + seedNode);
   clique.Add(seedNode);
} // restart
...

此時，演算法會檢查是否均有所不足的進度。重新啟動變數會決定多久等待重新啟動。在此我會使用目前的最佳 clique 兩倍大的值。在 [最大的 clique 值的參考資料，重新啟動的最佳值仍是開啟的問題。我在這裡所使用的值根據的實驗我所需進行幾個基準測試圖形問題。如果目錄不是缺乏中找出新的最佳解決方案的進度，或經過相當長的時間，從上次啟動，就會發生重新啟動電腦。若您重新啟動電腦，演算法將清除目前的 clique，然後再選擇從圖表] 中的所有節點的 [隨機的節點。請注意這是一種粗糙的方法。請參閱至示範在執行圖 2，您會看到上次重新啟動挑選初始的節點已被用作為第一個識別值種子節點：

...
possibleAdd = MakePossibleAdd(graph, clique);
    oneMissing = MakeOneMissing(graph, clique);
  } // loop
  return bestClique;
}

FindMaxClique 方法會重新計算根據新的 clique 的 possibleAdd 和 oneMissing 清單。當主要處理迴圈結束時，這個方法會傳回找到的最佳 clique。

加入最佳的節點

有兩個步驟，還是決定最佳的節點將新增至目前的 clique。首先，需要將放大目前的 clique 的所有節點的清單。其次，需要某種方式來判斷這些節點的哪一個是最佳的節點:

static List<int> MakePossibleAdd(MyGraph graph, List<int> clique)
{
  List<int> result = new List<int>();
  for (int i = 0; i < graph.NumberNodes; ++i) {
    if (FormsALargerClique(graph, clique, i) == true)
      result.Add(i);
  }
  return result;
}

透過圖表] 中的每個節點，掃描的 MakePossibleAdd 方法。正在檢查節點是否已連接到所有的節點，在目前的 clique 是由協助程式 FormsALargerClique，正在檢查節點是可能的「加入」節點，並聯結 (join) 結果清單。請注意，結果可能是空的清單，但絕對不會為空值：

static bool FormsALargerClique(MyGraph graph, List<int> clique, int node)
{
  for (int i = 0; i < clique.Count; ++i) {
    if (graph.AreAdjacent(clique[i], node) == false)
      return false;
  }
  return true;
}

FormsALargerClique 方法會比較依據目前的 clique 中的所有節點的一個節點。如果候選節點不相鄰，即使只有其中的 clique 中的節點，候選節點無法加入至目前的 clique。請注意當一個節點會比對本身，則 AreAdjacent 會傳回 false，因為在目前的 clique 節點將不會加入至 possibleAdd 節點的清單。

決定最佳的節點後面新增主要概念，就是從較多的 possibleAdd 節點清單中選取一個節點連接至 possibleAdd 集合中的所有其他節點。高度連接的節點會產生您要新增在演算法的下一個反覆項目節點的最大可能新的清單。

接下來要：

static int GetNodeToAdd(MyGraph graph, List<int> possibleAdd)
{
  if (possibleAdd.Count == 1)
    return possibleAdd[0];
...

GetNodeToAdd 方法會假設 [possibleAdd] 清單中有一個以上的節點。如果正好與其中一個節點，所必須是最佳的節點：

int maxDegree = 0;
for (int i = 0; i < possibleAdd.Count; ++i) {
  int currNode = possibleAdd[i];
  int degreeOfCurrentNode = 0;
  for (int j = 0; j < possibleAdd.Count; ++j) {
    int otherNode = possibleAdd[j];
    if (graph.AreAdjacent(currNode, otherNode) == true)
      ++degreeOfCurrentNode;
  }
  if (degreeOfCurrentNode > maxDegree)
    maxDegree = degreeOfCurrentNode;
}
...

可能有數個 possibleAdd 清單中的節點，並為最已連線到清單中的其他節點繫結與其他人。例如，假設在 [分析] 下的圖表] 是圖表中顯示圖 1 ，目前的 clique 都有的只是節點 0。 PossibleAdd 節點都 {1、 3，4}。節點 1 連接至兩個 possibleAdd 中的節點，還有，事實上，節點 3 和 4。因此初步的掃描是由以判斷可用連接的最大數目：

List<int> candidates = new List<int>();
for (int i = 0; i < possibleAdd.Count; ++i) {
  int currNode = possibleAdd[i];
  int degreeOfCurrentNode = 0;
  for (int j = 0; j < possibleAdd.Count; ++j) {
    int otherNode = possibleAdd[j];
    if (graph.AreAdjacent(currNode, otherNode) == true)
      ++degreeOfCurrentNode;
    }
    if (degreeOfCurrentNode == maxDegree)
      candidates.Add(currNode);
}
...

一旦知道連線的最大數目，演算法會重新掃瞄 [possibleAdd] 清單，並將每一節點中擁有最龐大的候選節點的連接清單的 possibleAdd。請注意無法以追蹤每個 possibleAdd 節點都有的連線數目的輔助資料存放區，以消除雙掃描：

...
return candidates[random.Next(0, candidates.Count)];
}

此時，候選清單都有一或多個最佳的節點，加入 clique。請注意候選項目必須有至少一個計數，因為 possibleAdd 清單都假設含有至少一個計數。演算法隨機選取其中一個候選節點，然後將它傳回。我可能已對檢查，以查看 [候選字清單的大小是否正確，以及如果是的話，傳回單一節點，在 [求職者中。

正在卸除最佳的節點

判斷最佳的節點，以從目前的 clique，是有點難以捉摸。其概念是要卸除的 possibleAdd 節點清單中最大的增加，將會導致目前 clique 中的一個節點。

若要執行這項操作的方法之一是要測試每個節點目前的 clique 中實際移除它從目前的 clique，並接著計算所產生的 possibleAdd 清單的大小。但是還有更有效率的方法所使用的已連線至除了只有其中一個目前的 clique 中的節點的節點清單。如果沒有這種 oneMissing 的節點清單，清單可用，如下所示：審視目前的 clique 中的每個節點，並計算 oneMissing 清單中的幾個節點未連線到 [clique] 節點。最少連線的 [oneMissing] 清單中的節點到目前 clique 中的節點是最佳的節點，來卸除。後卸除這個最小連接] 節點，並未連線到卸除的節點的 [oneMissing] 清單中的所有節點將立即完整都連線到 clique，因此變得 possibleAdd 的新節點中剩下的節點。

MakeOneMissing 方法所示圖 4。透過圖表] 中的每個節點，掃描的方法。其概念是，若要計算 clique 中的幾個節點連接到目前正在檢查的節點。如果總和計算的連接節點正好一個小於目前的 clique，大小，那麼正在檢查節點就是 oneMissing 的節點。此方法 short-circuits，如果目前的節點，正在檢查有少於必要數目的其他例項。此方法必須篩選出已在 clique 因為他們連線到他們自己的 clique (也就是本身) 中的某個節點的節點。二進位搜尋因為目前的 clique 排序 (每個新增或卸除) 之後，可以用來代替較慢的線性搜尋 (請參閱圖 4)。

[圖 4 將清單中的 oneMissing 節點

static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
{
  int count;
  List<int> result = new List<int>();
  for (int i = 0; i < graph.NumberNodes; ++i) {
    count = 0;
    if (graph.NumberNeighbors(i) < clique.Count - 1) continue;
    if (clique.BinarySearch(i) >= 0) continue;
    for (int j = 0; j < clique.Count; ++j) {
      if (graph.AreAdjacent(i, clique[j]))
        ++count;
    }
    if (count == clique.Count - 1)
      result.Add(i);
  }
  return result;
}

GetNodeToDrop 方法會開始：

static int GetNodeToDrop(MyGraph graph, List<int> clique,
  List<int> oneMissing)
{
  if (clique.Count == 1)
    return clique[0];
...

這個方法會假定目前的 clique 有一個以上的節點。如果只有一個節點中目前的 clique，那麼它就是唯一可以卸除的節點。方法會判斷 oneMissing 清單中未連線至目前的 clique 中的任何節點，因為 clique 編碼中斷連接到 [oneMissing] 清單中可能有一個以上的節點的節點的最大數目:

int maxCount = 0;
for (int i = 0; i < clique.Count; ++i) {
  int currCliqueNode = clique[i];
  int countNotAdjacent = 0;
  for (int j = 0; j < oneMissing.Count; ++j) {
    int currOneMissingNode = oneMissing[j];
    if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false)
      ++countNotAdjacent;
  }
  if (countNotAdjacent > maxCount)
    maxCount = countNotAdjacent;
}
...

之後即中斷連線的最大數目，這個方法重新掃瞄來尋找最中斷連線，並將每一份候選節點 clique。如同 GetNodeToAdd 方法中，GetNodeToDrop 可以避免重新掃描，藉由維護輔助資料存放區：

List<int> candidates = new List<int>();
for (int i = 0; i < clique.Count; ++i) {
  int currCliqueNode = clique[i];
  int countNotAdjacent = 0;
  for (int j = 0; j < oneMissing.Count; ++j) {
    int currOneMissingNode = oneMissing[j];
    if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false)
      ++countNotAdjacent;
  }
  if (countNotAdjacent == maxCount)
    candidates.Add(currCliqueNode);
}
...

藉由從卸除的最佳節點清單中傳回隨機選取的節點，完成方法 GetNodeToDrop：

...
return candidates[random.Next(0, candidates.Count)];
} // GetNodeToDrop

結論

如何有效是窮盡的演算法？不論其相對的簡單起見，窮盡演算法已顯示目前已在許多案例中問題相當有效。不過，您可以使用幾個標準，包括速度和方案的品質來定義有效性。我執行這個演算法對 DIMACS 的參考資料組織所維護的幾個非常困難的基準測試圖形問題且演算法是十分有效率，快速地執行，而且產生的最大值通常是 5 個百分點的最著名的方案中的 cliques。

測試窮盡演算法可能不容易。除了所有一般測試技術，例如單元測試，如此類推測試界限條件 — 而且窮盡的演算法有越來越高的解決方案，有效的測試策略，就是撰寫反覆檢查狀態的演算法使用的資料結構的 helper 方法。比方說，同時測試此處所提供的最大 clique 演算法，我要撰寫驗證目前的 clique 中沒有任何重複的節點的方法，確認沒有在目前的 clique 中的節點位於目前的 possibleAdd，或目前的 oneMissing 所列出的依此類推。

我在此處提供的窮盡的最大 clique 演算法可加以修改，以產生較佳的結果，在許多方面。其中一種技術，最窮盡演算法，通常是加入所謂的 tabu 功能。 Tabu 演算法會維護一份最近使用過的資料及可能是一份最近看到的方案。在 [tabu] 清單中的資料不用來建構新的方案。此外，窮盡演算法可以通常會運用策略，稱為高原搜尋。窮盡演算法無法改善其目前的方案時，高原搜尋就會產生新的方案而不會回溯，例如卸除最大 clique 問題中的節點。我將在未來的專欄中提供這些既有趣又有用的 tabu 和高原技巧。

Dr。詹姆斯 McCaffrey 適用於 Volt 資訊科學 Inc.，他用來管理使用 Microsoft 里德蒙，Wash.，在校園的軟體工程師技術的訓練。他已投入許多 Microsoft 產品，包括網際網路檔案總管] 及 [MSN 搜尋。 Dr。 McCaffrey 是作者」。NET 測試自動化的食譜」 (Apress 2006)，並且可以連線到 jammc@microsoft.com。

因為有到下列的技術專家來檢閱這份文件： Paul Koch，黎國明 Liebling， Ann Loomis Thompson 和 Shane Williams