标签: graph-algorithm

请考虑以下图表:

由以下数组结构表示:

$graph = array
(
    'a' => array(),
    'b' => array('a'),
    'c' => array('a', 'b'),
    'd' => array('a'),
    'e' => array('d'),
    'f' => array('a', 'b', 'c', 'd'),
    'g' => array('d'),
    'h' => array('c'),
    'i' => array('c', 'g'),
    'j' => array(),
);

在没有重复节点的情况下,在任一方向上从节点X到节点Y 查找所有路径(不仅是最短路径)的最有效算法是什么？例如,从节点到节点的路径是:CA

C --> A
C --> B --> A
C --> F --> A
C --> F --> B --> A
C --> F --> D --> A
C --> I --> …

如果你有一个图形,并且需要找到它的直径(这是两个节点之间的最大距离),你怎么能在O(log v * (v + e))复杂性上做到这一点.

维基百科说,你可以用这个做Dijkstra's algorithm了binary heap.但我不明白这是如何工作的.有人可以解释一下吗？

或者显示伪代码？

我正在尝试使用dijkstra算法进行最短路径查找,但似乎无法正常工作.无法弄清问题是什么.这是代码和错误消息.(我正在研究Python 3.5.https ://www.youtube.com/watch?v=LHCVNtxb4ss)

graph = {
    'A': {'B': 10, 'D': 4, 'F': 10},
    'B': {'E': 5, 'J': 10, 'I': 17},
    'C': {'A': 4, 'D': 10, 'E': 16},
    'D': {'F': 12, 'G': 21},
    'E': {'G': 4},
    'F': {'E': 3},
    'G': {'J': 3},
    'H': {'G': 3, 'J': 3},
    'I': {},
    'J': {'I': 8},
}

def dijkstra(graph, start, end):
    D = {}
    P = {}
    for node in graph.keys():
        D[node]= -1
        P[node]=""
    D[start]=0
    unseen_nodes=graph.keys()
    while len(unseen_nodes) > 0:
        shortest=None
        node=' '
        for …

我有一个有向图(N, A),每个节点n[i]都有一个值v[i]和一个阈值t[i].对于每个箭头(n[i], n[j]),不变量v[i] <= v[j]成立.我需要有效地实现以下操作:

• increaseThreshold(i, x):设置t[i] = max(t[i], x).这是微不足道的,只是为了完整性.
• increaseValue(i, x):v[i] = max(v[i], x)根据需要设置和增加其他值,以便保持上述不变量.
• evaluate(i):如果返回true v[i] < t[i]

最简单的实现将存储v[i],t[i]以及每个节点的传出箭头.在increaseValue(i, x),它会沿着所有传出箭头传播值(使用一组"开放"节点,就像许多其他图形算法一样).v[i]与每个节点一起存储,evaluate(i)是微不足道的.

由于increaseValue比其他操作更频繁,这种急切的方法似乎是浪费.所以我想知道,如果v[i]根据需要重新计算一些惰性传播可能会更有效.对于这一点,我想保持w[i]作为最大的是x来自increaseValue(i, x)和计算v[j]时的飞行evaluate(j)需要它.它可以计算为有路径的w[i]所有节点的最大值.实际上,一旦我知道,确切的值无关紧要,我可以停止计算.n[i]n[j]v[j] >= t[j]v[j]

不幸的是,这种惰性算法的效率非常低,因此即使increaseValue频率高于数量级,它也不会得到回报evaluate.

我想,一些"部分懒惰"的算法可能会更好,但这只是我的直觉,我无法用它取得任何进展. …

我必须制作一个程序,它将说明图形是否可着色 - 基本上我必须检查色度指数是d还是d + 1,其中d是所有顶点的最大度数(vizing定理).我知道这个问题是NP完全的,基本上它必须是强制性的.我有一个想法,但不知道它是否正确 -

1)找到具有deg(v)= d的顶点并用v与d区分颜色的所有边缘着色.

2)对于与v相邻的顶点入射的所有边,从d组颜色中应用一些颜色

3)重复2)"发现"边缘

如果所有边缘都用d颜色着色,则色度指数为d,并且我有一个图G的着色.

如果某些边缘不能用d颜色的颜色着色,那么用d + 1-st颜色为颜色设置颜色,用d + 1颜色设置颜色剩余边缘颜色 - 这是问题 - 使用这个方案,如果我宣称色度指数为d + 1,是否有可能与其他一些着色色度指数为d？(对于每个要着色的边缘,我选择一种可以使用的颜色)

此外,哪个图形表示最适合此问题？在输入文件中,图形写在邻接矩阵中.我知道它可以通过递归来解决,但我不知道如何.我坚持一些太复杂的想法:S(一些提示或伪代码将被赞赏).

编辑:

只是想到了我的想法,我觉得它应该没问题(纯粹的暴力).我还没有尝试实现这个.如果你看错了,请评论.再说一遍 - 算法应检查图形是否可用d或d + 1颜色进行边缘着色,其中d是给定简单图形中所有顶点的最大度数,并找到一个着色...

colorEdge(edge, color, extra) {
    if (edge colored) return;  //if already colored, return
    if (can be colored in color) color it; //if color can be applied, apply it
    else {
        //else, 'd+1'-st color neded, so color it with that color, continue finding 
        //coloring with d+1 colors
        extra = true; 
        color it in …

我的问题很简单,但我真的不知道它的名字,因此,很难找到自己的解决方案:如何简化依赖图(如(->取决于)):

A - > B - > C&A - > C.

至

A -> B -> C 

我需要为庞大的数据集找到连接的组件.(图形未指向)

一个显而易见的选择是MapReduce.但我是MapReduce的新手,我很安静,没时间去挑选它并自己编写代码.

我只是想知道是否有任何现有的API,因为它是社交网络分析中一个非常常见的问题？

或者至少如果有人知道任何可靠(经过试验和测试)的来源,至少我可以自己开始实施吗？

谢谢

给定未加权无向图的邻接矩阵,是否有一种有效的方法(多项式算法)来扩展/增加任何给定的两个节点s和t之间的最短路径的长度？

例:

在下面的例子中,从顶点s = 1到顶点t = 5有5个不同的"最短路径",每个都有3个长度.我想删除最少数量的边缘,以便最短路径长度被强制为4或更多.(断开图表是可以的.)

邻接矩阵(扩展以纠正示例):

 0 1 0 0 0 1 1 1 0 1 0 
 1 0 1 1 0 0 0 0 0 0 0  
 0 1 0 0 1 0 0 0 0 0 1 
 0 1 0 0 1 1 0 0 0 0 0  
 0 0 1 1 0 1 0 0 0 0 0 
 1 0 0 1 1 0 0 0 1 0 0 
 1 0 0 0 0 0 …

克隆树的算法非常简单,我们可以为此预先遍历遍历.是否有一种有效的算法来克隆图形？

我尝试了类似的方法,并得出结论,我们需要维护已添加到新图中的节点的哈希映射,否则会有重复的节点,因为一个节点可以有许多父节点.

因此，我使用 UCT 在蒙特卡罗树搜索算法中实现了转置表。这允许保持游戏状态的累积奖励值，无论在整个树中在何处以及多少次遇到它。这提高了收集到的特定游戏状态信息的质量。

唉，我注意到这给 UCT 的开发与探索选择阶段带来了某些问题。简而言之，分配给某个州的 UCT 分数会考虑访问父州的次数与访问子州（我们为其计算 UCT 分数）的次数之间的比率。从这张图中可以看出，当将状态从转置表拉入树的新创建的分支时，该比率完全不正常，子状态已被访问大量次（从树中的其他位置）并且父状态已被访问被访问的次数要少得多，这在技术上应该是不可能的。

因此，使用换位表并保留状态的累积奖励值有助于算法的利用部分做出更好的选择，但同时它会以潜在有害的方式扭曲算法的利用部分。您知道有什么方法可以解决这个意外问题吗？