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

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

Просмотр 4 веток ответов
  • Автор
    Сообщения
    • #2820
      @questioner
      StudLance.ru

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

      StudLance.ru

    • #2821
      @admin

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

      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
      @admin

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

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

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

      kruskal_algorithm_minimum_spanning_trees_prolog

    • #6844
      @dslk

      Если список ребер задается не пользователем, а в goal сразу мной и я передаю этот список по идее в  kruskal_minimum_spanning_tree_algorithm, соответственно,  kruskal_minimum_spanning_tree_algorithm у меня имеет два терма edges_d,то мне не нужен findall, но как организовать поиск вместо findall?

      • #6845
        @admin

        findall собирает все факты БД в список. Если у вас ребра сразу заданы списком — то конечно findall не нужен.

        Должно быть как-то так:

        goal
         Edges = [], % ваш список ребер
         Nodes = [], % ваш список узлов
         qsort(Edges, SortedEdges),
         nodes_to_branching(Nodes, Branching),
            
         kruskal_minimum_spanning_tree_algorithm(SortedEdges, Branching, [], SpanningTree).

    • #6880
      @dslk

      Можно еще узнать:
      1. Почему в kruskal_minimum_spanning_tree_algorithm при обработке Buffer становится постепенно пустым? Как это происходит?
      2. Это условие kruskal_minimum_spanning_tree_algorithm(_SortedEdges, [_Tree], Buffer, Buffer):-!. вступает в силу, когда  Branching становится одним единым списком, состоящих из символов, а не списком, в котором эти некоторые символы могут быть объединены в маленькие списки, и когда Buffer и SpanningTree одинаковы?

      • #6881
        @admin

        1. Смотрим сюда:

        % ...
        kruskal_minimum_spanning_tree_algorithm([edge(From, To, Distance)|TailEdges], Branching, Buffer, SpanningTree):-
          % ...
          kruskal_minimum_spanning_tree_algorithm(
            TailEdges,  
            [ToFromTree|BranchingWithoutToFrom], 
            [edge(From, To, Distance)|Buffer], 
            SpanningTree
          );
          % ...

        Я заменил многоточиями то, что к вопросу не относится. Тут видно, что функция рекурсивная. На вход подано [edge(From, To, Distance)|TailEdges], а рекурсивный вызов происходит для TailEdges, т.е. для списка ребер без первого ребра. Т.е. по ходу рекурсивного спуска, ребра удаляются из списка и, очевидно, однажды список ребер окажется пуст.

        2. Это правило
        kruskal_minimum_spanning_tree_algorithm(_SortedEdges, [_Tree], Buffer, Buffer):-!
        Выполнится тогда, когда во втором аргументе функции окажется список из одного элемента, т.е. [_Tree].

        • #6882
          @dslk

          Про второй пункт поняла, спасибо.
          А в первом про TailEdges это понятно, но именно в Buffer происходит, так сказать, опустошение списка после того, как он и SpanningTree наполнятся нужными ребрами. Я просто написала write() после

          kraskal(TailEdges,[ToFromTree|BranchingWithoutToFrom],[edge(From, To, Distance)|Buffer],SpanningTree),

          чтобы следить, что именно происходит, и там сначала Buffer и SpanningTree наполняются одинаковыми ребрами, а потом Buffer опустошается постепенно на одно ребро(например,edge(a,b,3)) , пока не станет пустым,а SpanningTree остается наполненным, как надо. И как только Buffer становится пустым, выводится сам результат.

          • #6883
            @admin

            Вы неудачно написали write, ведь вы отслеживаете только одно правило из трех.

            Попробуйте добавить в самое начало. Вот так:

            kruskal_minimum_spanning_tree_algorithm(SortedEdges, Tree, Buffer, _SpanningTree):-
              write(['SortedEdges:', SortedEdges, '-', 'Tree: ', Tree, '-', 'Buffer', Buffer]), nl, fail.
            kruskal_minimum_spanning_tree_algorithm(_SortedEdges, [_Tree], Buffer, Buffer):-!.
            % ...

            Но да, дуги удаляются из списка-второго аргумента добавляются в два остальных списка.

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