Алгоритм Крускала – минимальное остовное дерево на Prolog

      Комментарии к записи Алгоритм Крускала – минимальное остовное дерево на Prolog отключены

Главная Форумы Программирование Помощь с решением задач на Prolog Обработка графов (деревьев) на Prolog Алгоритм Крускала – минимальное остовное дерево на Prolog

В этой теме 2 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 10 мес., 3 нед. назад.

  • Автор
    Сообщения
  • #2820

    questioner
    Участник

    Нужно реализовать на языке Prolog (желательно Visual Prolog 5.2) алгоритм Крускала для построения минимального остовного дерева исходного графа. Т.е. на входе должен быть граф, а на выходе — его подграф, включающий все вершины и такое подмножество ребер, что все вершины оказываются связанными друг с другом. При этом набор ребер (остов) должен быть минимального веса.

  • #2821

    За основу можно взять программу, выполняющую ввод и вывод графа — однако граф там является невзвешенным (его ребра не имеют вес), а в алгоритме Крускала минимизируется суммарный вес подграфа. Кроме того, в алгоритме используется лес — в теории графов так называют множество деревьев, для него нам нужно будет объявить дополнительный тип данных:

    DOMAINS
    	node_d = string
    	edge_d = edge(node_d, node_d, integer)
    	
    	nodes_d = node_d*
    	edges_d = edge_d*
    	
    	branching_d = nodes_d*

    В базе данных будет храниться граф в виде набора вершин и дуг:

    DATABASE
    	node(node_d)
    	edge(node_d, node_d, integer)

    kruskal_algorithm_flowchart Блок-схема алгоритма Крускала

    В алгоритме можно выделить подготовительный этап, связанный с сортировкой списка ребер и построением набора деревьев из вершин, вынесем его в отдельную функцию:

    kruskal_minimum_spanning_tree_algorithm(SpanningTree):-
    	findall(Edge, get_edge(Edge), Edges),
    	findall(Node, node(Node), Nodes), 
    		
    	qsort(Edges, SortedEdges),
    	nodes_to_branching(Nodes, Branching),
    		
    	kruskal_minimum_spanning_tree_algorithm(SortedEdges, Branching, [], SpanningTree).

    Эта функция:

    1. собирает все дуги графа с помощью стандартного предиката findall и функции get_edge, возвращающей дугу. Вспомогательная функция нужна в связи с тем, что Visual Prolog не разрешает следующее поведение findall: findall(edge(From, To, Distance), edge(From, To, Distance), Edges). Поэтому мы вынуждены написать вспомогательную функцию, которая завернет дугу графа в нужную нам структуру:
      % nondeterm get_edge(edge_d)
      get_edge(edge(From, To, Dist)):-
        	edge(From, To, Dist).

    2. Функция qsort выполняет быструю сортировку списка, однако для сравнения элементов (дуг) нужно использовать вспомогательную функцию:
      edge_less(edge(_AFrom, _ATo, ALen), edge(_BFrom, _BTo, BLen)):-
      	ALen >= BLen.

    3. для построения начального списка деревьев, которые во время работы алгоритма будут объединяться, каждый узел графа нужно поместить в отдельный список. Все деревья будут при этом являться элементами списка:
      nodes_to_branching([], []):-!.
      nodes_to_branching([Head|Tail], [[Head]|TailBranching]):-
      	nodes_to_branching(Tail, TailBranching).

    В основном цикле алгоритма Крускала последовательно выбираются заранее отсортированные дуги. Для каждой дуги выполняется поиск деревьев, содержащих начало и конец дуги. Для поиска узла внутри дерева можно применить функцию member, но дерево мало найти — нужно выполнить его удаление из списка, т.к. деревья, содержащие начало и конец должны объединиться. Одновременно поиск и удаление элементов может выполняться с помощью функции select. Соединение деревьев может быть выполнено с помощью предиката append:

    kruskal_minimum_spanning_tree_algorithm(_SortedEdges, [_Tree], Buffer, Buffer):-!.
    kruskal_minimum_spanning_tree_algorithm([edge(From, To, Distance)|TailEdges], Branching, Buffer, SpanningTree):-
    	select(ToTree, Branching, BranchingWithoutTo), member(To, ToTree),
    	select(FromTree, BranchingWithoutTo, BranchingWithoutToFrom), member(From, FromTree),
    	NOT(ToTree = FromTree), 
    	append(ToTree, FromTree, ToFromTree), !,
    	kruskal_minimum_spanning_tree_algorithm(
    		TailEdges,  
    		[ToFromTree|BranchingWithoutToFrom], 
    		[edge(From, To, Distance)|Buffer], 
    		SpanningTree
    	);
    	kruskal_minimum_spanning_tree_algorithm(TailEdges, Branching, Buffer, SpanningTree).

    Функции select, memeber и append являются встроенными в SWI Prolog, однако в Visual Prolog и Turbo Prolog их нужно реализовывать вручную.

    Приведенный фрагмент алгоритма:

    1. выбирает первую дугу из упорядоченного списка;
    2. удаляет из леса деревья, содержащие начало и конец дуги;
    3. если начало и конец принадлежат разным деревьям — деревья объединяются и обрабатываются рекурсивно;
    4. если же они принадлежат одному дереву — дуга пропускается и рекурсивно обрабатываются остальные
  • #2822

    Результат работы алгоритма для графа, приведенного на рисунке:

    graph_example Пример графа

    будет следующим:

    kruskal_algorithm_minimum_spanning_trees_prolog

Для ответа в этой теме необходимо авторизоваться.