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

Question

图中受约束的最短路径问题 G=(V,E)是，给定源节点 s和接收器节点 t , 从s中求出最短路径至 t这样路径上消耗的总资源最多为标量 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在需要新标签时构建结构，并使用成员 next 在链表中显式维护这些标签和 prev的 struct

方法二:

而不是 new荷兰国际集团structs ，我开始将新结构存储在 std::vector 中容器:

vector <labels_s> labels;

为此，自vector提供对各种标签的整数索引访问，prev和 next的 struct labels_s可以改为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 中间插入或从 vector 中删除。

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

我主要关心的是方法 2 的第 3 步。自 push_back()创建 newlabel 的拷贝, 这种复制操作成本高吗？可以避免吗？

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

欢迎任何意见。

Answer 1

在 C++11 中，您可以使用 emplace_back ( cppreference ) 在 vector 末尾的位置构造一个标签。你可以这样做:

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, …);

然后完成。

除此之外，您应该在填充标签 之前慷慨地保留 ( cppreference ) 以避免频繁重新分配。