首页 / C# / C#-完整无向图的最有效实现
C#-完整无向图的最有效实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了C#-完整无向图的最有效实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2270字,纯文字阅读大概需要4分钟。
内容图文
![C#-完整无向图的最有效实现](/upload/InfoBanner/zyjiaocheng/656/451c9361d0a146ef85e06f612bdb46d0.jpg)
问题背景
我目前正在开发蚁群系统算法的框架.我以为我会首先尝试将它们应用于第一个问题:旅行商问题(TSP).我将在任务中使用C#.
所有TSP实例将由一个完整的无向图组成,并且每个边缘具有2个不同的权重.
题
到目前为止,我只使用了邻接列表表示形式,但我读到它们仅建议用于稀疏图.因为我不是最了解数据结构的人,所以我想知道实现无向完整图的最有效方法是什么?
如果需要,我可以提供其他详细信息.
感谢您的时间.
更新
澄清重量.每个边缘将具有与它们关联的两个值:
>两个城市之间的距离(d(i,j)= d(j,i)双向距离相同)
>特定边缘上蚂蚁沉积的信息素的数量
操作.我将在图表上进行的操作的小摘要:
>对于每个节点,该特定节点上的ant将必须遍历与所有入射边缘关联的值
问题澄清
蚁群优化算法可以“解决” TSP,因为这是最初应用于它们的地方.我说“解决”是因为它们是称为元启发式优化的一系列算法的一部分,因此它们永远不能保证返回最优解.
关于眼前的问题:
>蚂蚁会知道如何完成游览,因为每个蚂蚁都会有一个记忆.
>蚂蚁每次访问城市时,都会将该城市存储在其内存中.
>每次蚂蚁考虑访问一个新城市时,它都会在内存中进行搜索并选择出站边缘,只要该边缘不会将其引向已访问过的城市.
>当没有更多的边缘时,蚂蚁可以选择完成一次巡回演出;在这一点上,我们可以通过回溯蚂蚁的记忆来追溯蚂蚁创造的旅程.
研究文章详细信息:Ant Colony System article
效率考虑
我比内存更担心运行时间(速度).
解决方法:
首先,有一个关于邻接表与矩阵here.的通用指南,尽管这是一个非常低级的,非特定的讨论,所以它可能不会告诉您您所不知道的任何内容.
我想得出的结论是:如果您经常发现自己需要回答以下问题:“我需要确切地知道节点i和节点j之间的边缘的距离或信息素水平,”那么您可能想要矩阵形式,因为该问题可以在O(1)时间内回答.
您确实提到需要在节点附近的边缘上进行迭代-这可能是一些聪明和精妙之处.如果您不关心迭代的顺序,那么您就不必关心数据结构.如果您非常在意订单,并且预先知道订单并且从未更改过,则可以直接将其编码为邻接列表.如果您发现自己一直想要例如最大或最小的信息素浓度,则可以尝试尝试更结构化的操作,例如优先级队列.这实际上取决于您正在执行哪种操作.
最后,我知道您提到过,您对速度比对内存更感兴趣,但是我不清楚您将使用多少个图形表示形式.如果只有一个,那么您真的不在乎.但是,如果每个蚂蚁都在建立自己的图形表示形式,那么您可能会比您想的要多,邻接表将使您可以携带不完整的图形表示形式.另一方面,当蚂蚁在其边界上探索时,将需要一些时间来建立表示.
最后,我知道您说您正在处理完整的图形和TSP,但值得考虑的是,是否需要将这些例程适应可能的图形上的其他问题,如果可以,那么该怎么办.
我倾向于邻接表和/或更多结构,但我认为您找不到干净,清晰的答案.
内容总结
以上是互联网集市为您收集整理的C#-完整无向图的最有效实现全部内容,希望文章能够帮你解决C#-完整无向图的最有效实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。