在特定成本内找到路径

Question

有许多算法或策略可用于查找成本最低或最高的路径。但是，很难找到一种方法可以找到在（或以下）所需成本 (RC) 内的路径，即这样的 RC 不是最小值或最大值，并且实际成本应该低于这样的RC。

我正在寻找一种可行的算法来找到满足两个约束的路径：

这样一条路径的成本应该低于所需的成本。
从源到目的地的路径应包含尽可能多的跃点。

一个例子如下，例如，

源为A节点，目的为B节点；所需费用为10。从A到B可以找到3条路径：

 1. A --> C --> B;               cost is 5
 2. A --> C --> D --> B;         cost is 8
 3. A --> C --> D --> E --> B;   cost is 12

根据两个提到的约束条件，path 2 (A --> C --> D --> B; cost is 8)是最好的，因为成本是 8，小于所需的成本 10，路径 2 比路径 1 长。

希望我清楚地解释我的问题。是否有任何已发布的算法或方法来解决此问题？

提前谢谢你。

Answer 1

我不认为有 well-known 这个问题的算法。

让我给你看我的片段。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

class info
{
    public:
        int hopcount;
    vector<int> path;
    int cost;
};

int main()
{
    int n;
    int s, e;
    vector<vector < int>> arr;
    cin >> n;
    arr.resize(n + 1);
    for (int i = 1; i <= n; i++)
    {
        arr[i].resize(n + 1);
    }
    cin >> s >> e;
    int pc;
    cin >> pc;
    for (int i = 0; i < pc; i++)
    {
        int source, def, cost;
        cin >> source >> def >> cost;
        arr[source][def] = cost;
    }
    int maxcost;
    cin >> maxcost;
    queue<info> q;
    q.push({1, {s}, 0 });
    int maxhopcount = -1;
    vector<int> hoppath;
    while (!q.empty())
    {
        auto qel = q.front();
        q.pop();
        int currentN = qel.path[qel.path.size() - 1];
        if (currentN == e)
        {
            if (qel.hopcount > maxhopcount)
            {
                maxhopcount = qel.hopcount;
                hoppath = qel.path;
            }
        }
        for (int i = 1; i <= n; i++)
        {
            int sign = 0;
            for (auto c: qel.path)
            {
                if (c == i)
                {
                    sign = 1;
                    break;
                }
            }
            if (sign == 1) continue;
            if (arr[currentN][i] > 0)
            {
                info ni = qel;
                ni.path.push_back(i);
                ni.hopcount += 1;
                ni.cost += arr[currentN][i];
                if (ni.cost <= maxcost)
                {
                    q.push(ni);
                }
            }
        }
    }
    cout << maxhopcount << endl;
    for (auto c: hoppath)
    {
        cout << c << " ";
    }
    return 0;
}
/*
testcases
5
1 2
6
1 3 2
3 2 3
3 4 3
4 2 3
4 5 4
5 2 3
10

1 3 4 2
4
*/

我用简单的 bfs 方法写了一个代码。

写下每一步的信息就可以解决这个问题。

如果有任何极端情况，请告诉我。

在特定成本内找到路径

Find a path within a specific cost

algorithm

routes

graph

dijkstra