高效的數據結構

受約束的最短路徑中的曲線圖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; 
};

隨着算法的進行，需要創建和存儲上述許多結構。

方法1：

一個非常早期的實現我的這個是非常低效的計算。這涉及到需要新標籤時的結構，並使用struct的成員next和prev明確地將這些結構保存在鏈接列表中。

方法2：

而不是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同樣的問題計算次。標籤只添加在矢量的末尾。不需要插入矢量的中間或從矢量中刪除。

除方法2之外還有其他管理這些標籤的方法嗎？

我主要關注的是方法2的步驟3。由於push_back()創建了newlabel的副本，此複製操作代價高昂，可以避免這種情況嗎？

我正在考慮的一種替代方法是維護一個指向標籤結構的指針向量，而不是像當前那樣使用標籤結構向量。但是在我看來，維護指向標籤結構的向量應該不如方法1更高效。

任何輸入表示讚賞。

來源

2017-10-07 Tryer

您的「約束最短路徑」聽起來像「首先，對於每個頂點權重，執行：if（weight> max）then weight = max。然後，進行正常的最短路徑搜索」。 ...鑑於此，這可能有助於尋找正常最短路徑問題的解決方案。儘管目前我並沒有掌握Dijkstra的所有細節，但我相當確信動態縮小/增長的矢量是不必要的。 – deviantfan

通常，A *只存儲一個指向前一個節點的指針。 – o11c

由於（全局）開集和閉集，您不必擔心循環，並且您只能從最短節點前進。 – o11c

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

並且完成。

除此之外，您應該在填充labels之前慷慨地提供reserve（cppreference）以避免頻繁重新分配。

來源

2017-10-07 17:11:56 Knoep

這可能正是我所期待的。那麼，根據你的建議，步驟（1和2）和步驟3基本上只能完成一次。在我目前的實現中，第3步基本上是第1步和第2步的重複。使用emplace_back（）;然後我可以只有標籤[labels.size（） - 1] .member1 = xyz;等等？ – Tryer

第3步（臨時變量的複製）不會發生，您直接在矢量中填充標籤，不需要複製。 – Knoep

對不起，沒有注意到編輯。是的，你可以做到這一點。 labels.back（）。member1 = xyz可能會更乾淨，但。編輯更清楚。 – Knoep

高效的數據結構

回答

相關問題