标签: graph-algorithm

流行语言（如Java、C#、Ruby、JavaScript等）中是否有某种成熟的非三列行问题算法？

谢谢。

对于具有负权重的有向图 G(V,E)，我搜索了一些类似的主题，似乎贝尔曼福德可以检测负循环。但是一旦发现负循环就停止了，那么在这种情况下我们如何列出所有负循环呢？

考虑到埃里克·利珀特的建议，我尝试删除从图中发现的负循环，但我觉得这是不正确的，为什么？因为循环被删除后图形会发生变化，并且旧图形中可能存在额外的非负循环，但在新图形中不会找到。有人可以帮助我理清这个问题吗？

这可以用 java 或 c# 实现（不过我更喜欢 c#）

谢谢

我正在学习 A* 路径查找算法，我找到的所有示例都是基于网格的。因此，它们的所有启发式函数都依赖于某种物理距离（即基于曼哈顿的距离、对角线距离或欧几里德距离）。

但是如果我们用自由图形代替网格怎么办？说下面的例子，哪里S是起点，哪里G是目标：

S---A
|   
|   G
|   |
B---C---D

在这种情况下，“如乌鸦飞翔”的近似值没有意义，因为该图与

S---A
|   
B---C---D
    |
    G

那么在这种情况下我可以使用什么样的启发式函数呢？

这些图片显示了像像素网格一样排列的节点图，具有直行和直列。每个节点（除了边上的节点）都有 8 条边，这些边都指向其周围最近的 8 个节点。右图显示了 A* 搜索，其中包含简单的行驶距离 + 目标启发式欧几里德距离。

现在，我说右图给出的路径不够好。相反，我想要一条如果您使用最短的字符串连接起始节点和目标节点时会得到的路径。调用该函数的算法是什么？

最大流问题通常通过edmond-karp算法来解决，该算法构建残差图，并使用BFS寻找增广路径。

但通常最大流问题是为加权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。

我有一个有n 个节点的连通无向图。给定两个节点，我想找到必须删除的最小边数，以确保这两个节点之间只有一条无循环路径。

例如，如果这是图表：

1------------2------------5
|                         | 
|                         | 
3-------------------------4

那么给定节点1和5，答案将是1：只需删除（例如）节点 3 和节点 4 之间的边。

暴力方法是，对于边集的每个子集，尝试删除这些边并测试两个感兴趣的节点之间是否存在唯一的无循环路径。

有更有效的方法吗？（我用谷歌搜索过，但没有找到任何相关内容。）

（亲爱的 cryptomanic，我添加这些示例是为了帮助讨论确切的要求；请编辑此部分并指出这些解决方案中哪些是有效的。m69）

输入图：（从X到Y）

          O---O---O---O       O
         /     \ /     \     / \
O---O---X       O       Y---O---O
         \             /
          O---O---O---O
             / \       \
            O---O       O

解决方案A：（X和Y之间没有循环）

          O---O---O---O       O
         /       /     \     / \
O---O---X       O       Y---O---O
                       /
          O---O---O---O
             / \       \
            O---O       O

解决方案 B：（X 和 Y 之间没有旁路）

          O---O---O---O       O
         /             \     / \
O---O---X       O       Y---O---O
                       /
          O---O---O---O …

我有一个城市区域（让我们将其视为街道图），其中所有街道都有一些与之相关的权重和长度。我想要做的是找到一组连接的街道，位于其他街道附近，具有最大（或接近最大）总权重 W，因为我的最大子图最多只能包含 N 个街道。

我特别对跨越整个图表的子图不感兴趣，而只对一小群具有最大或接近最大组合权重的街道感兴趣，并且所有街道都彼此“靠近”，其中“附近”将定义为距离集群中心不超过 X 米的街道。生成的子图必须连接起来。

有谁知道这个算法的名称是否存在（假设它存在）？

也对任何解决方案感兴趣，无论是精确的还是近似的。

为了直观地显示这一点，假设我的图表是下图中的所有街道路段（十字路口到十字路口）。因此，个别街道不是 A 大道，而是 10 号和 11 号之间的 A 大道，依此类推。街道的权重为 1 或 0。假设权重最大的街道集位于选定的多边形中 - 我想要做的是找到该多边形。

给你一个整数 N。你必须找到 N 的最小倍数，它只由数字 0 和 1 组成。由于这个倍数可能很大，所以以字符串的形式返回它。

返回的字符串不应包含前导零。

例如，

对于 N = 55，110 是由数字 0 和 1 组成的最小倍数。对于 N = 2，10 是答案。

我看到了几个相关的问题，但我找不到我的代码的问题。这是我的代码，即使在使用 map 而不是 set 之后，在某些情况下也会给出 TLE。

#define ll long long
int getMod(string s, int A)
{
    int res=0;
    for(int i=0;i<s.length();i++)
    {
        res=res*10+(s[i]-'0');
        res%=A;
    }
    return res;
}
string Solution::multiple(int A) {
    if(A<=1)
    return to_string(A);

    queue<string>q;
    q.push("1");
    set<int>st;
    string s="1";

    while(!q.empty())
    {
        s=q.front();
        q.pop();
        int mod=getMod(s,A);
        if(mod==0)
        {
            return s;
        }
        else if(st.find(mod)==st.end())
        {
            st.insert(mod);
            q.push(s+"0");
            q.push(s+"1");
        } …

在一本著名的算法书中，提到广度优先搜索是一种贪婪算法。但我搜索了它，但发现很多链接都没有这么说。

我的问题：广度优先搜索是贪婪算法吗？为什么？

你能为我的答案提供一个值得注意的参考吗？

我得到一个有向无环图 G = (V,E)，可以假设它是拓扑有序的（如果需要）。G 中的边有两种类型的成本 - 名义成本 w(e) 和尖峰成本 p(e)。

目标是找到从节点 s 到节点 t 的最短路径，使以下成本最小化：sum_e (w(e)) + max_e (p(e))，其中在所有边上取和和最大值小路。

标准的动态规划方法表明这个问题可以在 O(E^2) 时间内解决。有没有更有效的方法来解决它？理想情况下，O(E*polylog(E,V)) 算法会很好。

- - 编辑 - - -

这是我使用动态规划找到的 O(E^2) 解决方案。

首先，按升序排列所有成本 p(e)。这需要 O(Elog(E)) 时间。

其次，定义由状态 (x,i) 组成的状态空间，其中 x 是图中的一个节点，i 在 1,2,...,|E| 中。它表示“我们在节点 x 中，到目前为止我们看到的最高边权重 p(e) 是第 i 个最大的”。

设 V(x,i) 是从 s 到 x 的最短路径（在经典意义上）的长度，其中遇到的最高 p(e) 是第 i 个最大的。给定 V(y,j) 对于 x 的任何前驱 y 和 1,...,|E| 中的任何 j，计算 V(x,i) 很容易 （有两种情况需要考虑 - 边 y->x 具有第 j 个最大权重，或者没有）。

在每个状态 …