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

标签 c++ algorithm vector struct graph-algorithm

图中受约束的最短路径问题 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 在链表中显式维护这些标签和 prevstruct

方法二:

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

vector <labels_s> labels;

为此,自vector提供对各种标签的整数索引访问,prevnextstruct 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 更有效。

欢迎任何意见。

最佳答案

在 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 ) 以避免频繁重新分配。

关于c++ - 用于在图中查找约束最短路径的高效数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46622722/

相关文章:

c++ - move 语义 std::move

c++ - OpenCV 的 Python 或 C++ 编码之间的性能是否不同?

python - 从一个列表中删除另一个列表的元素,同时保留重复项

将巧克力 block 等分的算法

c++ - 使用类的 vector

java - Java的Vector如何添加原始数组?

c++ - Visual Studio 中 C++ 代码的变量依赖关系图

有序分区集的算法

vector - OpenLayers 矢量层特征处理程序

c++ - dll中静态成员变量的生存期