Алгоритм графа для поиска всех связей между двумя произвольными вершинами
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь определить лучший алгоритм, эффективный по времени, для выполнения задачи, описанной ниже.
У меня есть набор рекордов.Для этого набора записей у меня есть данные о соединении, которые показывают, как пары записей из этого набора соединяются друг с другом.По сути, это представляет собой неориентированный граф, в котором записи являются вершинами, а данные соединений — ребрами.
Все записи в наборе содержат информацию о соединении (т.никаких потерянных записей нет;каждая запись в наборе соединяется с одной или несколькими другими записями в наборе).
Я хочу выбрать любые две записи из набора и иметь возможность показывать все простые пути между выбранными записями.Под «простыми путями» я подразумеваю пути, в пути которых нет повторяющихся записей (т.е.только конечные пути).
Примечание:Две выбранные записи всегда будут разными (т.е.начальная и конечная вершина никогда не будут одинаковыми;никаких циклов).
Например:
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
Это пример: на практике у меня могут быть наборы, содержащие сотни тысяч записей.
Решение
Похоже, что это можно сделать с помощью поиска в глубину графа. Поиск в глубину найдет все нециклические пути между двумя узлами. Этот алгоритм должен быть очень быстрым и масштабироваться для больших графов (структура данных графа разрежена, поэтому он использует столько памяти, сколько необходимо).
Я заметил, что указанный вами выше граф имеет только одно направленное ребро (B,E).Это опечатка или это действительно ориентированный граф?Это решение работает независимо.Извините, я не смог сделать это на 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
Другие советы
В онлайн-словаре алгоритмов и структур данных Национального института стандартов и технологий (NIST) эта проблема описана как «все простые пути» и рекомендует поиск в глубину.CLRS предоставляет соответствующие алгоритмы.
Найден хитрый метод с использованием сетей Петри. здесь
Вот псевдокод, который я придумал.Это не какой-то конкретный диалект псевдокода, но он должен быть достаточно простым для понимания.
Любой хочет разобрать это на части.
[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
Этот код поддерживает два параллельных стека:один содержит более ранние узлы текущего пути, а другой — текущий индекс соседа для каждого узла в стеке узлов (чтобы мы могли возобновить итерацию по соседям узла, когда вынимаем его обратно из стека).Я мог бы с тем же успехом использовать один стек пар (узел, индекс), но решил, что метод с двумя стеками будет более удобочитаемым и, возможно, более простым в реализации для пользователей других языков.
Этот код также использует отдельный visited set, который всегда содержит текущий узел и любые узлы в стеке, чтобы я мог эффективно проверить, является ли узел уже частью текущего пути.Если ваш язык имеет структуру данных «упорядоченного набора», которая обеспечивает как эффективные стековые операции push/pop, так и и эффективные запросы членства, вы можете использовать это для стека узлов и избавиться от отдельных visited набор.
В качестве альтернативы, если вы используете собственный изменяемый класс/структуру для своих узлов, вы можете просто сохранить логический флаг в каждом узле, чтобы указать, был ли он посещен как часть текущего пути поиска.Конечно, этот метод не позволит вам одновременно выполнить два поиска на одном и том же графике, если вы по какой-то причине захотите это сделать.
Вот небольшой тестовый код, демонстрирующий, как работает приведенная выше функция:
# 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) дает тот же результат, за исключением третьего пути (A -> C -> B -> D), что уже невозможно.
Пс. Легко построить графики, для которых простые алгоритмы поиска, подобные этому (и другим, представленным в этой теме), работают очень плохо.
Например, рассмотрим задачу найти все пути от A до B в неориентированном графе, где у начального узла A есть два соседа:целевой узел B (у которого нет других соседей, кроме A) и узел C, который является частью клика из н+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 — прямой, но простой DFS, запущенный с узла A, будет тратить O(н!) время бесполезно исследует пути внутри клики, хотя очевидно (для человека), что ни один из этих путей не может привести к B.
Можно также построить группы обеспечения доступности баз данных с аналогичными свойствами, напр.за счет подключения начального узла A к целевому узлу B и к двум другим узлам C.1 и С2, оба из которых соединяются с узлами D1 и Д2, оба из которых подключаются к E1 и Е2, и так далее.Для н слоев узлов, расположенных таким образом, наивный поиск всех путей от A до B приведет к потере O(2н) время изучить все возможные тупики, прежде чем сдаться.
Конечно, добавив к целевому узлу B ребро из одного из узлов клики (кроме C) или из последнего слоя DAG, бы создать экспоненциально большое количество возможных путей от A до B, и алгоритм чисто локального поиска не может заранее сказать, найдет ли он такое ребро или нет.Таким образом, в некотором смысле бедные выходная чувствительность таких наивных поисков связано с незнанием глобальной структуры графа.
Хотя существуют различные методы предварительной обработки (например, итеративное исключение листовых узлов, поиск одноузловых разделителей вершин и т. д.), которые можно использовать, чтобы избежать некоторых из этих «тупиков экспоненциального времени», я не знаю ни одного общего метода. трюк предварительной обработки, который мог бы устранить их в все случаи.Общим решением было бы на каждом этапе поиска проверять, доступен ли целевой узел (с помощью подпоиска), и раньше возвращаться, если это не так, но, увы, это значительно замедлит поиск (в худшем случае , пропорционально размеру графа) для многих графов, которые не содержат такие патологические тупики.
Вот логически более привлекательная рекурсивная версия по сравнению со вторым этажом.
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);
}
Недавно я решил подобную задачу, вместо всех решений меня интересовали только самые короткие.
Я использовал итеративный поиск «в ширину», в котором использовалась очередь статусов, каждая из которых содержала запись, содержащую текущую точку на графике и путь, пройденный для ее достижения.
вы начинаете с одной записи в очереди, которая имеет начальный узел и пустой путь.
Каждая итерация кода удаляет элемент из головы списка и проверяет, является ли он решением (достигнутый узел — это тот, который вам нужен, если это так, то мы закончили), в противном случае он создает новый элемент очереди с узлами, подключающимися к текущему узлу, и измененные пути, основанные на пути предыдущего узла, с новым переходом, прикрепленным в конце.
Теперь вы могли бы использовать что-то подобное, но когда вы найдете решение, вместо того, чтобы останавливаться, добавьте это решение в свой «список найденных» и продолжайте.
Вам необходимо отслеживать список посещенных узлов, чтобы никогда не возвращаться к самому себе, иначе у вас возникнет бесконечный цикл.
если вам нужно немного больше псевдокода, оставьте комментарий или что-то в этом роде, и я уточню.
Я думаю, вам следует описать вашу реальную проблему, стоящую за этим.Я говорю это потому, что вы просите о чем-то, экономящем время, а количество ответов на проблему, кажется, растет в геометрической прогрессии!
Поэтому я бы не ожидал лучшего алгоритма, чем что-то экспоненциальное.
Я бы сделал возврат и просмотрел весь график.Во избежание циклов сохраняйте все посещенные узлы по пути.Когда вы вернетесь, снимите отметку с узла.
Использование рекурсии:
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
}
Или это неправильно?
редактировать:Ой, и я забыл:Вам следует исключить рекурсивные вызовы, используя этот стек узлов.
Основной принцип заключается в том, что вам не нужно беспокоиться о графиках. Это стандартная проблема, известная как проблема динамической связности.Существуют следующие типы методов, с помощью которых можно добиться того, соединены или нет узлы:
- Быстрый поиск
- Быстрый Союз
- Улучшенный алгоритм (комбинация обоих)
Вот код C, который я пробовал с минимальной временной сложностью O(log*n). Это означает, что для списка из 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;
}
Возможно, это поздно, но вот та же версия алгоритма DFS на C# на Java от Кейси для обхода всех путей между двумя узлами с использованием стека.Читабельность, как всегда, лучше с рекурсией.
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]получает список соседних вершин в направленный график – отрегулируйте соответствующим образом. - это предполагает, что вы предварительно обработали удаление «пряжек» (петлей), циклов и нескольких кромок.
Вот такая мысль пришла мне в голову:
- Найдите одну связь.(Поиск в глубину, вероятно, является хорошим алгоритмом для этого, поскольку длина пути не имеет значения.)
- Отключите последний сегмент.
- Попробуйте найти другое соединение с последнего узла перед ранее отключенным соединением.
- Переходите к шагу 2, пока соединений не останется.
Насколько я могу судить, решения, данные Райаном Фоксом (58343, Кристиан (58444), и себя (58461) примерно настолько хороши, насколько это возможно.Я не верю, что обход в ширину поможет в этом случае, поскольку вы не получите все пути.Например, с краями (A,B), (A,C), (B,C), (B,D) и (C,D) ты получишь пути ABD и ACD, но нет ABCD.
Я нашел способ перечислить все пути, включая бесконечные, содержащие циклы.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Поиск атомных путей и циклов
Definition
Нам нужно найти все возможные пути, ведущие из точки А в точку Б.Поскольку здесь задействованы циклы, вы не можете просто просмотреть и перечислить их все.Вместо этого вам придется найти атомарный путь, который не зацикливается, и наименьшие возможные циклы (вы не хотите, чтобы ваш цикл повторялся).
Первое определение атомарного пути, которое я дал, — это путь, который не проходит через один и тот же узел дважды.Однако я обнаружил, что он не использовал все возможности.После некоторых размышлений я понял, что узлы не важны, а ребра!Таким образом, атомарный путь — это путь, который не проходит через одно и то же ребро дважды.
Это определение удобно, оно также работает для циклов:Атомный цикл точки А — это атомный путь, идущий из точки А и заканчивающийся в точке А.
Выполнение
Atomic Paths A -> B
Чтобы получить весь путь, начинающийся из точки А, мы собираемся рекурсивно пройти по графику из точки А.Проходя через дочерний элемент, мы собираемся создать связь дочерний -> родительский, чтобы знать все ребра, которые мы уже пересекли.Прежде чем мы перейдем к этому дочернему элементу, мы должны пройти по этому связанному списку и убедиться, что указанное ребро еще не пройдено.
Когда мы прибудем в пункт назначения, мы сможем сохранить найденный путь.
Freeing the list
Проблема возникает, когда вы хотите освободить связанный список.По сути, это дерево, сцепленное в обратном порядке.Решением было бы соединить этот список двойной связью и, когда все атомарные пути будут найдены, освободить дерево от начальной точки.
Но умное решение — использовать подсчет ссылок (вдохновленный сборкой мусора).Каждый раз, когда вы добавляете ссылку на родительский элемент, вы добавляете ее к счетчику ссылок.Затем, когда вы достигаете конца пути, вы идете назад и освобождаетесь, пока счетчик ссылок равен 1.Если оно выше, просто удалите один и остановитесь.
Atomic Cycle A
Поиск атомного цикла А — это то же самое, что поиск атомного пути от А к А.Однако есть несколько оптимизаций, которые мы можем сделать.Во-первых, когда мы прибываем в точку назначения, мы хотим сохранить путь только в том случае, если сумма стоимости ребер отрицательна:мы хотим только пройти через поглощающие циклы.
Как вы видели ранее, при поиске атомарного пути просматривается весь граф.Вместо этого мы можем ограничить область поиска сильно связным компонентом, содержащим A.Для поиска этих компонентов требуется простой обход графа с помощью алгоритма Тарьяна.
Объединение атомарных путей и циклов
На данный момент у нас есть все атомарные пути, идущие от A к B, и все атомарные циклы каждого узла, и нам остается организовать все, чтобы получить кратчайший путь.С этого момента мы собираемся изучить, как найти лучшую комбинацию атомных циклов на атомном пути.
Как умело описано некоторыми другими авторами, проблема в двух словах заключается в использовании алгоритма поиска в глубину для рекурсивного поиска в графе всех комбинаций путей между сообщающимися конечными узлами.
Сам алгоритм начинается с начального узла, который вы ему даете, проверяет все его исходящие ссылки и продолжает расширять первый дочерний узел появившегося дерева поиска, выполняя поиск все глубже и глубже, пока не будет найден целевой узел или пока он не встретит узел. у которого нет детей.
Затем поиск возвращается к самому последнему узлу, исследование которого еще не завершено.
я в блоге об этой самой теме совсем недавно, опубликовав в процессе пример реализации на C++.
В дополнение к ответу Кейси Уотсона, вот еще одна реализация 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();
}
}
