标签: graph-theory

我在我的一本AI书中读过,用于模拟或游戏中寻路的流行算法(A-Star,Dijkstra)也用于解决众所周知的"15-puzzle".

任何人都可以给我一些关于如何将15-puzzle减少到节点和边缘图的指针,以便我可以应用其中一种算法？

如果我将图中的每个节点视为游戏状态,那么该树不会变得非常大吗？或者只是这样做的方式？

我正在使用具有路径压缩的Lengauer和Tarjan算法来计算有数百万个节点的图的支配树.算法非常复杂,我不得不承认我没有花时间完全理解它,我只是使用它.现在我需要计算根节点的直接子节点的支配树,并可能将图形向下递减到重复此操作的某个深度.即,当我为根节点的子节点计算支配树时,我想假装根节点已从图中移除.

我的问题是,是否有一个有效的解决方案,利用已经在根节点的初始支配树中计算的直接支配者信息？换句话说,我不想从头开始为每个孩子,因为整个过程非常耗时.

天真地看起来一定是可能的,因为在图表的内部会有很多节点,这些节点在它们之上只有一点点,并且不受图形顶部变化的影响.

顺便说一句:在统治者树的主题是由编译人员"拥有"并且在经典图论的书中没有提到它,这是奇怪的.我正在使用它的应用程序 - 我的FindRoots java堆分析器 - 与编译器理论无关.

澄清:我在这里谈论有向图.我所指的"根"实际上是具有最大可达性的节点.我已经更新了上面的文本,用"graph"替换了对"tree"的引用.我倾向于将它们视为树木,因为形状主要是树等.该图实际上是java堆中的对象,您可以想象它是合理的层次结构.我发现主导树在进行OOM泄漏分析时很有用,因为你感兴趣的是"是什么让这个物体保持活力？" 答案最终是它的统治者.支配树允许你<ahem>看到木头而不是树木.但有时很多垃圾漂浮在树顶,所以你有一个直接在它下面有数千个孩子的根.对于这样的情况,我想尝试计算根植于根的每个直接子节点(在原始图形中)的支配树,然后可以进入下一级别,依此类推.(我试着暂时不担心反向链接的可能性:)

设G是图.所以G是一组节点和一组链接.我需要找到一种快速分割图形的方法.我现在正在使用的图表只有120*160个节点,但我可能很快会在另一个上下文(不是医学,但是网站开发)中处理同等问题,有数百万个节点.

所以,我所做的是将所有链接存储到图表矩阵中:

M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))

如果节点s连接到节点t,则M在位置s,t中保持1.我确保M是对称的M [s,t] = M [t,s],并且每个节点链接到它自己M [s,s] = 1.

如果我记得很好,如果我将M与M相乘,则结果是一个矩阵,表示连接通过两个步骤到达的顶点的图形.

因此,我继续将M自身与M一起使用,直到矩阵中的零数不再减少为止.现在我有连接组件的列表.现在我需要对这个矩阵进行聚类.

到目前为止,我对算法非常满意.我认为它简单,优雅,而且速度相当快.我在这部分遇到了麻烦.

基本上我需要将此图拆分为其连接的组件.

我可以浏览所有节点,看看它们连接的是什么.

但是如何排序矩阵重新排序.但我不知道是否可以这样做.

以下是目前的代码:

def findzeros(M):
    nZeros=0
    for t in M.flat:
        if not t:
            nZeros+=1
    return nZeros

M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))    
for s in data.keys():
    MatrixCells[s,s]=1
    for t in data.keys():
        if t<s:
            if (scipy.corrcoef(data[t],data[s])[0,1])>threashold:
                M[s,t]=1
                M[t,s]=1

nZeros=findzeros(M)
M2=M*M
nZeros2=findzeros(M2)

while (nZeros-nZeros2):
    nZeros=nZeros2
    M=M2
    M2=M*M
    nZeros2=findzeros(M2)

编辑:

有人建议我使用SVD分解.以下是5x5图表上问题的简单示例.我们将使用这个,因为19200x19200方阵并不容易看到簇.

import numpy
import scipy

M=numpy.mat(numpy.zeros((5,5)))

M[1,3]=1
M[3,1]=1
M[1,1]=1
M[2,2]=1
M[3,3]=1
M[4,4]=1
M[0,0]=1

print M

u,s,vh = numpy.linalg.linalg.svd(M)
print u
print s
print …

根据书(算法简介),在dfs中,边被分为4种:

1. 树边缘,如果在边缘(u,v)中,首先发现v,则(u,v)是树边缘.
2. Back Edge,如果......,v已经被发现而v是一个祖先,那么它就是一个后缘.
3. 前向边缘,如果......,v已经被发现而v是u的后代,它是前沿.
4. Cross Edge,除上述三个以外的所有边缘.

我的问题是,当我试图找出(u,v)是后边缘还是前边缘时,如何确定v是你的祖先还是后代？

我有这个问题.我有一个n个节点的图形,我想分成两个x节点子节点和nx个节点,这些节点受到剩余边数最大化(或最小化被切割边数)的约束.

不确定这是否有意义.不是图论人,但这是我问题的抽象版本.我应该看哪些算法可能对我有帮助？

这不是一个家庭作业问题.虽然我觉得有趣的问题!

我计划在C中实施

我找到了几种解释如何在有向图中找到强连通组件的算法,但没有一种解释为什么你想要这样做.强连接组件的一些应用是什么？

如果图形的两个边共享一个公共顶点,则它们被称为相邻(有时重合).如果第一个的头部位于第二个的头部(凹口端),则有向图的两个箭头被称为连续的.类似地,如果两个顶点共享公共边(如果它们位于箭头的凹口处和箭头处,则是连续的),这两个顶点被称为相邻,在这种情况下,公共边被称为连接两个顶点.该边缘上的边和顶点称为事件.

我不明白这个定义.有人能举一个事件优势的例子吗？示意图将有所帮助.

这只是我自己想出来的东西,但它似乎是一个有趣的问题而且让我难过.

在二维空间中有一组点,其中一个点指定为"开始",一个指定为"结束".每个点都有坐标(以距离原点为单位),但也有"加速度数"(以米 - 秒为单位的Δ-V).到达某个点(包括开始点)后,您可以在任何方向上加速到该点的加速度数.边缘成本取决于您当前的速度,但您还必须朝着正确的方向前进.

是否有一种有效的算法来寻找到达终点的最快路径？我没有提出比"尝试每条路径并检查结果"更好的东西.Djikstra和其他简单的算法不起作用,因为你不能轻易地说中间点的一条路径比另一条路径更好或更差,如果它们以不同的初始速度到达.

如果这太简单了,如果你添加了必须在终点停止的要求怎么办？(即,当你到达终点时,你必须小于它的加速度值.)

编辑:要明确,方向很重要.在遍历图形时保持速度矢量,加速意味着向其添加矢量,其大小以该点的加速度数量为上限.这意味着在哪里建造了一个巨大的速度是有害的,因为你会走得太快,以"引导"对其他宝贵的意见/目的地的情况.

我正在寻找的是一个完整的图遍历算法列表,简要描述了它们的目的,作为研究它们的跳转点.到目前为止我知道:

• Dijkstra的 - 单源最短路径
• Kruskal's - 找到最小的生成树

还有哪些其他众所周知的？请为每个答案提供每种算法的简要说明.

我一直在使用我编写的一个小蟒蛇脚本来管理我的室友之间的债务.它有效,但有一些缺失的功能,其中之一是简化不必要的复杂债务结构.例如,如果下面的加权有向图表示某些人,而箭头表示他们之间的债务(Alice欠Bob 20美元和Charlie $ 5,Bob欠Charlie 10美元,等等):

很明显,该图应简化为下图:

如果爱丽丝可以直接将它交给查理,10美元从艾丽丝到鲍勃,然后从鲍勃到查理,没有任何意义.

那么,在一般情况下,目标是采用债务图并简化它(即生成具有相同节点但不同边缘的新图),以便

1. 没有节点有边缘指向它的内部(没有无用的钱转手)
2. 所有节点都具有与原始图中相同的"流"(它们在资金最终位置方面相同).

通过"流量",我的意思是所有输入的值减去所有输出(这是否有技术术语？我不是图论专家).所以在上面的例子中,每个节点的流量值是:

• 鲍勃:+10
• 爱丽丝:-25
• 查理:+15

您可以看到第一个和第二个图表在每个节点上具有相同的流量,因此这是一个很好的解决方案.还有一些其他简单的情况,例如,可以通过移除最低值边缘并从所有其他边缘减去其值来简化任何循环.

这个:

应简化为:

我无法想象没有人研究过这个问题; 我只是不知道要搜索哪些术语来查找信息(再次,不是图论专家).我一直在寻找几个小时无济于事,所以我的问题是:根据上面针对任何加权有向图指定的条件,什么算法会产生简化(新图)？