# 禁忌算法和最大团

James McCaffrey

## 整体的程序结构

``````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) { ...  }
List<int> clique) { ...
}
static bool FormsALargerClique(MyGraph graph,
List<int> clique, int node) { ...
}
}
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
``````

``````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));
``````

## FindMaxClique 方法

FindMaxClique 方法调用几个的帮助器方法，我将描述不久。 在高级别的伪代码中的 FindMaxClique 算法以图 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
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 nodeToDrop = -1;
...
``````

``````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();
...
``````

LastMoved 数组用于确定是否允许或禁止在任何给定的时间节点。 数组的索引表示一个节点，并相应的数组值是该节点感动最后的时间 （添加或删除）。 通过使用 lastMoved 数组，，我不再需要显式创建允许节点的列表 （或，相等，禁止节点）。 初始化所有单元格的 lastMoved 为 int。MinValue 以便以后可以确定是否从未使用过的节点。

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

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

MakeOneMissing 方法构造连接到所有但完全之一，目前集团中的节点的所有节点的列表。 它并不明显，但事实证明维持这样的列表创建聪明的方式，以确定哪些节点在当前集团是最佳节点以降，我稍后会解释。 主要加工循环开始：

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

``````if (possibleAdd.Count > 0) {
prohibitPeriod, lastMoved);
clique.Sort();  cliqueChanged = true;
if (clique.Count > bestSize) {
bestSize = clique.Count;
bestClique.Clear();
timeBestClique = time;
}
}
}
``````

SelectAllowedNodes 中的键的行是：

``````if (time > lastMoved[currNode] + prohibitPeriod)
``````

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

``````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();
...
``````

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

``````...
clique.Clear();
}
``````

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

PossibleAdd 和 oneMissing 列表将会重新生成。 另一种方法是保持辅助数据结构和更新的而不是重新从零开始的这两个列表。 UpdateProhibitPeriod 方法是禁忌算法的自适应部分的关键组件，不久我将描述它。

## 记得以前的解决方案

``````private class CliqueInfo
{
private List<int> clique;
private int lastSeen;
public CliqueInfo(List<int> clique, int lastSeen)
{
this.clique = new List<int>();
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 项目将添加到解决方案历史哈希表对象，因为我需要一个自定义的 GetHashCode 哈希函数。 编写自定义的哈希函数是非常棘手的事情，而且涉及的所有问题的全面讨论需要整列。 在这种情况下，使用最简单 — — 但不是最有效 — — 的做法。 我在集团字段中，由空格分隔创建节点的字符串表示形式，然后使用内置的 String.GetHashCode。 例如，如果集团包含节点 {3 5 8}，生成"3 5 8" （带有尾随空格），然后从该字符串生成哈希代码。 记得这样它就不可能有一个集团派系都始终保持按排序顺序，{3 5 8} 和另一个集团 {8 3 5}。 所以，派的节点之间的空格处我 {3 5 8} 是有别于集团 {3 58}。

## 更新禁止期

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

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

"足够短"的时间间隔是在图中，少一个节点数的两倍。 这用于确定何时增加禁止时间。 这里使用的最佳值是最大的集团研究中另一个悬而未决的问题。 禁止时间的"上限值"是当前已知最佳解决方案的大小的两倍。 最佳的上限值，正如您可能已经猜到目前为止，开放研究的另一个问题。

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

## 更多的研究

**博士。**James McCaffrey适合伏信息科学 Inc.，他在管理技术培训为软件工程师工作在微软雷德蒙德，华盛顿，校园。他被在几个 Microsoft 产品，包括互联网资源管理器和 MSN 搜索。 博士。 麦卡弗里是作者"。网络测试自动化食谱"（很，2006年），可以在达到 jammc@microsoft.com