用于在图中查找约束最短路径的高效数据结构

Question

图G=(V,E)中的约束最短路径问题是，给定源节点s和汇节点t，找到从s到[=的最短路径14=] 这样路径上消耗的总资源至多为标量 R。图中的每个弧线 (i,j) 都有一个成本，标量 c_{ij} 并用尽资源以达到标量 r_{ij} 的调谐。路径的成本是构成路径的各个弧的成本之和，路径消耗的资源是构成路径的各个弧的资源之和。此问题已知为 NP-HARD。

解决此问题的大多数实现都使用动态规划方法，该方法本质上是一种蛮力枚举以及其他巧妙的探索方法，以减少完成的搜索量。

动态编程是使用 labelling approach 实现的。

我已经使用几种不同的方法实现了这个算法，我想确保我是否尽可能高效地执行它。

标签方法创建多个标签，这些标签本质上是从 s 到其他各种节点的部分路径。算法过程中会创建大量标签（注意，问题是 NP HARD），直到满足停止条件。

每个标签都可以表示为一个struct，如下所示。

struct labels_s {
    double current_states[10];
    double unscanned_states[10];
    int already_visited[100];//If node i is already visited on partial path, already_visited[i] = 1, else 0
    int do_not_visit[100];//if node i is not to be visited from this label, do_not_visit[i] = 1; 0 otherwise
    struct labels_s* prev;
    struct labels_s* next;
};

随着算法的进行，需要创建和存储上述许多结构。

方法一：

我很早就实现了这个，计算效率非常低。这涉及 new 在需要新标签时构建结构，并使用 struct 的成员 next 和 prev 在链表中显式维护这些结构。

方法二：

我开始将新结构存储在 std::vector 容器中，而不是 newing structs：

vector <labels_s> labels;

为此，由于 vector 提供对各种标签的整数索引访问，struct labels_s 的 prev 和 next 可以更改为 int prev;和 int next;

存储标签涉及以下内容：

struct labels_s newlabel;//Step 1
//populate newlabel's members//Step 2
labels.push_back(newlabel);//Step 3

使用方法 2 对同一问题的计算时间明显优于 方法 1。标签仅添加在向量的末尾。不需要在vector中间插入，也不需要从vector中删除。

除了方法 2 之外，还有其他管理这些标签的方法吗？

我主要关心的是方法 2 的第 3 步。由于 push_back() 创建了 newlabel 的副本，此复制操作是否成本高昂且可以避免？

我正在考虑的一个替代方案是维护一个指向标签结构的指针向量，而不是像我目前所做的那样维护标签结构向量。但在我看来，维护指向标签结构的指针向量应该不会比 方法 1.

更有效

欢迎任何意见。

Answer 1

在 C++11 中，您可以使用 emplace_back (cppreference) 在向量末尾就地构造标签。你可以这样做：

labels.emplace_back();  // default construct a new label at the end of labels
// then populate members like this:
labels.back().member1 = val1;

根据您的用例，您还可以为 labels_s 创建一个构造函数，它获取成员的所有值并对其进行初始化。在这种情况下你可以写

labels.emplace_back(val1, val2, …);

完成。

除此之外，您应该 reserve (cppreference) 在填充 labels 之前慷慨地避免频繁重新分配。

用于在图中查找约束最短路径的高效数据结构

Efficient data structure for finding constrained shortest path in a graph

c++

algorithm

struct

vector

graph-algorithm