Инструментовка. Для решения задачи достаточно таких структур данных, как массивы и стеки, поэтому годится почти любой алгебраический язык высокого уровня с подходящими управляющими структурами. (Попытки записи решения на Фортране или Бейсике должны показать скудость этих языков.) С другой стороны, перебор с возвратами выглядит элегантно в рекурсивной формулировке. Поэтому, возможно, полезным окажется язык с рекурсивными процедурами. И рекурсия, и подходящие структуры данных имеются в языке Лисп.
Длительность исполнения. Одному исполнителю на 1 неделю.
Развитие темы. При использовании метода перебора с возвратами огромное влияние на время работы оказывает порядок выбора регионов. Учитывая этот эффект, можно заранее упорядочить регионы или использовать некоторые эвристики для выбора очередного региона. По-видимому, те регионы, у которых много соседей, раскрасить труднее, поскольку на их цвет накладывается больше ограничений. Из тех же соображений почти изолированную группу регионов следует рассмотреть отдельно, так как если ее не удастся раскрасить некоторым набором цветов, то и всю карту — тоже. Идея в обоих случаях состоит в том, что, если раскраска какого-либо региона может вызвать затруднения, ее нужно выполнить пораньше, чтобы не тратить время на разрушение почти законченной раскраски. Разумеется, полное решение такой «предварительной» задачи равносильно решению исходной задачи, но ведь и небольшой вклад может принести вполне ощутимую прибыль. Сравните несколько стратегий предварительного упорядочения по стоимости и эффекту.
Литература
Битнер, Рейнгольд (Bitner J. R., Reingold E. M.). Backtrack Programming Techniques. С ACM, 18, 11, pp. 651–656, November 1975.
Эта статья — очень краткое руководство по программированию методом перебора с возвратами. Но если приведенных авторами примеров окажется недостаточно, чтобы вы поняли суть метода, к вашим услугам обширная библиография по проблемам, которые решены методом перебора с возвратами или которые целесообразно этим методом решать.
Ope (Ore О.). The Four Color Problem. Academic Press, New York, 1967.
В книге дан обзор математических вопросов, связанных с гипотезой четырех красок. По ней можно ознакомиться со многими разделами теории графов; можно почерпнуть и способ ускорения перебора с возвратами. Но не пытайтесь найти в книге быстрого алгоритмического решения.
*Ершов А. П. Введение в теоретическое программирование. — М.: Наука, 1977.
