3

问题背景

我目前正在开发一个蚁群系统算法框架。我想我会先尝试他们应用到的第一个问题：旅行推销员问题（TSP）。我将使用 C# 来完成这项任务。

所有 TSP 实例将由一个完整的无向图组成，每个边有 2 个不同的权重。

问题

到目前为止，我只使用了邻接列表表示，但我读过它们只推荐用于稀疏图。由于我不是最了解数据结构的人，所以我想知道实现无向完整图的最有效方法是什么？

如果需要，我可以提供更多详细信息。

感谢您的时间。

更新

重量澄清。每条边都会有两个与之关联的值：

  1. 两个城市之间的距离（ d(i,j) = d(j,i) 两个方向的距离相同）
  2. 蚂蚁在特定边缘沉积的信息素量

操作。我将在图表上执行的操作的小总结：

  • 对于每个节点，该特定节点上的蚂蚁将必须遍历与所有入射边关联的值

问题说明

蚁群优化算法可以“解决” TSP，因为这是它们首次应用于 . 我说“解决”是因为它们是称为元启发式优化的算法家族的一部分，因此它们从不保证返回最优解。

关于手头的问题：

  • 蚂蚁会知道如何完成一次旅行，因为每只蚂蚁都会有记忆。
  • 每次蚂蚁访问一个城市时，它都会将该城市存储在它的记忆中。
  • 每次蚂蚁考虑访问一个新城市时，它都会在其记忆中搜索并选择一条出边，前提是该边不会将其引导至已访问过的城市。
  • 当没有更多的边时，蚂蚁可以选择它已经完成了一次旅行；在这一点上，我们可以通过回溯它的记忆来回溯蚂蚁创建的旅程。

研究文章详情：蚁群系统文章

效率考虑

我更担心运行时间（速度）而不是内存。

4

2 回答 2

2

首先，这里有邻接列表与矩阵的一般指南。 不过，这是一个相当低级、非特定的讨论，因此它可能不会告诉您任何您不知道的事情。

我认为，要点是：如果你经常发现自己需要回答这个问题，“我需要知道节点 i 和节点 j 之间边缘的距离或信息素水平”，那么你可能需要矩阵形式，因为这个问题可以在 O(1) 时间内回答。

您确实提到需要迭代与节点相邻的边——这里可能会出现一些巧妙和微妙的地方。如果您不关心迭代的顺序，那么您就不会关心数据结构。如果您非常关心顺序，并且您预先知道顺序，并且它永远不会改变，那么您可以将其直接编码到邻接列表中。如果您发现自己总是想要，例如最大或最小浓度的信息素，您可能想尝试一些更有条理的东西，例如优先队列。这真的取决于你在做什么类型的操作。

最后，我知道您提到您对速度比对内存更感兴趣，但我不清楚您将使用多少图形表示。如果只有一个，那你真的不在乎。但是，如果每只蚂蚁都在构建自己的图表示，那么您可能比您想象的更关心，并且邻接表将让您携带不完整的图表示；不利的一面是，当蚂蚁在其边界进行探索时，建立表征需要时间。

最后，我知道您说您正在处理完整的图和 TSP，但值得考虑的是您是否需要使这些例程适应可能的图上的其他一些问题，如果是，那该怎么办。

I lean toward adjacency lists and/or even more structure, but I don't think you will find a clean, crisp answer.

于 2012-06-18T17:16:45.843 回答
1

既然你有一个完整的图表，我认为最好的表示是二维数组。

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
  }
}

如果您有很多节点，并且不按此图中的索引“记住”节点，那么拥有一个将 a 映射Node到图中的索引的字典可能是有益的。进行反向查找也可能会有所帮助（List此处将是适当的数据结构。这将使您能够根据图中的那个节点。

于 2012-06-08T15:55:29.230 回答