Минимальное остовное дерево взвешенного графика

Question

Мне нужно написать предикат, который создает минимальное остовное дерево взвешенного неориентированного графа, используя Алгоритм Прима . Это то, что я до сих пор:

% call the recursive predicate with the list of all nodes and
%    one element (in this case the last one).
mst(T) :- nodes(N), last(N,E), mst(T,N,E).

% The element E is added to the visited list and removed from the toVisit list.
mst(T,N,E) :- append(T,E,S), delete(R,E,L)...

Затем список toVisit должен быть отсортирован по расстоянию ребер, соединенных с любым из узлов в списке посещенных. Любые предложения о том, как это сделать?

Answer 1

Итак, прежде всего, давайте попробуем создать решение, чтобы найти связующее дерево, а не минимум, из Википедии: «связующее дерево T неориентированного графа G - это подграф, который представляет собой дерево, которое включает в себя все вершины G, с минимально возможным числом ребер »и« Дерево - это связный неориентированный граф без циклов. Это остовное дерево графа G, если оно охватывает G (то есть включает каждая вершина G) и является подграфом G (каждое ребро дерева принадлежит G) ". В этом примере я рассматриваю построенный таким образом график:

graph(ListOfVertices,ListOfEdges)

и каждый элемент ListOfEdges равен edge(X,Y,Cost).

Давайте создадим предикат, который создает дерево (в данном случае это полностью связный граф). make_kn_weighted/4 имеет в качестве входных данных степень каждого узла (Size), MinValue и MaxValue стоимости ребер и создает график в graph(LV,Comb).

make_kn_weighted(Size,MinValue,MaxValue,graph(LV,Comb)):-
    Size1 is Size+1,
    make_ordered_list(1,Size1,LV),
    find_all_combinations_weighted(LV,MinValue,MaxValue,[],Comb).

make_ordered_list(Max,Max,[]):- !.
make_ordered_list(I,Max,[I|T]):-
    I < Max,
    I1 is I+1,
    make_ordered_list(I1,Max,T).

find_all_combinations_weighted([_],_,_,C,C):- !.
find_all_combinations_weighted([H|T],Min,Max,CT,CO):-
    find_combinations_weighted(H,T,Min,Max,C),
    append(CT,C,C1),
    find_all_combinations_weighted(T,Min,Max,C1,CO).

find_combinations_weighted(_,[],_,_,[]):- !.
find_combinations_weighted(E,[H|T],Min,Max,[edge(E,H,V)|TE]):-
    random(Min,Max,V),
    find_combinations_weighted(E,T,Min,Max,TE).

?- make_kn_weighted(4,2,7,G).
G = graph([1, 2, 3, 4], [edge(1, 2, 6), edge(1, 3, 6), edge(1, 4, 5), edge(2, 3, 4), edge(2, 4, 5), edge(3, 4, 5)]).

Затем мы создаем предикат, который генерирует остовное дерево:

spanning_tree(graph([N|T],Edges),graph([N|T],TreeEdges)) :- 
   generate_spanning_tree(T,Edges,TreeEdgesUnsorted),
   sort(TreeEdgesUnsorted,TreeEdges).

generate_spanning_tree([],_,[]).
generate_spanning_tree(Curr,Edges,[Edge|T]) :- 
    select(Edge,Edges,Edges1),
    get_vertices(Edge,X,Y),
    is_connected_to_tree(X,Y,Curr),
    delete(Curr,X,Curr1),
    delete(Curr1,Y,Curr2),
    generate_spanning_tree(Curr2,Edges1,T).

get_vertices(edge(X,Y),X,Y).
get_vertices(edge(X,Y,_),X,Y).

is_connected_to_tree(X,Y,Ns):- 
    memberchk(X,Ns), 
    \+ memberchk(Y,Ns), !.
is_connected_to_tree(X,Y,Ns):- 
    memberchk(Y,Ns), 
    \+ memberchk(X,Ns).

Итак, очевидно, что и связующее дерево, и граф имеют одинаковые вершины, и именно поэтому я написал graph([N|T],Edges),graph([N|T],TreeEdges). Чтобы сгенерировать фактическое дерево, сначала мы выбираем узел из списка, с select/3 (в Edges1 у нас есть все элементы с Edges без Edge. Затем с get_vertices/3 мы получаем две вершины, соединенные ребро. С помощью is_connected_to_tree/3 мы проверяем, если две вершины еще не соединены (в списке или оставшихся вершинах). Затем удаляем два выбранных ребра в список несвязанных вершин (Curr), используя два раза delete/3 применяется к Curr. Последний вызов, рекурсивный вызов с обновленными параметрами. Тест:

?- make_kn(4,G), spanning_tree(G,T).
G = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(1, 4), edge(2, 3), edge(2, 4), edge(3, 4)]),
T = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(1, 4)]) ;
G = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(1, 4), edge(2, 3), edge(2, 4), edge(3, 4)]),
T = graph([1, 2, 3, 4], [edge(1, 2), edge(1, 3), edge(2, 4)])
and so on...

Теперь давайте сосредоточимся на алгоритме Примм: чтобы адаптировать наш предикат для генерации дерева с минимальными затратами, мы сначала отсортируем ребра с учетом стоимости каждого ребра, затем мы можем вызвать, как указано выше, generate_spanning_tree/3. Итак, в прологическом коде:

mst_prim(graph([H|T],Edges),graph([H|T],TreeEdges),Cost):-
    predsort(compare_edges_value,Edges,SortedEdges),
    generate_spanning_tree(T,SortedEdges,TreeEdgesUnsorted),
    sort(TreeEdgesUnsorted,TreeEdges),
    sum_cost(TreeEdges,0,Cost).

compare_edges_value(O,edge(X1,Y1,C1),edge(X2,Y2,C2)):-
    compare(O,C1+X1+Y1,C2+X2+Y2).

sum_cost([],C,C).
sum_cost([edge(_,_,C)|T],CT,Tot):-
    CT1 is CT+C,
    sum_cost(T,CT1,Tot).

predsort/3 сортирует, используя compare_edge/3 для определения порядка. sum_cost/3 просто суммирует стоимость каждого выбранного ребра. Запрос:

make_kn_weighted(4,2,7,G), mst_prim(G,T,C).
G = graph([1, 2, 3, 4], [edge(1, 2, 3), edge(1, 3, 6), edge(1, 4, 6), edge(2, 3, 5), edge(2, 4, 2), edge(3, 4, 2)]),
T = graph([1, 2, 3, 4], [edge(1, 2, 3), edge(2, 4, 2), edge(3, 4, 2)]),
C = 7 ;

При обратном отслеживании генерируются все связующие деревья (если вам не нужно это поведение, вы можете добавить вырезку после вызова generate_spanning_tree/2).