最高效的实现了一个完整的无向图 [英] Most efficient implementation for a complete undirected graph

问题描述

问题背景

我目前正在开发的蚁群算法体系的框架。我想我会试图通过他们，他们被应用到的第一个问题开始了：旅行商问题（TSP）。我将使用C＃来完成任务。

所有的TSP实例将包括一个完整的无向图与每个边缘有关2种不同的权重。

问

到现在为止我只用邻接表表示，但我读过他们是建议只对稀疏图。因为我不是最博学的人，当涉及到数据结构，我想知道什么是实现一个无向完全图的最有效方法是什么？

如果需要，我可以提供更多的细节。

感谢您的时间。

更新

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

1. 两个城市（D（I，J）= D（J之间的距离，我在两个方向）相同的距离）


2. 在那个特定的边缘

<沉积蚂蚁信息素的量Pr > 操作即可。我会在图上做业务的小总结：

• 对于每个节点，特定节点上的蚂蚁将不得不通过迭代与所有关联边

问题澄清

$ b $关联的值b

蚁群算法可以解决TSP，因为这是他们首次应用。我说：解决，因为他们是一个家庭的算法称为共通启发式演算法优化的一部分，因此，他们永远无法保证返回的最优解

对于手头上的问题：

• 蚂蚁会知道如何完成巡演，因为每只蚂蚁都会有记忆。


• 每次一只蚂蚁访问一个城市，将该市存储到内存中。


• 每个蚂蚁考虑访问一个新的城市，将在内存中搜索并选择相应的出边只有当这种优势将不是导致已经访问过的城市的时间。


• 当没有更多的边缘蚂蚁可以选择它完成游;在这一点上，我们可以通过它的记忆回溯折回的蚂蚁创建的旅游

研究文章详细介绍：的蚁群文章

效率的考虑

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

解决方案

首先，有一个通用指南邻接表VS矩阵的这里这是一个相当低的水平，非特异性的讨论，虽然如此，它可能不会告诉你任何你不知道的。

外卖，我认为是这样的：如果你经常发现自己需要回答这个问题，我需要知道的距离或精确节点i和节点j之间的边的信息素水平，那么你可能希望的矩阵形式，因为这问题可以在O（1）时间来回答。

您也提到需要遍历邻近node--这里的优势又在哪里一些聪明和微妙的可以进来了。如果你不关心秩序迭代的，那么你不关心的数据结构。如果您十分关心的顺序，你知道订单达阵，它不会改变，你也许可以直接编码到邻接表这一点。如果你发现自己总是想，例如，信息素的最大或最小浓度，你可能想尝试一些更结构化的，就像一个优先级队列。这真的取决于你在做什么样的操作。

最后，我知道你提到你更感兴趣的速度比内存，但它不是我清楚，你会多少图形表示使用。如果只有一个，那么你真的不在乎。但是，如果每个蚂蚁建立自己的图形表示法，因为它去一起，你可能会关心比你想象的，而邻接表可以让你随身携带不完全图的表示;那另一面是，这将需要时间来建立的交涉起来的时候蚂蚁边界上所探讨的问题。

最后的最后，我知道你说你处理完全图和TSP，但它是值得考虑你是否会的曾经的需要将这些程序适应其他一些问题上可能的图形，如果是这样，那又怎么样。

我倚向邻接表和/或更多的结构，但我不认为你会找到一个干净，清晰的答案。

Problem background

I am currently developing a framework of Ant Colony System algorithms. I thought I'd start out by trying them on the first problem they were applied to: Travelling Salesman Problem (TSP). I will be using C# for the task.

All TSP instances will consist of a complete undirected graph with 2 different weights associated with each edge.

Question

Until now I've only used adjacency-list representations but I've read that they are recommended only for sparse graphs. As I am not the most knowledgeable of persons when it comes to data structures I was wondering what would be the most efficient way to implement an undirected complete graph?

I can provide additional details if required.

Thank you for your time.

UPDATE

Weight clarification. Each edge will have the two values associated with them:

1. distance between two cities ( d(i,j) = d(j,i) same distance in both directions)
2. amount of pheromone deposited by ants on that particular edge

Operations. Small summary of the operations I will be doing on the graph:

• for each node, the ant on that particular node will have to iterate through the values associated with all incident edges

Problem clarification

Ant Colony Optimization algorithms can "solve" TSP as this is where they were first applied to . I say "solve" because they are part of a family of algorithms called metaheuristics optimizations, thus they never guarantee to return the optimal solution.

Regarding the problem at hand:

• ants will know how to complete a tour because each ant will have a memory.
• each time an ant visits a city it will store that city in its memory.
• each time an ant considers visiting a new city it will search in its memory and pick an outgoing edge only if that edge will not lead it to an already visited city.
• when there are no more edges the ant can choose it has complete a tour; at this point we can retrace the tour created by the ant by backtracking through its memory.

Research article details: Ant Colony System article

Efficiency considerations

I am more worried about run time (speed) than memory.

解决方案

First, there's a general guide to adjacency lists vs matrices here. That's a pretty low-level, non-specific discussion, though, so it might not tell you anything you don't already know.

The takeaway, I think, is this: If you often find yourself needing to answer the question, "I need to know the distance or the pheromone level of the edge between exactly node i and node j," then you probably want the matrix form, as that question can be answered in O(1) time.

You do mention needing to iterate over the edges adjacent to a node-- here is where some cleverness and subtlety may come in. If you don't care about the order of the iteration, then you don't care about the data structure. If you care deeply about the order, and you know the order up front, and it never changes, you can probably code this directly into an adjacency list. If you find yourself always wanting, e.g., the largest or smallest concentration of pheromones, you may want to try something even more structured, like a priority queue. It really depends on what kind of operations you're doing.

Finally, I know you mention that you're more interested in speed than memory, but it's not clear to me how many graph representations you'll be using. If only one, then you truly don't care. But, if each ant is building up its own representation of the graph as it goes along, you might care more than you think, and the adjacency list will let you carry around incomplete graph representations; the flip side of that is that it will take time to build the representations up when the ant is exploring on its frontier.

Finally finally, I know you say you're dealing with complete graphs and TSP, but it is worth thinking about whether you will ever need to adapt these routines to some other problem on possibly graphs, and if so, what then.

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

这篇关于最高效的实现了一个完整的无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！