Пути заданной длины в графе

vladpo07

Подскажите, пожалуйста, как найти в ациклическом ориентированном графе все пути заданной длины?

Sander

почему не подходит полный перебор?

vladpo07

Подходит. Но это может быть очень долго.

elektronik

Такой вопрос: правильно ли я понимаю, что ациклический граф -- граф без циклов?
То есть если бы он был бы ещё и связен, то получилось бы дерево?!
// А так у него несколько компонент связности, каждая из которых -- дерево. То есть лес
Второе, по ребру можно идти в любом направлении?
И последнее пока, связан ли этот вопрос с предыдущей вашей задачей поиска наибольшего пути в ациклическом графе?

vladpo07

Ну дерево вряд ли...
Ведь дерево - это граф с одной вершиной (корневой вершиной в которую нет входящих ребер, а в каждую другую вершину входит только одно ребро. В моем графе в одну вершину может входить более одного ребра.
Ориентированный граф - граф, вершины которого соединены направленными ребрами (дугами). По направленному ребру можно идти только в одном указанном направлении.
Вопрос связан, да.

Sander

почему долго то?
Если вершин N и M ребер, при длине L, у меня получилась такая оценка:
Пусть K(L) --- кол-во путей длины L.
Вводим переменную K_m = MAX(K(l при l от 1 до L.
Оценка кол-ва операций --- N*K_m*L
при этом K(l) можно оценить, как (M/l)^l.
могу подробней написать, почему так, но позднее - сейчас лень.

elektronik

Всё понятно
Ответ на второй вопрос -- граф ориентированный (не заметил то есть по ребру можно идти только в одну (заранее определённую) сторону.
По первому вопросу: был бы лес ( если, например, граф был бы не ориентированным... (определения дерева у нас с вами разные, но суть-то одна)

UltraLoko

определения дерева у нас с вами разные, но суть-то одна
нет слов... Нет уж, ромб - по любому не дерево.
 
x
/ \
/ \
V V
x x
\ /
\ /
V V
x
Во! Это ациклический граф, но не дерево.

elektronik

    x
/ \
/ \
V V
x x
\ /
\ /
V V
x
> Это ациклический граф
Это ациклический ориентированный граф. Где противоречие?

Stepprof

Вот граф:
1: 2, 3, 4, 5, 6
2: 3, 4, 5, 6
3: 4 ,5, 6
4: 5, 6
5: 6
Сколько тут путей из вершины 1 в вершину 6?
А если 92 вершины?

Sander

А в чем, собственно, проблема?
Если задача: найти кол-во путей, а кол-во путей есть K,
то , очевидно, меньше чем за K операций ее нельзя решить.
Алгоритм перебора (с некоторыми оговорками) имеет сложнось K*L*N.
Собственно, с данным примером такая оценка в противоречие не вступает.

Stepprof

Да, похоже, что перебором надо. Волновым алгоритмом.

teraskin

Если задача: найти кол-во путей, а кол-во путей есть K,
то , очевидно, меньше чем за K операций ее нельзя решить.
Нет, в такой постановке ее быстрее решить можно. Быстрее нельзя построить сами пути, а не посчитать их количество.
Если же просто считать количество путей длины L, то сложность будет порядка V+L*E, где V - количество вершин, E - количестов ребер.

teraskin

А памяти сколько надо будет на такое? Количество различных путей длины L может расти экспоненциально от L. При этом потребуются огромные объемы памяти для их хранения (при волновом алгоритме, если я правильно понимаю то, как ты их будешь этим алгоритмом строить пути а полезных путей может оказаться мало. Пример:
0 -> 1, n + 1, 2*n + 1
1 -> 2, n + 2
n+1 -> 2, n + 2
2 -> 3, n + 3
n + 2 -> 3, n + 3
......
n ->
2 * n ->
2 * n + 1 -> 2 * n + 2
2 * n + 2 -> 2 * n + 3
2 * n + 3 -> 2 * n + 4
....
3 * n -> 3 * n + 1
3 * n + 1 ->
(т.е. конечные вершины - n, 2 * n и 3 * n + 1)
Всего вершин N = 3 * n + 2; Будем искать пути длины L = n + 1 (количество ребер в пути такой всего один. Если же мы будем строить с помощью волны все пути, то также постоим и все пути длины n из вершины 0, (которых 2^n + 1 (2^n до вершин n и 2*n) и один до 3*n). В таком случае будет построено 2^N+1)/3) путей (и соответственно, сделано не меньшее количество шагов хотя большинство из этих путей бесполезны.

Sander

В указанной формулировке их всех надо найти.
Следовательно и построить (или предъявить).

Sander

На самом деле, ты конечно прав, на счет того, что волновой алгоритм "не очень хороший". Т.е. может отжирать кучу ресурсов, а при этом в результате можем получить "совсем немного" последовательностей.

Stepprof

Ну ладно, ресурсы ресурсами. Так есть ли что-нибудь лучше волнового алгоритма-то?

Sander

Хз. я волновым алгоритмом пользуюсь.
Раньше когда только писал этот алгоритм думал над тем, как лучше, но ничего умнее волны не придумал.
Да и вообще - все от данных зависит. вот у меня, например данные более-менее регулярные и описанные глюки редко возникают: в моем случае обычно количество найденных путей имеет тот же порядок, что и максимальое количество путей, так что волна работает довольно неплохо.
А алгоритм лучше придумать, наверное, можно.

teraskin

Ну есть такое Если ищем пути длины L, таких путей K(L) в графе из V вершин и E ребер, то следующий алгоритм дает сложность порядка E+V+K(L)*L. Т.е. линейно по длине входа и выхода.

type
tnode = record
incoming_count, outgoing_count: integer;
incoming, outgoing: array of integer;
end;

var
vertices: array [1..max_n] of integer;
depth: array [1..max_n] of integer;
tar: array [1..max_n] of integer;
vert_count: integer;
path: array [1..max_path] of integer;

procedure preinit;
var
quee: array [1..max_n] of integer;
i, ov, nv: integer;
queep, queec: integer;

begin
for i:=1 to vert_count do begin
tar[i] := vertices[i].outgoing_count;
end;
queep:=0;
for i:=1 to vert_count do
if tar[i] = 0 then begin
inc(queep);
quee[queep]:=i;
depth[i]:=0;
end;

queec:=0;
repeat
inc(queec);
cv:=quee[queec];
for i:=1 to vertices[cv].incoming_count do begin
nv:=vertices[cv].incoming[i];
inc(vertices[nv].outgoing_count);
vertices[nv].outgoing[vertices[nv].outgoing_count]:=i;
dec(tar[nv]);
if 0 = tar[nv] then begin
depth[nv]:=depth[cv] + 1;
inc(queep);
quee[queep]:=nv;
end;
end;
until queec=queep;
end;

procedure bfv(vert, ind, len);
var
ce: integer;
begin
path[ind]:=vert;
if 0 = len then begin
output_path;
exit;
end;
ce := vertices[vert].outgoing_count;
while (0 < ce) and (len - 1 <= depth[vertices[vert].outgoing[ce]]) do begin
bfv(vertices[vert].outgoing[ce], ind+1, len-1);
dec(ce);
end;
end;

procedure build_paths;
var
i: integer;
begin
for i:=1 to vert_count do
if depth[i] >= l then
bfv(i, 1, l);
end;

procedure go;
begin
preinit;
build_paths;
end;
Перед работой должно быть следующее:
Для каждой вершины посчитано количество входящих и исходящих ребер, а также заполнены массивы входящих ребер.
На самом деле это поиск в глубину + метод ветвей и границ. Ну и правильное заполнение массива исходящих ребер (в preinit чтобы не пришлось сортировать .
Оставить комментарий
Имя или ник:
Комментарий: