問題ステートメントの重要性
何がカウントされているのかは不明です。
- 開始ノードは、少なくとも1つの出力エッジがあるすべてのノードを設定しますか、それとも特定の開始ノード基準がありますか？
- 終了ノードセットは、出力エッジがゼロのすべてのノードのセットですか、それとも少なくとも1つの入力エッジがあるノードが終了ノードになる可能性がありますか？
あいまいさがないように問題を定義します。
推定
ランダムに作成された有向グラフ用に設計された場合、推定は桁違いにずれることがあり、グラフの作成は統計的に非常に歪んでいるか、体系的です。これはすべての推定プロセスに典型的ですが、指数関数的なパターンの複雑さの可能性があるため、グラフで特に顕著です。
2つの最適化ポイント
std :: bitsetモデルは、特定のビットオフセットでビットをテストする命令セットの仕組みのため、ほとんどのプロセッサアーキテクチャのブール値よりも遅くなります。ビットセットは、速度ではなくメモリフットプリントが重要な要素である場合に、より便利です。
ケースを排除するか、控除によって削減することが重要です。たとえば、出力エッジが1つしかないノードがある場合、それがないパスの数を計算し、サブグラフのパスの数に、それが指すノードからのパスの数を追加できます。
クラスターに頼る
問題は、開始ノードに従って分散することにより、クラスター上で実行できます。いくつかの問題は単にスーパーコンピューティングを必要とします。1,000,000個の開始ノードと10個のプロセッサーがある場合、各プロセッサーに100,000個の開始ノードケースを配置できます。上記のケースの削除と削減は、ケースを配布する前に行う必要があります。
典型的な深さ優先再帰とそれを最適化する方法
これは、基本的な深さ優先、任意のノードから任意のノードへの非周期的トラバーサルを提供する小さなプログラムです。これは、変更、ループへの配置、または分散が可能です。最大データセットサイズがわかっている場合は、サイズを1つのパラメーターとして持つテンプレートを使用して、リストを静的ネイティブ配列に配置できます。これにより、反復とインデックス作成の時間が短縮されます。
#include <iostream>
#include <list>
class DirectedGraph {
private:
int miNodes;
std::list<int> * mnpEdges;
bool * mpVisitedFlags;
private:
void initAlreadyVisited() {
for (int i = 0; i < miNodes; ++ i)
mpVisitedFlags[i] = false;
}
void recurse(int iCurrent, int iDestination,
int path[], int index,
std::list<std::list<int> *> * pnai) {
mpVisitedFlags[iCurrent] = true;
path[index ++] = iCurrent;
if (iCurrent == iDestination) {
auto pni = new std::list<int>;
for (int i = 0; i < index; ++ i)
pni->push_back(path[i]);
pnai->push_back(pni);
} else {
auto it = mnpEdges[iCurrent].begin();
auto itBeyond = mnpEdges[iCurrent].end();
while (it != itBeyond) {
if (! mpVisitedFlags[* it])
recurse(* it, iDestination,
path, index, pnai);
++ it;
}
}
-- index;
mpVisitedFlags[iCurrent] = false;
}
public:
DirectedGraph(int iNodes) {
miNodes = iNodes;
mnpEdges = new std::list<int>[iNodes];
mpVisitedFlags = new bool[iNodes];
}
~DirectedGraph() {
delete mpVisitedFlags;
}
void addEdge(int u, int v) {
mnpEdges[u].push_back(v);
}
std::list<std::list<int> *> * findPaths(int iStart,
int iDestination) {
initAlreadyVisited();
auto path = new int[miNodes];
auto pnpi = new std::list<std::list<int> *>();
recurse(iStart, iDestination, path, 0, pnpi);
delete path;
return pnpi;
}
};
int main() {
DirectedGraph dg(5);
dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(0, 3);
dg.addEdge(1, 3);
dg.addEdge(1, 4);
dg.addEdge(2, 0);
dg.addEdge(2, 1);
dg.addEdge(4, 1);
dg.addEdge(4, 3);
int startingNode = 0;
int destinationNode = 1;
auto pnai = dg.findPaths(startingNode, destinationNode);
std::cout
<< "Unique paths from "
<< startingNode
<< " to "
<< destinationNode
<< std::endl
<< std::endl;
bool bFirst;
std::list<int> * pi;
auto it = pnai->begin();
auto itBeyond = pnai->end();
std::list<int>::iterator itInner;
std::list<int>::iterator itInnerBeyond;
while (it != itBeyond) {
bFirst = true;
pi = * it ++;
itInner = pi->begin();
itInnerBeyond = pi->end();
while (itInner != itInnerBeyond) {
if (bFirst)
bFirst = false;
else
std::cout << ' ';
std::cout << (* itInner ++);
}
std::cout << std::endl;
delete pi;
}
delete pnai;
return 0;
}