8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

最大限度重访的完整图遍历

Alireza Yadegari 2月前

53 0

我有一个无向图 G,没有任何权重。为简单起见,我们假设它是一个 5x5 方格图。我们如何才能从起始节点访问所有节点,同时最小化最大值

我有一个无向图 G,没有任何权重。为简单起见,我们假设它是一个 5x5 方格图。

我们如何才能从起始节点访问所有节点,同时最小化“最大最短路径”并最大化所有节点的重新访问次数 (当起始节点试图到达其他节点时)?

我的尝试:

我使用 BFS(它比 DFS 的结果更好),并且能够计算出起始节点尝试到达其他节点时,某个节点被重新访问了多少次。为了确保最大程度的重新访问,我循环遍历所有节点作为起始节点,并检查哪个起始节点的重新访问次数最多。

但我不确定这个“算法”是否能提供最大限度的重访。

我尝试搜索互联网和文献,似乎存在用于最小重访次数的算法,但没有用于最大重访次数的算法。

帖子版权声明 1、本帖标题:最大限度重访的完整图遍历
    本站网址:http://xjnalaquan.com/
2、本网站的资源部分来源于网络,如有侵权,请联系站长进行删除处理。
3、会员发帖仅代表会员个人观点,并不代表本站赞同其观点和对其真实性负责。
4、本站一律禁止以任何方式发布或转载任何违法的相关信息,访客发现请向站长举报
5、站长邮箱:yeweds@126.com 除非注明,本帖由Alireza Yadegari在本站《algorithm》版块原创发布, 转载请注明出处!
最新回复 (0)
  • 是的,通常情况下是这样。在这种情况下,我知道现有的算法可以解决我的问题。但就我而言,这是目标之一。如果不是,我就不会问这个问题了:)

  • 如果您的目标是访问每个节点 1000 次,只需在基本 DFS 或 BFS 或任何其他方法上循环 1000 次。请注意,您不能同时最小化或最大化两个事物。

  • 如果您只使用每条边一次,那么访问每个节点的次数是固定的(连接到节点的边数为 1/2,每次到达和离开时都会用掉一条边)。如果您可以重复使用边,那么访问次数不受限制,只需在节点之间来回移动即可。

返回
作者最近主题: