Решение раскраски графика с 3-мя цветами и списками - Пролог

Мне нужно решить проблему раскраски графа с помощью Prolog. Речь идет о карте Латинской Америки с 3 цветами, и в описании задачи говорится, что i-й член раскраски должен использоваться для раскрашивания i-го члена страны, что мне не очень понятно, как им сопоставить.

???? Вот программа пока что,

adjacent(brazil, suriname).
adjacent(brazil, guyana).
adjacent(brazil, venezuela).
adjacent(brazil, colombia).
adjacent(brazil, peru).
adjacent(brazil, bolivia).
adjacent(brazil, paraguay).
adjacent(brazil, argentina).
adjacent(brazil, uruguay).
adjacent(frenchguiana, suriname).
adjacent(suriname, guyana).
adjacent(guyana, venezuela).
adjacent(venezuela, colombia).
adjacent(colombia, ecuador).
adjacent(colombia, peru).
adjacent(ecuador, peru).
adjacent(peru, bolivia).
adjacent(bolivia, chile).
adjacent(bolivia, paraguay).
adjacent(chile, argentina).
adjacent(paraguay, argentina).
adjacent(argentina, uruguay).
adjacent(chile, peru).
adjacent(argentina, bolivia).

coloring([red,yellow,green]).

neighbor(X,Y) :- adjacent(X, Y). 
neighbor(X,Y) :- adjacent(Y, X).

conflict(A,Ca,B,Cb) :-
   adjacent(A,B),
   Ca \= Cb.

solve(?, ?) :-

???? и это должен быть запрос. solve([brazil,colombia,argentina,peru,venezuela,chile,ecuador,bolivia,paraguay,uruguay,guyana,suriname,frenchguiana],Coloring)

Я видел примеры алгоритмов в Google, но, похоже, он отличается от того, как я должен это делать.


graph-coloring prolog
person Jun Young Bang    schedule 12.05.2020    source источник
comment
Я впервые использую этот язык, поэтому не знаю, с чего начать.   -  person Jun Young Bang    schedule 12.05.2020
comment
Начните с того, что вы хотите solve получить в качестве запроса. Как выглядит результат? Вы показываете два аргумента. Что они собой представляют? Вам нужны два аргумента? Реализация solve описывает условия, которые позволят добиться этого результата.   -  person lurker    schedule 12.05.2020
comment
Ознакомьтесь с руководством Маркуса Триски по раскраске карт в Прологе: youtube.com/watch?v=6XD7vBbywMc   -  person David Tonhofer    schedule 12.05.2020
comment
Поскольку все страны находятся в вашей базе данных, вам не нужно указывать их в своем запросе. Их можно получить с помощью запроса setof(Country, X^(adjacent(Country, X) ; adjacent(X, Country)), Countries), который выдаст список Countries. Итак, solve(Coloring) достаточно и включите setof запрос в свою solve реализацию.   -  person lurker    schedule 12.05.2020
comment
... но, похоже, это отличается от того, как я должен это делать. Как вы думаете, каким образом вы должны это делать, чтобы отличаться от того, что вы видели в Интернете?   -  person lurker    schedule 12.05.2020

Ответы (1)


arrow_upward
0
arrow_downward

Я опишу один подход к решению без написания кода за вас и без лишнего опыта обучения с эффектом присутствия. :)

Вам нужен только один аргумент для вашего предиката solve, который представляет собой набор цветов, в которые могут быть раскрашены ваши страны. Это уже приводит к вопросу: как он выглядит по своей структуре? Кажется логичным, чтобы это был список пар страна-цвет. Хороший способ создавать пары в Прологе - использовать функтор дефиса, например, uruguay-red.

solve сделал бы это:

  1. Соберите список стран - можете использовать setof
  2. Привязать список цветов к переменной (вызов coloring)
  3. Вызовите предикат (возможно, назовите его countries_colors), который построит список цветов страны. Ему потребуется список стран, список вариантов цвета и пустой список в качестве начального списка определенных пар страна-цвет.

countries_colors рекурсивно просматривает каждую страну в списке стран, выбирает цвет из списка цветов и проверяет, конфликтует ли страна этого выбранного цвета с какой-либо парой страна-цвет, определенной на данный момент (из списка определенных пар страна-цвет) . Это бы:

  1. Выбери цвет
  2. Проверить, конфликтует ли текущая страна и цвет с парой цвет страны в текущем списке цветов страны
  3. Шаг 2 возвращается, чтобы попробовать другой цвет, если это не удается
  4. Включите новую пару цветов страны в список цветов страны и рекурсивно сравните остальные страны с этим списком с разными цветами.

Если вы реализуете это правильно, в вашей текущей базе данных не будет решений. Это потому, что ваши факты смежности не могут быть правдой в двух измерениях. Вы можете получить решения, если просто удалите, например, adjacent(argentina, bolivia). из базы данных.

person lurker    schedule 12.05.2020