标签: graph-algorithm

我正在寻找具有一些不寻常属性的图算法.

图中的每条边都是"向上"边缘或"向下"边缘.

有效路径可以是无限数量的"向上",然后是无限数量的"向下",反之亦然.然而,它不能多次改变方向.

例如,有效路径可能是A"向上"B"向上"C"向下"E"向下"F无效路径可能是A"向上"B"向下"C"向上"D

找到两个节点之间最短有效路径的好算法是什么？如何找到所有等长的最短路径？

所以我从Android GPS中记录了一些数据,我试图找到这些图的高峰,但我找不到任何具体的东西,也许是因为我不太确定我在寻找什么对于.我找到了一些MatLab函数,但我找不到实际的算法.我需要在Java中执行此操作,但我应该能够翻译其他语言的代码.

正如你所看到的,有许多"迷你峰",但我只想要主要的.

我正在尝试为树木编写一个分而治之的算法.对于除法步骤,我需要一种算法,通过移除节点将给定的无向图G =(V,E)与n个节点和m个边分割成子树.所有子图应具有不包含超过n/2个节点的属性(树应尽可能分割).首先,我尝试以递归方式从树中删除所有叶子以找到最后剩余的节点,然后我尝试在G中找到最长的路径并删除它的中间节点.下面给出的图表显示两种方法都不起作用:

是否有一些工作算法可以满足我的需要(在上述情况下返回节点H).

这与图算法(不是SEO或任何东西)严格相关.我有兴趣知道是否还有其他算法只使用图形结构(不像关键字等内容)来推断？

因此,例如,如果给定一个充满节点的大图,你怎么能做出推断,假设你不知道节点中的值实际意味着什么(例如,pagerank知道谁链接(边缘)给谁,什么都不知道关于内容本身)？

这不是网络搜索所独有的,任何使用图形结构进行推理的东西.

假设我有两组:(n_1,n_2,...)和(m_1,m_2,...)和匹配函数匹配(n,m),它返回0到1之间的值.我想找到两组之间的映射,以满足以下约束:

• 每个元素在相反的集合中必须至多有1个匹配的元素.
• 不匹配的元素将与成本1的虚拟元素配对
• 应用于所有元素时匹配函数的总和是最大的
• 我无法正式表达这一点,但是如果你按照原始顺序排列每个彼此平行的组并在匹配的元素之间画一条线,那么任何一条线都不会交叉.Ex [n_1 < - > m_2,n_2 < - > m_3]是有效的映射,但[n_1 < - > m_2,n_2 < - > m_1]不是.

(我相信前三个是标准加权的二分匹配约束,但我指定它们以防我误解加权二分匹配)

这在指数时间(相对于集合的大小)进行穷举搜索是相对简单的,但我希望多项式时间(理想情况下为O((| n |*| m |)^ 3)或更好)解决方案存在.

我已经在"赋值问题"/"加权二分匹配"上搜索了相当多的数量,并且已经看到了具有不同约束的变体,但没有找到匹配的或者我能够通过这个添加的排序约束减少到一个.你有什么想法我可以解决这个问题吗？或者也许是在多项式时间内无法解决的粗略证明(对于我的目的,减少到NP-complete也会起作用)？

我正在get_connected_components为一个类写一个函数Graph:

def get_connected_components(self):
    path=[]
    for i in self.graph.keys():
        q=self.graph[i]
        while q:
            print(q)
            v=q.pop(0)
            if not v in path:
                path=path+[v]
    return path

我的图是:

{0: [(0, 1), (0, 2), (0, 3)], 1: [], 2: [(2, 1)], 3: [(3, 4), (3, 5)], \
4: [(4, 3), (4, 5)], 5: [(5, 3), (5, 4), (5, 7)], 6: [(6, 8)], 7: [], \
8: [(8, 9)], 9: []}

其中键是节点,值是边缘.我的函数给了我这个连接组件:

[(0, 1), (0, 2), (0, 3), (2, 1), (3, 4), (3, 5), …

我正在研究对应于大数学表达式(数百万个节点)的表达式图实现公共子表达式消除(CSE).

什么算法适合执行此操作？我在互联网上搜索一个易于实现的算法,但我找不到任何东西.如果可能,算法应该具有完整表达图的节点数的线性复杂度.

假设我在二维空间中有一个对象,以及一组我需要该对象访问的点.积分可以随时添加,但不能删除.

我想要的是能够确定我的对象在O(lg(n))时间内的下一个最近点,然后转到它,然后确定下一个最接近的等等.

简单的优先级队列对此不起作用,因为对象正在改变位置,因此每次移动时都需要重新排列队列.我想象的是以某种方式将点分类为BST,但我不确定如何对(x,y)进行排序或者是否可能.

这感觉就像我可以试图解决旅行推销员而没有意识到,如果是这样,我道歉哈哈.

我在想一个算法来解决下面的问题:

由顶点和边组成的给定图.

有N个客户想要从顶点行进到另一个顶点.每个客户需求都需要一个有向边来连接两个顶点.

问题是如何找到满足所有客户要求的最小边数？

有一个简单的例子:

• 客户1想要从顶点a行进到顶点b.
• 客户2想要从顶点b行进到顶点c.
• 客户3想要从顶点a行进到顶点c.

最简单的方法是为每个客户提供优势:

• 边1:顶点a - >顶点b
• 边2:顶点b - >顶点c
• 边3:顶点a - >顶点c

但实际上只需要2个边缘(即边缘1和边缘2)来满足三个客户的要求.

如果客户数量很大,如何找到满足所有客户要求的最小边缘？

有没有算法来解决这个问题？

在n人中," 名人 "被定义为 每个人都知道但不认识任何人的人.问题是识别名人,如果存在的话,只询问表格的问题," 对不起,你知道那边的那个人吗？ "(假设所有的答案都是正确的,甚至那个名人也会也回答.)目标是尽量减少问题的数量.

这个订单的解决方案是否少于明显的解决方案O(n^2)？