Find a path within a specific cost

Question

There are many algorithms or policies for finding a path with minimum or maximum costs. But, it is hard to find an approach that can find a path within (or below) a required cost (RC), i.e., such an RC is not a minimum or maximum one, and the actual cost should less than such an RC.

I am looking for a feasible algorithm to find a path satisfying the two constraints:

1. The cost of such a path should be lower than the required cost.
2. The path from source to destination should contain as many hops as possible.

One example is as specified below, e.g.,

The source is node A, the destination is node B; the required cost is 10. There are three pathes can be found from A to B:

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

Zgodnie z dwoma wymienionymi ograniczeniami, path 2 (A --> C --> D --> B; cost is 8)jest najlepsze, ponieważ koszt wynosi 8, czyli mniej niż wymagany koszt 10, a ścieżka 2 jest dłuższa niż ścieżka 1.

Mam nadzieję, że jasno wyjaśnię moje pytanie. Czy są jakieś wydane algorytmy lub metody rozwiązania tego problemu?

Z góry dziękuję.

Answer 1

Myślę, że nie ma dobrze znanego algorytmu dla tego problemu.

Pokażę ci tylko mój fragment.

#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
*/

Napisałem kod za pomocą prostej metody bfs.

Pisanie informacji o każdym kroku rozwiąże ten problem.

Daj mi znać, jeśli są jakieś przypadki narożne.