c# - 完整无向图的最有效实现

Question

问题背景

我目前正在开发蚁群系统算法框架。我想我应该先尝试解决第一个问题:旅行商问题 (Traveling Salesman Problem, TSP)。我将使用 C# 来完成这项任务。

所有 TSP 实例都将包含一个完整的无向图，每条边具有 2 个不同的权重。

问题

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

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

感谢您的宝贵时间。

更新

权重说明。每条边都会有两个与之关联的值:

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

操作。我将在图表上进行的操作的小总结:

• 对于每个节点，该特定节点上的 Ant 将必须遍历与所有事件边关联的值

问题说明

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

关于手头的问题:

• Ant 会知道如何完成一次旅行，因为每只 Ant 都有内存。
• 每次 Ant 访问一个城市时，它都会将该城市存储在它的内存中。
• 每次 Ant 考虑访问一个新城市时，它都会在其内存中进行搜索，并仅当该边缘不会将其引向已访问过的城市时，才选择出局边缘。
• 当没有更多的边时， Ant 可以选择它完成了一次旅行；在这一点上，我们可以通过回溯 Ant 的内存来追溯 Ant 创建的旅程。

研究文章详情:Ant Colony System article

效率方面的考虑

与内存相比，我更担心运行时间(速度)。

Answer 1

首先，有一个关于邻接列表与矩阵的通用指南 here.不过，这是一个非常低级的、非特定的讨论，因此它可能不会告诉您任何您还不知道的信息。

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

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

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

最后，我知道你说你正在处理完整的图和 TSP，但值得考虑的是你是否会曾经需要调整这些例程以适应可能图上的其他问题，如果是这样，那又怎样。

我倾向于邻接列表和/或更多结构，但我认为您不会找到干净、清晰的答案。