Повышение эффективности программы раскраски карты

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

Предположим, что карта задана с помощью следующего отношения с описанием соседних государств: _ЩЫ Country, Neighbours)

где Neighbours — список государств, граничащих с государством Country. Поэтому карта Европы, в которую входит 30 государств, может быть задана (в алфавитном порядке) следующим образом:

щЫ albania, [gr еесе, macedonia» Yugoslavia]). ngb(andorra, [franee, Spain]>.

Slovakia, Slovenia,^ЬSwitzerland])^ГгааПУ' Hungary, "^ ^lieChtenS"ⁱⁿ'

Предположим, что решение должно быть представлено в виде списка пар в форме 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, как обычно, представляет собой отношение для конкатенации списков.