标签: graph-algorithm

这是Vazirani的算法书中的一个问题

该问题的输入是树T,边缘上具有整数权重.权重可以是负数,零或正数.给出线性时间算法以找到T中最短的简单路径.路径的长度是路径中边缘权重的总和.如果没有重复顶点,则路径很简单.请注意,路径的端点不受约束.

提示:这与在树中查找最大独立集的问题非常相似.

如何在线性时间内解决这个问题？

这是我的算法,但我想知道它是否是线性时间,因为它与深度优先没什么不同:

1. 遍历树(深度优先)
2. 保留索引(节点)
3. 添加值
4. 做(1)直到树的尽头
5. 比较总和并打印路径和总和

这个问题与此主题类似,但没有确定的答案.

我正在寻找一种算法,可以生成类似于此图像中的内容:

我读过有关醉酒步行算法的文章,但它们似乎并不适合我的需要.我不确定我是否可以使用经过大量修改的醉酒步行算法来实现我正在寻找的东西,或者我是否应该寻找其他算法来解决问题.

我最近一直在玩OSRM路由库.它似乎在解决最短路径问题方面非常有效.但是,我没有看到如何用它计算单源最短路径.更确切地说,给定固定的起始点,计算到达给定距离限制内可达到的所有位置的最短距离(例如,可在30分钟内到达).

OSRM在内部使用收缩层次结构.根据我的理解,当计算真实世界数据中两个位置之间的距离时,这种技术优于Dijkstra算法.但是,对于我的问题,Dijkstra的算法似乎更合适,不是吗？

OSRM是否提供API来计算单源最短路径问题(距离限制)？是否有其他免费路由库更适合此类问题？最好是对OpenStreetMap数据有良好支持的.

我有一个带有起始节点S和结束节点E的图G.这个图的特殊之处在于,不是边缘有成本,而是具有成本的节点.我想找到S和E之间的方式(一组节点,W),以便最小化(W).(实际上,我对W不感兴趣,只是max(W))等价,如果我删除成本大于k的所有节点,那么最小的k是什么,以便S和E仍然连接？

我有一个想法,但想知道它是否正确和最佳.这是我目前的伪代码:

L := Priority Queue of nodes (minimum on top)
L.add(S, S.weight)

while (!L.empty) {
    X = L.poll()
    return X.weight if (X == G)
    mark X visited
    foreach (unvisited neighbour N of X, N not in L) {
        N.weight = max(N.weight, X.weight)
        L.add(N, N.weight)
    }
}

我认为最坏的情况是O(n log n),其中n是节点数.

以下是我的具体问题(渗透)的一些细节,但我也对这个问题的算法感兴趣.节点权重在0和给定的最大值之间随机均匀分布.我的节点是在R²平面上的泊松分布,如果两个节点之间的距离小于给定的常数,则存在两个节点之间的边.可能有很多节点,因此它们是动态生成的(隐藏在伪代码中的foreach中).我的起始节点在(0,0)中,结束节点是距离(0,0)大于R的距离上的任何节点.

编辑:节点上的权重是浮点数.

我有一个值为0或1的矩阵,我想获得一个相邻1的组列表.

例如,矩阵

mat = rbind(c(1,0,0,0,0),
            c(1,0,0,1,0),
            c(0,0,1,0,0),
            c(0,0,0,0,0),
            c(1,1,1,1,1))

> mat
     [,1] [,2] [,3] [,4] [,5]
[1,]    1    0    0    0    0
[2,]    1    0    0    1    0
[3,]    0    0    1    0    0
[4,]    0    0    0    0    0
[5,]    1    1    1    1    1

应返回以下4个连接组件:

C1 = {(1,1);(2,1)}

C2 = {(2,4)}

C3 = {(3,3)}

C4 = {(5,1);(5,2);(5,3);(5,4);(5,5)}

有没有人知道如何在R中快速做到这一点？我的真实矩阵确实相当大,如2000x2000(但我希望连接组件的数量相当小,即200).

我正在做一项任务,我必须使用一颗星来解决一个15谜题(在C中).

启发函数是曼哈顿距离(又名出租车距离).

我们给出了一个示例输入/输出,其中电路板在22次移动中和扩展395个节点(电路板状态)后解决(即我们必须查看395个节点的子节点)

通过'正确'启发式,我的意思是我的功能与用于产生样本输出的功能相同并产生正确的距离.

问题是我的解决方案扩展了超过400个节点以找到解决方案(它是最佳的22个移动而不是另一个).

我注意到数字的变化取决于我生成子节点的顺序(向上,向左,向下,向右或其他方向移动空间区域).

有24种方法可以向上,向下,向左和向右移动空间磁贴以生成子项,我尝试了所有这些,但它们都没有扩展395个节点.

为什么会这样？

术语:

• node:每个节点都是15-puzzle board的配置
• children:通过从当前节点向上,向下,向左或向右移动空间磁贴可以实现的配置

PS:如果重要的话,我正在使用二进制堆作为开放列表

谢谢

我试图在图论中编写Bron-Kerbosch算法的C#实现,用于在图中找到最大尺寸的派系.

理想情况下,此算法将生成一个图表列表,其中每个图表将表示来自初始输入图表的最大集团.我的代码没有产生预期的结果,我希望能够编写更好的代码来实现这个实现.

此实例中使用的图类是基于图的邻接列表表示的自定义类.

public class BronKerbosch
{
    public List<Graph<Person>> Run(Graph<Person> R, Graph<Person> P, Graph<Person> X, List<Graph<Person>> maximalCliques)
    {
        // if P and X are both empty, and the size of R is greater than 1 (implies clique):
        if (!P.Nodes.Any() && !X.Nodes.Any() && R.Nodes.Count() > 1)
            // report R as a maximal clique
            maximalCliques.Add(R);

        else
        {
            // Copy P's nodes for traversal
            List<GraphNode<Person>> nodesCopy = P.Nodes.ToList();

            // For each node v in P:
            foreach (GraphNode<Person> v in nodesCopy)
            { …

设G =(V,E)为加权,连通和无向图,并且令T为最小生成树.设e是不在E中的任何边(并且具有权重W(e)).证明或反驳:TU {e}是包含G'=(V,EU {e})的最小生成树的边集.

嗯,这对我来说听起来是对的,所以我决定证明这一点,但我每次都被卡住了......

例如,如果e是具有最小权重的新边缘,那么谁可以向我们保证T中的边缘不会以不良方式被选择,这将阻止我们在没有E中其他边缘的"帮助"的情况下获得新的最小权重 - T？

我将不胜感激任何帮助,在此先感谢.

我应该使用什么算法来查找有向下限但不是上限的有向图上的最小流量？比如这个简单的例子:

在文献中,这是最小的成本流问题.然而,在我的情况下,成本与每个边缘所需流量的非零下限相同,所以我在上面提出问题.在文献中,问题是:找到单源/单宿有向无环图的最小成本流的最佳算法是什么,其中每个边具有无限容量,流上的非零下界,以及成本等于流量的下限.

根据我的研究,似乎人们处理任何类型网络的任何类型的最低成本的主要方式是将问题设置为LP类型问题并以此方式解决.然而,我的直觉是没有流动的上限,即具有无限容量的边缘,使问题更容易,所以我想知道是否有一种算法专门针对这种情况使用比单纯形法等更多的"图形"技术. .人.

我的意思是,如果所有的成本和下限都是1,如上所述...我们正在寻找一个涵盖所有边缘的流程,遵守流程规则,并且不会在从s到t的任何路径上推动太多流量.这只是感觉它不应该要求LP求解器,事实上维基百科关于最小成本流的文章指出"如果容量约束被移除,问题就会减少到最短路径问题"但我认为他们正在讨论下限全部为零的情况.

还有开源C/C++代码,可以在任何地方实现最低成本流量吗？从谷歌搜索可用的东西,我发现我可以自己设置问题作为LP问题,并用开源LP解算器解决,或者我可以使用LEMON,它为最低成本流提供了几种算法.据我所知,boost图库不包含实现.

还有别的事吗？

我想乘车从X市到Y市.我的车有一个小水箱,加油站只存在于道路交叉口(交叉口是节点,道路是边缘).因此,我想采取一条路径,使我在两个加油站之间行驶的最大距离最小化.我可以使用什么有效的算法来找到该路径？蛮力是一个坏的解决方案.我想知道是否存在更有效的算法.