Раскраска плоской карты на Prolog

      Комментарии к записи Раскраска плоской карты на Prolog отключены

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

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

    questioner
    Участник

    Нужно выполнить раскраску плоской карты на языке Prolog четырьмя цветами.

    Дана карта:

    source_map_coloring

     

    Нужно подобрать для каждой области цвет таким образом, чтобы ни одна пара смежных областей не была окрашена одним цветом. Известно, что для решения задачи достаточно четырех цветов:

    map_coloring

     

    Для решения задачи нужно подобрать структуру данных, удобную для представления карты и проверки смежных областей. Можно использовать любой алгоритм. Задача может иметь несколько решений — для приведенного примера вершина b могла быть окрашена в синий цвет, кроме того, возможны перестановки цветов (для четырех цветов будет 256 перестановок). Нужно вывести любое из решений.

    Решить желательно на Visual Prolog.

  • #2828

    В качестве структуры данных можно использовать граф, т.к. с его помощью удобно задавать смежные области — если области a и b смежные — то существует дуга между ними.

    При решении задачи на Visual Prolog нужно сначала объявить используемые типы данных (на SWI Prolog этот шаг можно пропустить, т.к. в нем используется динамическая типизация):

    DOMAINS
    	color_d = red; green; blue; black
    	
    	node_d = symbol
    	node_color_d = node_color(node_d, color_d)
    	edge_d = edge(node_d, node_d)
    	
    	nodes_d = node_d*
    	coloring_d = node_color_d*

    Тут объявлены:

    1. 4 цвета, которых будет достаточно для раскраски карты;
    2. тип узла, представляющегося символом;
    3. структура node_color_d, совмещающая узел и цвет;
    4. структура дуги, совмещающая два узла — начало и конец дуги;
    5. список вершин графа;
    6. список типа node_color_d, задающий раскраску графа

    В базе данных могут лежать дуги — это будет удобно если мы захотим изменять карту во время выполнения программы:

    DATABASE
    	edge(node_d, node_d)

    Приведенный вами граф может быть задан следующим набором ребер:
      	edge(a, b).
      	edge(a, c).
      	edge(a, d).
      	edge(b, c).
      	edge(b, e).
      	edge(c, d).
      	edge(c, e).
      	edge(c, f).
      	edge(d, f).
      	edge(e, f).

    Т.к. ребра являются ориентированными, а отношение смежности — симметричным, нам потребуется вспомогательный предикат, выполняющий проверку смежности:
    exist_edge(From, To):-
      		edge(From, To), !; edge(To, From), !.

    Он проверяет существование дуги из From в To, а при неудаче — поиск обратной дуги.

    Программа будет перебирать все варианты окраски узлов графа, а затем проверять корректность выбранных цветов.
    Предикат color должен выдавать нам все возможные цвета, это нужно для перебора вариантов:

    	color(red). 
    	color(green).
    	color(blue).
    	color(black).

    Предикат nondeterm generate_colors(nodes_d, coloring_d) принимает список вершин графа и возвращает вариант раскраски графа, при этом для каждой вершины он вызывает предикат color, а остальные вершины обрабатывает рекурсивно:
    	generate_colors([], []).
    	generate_colors([HeadNode|TailNodes], [node_color(HeadNode, NodeColor)|TailNodeColors]):-
    		color(NodeColor), 
    		generate_colors(TailNodes, TailNodeColors).

    Проверка раскраски карты может сводиться к поиску такой пары смежных областей, что их цвета совпадают:
    check_coloring(Coloring):-
    		member(node_color(ANode, Color), Coloring),
    		member(node_color(BNode, Color), Coloring),
    		exist_edge(ANode, BNode), !, fail; !.

    Тут с помощью встроенной функции member (реализация функции member для Visual/Turbo Prolog) выполняется поиск в списке (задающем раскраску) некоторого узла (ANode с цветом Color) — фактически, осуществляется перебор элементов. Вторым вызовом member выполняется поиск в списке узлов с таким же цветом (переменная Color к этому времени уже инициализирована). Затем, выполняется проверка существования дуги между этими вершинами (смежности областей) и если области смежны — применяется отсечение и fail. Отсечение запрещает перебор (поиск других вариантов решения для этих же входных данных), а fail — показывает, что решения нет. В противном случае (если перебраны все вершины и не было найдено ни одной пары смежных областей одного цвета) — управление передается коду, расположенному после точки с запятой (см. Принципы построения Prolog-программ), который всегда завершается успешно.

    Остается вызывать все эти функции чтобы получить решение:

    GOAL 
    	generate_colors([a, b, c, d, e, f], NodeColors),
    	check_coloring(NodeColors), !.

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

    map_coloring_trace

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