任意の 2 つの頂点間のすべての接続を検索するグラフ アルゴリズム
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
以下で説明するタスクを達成するために、最も時間効率の良いアルゴリズムを決定しようとしています。
私は一連の記録を持っています。このレコードのセットには、このセットのレコードのペアがどのように相互に接続されているかを示す接続データがあります。これは基本的に、レコードが頂点、接続データがエッジである無向グラフを表します。
セット内のすべてのレコードには接続情報があります (つまり、孤立したレコードは存在しません。セット内の各レコードは、セット内の 1 つ以上の他のレコードに接続されます)。
セットから任意の 2 つのレコードを選択し、選択したレコード間のすべての単純なパスを表示できるようにしたいと考えています。「単純なパス」とは、パス内に繰り返しレコードがないパスを意味します（つまり、有限パスのみ)。
注記：選択された 2 つのレコードは常に異なります (つまり、開始頂点と終了頂点が同じになることはありません。サイクルはありません）。
例えば：
If I have the following records:
A, B, C, D, E
and the following represents the connections:
(A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
(C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)
[where (A,B) means record A connects to record B]
開始レコードとして B を選択し、終了レコードとして E を選択した場合、レコード B をレコード E に接続するレコード接続を介したすべての単純なパスを検索する必要があります。
All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E
これは一例であり、実際には、数十万のレコードを含むセットが存在する可能性があります。
解決
これはグラフの深さ優先検索で実現できるようです。 深さ優先検索では、2 つのノード間のすべての非循環パスが検索されます。 このアルゴリズムは非常に高速であり、大きなグラフに対応できる必要があります (グラフ データ構造は疎であるため、必要な量のメモリのみを使用します)。
上で指定したグラフには、方向 (B、E) のエッジが 1 つだけあることに気付きました。これはタイプミスでしょうか、それとも本当に有向グラフなのでしょうか?このソリューションは関係なく機能します。申し訳ありませんが、C 言語ではそれができませんでした。私はその分野が少し苦手です。ただし、この Java コードはそれほど問題なく翻訳できると思います。
グラフ.java:
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class Graph {
private Map<String, LinkedHashSet<String>> map = new HashMap();
public void addEdge(String node1, String node2) {
LinkedHashSet<String> adjacent = map.get(node1);
if(adjacent==null) {
adjacent = new LinkedHashSet();
map.put(node1, adjacent);
}
adjacent.add(node2);
}
public void addTwoWayVertex(String node1, String node2) {
addEdge(node1, node2);
addEdge(node2, node1);
}
public boolean isConnected(String node1, String node2) {
Set adjacent = map.get(node1);
if(adjacent==null) {
return false;
}
return adjacent.contains(node2);
}
public LinkedList<String> adjacentNodes(String last) {
LinkedHashSet<String> adjacent = map.get(last);
if(adjacent==null) {
return new LinkedList();
}
return new LinkedList<String>(adjacent);
}
}
検索.java:
import java.util.LinkedList;
public class Search {
private static final String START = "B";
private static final String END = "E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "E"); // this is the only one-way connection
graph.addEdge("B", "F");
graph.addEdge("C", "A");
graph.addEdge("C", "E");
graph.addEdge("C", "F");
graph.addEdge("D", "B");
graph.addEdge("E", "C");
graph.addEdge("E", "F");
graph.addEdge("F", "B");
graph.addEdge("F", "C");
graph.addEdge("F", "E");
LinkedList<String> visited = new LinkedList();
visited.add(START);
new Search().depthFirst(graph, visited);
}
private void depthFirst(Graph graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
if (node.equals(END)) {
visited.add(node);
printPath(visited);
visited.removeLast();
break;
}
}
for (String node : nodes) {
if (visited.contains(node) || node.equals(END)) {
continue;
}
visited.addLast(node);
depthFirst(graph, visited);
visited.removeLast();
}
}
private void printPath(LinkedList<String> visited) {
for (String node : visited) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
プログラム出力:
B E
B A C E
B A C F E
B F E
B F C E
他のヒント
これが私が思いついた擬似コードです。これは特定の擬似コード方言ではありませんが、理解できるほど単純なものである必要があります。
誰でもこれを区別したいと思います。
[p] は、現在のパスを表す頂点のリストです。
[x] は条件を満たすパスのリストです。
[s] はソース頂点です
[d] は目的の頂点です
[c] は現在の頂点 (PathFind ルーチンの引数) です。
隣接する頂点を検索する効率的な方法があると仮定します (6 行目)。
1 PathList [p]
2 ListOfPathLists [x]
3 Vertex [s], [d]
4 PathFind ( Vertex [c] )
5 Add [c] to tail end of list [p]
6 For each Vertex [v] adjacent to [c]
7 If [v] is equal to [d] then
8 Save list [p] in [x]
9 Else If [v] is not in list [p]
10 PathFind([v])
11 Next For
12 Remove tail from [p]
13 Return
既存の非再帰的 DFS 実装は次のとおりです。 この答え 壊れているようです。実際に動作するものを提供しましょう。
私はこれを Python で書きました。これは非常に読みやすく、実装の詳細が整理されているためです (また、便利な機能があるため)。 yield 導入のためのキーワード 発電機) ですが、他の言語に移植するのはかなり簡単です。
# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
# get a list of the neighbors of the current node
neighbors = graph[current]
# find the next unvisited neighbor of this node, if any
while i < len(neighbors) and neighbors[i] in visited: i += 1
if i >= len(neighbors):
# we've reached the last neighbor of this node, backtrack
visited.remove(current)
if len(nodestack) < 1: break # can't backtrack, stop!
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
# yay, we found the target node! let the caller process the path
yield nodestack + [current, end]
i += 1
else:
# push current node and index onto stacks, switch to neighbor
nodestack.append(current)
indexstack.append(i+1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0
このコードは 2 つの並列スタックを維持します。1 つは現在のパス内の以前のノードを含み、もう 1 つはノード スタック内の各ノードの現在の隣接ノードのインデックスを含みます (これにより、ノードをスタックからポップバックしたときにノードの隣接ノードの反復を再開できるようになります)。(ノード、インデックス) ペアの単一スタックを同様に使用することもできましたが、2 スタック方式の方が読みやすく、おそらく他の言語のユーザーにとって実装が簡単であると考えました。
このコードでは別の visited set には、現在のノードとスタック上のすべてのノードが常に含まれており、ノードがすでに現在のパスの一部であるかどうかを効率的に確認できます。あなたの言語が効率的なスタックのようなプッシュ/ポップ操作を提供する「順序付きセット」データ構造を持っている場合 そして 効率的なメンバーシップ クエリを使用すると、それをノード スタックに使用して、個別のクエリを削除できます。 visited セット。
あるいは、ノードにカスタムの変更可能なクラス/構造を使用している場合は、各ノードにブール値フラグを格納して、現在の検索パスの一部としてアクセスされたかどうかを示すこともできます。もちろん、何らかの理由で同じグラフ上で 2 つの検索を並行して実行したい場合、この方法では実行できません。
上記の関数がどのように機能するかを示すテスト コードを次に示します。
# test graph:
# ,---B---.
# A | D
# `---C---'
graph = {
"A": ("B", "C"),
"B": ("A", "C", "D"),
"C": ("A", "B", "D"),
"D": ("B", "C"),
}
# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)
指定されたサンプル グラフでこのコードを実行すると、次の出力が生成されます。
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
この例のグラフは無向であることに注意してください (つまり、すべてのエッジは両方向に進みます)、このアルゴリズムは任意の有向グラフでも機能します。たとえば、 C -> B エッジ（除去することによって） B 隣人リストから C) 3 番目のパス (A -> C -> B -> D）、それはもう不可能です。
追伸 このような単純な検索アルゴリズム (およびこのスレッドで説明されている他のアルゴリズム) のパフォーマンスが非常に悪いグラフを構築するのは簡単です。
たとえば、開始ノード A に 2 つの隣接ノードがある無向グラフ上で A から B までのすべてのパスを見つけるタスクを考えてみましょう。ターゲット ノード B (A 以外に近隣ノードはありません) と、 派閥 の n+1 ノード、次のように:
graph = {
"A": ("B", "C"),
"B": ("A"),
"C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
"H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
"I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
"J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
"K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
"L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
"M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
"N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
"O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}
A と B 間の唯一のパスが直接パスであることは簡単にわかりますが、ノード A から開始された単純な DFS は O(n!) たとえそれらの道がいずれも B につながる可能性がないことが (人間にとって) 明白であるにもかかわらず、徒党内の道を無駄に探索することに時間を費やすことになります。
構築することもできます DAG 同様のプロパティを持つもの、例:開始ノード A をターゲット ノード B と他の 2 つのノード C に接続することによって1 とC2, 、両方ともノード D に接続します。1 そしてD2, 、どちらも E に接続します1 そしてE2, 、 等々。のために n このように配置されたノードのレイヤーでは、A から B までのすべてのパスを単純に検索すると、最終的に O(2n) あきらめる前に、行き止まりの可能性をすべて検討してください。
もちろん、クリーク内のノードの 1 つ (C 以外)、または DAG の最後のレイヤーからターゲット ノード B にエッジを追加すると、 するだろう A から B までの可能なパスが指数関数的に多数作成されるため、純粋にローカルな検索アルゴリズムでは、そのようなエッジが見つかるかどうかを事前に知ることはできません。つまり、ある意味、貧乏人は、 出力感度 このような単純な検索が行われないのは、グラフのグローバル構造を認識していないことが原因です。
これらの「指数関数的時間行き止まり」の一部を回避するために使用できるさまざまな前処理方法 (葉ノードを反復的に削除する、単一ノードの頂点セパレーターを検索するなど) はありますが、一般的な方法はわかりません。それらを排除できる前処理トリック 全て ケース。一般的な解決策は、検索の各ステップでターゲット ノードがまだ到達可能かどうかをチェックし (サブ検索を使用して)、到達可能でない場合は早めにバックトラックすることです。しかし、悲しいことに、そうすると (最悪の場合) 検索が大幅に遅くなります。 、グラフのサイズに比例します）多くのグラフでは、 しないでください このような病的な行き止まりが含まれています。
ここでは、2 階と比較して論理的に見栄えの良い再帰バージョンを示します。
public class Search {
private static final String START = "B";
private static final String END = "E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "E"); // this is the only one-way connection
graph.addEdge("B", "F");
graph.addEdge("C", "A");
graph.addEdge("C", "E");
graph.addEdge("C", "F");
graph.addEdge("D", "B");
graph.addEdge("E", "C");
graph.addEdge("E", "F");
graph.addEdge("F", "B");
graph.addEdge("F", "C");
graph.addEdge("F", "E");
List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
String currentNode = START;
List<String> visited = new ArrayList<String>();
visited.add(START);
new Search().findAllPaths(graph, seen, paths, currentNode);
for(ArrayList<String> path : paths){
for (String node : path) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {
if (currentNode.equals(END)) {
paths.add(new ArrayList(Arrays.asList(visited.toArray())));
return;
}
else {
LinkedList<String> nodes = graph.adjacentNodes(currentNode);
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
List<String> temp = new ArrayList<String>();
temp.addAll(visited);
temp.add(node);
findAllPaths(graph, temp, paths, node);
}
}
}
}
プログラム出力
B A C E
B A C F E
B E
B F C E
B F E
C コードでの解決策。これは、最小限のメモリを使用する DFS に基づいています。
#include <stdio.h>
#include <stdbool.h>
#define maxN 20
struct nodeLink
{
char node1;
char node2;
};
struct stack
{
int sp;
char node[maxN];
};
void initStk(stk)
struct stack *stk;
{
int i;
for (i = 0; i < maxN; i++)
stk->node[i] = ' ';
stk->sp = -1;
}
void pushIn(stk, node)
struct stack *stk;
char node;
{
stk->sp++;
stk->node[stk->sp] = node;
}
void popOutAll(stk)
struct stack *stk;
{
char node;
int i, stkN = stk->sp;
for (i = 0; i <= stkN; i++)
{
node = stk->node[i];
if (i == 0)
printf("src node : %c", node);
else if (i == stkN)
printf(" => %c : dst node.\n", node);
else
printf(" => %c ", node);
}
}
/* Test whether the node already exists in the stack */
bool InStack(stk, InterN)
struct stack *stk;
char InterN;
{
int i, stkN = stk->sp; /* 0-based */
bool rtn = false;
for (i = 0; i <= stkN; i++)
{
if (stk->node[i] == InterN)
{
rtn = true;
break;
}
}
return rtn;
}
char otherNode(targetNode, lnkNode)
char targetNode;
struct nodeLink *lnkNode;
{
return (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;
}
int entries = 8;
struct nodeLink topo[maxN] =
{
{'b', 'a'},
{'b', 'e'},
{'b', 'd'},
{'f', 'b'},
{'a', 'c'},
{'c', 'f'},
{'c', 'e'},
{'f', 'e'},
};
char srcNode = 'b', dstN = 'e';
int reachTime;
void InterNode(interN, stk)
char interN;
struct stack *stk;
{
char otherInterN;
int i, numInterN = 0;
static int entryTime = 0;
entryTime++;
for (i = 0; i < entries; i++)
{
if (topo[i].node1 != interN && topo[i].node2 != interN)
{
continue;
}
otherInterN = otherNode(interN, &topo[i]);
numInterN++;
if (otherInterN == stk->node[stk->sp - 1])
{
continue;
}
/* Loop avoidance: abandon the route */
if (InStack(stk, otherInterN) == true)
{
continue;
}
pushIn(stk, otherInterN);
if (otherInterN == dstN)
{
popOutAll(stk);
reachTime++;
stk->sp --; /* back trace one node */
continue;
}
else
InterNode(otherInterN, stk);
}
stk->sp --;
}
int main()
{
struct stack stk;
initStk(&stk);
pushIn(&stk, srcNode);
reachTime = 0;
InterNode(srcNode, &stk);
printf("\nNumber of all possible and unique routes = %d\n", reachTime);
}
私は最近、これと同様の問題を解決しましたが、すべての解決策ではなく、最短のものだけに興味がありました。
私は、ステータスのキューを使用する「幅優先」の反復検索を使用しました。各ステータスのキューには、グラフ上の現在の点とそこに到達するまでにたどったパスを含むレコードが保持されます。
キュー内の 1 つのレコードから開始します。このレコードには開始ノードと空のパスがあります。
コードを反復するたびに、リストの先頭から項目が削除され、それが解決策であるかどうかが確認されます (到達したノードが必要なノードです。そうであれば、作業は完了です)。そうでない場合は、新しいノードが構築されます。現在のノードに接続しているノードを含むキュー項目と、前のノードのパスに基づいて修正されたパスで、最後に新しいジャンプが接続されます。
同様のものを使用することもできますが、解決策が見つかったら、停止するのではなく、その解決策を「見つかったリスト」に追加して続行します。
自分自身を後戻りしないように、訪問したノードのリストを追跡する必要があります。そうしないと、無限ループが発生します。
もう少し疑似コードが必要な場合は、コメントなどを投稿してください。詳しく説明します。
この背後にある本当の問題を説明する必要があると思います。私がこれを言うのは、あなたは時間効率の良いものを求めているにもかかわらず、問題に対する答えは指数関数的に増大しているように見えるからです。
したがって、指数関数的なアルゴリズムよりも優れたアルゴリズムは期待できません。
私なら遡ってグラフ全体を調べます。循環を避けるために、途中で訪問したすべてのノードを保存します。戻ったら、ノードのマークを外します。
再帰を使用する:
static bool[] visited;//all false
Stack<int> currentway; initialize empty
function findnodes(int nextnode)
{
if (nextnode==destnode)
{
print currentway
return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
findnodes(n);
visited[nextnode]=false;
pop from currenteay
}
それともそれは間違っていますか？
編集：ああ、忘れていました:そのノードスタックを利用して再帰呼び出しを排除する必要があります
基本原則は、グラフについて心配する必要はないということです。これは、動的接続問題として知られる標準的な問題です。ノードが接続されているかどうかを確認できる方法には、次の種類があります。
- クイック検索
- クイックユニオン
- アルゴリズムの改善 (両方の組み合わせ)
これは最小の時間計算量 O(log*n) で試した C コードです。つまり、65536 個のエッジのリストの場合は 4 回の検索が必要で、2^65536 の場合は 5 回の検索が必要になります。アルゴリズムの実装を共有します。 プリンストン大学のアルゴリズムコース
ヒント：上記で共有されているリンクから Java ソリューションを適切な説明とともに見つけることができます。
/* Checking Connection Between Two Edges */
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
/*
Data structure used
vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/
/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);
int main() //Main Function
{
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;
printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
printf("File does not exist");
exit(1);
}
while (1)
{
if (first == 0) //getting no. of vertices
{
ch = getc(fp);
if (temp == 0)
{
fseek(fp, -1, 1);
fscanf(fp, "%s", &ch1);
fseek(fp, 1, 1);
temp = 1;
}
if (isdigit(ch))
{
size = atoi(ch1);
vertex = (int*) malloc(size * sizeof(int)); //dynamically allocate size
sz = (int*) malloc(size * sizeof(int));
initalize(vertex, sz, size); //initialization of vertex[] and sz[]
}
if (ch == '\n')
{
first = 1;
temp = 0;
}
}
else
{
ch = fgetc(fp);
if (isdigit(ch))
temp = temp * 10 + (ch - 48); //calculating value from ch
else
{
/* Validating the file */
if (ch != ',' && ch != '\n' && ch != EOF)
{
printf("\n\nUnkwown Character Detected.. Exiting..!");
exit(1);
}
if (ch == ',')
node1 = temp;
else
{
node2 = temp;
printf("\n\n%d\t%d", node1, node2);
if (node1 > node2)
{
temp = node1;
node1 = node2;
node2 = temp;
}
/* Adding the input nodes */
if (!connected(vertex, node1, node2))
add(vertex, sz, node1, node2);
}
temp = 0;
}
if (ch == EOF)
{
fclose(fp);
break;
}
}
}
do
{
printf("\n\n==== check if connected ===");
printf("\nEnter First Vertex:");
scanf("%d", &node1);
printf("\nEnter Second Vertex:");
scanf("%d", &node2);
/* Validating The Input */
if( node1 > size || node2 > size )
{
printf("\n\n Invalid Node Value..");
break;
}
/* Checking the connectivity of nodes */
if (connected(vertex, node1, node2))
printf("Vertex %d and %d are Connected..!", node1, node2);
else
printf("Vertex %d and %d are Not Connected..!", node1, node2);
printf("\n 0/1: ");
scanf("%d", &temp);
} while (temp != 0);
free((void*) vertex);
free((void*) sz);
return 0;
}
void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
vertex[i] = i;
sz[i] = 0;
}
}
int root(int *vertex, int i) //obtaining the root
{
while (i != vertex[i])
{
vertex[i] = vertex[vertex[i]];
i = vertex[i];
}
return i;
}
/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);
/* Adding small subtree in large subtree */
if (sz[i] < sz[j])
{
vertex[i] = j;
sz[j] += sz[i];
}
else
{
vertex[j] = i;
sz[i] += sz[j];
}
}
/* Time Complexity for Search -->lg* n */
int connected(int *vertex, int p, int q) //Checking of connectivity of nodes
{
/* Checking if root is same */
if (root(vertex, p) == root(vertex, q))
return 1;
return 0;
}
遅れているかもしれませんが、スタックを使用して 2 つのノード間のすべてのパスを横断する、Casey による Java での DFS アルゴリズムの同じ C# バージョンを次に示します。いつものように再帰的を使用すると読みやすくなります。
void DepthFirstIterative(T start, T endNode)
{
var visited = new LinkedList<T>();
var stack = new Stack<T>();
stack.Push(start);
while (stack.Count != 0)
{
var current = stack.Pop();
if (visited.Contains(current))
continue;
visited.AddLast(current);
var neighbours = AdjacentNodes(current);
foreach (var neighbour in neighbours)
{
if (visited.Contains(neighbour))
continue;
if (neighbour.Equals(endNode))
{
visited.AddLast(neighbour);
printPath(visited));
visited.RemoveLast();
break;
}
}
bool isPushed = false;
foreach (var neighbour in neighbours.Reverse())
{
if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
{
continue;
}
isPushed = true;
stack.Push(neighbour);
}
if (!isPushed)
visited.RemoveLast();
}
}
This is a sample graph to test:
// Sample graph. Numbers are edge ids
// 1 3
// A --- B --- C ----
// | | 2 |
// | 4 ----- D |
// ------------------
find_paths[s, t, d, k]
この質問は古いもので、すでに回答されています。しかし、同じことを達成するための、おそらくより柔軟なアルゴリズムを示すものはありません。だから私は帽子をリングに投げ入れます。
私は個人的に次の形式のアルゴリズムを見つけました find_paths[s, t, d, k] 便利です。ここで:
- s は開始ノードです
- t はターゲットノードです
- d は検索する最大の深さです。
- k は検索するパスの数です
プログラミング言語の無限形式を使用して、 d そして k すべてのパスを提供します§。
§ 有向グラフを使用していて、すべてを必要とする場合は明らかに 方向性のない 間のパス s そして t これを両方の方法で実行する必要があります。
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
ヘルパー関数
私は個人的に再帰が好きですが、難しい場合もありますが、とにかく最初にヘルパー関数を定義しましょう。
def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
current_path.append(current)
if current_depth > max_depth:
return
if current == goal:
if len(paths_found) <= number_of_paths_to_find:
paths_found.append(copy(current_path))
current_path.pop()
return
else:
for successor in graph[current]:
self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)
current_path.pop()
メイン機能
以上で、コア関数は簡単です。
def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found)
まず、いくつかの点に注目してください。
- 上記の疑似コードは複数の言語をマッシュアップしたものですが、最もよく似ているのは Python です (コードを書いていただけなので)。厳密なコピー＆ペーストは機能しません。
[]は初期化されていないリストです。これを、選択したプログラミング言語に相当するものに置き換えてください。paths_found通り過ぎます 参照. 。再帰関数が何も返さないことは明らかです。これを適切に処理してください。- ここ
graph何らかの形を想定しているhashed構造。グラフを実装する方法はたくさんあります。どちらにしても、graph[vertex]隣接する頂点のリストを取得します。 指示された グラフ - 応じて調整します。 - これは、「バックル」（自己ループ）、サイクル、およびマルチエッジを除去するための前処理が完了していることを前提としています。
私の頭の上に浮かんだ考えは次のとおりです。
- 接続を 1 つ見つけます。(パスの長さは重要ではないため、深さ優先検索はおそらくこれに適したアルゴリズムです。)
- 最後のセグメントを無効にします。
- 以前に無効になった接続の前の最後のノードから別の接続を検索してみます。
- 接続がなくなるまで 2 に進みます。
ループを含む無限パスを含むすべてのパスを列挙する方法を見つけました。
http://blog.vjeux.com/2009/project/project-shortest-path.html
原子のパスとサイクルを見つける
Definition
私たちがやりたいのは、点 A から点 B に向かう可能なすべてのパスを見つけることです。サイクルが関係しているため、すべてをただ列挙することはできません。代わりに、ループしないアトミック パスと可能な限り最小のサイクルを見つける必要があります (サイクルが繰り返されることは望ましくありません)。
アトミック パスについて私が最初に定義したのは、同じノードを 2 回経由しないパスです。しかし、それはすべての可能性を考慮しているわけではないことがわかりました。少し考えてみたところ、エッジは重要ですが、ノードは重要ではないことがわかりました。したがって、アトミック パスは、同じエッジを 2 回通過しないパスです。
この定義は便利で、サイクルにも機能します。点 A の原子サイクルは、点 A から点 A に至る原子のパスです。
実装
Atomic Paths A -> B
点 A から始まるすべてのパスを取得するために、点 A からグラフを再帰的に走査します。子を通過する際、すでに通過したすべてのエッジを知るために、子 -> 親へのリンクを作成します。その子に移動する前に、リンクされたリストを走査し、指定されたエッジがまだウォークスルーされていないことを確認する必要があります。
目的地に到着したら、見つけた経路を保存できます。
Freeing the list
リンクされたリストを解放するときに問題が発生します。基本的には逆の順序でチェーンされたツリーです。解決策は、そのリストを二重リンクし、すべてのアトミック パスが見つかったら、ツリーを開始点から解放することです。
しかし、賢い解決策は、(ガベージ コレクションからヒントを得た) 参照カウントを使用することです。親にリンクを追加するたびに、その参照カウントに 1 が追加されます。次に、パスの終点に到着すると、参照カウントが 1 になるまで後戻りしてフリーになります。それより高い場合は、1 つ削除して停止します。
Atomic Cycle A
A の原子サイクルを探すことは、A から A への原子パスを探すことと同じです。ただし、実行できる最適化がいくつかあります。まず、目的点に到着したら、エッジ コストの合計が負の場合にのみパスを保存します。私たちは吸収サイクルを経たいだけなのです。
前に見たように、アトミック パスを探すときはグラフ全体が走査されます。代わりに、検索範囲を A を含む強連結成分に限定することができます。これらのコンポーネントを見つけるには、Tarjan のアルゴリズムを使用してグラフを単純に走査する必要があります。
アトミックパスとサイクルの組み合わせ
この時点で、A から B に向かうすべての原子パスと各ノードのすべての原子サイクルがあり、最短パスを取得するためにすべてを整理するのは私たちに任されています。これからは、原子パス内の原子サイクルの最適な組み合わせを見つける方法を研究していきます。
他の投稿者の何人かが適切に説明しているように、問題を簡単に言うと、深さ優先検索アルゴリズムを使用して、通信エンド ノード間のパスのすべての組み合わせをグラフで再帰的に検索することです。
アルゴリズム自体は、指定された開始ノードから始まり、そのすべての発信リンクを検査し、表示される検索ツリーの最初の子ノードを展開することで進行し、ターゲット ノードが見つかるまで、またはノードに遭遇するまで、徐々に深く検索していきます。それは子供がいません。
その後、検索は逆方向に戻り、まだ探索が完了していない最新のノードに戻ります。
私 ブログに書きました このトピックについてはつい最近、プロセス内の C++ 実装例を投稿しました。
Casey Watson の答えに加えて、ここに別の Java 実装があります。訪問ノードを開始ノードで初期化します。
private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
for(String node : adjacent){
if(visitedNodes.contains(node)){
continue;
}
if(node.equals(END)){
visitedNodes.add(node);
printPath(visitedNodes);
visitedNodes.removeLast();
}
visitedNodes.add(node);
getPaths(graph, visitedNodes);
visitedNodes.removeLast();
}
}
