c++ - 在具有附加条件的图中找到最小加权路径

Question

我遇到了如下问题，我真的被它困住了，因为它运行的时间超过了我想要的时间(大约 1 秒)。我真的希望你能帮助我建立一个比我的更高效的算法

Given an undirected graph G = (V, E) with two parameter of weights w1 and w2 for each edges. This graph has N vertices and M edges. A K-Elementary path S is a sub-graph of G which must be an elementary graph and it does have exactly K edges.

Find a K-elementary path S with the sum of w1 of all edges as minimum value and the sum of w2 of all edges of S must be smaller than a given value Q. If it does not exist any path satisfied, print out the value -1

Input:

The first line with four values N, M, K, Q (2 <= N, K <= 50, 1 <= M <= 2*N, 1 <= Q <= 10^9)

The next M lines show the edges of the graph: V1 V2 W1 W2 (1 <= V1, V2 <= N, 1 <= W1 <= 10^4, 1 <= W2 <= 10^4)

Output: One integer to show the minimum weight of the k-elementary graph found. -1 if non-exists

Sample test case:

Input:

5 7 3 6
1 2 1 2
1 4 2 2
1 5 3 6
2 3 3 2
2 4 4 4
3 4 5 1
4 5 4 7

Output:

6

首先，我想引用一个elementary path的定义.

简而言之，对于这个问题，我们需要找到一条 k 基本路径 S，使得到 w1 的权重最小，到 w2 的所有边的总和小于或等于 Q，并且它确实有 K 条边.

我确实有一种回溯方法，我尝试构建所有满足第二个条件 (w2) 的图，然后找到第一个条件 (w1) 的最小值，但是，如您所知，时间复杂度是相当高。但是，我发现很难将其转换为动态规划或任何其他方法来降低时间复杂度。我确实添加了一些 Branch-bound 条件，但它仍然很慢。

下面是我的源代码，你可以引用，但我认为它没有用

#include <bits/stdc++.h>
using namespace std;
#define N 51
#define INF 1e9
int n, m, K, Q;
bool appear[N];
int W1[N][N];
int W2[N][N];
int currentSum1 = 0;
int currentSum2 = 0;
int source = 0;
int res = INF;
int Log[N];
int minElement = INF;
bool check(int k, int v)
{
    return !appear[v] && W1[Log[k - 1]][v] != 0 && W2[Log[k - 1]][v] != 0;
}
void solution()
{
    if(currentSum1 != 0 && currentSum1 < res)
    {
        res = currentSum1;
        // for(int i = 0; i <= K; i++)
        //     cout << Log[i] << " ";
        // cout << endl;
    }
}
void solve(int k)
{
    for(int v = 1; v <= n; v++)
    {
        if(check(k, v) && currentSum2 + W2[source][v] <= Q && currentSum1 + (K - k) * minElement <= res) //Branch-bound condition
        {
            Log[k] = v;
            currentSum2 += W2[Log[k - 1]][v];
            currentSum1 += W1[Log[k - 1]][v];
            appear[v] = true;
            if(k == K)
                solution();
            else
                solve(k + 1);
            currentSum1 -= W1[Log[k - 1]][v];
            currentSum2 -= W2[Log[k - 1]][v];
            appear[v] = false;
        }
    }
}
int main()
{
    fast;
    // freopen("data.txt", "r", stdin);
    cin >> n >> m >> K >> Q;
    for(int i = 0; i < m; i++)
    {
        int x, y, w1, w2;
        cin >> x >> y >> w1 >> w2;
        minElement = min(minElement, w1);
        W1[x][y] = w1;
        W1[y][x] = w1;
        W2[x][y] = w2;
        W2[y][x] = w2;
    }
    for(int v = 1; v <= n; v++)
    {
        source = v;
        currentSum2 = 0;
        currentSum1 = 0;
        Log[0] = v;
        for(int i = 1; i <= n; i++)
            appear[i] = false;
        appear[source] = true;
        solve(1);
    }
    if(res != INF)
        cout << res << endl;
    else 
        cout << -1 << endl;
}

Answer 1

首先，寻找资源受限的最短路径是 NPHard。大多数解决此问题的方法都采用标记方案，这是动态规划的一个特例。您可以使用可用的库来完成此操作。参见 here用于提升实现。只要所有 w_2 权重都是正数，此实现将帮助您找到(可能)从 s 到 t 的非基本路径。如果权重 w_2 为负数，则权重 w_1 为负数且 Q 为正数时，问题可能是无界的。

现在，谈到对 k 初等最短路径的需求，据我所知，没有现成的算法可以帮助实现这一点。首先，忘记 k。可以使用上面 boost 链接中提到的论文中提供的标记方案来找到受额外资源限制的基本最短路径。在这种情况下，动态程序的状态空间应该增加以允许存储路径中所有先前访问过的节点的指示 vector 。与基本的资源受限最短路径问题相比，这使得问题更难解决。

现在，为了满足您对 k 基本最短路径的需求，必须将上述以递归方式查找基本最短路径的方案嵌入到另一个函数中，该函数不断检查返回的基本路径是否具有 k 条边。如果它确实有 k 个边，那么你就完成了。否则，您将不得不以某种方式对算法施加限制以阻止此特定路径。这可以通过使用预标签来实现。据我所知，这是在 this 中首次完成的工作。

祝你好运，但这个问题是双重/三重困难的(因为可能需要多次迭代)。您应该引用 boost 链接中提到的工作以及该领域的后续论文，以了解最先进的技术。我怀疑最先进的技术无法解决超过 10-15 个节点的问题。