标签: graph-algorithm

给定定向的未加权图并且问题是找到最大长度的简单路径(起始顶点和结束顶点不固定).它显然可以在O(n ^ 2*2 ^ n)中解决,但我听说有O(n*2 ^ n)算法,我不知道.那么如何在O(n*2 ^ n)中解决它？// n = | V |

我正在寻找关于TSP的相关(2000年以后)新论文.我发现的所有论文都很难,需要高水平的数学技能.我正在寻找那些具有简单的大学数学知识和良好的Java和C编程知识的人可以阅读的论文(我没有找到任何当前使用这些语言实现TSP的论文).

任何提示将受到高度赞赏.

(编辑)

我想说的是,我正在寻找那些不需要理解困难公式的论文.例如,一些论文描述了算法或解决方案的哲学.没有必要实现该算法,只需描述这些技术.也许使用一些简单的几何...

我找到了一些基于Lin-Kernighan方法的论文,看起来没问题......

我正在尝试为以下问题找到最佳解决方案

1. 每个节点内表示的数字表示为(x,y).
2. 节点的相邻节点总是具有y(当前节点y值+1)的值.
3. x当我们从一个节点到另一个节点时,值的变化为1
4. 如果没有值的变化,从节点到其相邻节点没有成本x.
5. 没有2个具有相同y值的节点被认为是相邻的.

最优解是成本最低的解决方案,我正在考虑使用A*路径寻找算法来寻找最优解.

我的问题,A*是这类问题的一个很好的选择,或者我应该看看任何其他算法,而且我还在考虑使用递归方法来计算启发式成本,但我感觉它不是好主意.

这是我如何认为启发式函数将是这样的例子

• 节点的启发式权重= Min(它的子节点的启发式权重)
• 子节点也是如此.

但就我所知,启发式意味着是一种近似,所以我认为就启发式函数而言,我的方向是错误的

任何人都可以想到一种方法来修改Kruskal算法的最小生成树,以便它必须包含一定的边(u,v)？

我有一个断开的二分无向图.我想完全断开图表.只有我可以执行的操作是删除节点.删除节点将自动删除其边缘.任务是最小化要删除的节点数.图中的每个节点最多有4个边.

通过完全断开图形,我的意思是不应该通过链接连接两个节点.基本上是一个空边集.

像Bellman-Ford算法和Dijkstra算法这样的算法用于找到从图上的单个起始顶点到每个其他顶点的最短路径.但是,在我写的程序中,起始顶点的变化比目标顶点的变化频繁得多.有什么算法可以反过来 - 也就是说,给定一个目标顶点,从每个起始顶点找到最短路径？

所以我现在正在教自己一些图形算法,现在在Kruskal上,并且理解建议使用union-find,因此检查添加边创建一个循环是否只需要O(Log V)时间.出于实际目的,我明白你为什么要这么做,但是严格地看一下Big O符号,这样做实际上是否会影响最坏情况的复杂性？

我的理由:如果不是联合查找,我们做了一个DFS来检查周期,那个运行时间是O(E + V),你必须为O的运行时间执行那个V次(V ^ 2 + VE ).它不仅仅是union find,也就是O(V*LogV),但Kruskal的大部分复杂性来自于删除优先级队列的最小元素E次,即O(E*logE),大O回答.我没有真正看到空间优势,因为union-find需要O(V)空间,因此使用DFS查找循环所需的数据结构也是如此.

所以对一个简单的问题可能是一个过长的解释:在Kruskal的算法中使用union-find是否会影响最坏情况的运行时？

我使用曼哈顿启发式和曼哈顿以及线性冲突启发式编码了15-puzzle的A-star算法.

我的问题是,对于某些特定的拼图实例,线性冲突会导致比单独使用a-Star的曼哈顿启发式创建和探索更多节点吗？

由于我尝试通过我的程序解决的大多数拼图实例需要<50 Moves使用曼哈顿的给定内存解决得体,并且解决更快将其与线性冲突组合作为启发式,需要> 50 Moves的实例导致程序运行无限期地挂断我的机器,但是对于一个需要42次移动的特定问题,我的程序在大约8秒内使用曼哈顿解决了但是使用线性冲突导致程序无限期地运行并挂断我的机器.

我一遍又一遍地浏览了我的代码,我在线性冲突或曼哈顿启发式代码中找不到错误.因此,这个一般性的问题要确保.

以下实例导致上述问题.

2,8,7,11                 //Takes 42 Moves to solve
5,0,4,15
13,9,14,3
1,10,6,12

有没有人实现Laszlo Babai的准多项式图同构？

http://people.cs.uchicago.edu/~laci/

我不是这方面的专家.我想知道 为什么不实施他的算法并运行它来验证它的时间复杂度？

我试图解决类似于GeeksforGeeks这个问题的问题,但是不同的是:
给定一个矩形的2-d网格,每个单元格中都有一些硬币值,任务是从左上角和右下角开始向右或者向下,从左下角到左上角向左或向上,最大化拾取的硬币总量.每个单元格中的硬币只能被挑选一次.
链接中的解决方案是同时启动两个遍历,但这不会在这里工作.
我该怎么解决这个问题？执行此操作的蛮力方式是枚举所有路径并选择两条路径,以最大化所拾取的硬币总和,但这对于大输入不起作用.