Повышение эффективности программы раскраски карты
Задача раскраски карты состоит в том, что каждому государству па заданной карте должен быть присвоен один из четырех указанных цветов таким образом, чтобы ни в одпой из пар соседних государств не использовался одинаковый цвет. В математике доказана теорема, которая гарантирует, что такое решение всегда возможно.
Предположим, что карта задана с помощью следующего отношения с описанием соседних государств: ЩЫ Country, Neighbours)
где Neighbours — список государств, граничащих с государством Country. Поэтому карта Европы, в которую входит 30 государств, может быть задана (в алфавитном порядке) следующим образом:
щЫ albania, [gr еесе, macedonia» Yugoslavia]). ngb( andorra, [franee, Spain]>.
Slovakia, Slovenia,ЬSwitzerland])ГгааПУ' Hungary, "^ lieChtenS"in'
Предположим, что решение должно быть представлено в виде списка пар в форме Country/Colour
которая определяет цвет для каждого государства на указанной карте. Для заданной карты названия государств определены заранее, и задача состоит в поиске значений для цветов. Таким образом, для карты Европы задача состоит в поиске подходящей конкретизации переменных С , C2, СЗ и т.д. в следующем списке:
{ albania/Cl, ar.de r га/С 2, austria/СЗ, . ..]
Предположим, что определен предикат colours( Countгy_colour_list!
который принимает истинное значение, если список Country_colour_list соответствует ограничению по раскраске карты применительно к указанному отношению ngb. Предположим, что в качестве четырех цветов выбраны желтый, синий, красный и зеленый. Условие, согласно которому ни одно из двух соседних государств не должно быть окрашено на карте в одинаковый цвет, можно сформулировать на языке Prolog следующим образом:
Глава 8.Сталь и методы программирования
colours ( []).
colours С [Country/Colour I Rest]) :-
colours! Rest},
member; Colour, [yellow, blue, red, green]),
not( member Countryl /Colour, Rest), neighbour* Ccuntry, Countryl)).
neighbour ( Country, Country!) :-ngb( Country, neighbours), member; Countryl, Neighbours).
В этой программе отношение member (x, L), как обычно, обеспечивает проверку принадлежности к списку. Приведенная выше программа хорошо работает при наличии простых карт с небольшим количеством государств. Но при обработке карты Европы могут возникнуть проблемы. При условии, что доступен встроенный предикат setcf, одна попытка раскрасить карту Европы может состоять в следующем. Вначале определим вспомогательное отношение: country! С) ;- пды; С, _}.
После этого вопрос для определения раскраски карты Европы можно сформулировать следующим образом:
?- setofC Cntry/Colour, countryl Cntry), CountryColourList), colours i CountryColourList!.
Цель setof формирует образец списка государство/цвет (CountryColOurList) для карты Европы, в котором неконкретизированные переменные будут обозначать цвета. Предполагается, что после этого цель colours позволит конкретизировать цвета. Но такая попытка, скорее всего, окончится неудачей из-за низкой эффективности программы.
Подробное изучение способа, с помощью которого система Prolog пытается достичь цели colours, обнаруживает причину неэффективности. Государства в списке го суд аре тв/ цвет о в расположены в алфавитном порядке, который не имеет ничего общего с их географическим местонахождением. Порядок назначения цветов государствам соответствует их последовательности в списке (начиная с конца), которая в данном случае не зависит от отношения ngb. Поэтому процесс назначения цветов начинается в какой-то одной части карты, переходит к совсем иной ее части и т.д.; при этом передвижение по карте происходит в основном случайным образом. Это может вполне приводить к таким ситуациям, в которых государство, стоящее в очереди на раскраску, окружено многими другими государствами, уже окрашенными во все четыре возможных цвета. Поэтому возникает необходимость использовать перебор с возвратами, что приводит к снижению эффективности.
Поэтому очевидно, что эффективность программы зависит от того, в какой последовательности раскрашиваются государства. Интуиция подсказывает следующую простую стратегию раскраски, которая должна быть лучше по сравнению со случайной; начать с некоторого государства, имеющего много соседей, после этого перейти к его соседям, затем к соседям соседей и т.д. Поэтому при раскраске карты Европы лучше всего начать с Германии (которая имеет больше всего соседей). Безусловно, при формировании списка государств/цветов Германию необходимо поместить в конец списка, а другие государства добавлять в начало списка. Благодаря этому алгоритм раскраски, запуск которого происходит с конца списка, начнет свою работу с Германии и будет проходить по списку от одного соседнего государства к другому.
Такой образец списка государств/цветов позволяет существенно повысить эффективность по сравнению с первоначальным, алфавитным порядком, и теперь возможные варианты раскраски для карты Европы вырабатываются без каких-либо сложностей.
Упорядоченный должным образом список государств может быть сформирован вручную, но этого делать не стоит. Такую задачу позволяет решить приведенная ниже процедура raakelist. Эта процедура начинает формирование списка с некоторого указанного государства (в данном случае с Германии) и собирает государства в список, называемый закрытым (Closed). Вначале каждое государство помещается в другой список, называемый открытым (Open), и только после этого переносится в список
180 Часть I. Язык Prolog
Closed. После того как каждое государство переносится из списка Open в список Closed, в список Open добавляются его соседи.
Jtia/.elisi : List] :-
collect ( [germany], [], List).
collect { [}, Closed, Closed). % Больше нет кандидатов на включение
% в список Closed
collect { [X| Open), Closed, List) :-
member ( X, Closed), !, Ъ Элемент Х уже внесен в список Closed?
collect( Open, Closed, List) . ft Отбросить элемент Х
collect! [X | Open], Closed, List) :-
ngb( X, Ngbs), % Найти соседей элемента X
conc( Rgba, Open, Openl] , % Поместить их в список Openl
collect! Openl, [X | Closed], List). \ Внести в список остальные элементы
Отношение cone, как обычно, представляет собой отношение для конкатенации списков.