Этюды для программистов

29. Красьте с нами, или... ПОЛНОЕ РЕШЕНИЕ ЗАДАЧИ

В данной главе в полном виде приводится программа для задачи о раскраске карты (см. гл. 3). Читатели, которым довелось испытать это на собственной шкуре, знают как трудно описывать программу, излагая алгоритм прозрачно и просто. Когда решение головоломки рассказано, обычной реакцией бывает: «Как я не догадался!» вместо: «Как здорово!» Ну а программа — это, конечно, тоже решение головоломки. Из описаний всегда устраняют дух исследования, историю неудавшихся подходов и отступлений, упоминание о глупых ошибках, сбивавших с правильного пути. Если бы мы попытались полностью изложить процесс разработки программы, вы бы не знали, плакать вам или смеяться над тупостью автора. Так что лучше пойдем уже проторенной дорогой от задачи к решению, лишь изредка поглядывая по сторонам. [61]

По условию задачи требуется раскрасить карту или неориентированный граф в минимальное число цветов так, чтобы никакие два соседних региона (никакие две смежные вершины) не были одного цвета. Хотя в данный момент не требуется точно специфицировать формат исходной и выводимой информации, а также внутреннее представление данных, можно сообразить, какие свойства графа будут существенны для любой программы. Очевидно, нужно знать число вершин графа, уметь регулярным образом обращаться к вершинам, уметь раскрашивать вершины и узнавать их цвет, определять, являются ли две вершины смежными, и, наконец, нужно уметь порождать много различных цветов. Проще всего удовлетворить перечисленным требованиям, обозначив вершины натуральными числами 1, 2, ..., n, где n — общее количество вершин. Аналогично и цвета обозначим натуральными числами (ясно, что при этом в нашем распоряжении окажется много цветов). Вопрос о конкретном способе определения смежности вершин целесообразно отложить.

Раскрашивать можно двумя способами: либо предположить, что каждая вершина уже раскрашена в свой цвет и попытаться избавиться от нескольких цветов, либо предположить, что ни одна вершина еще не раскрашена, и пытаться добавлять как можно меньше цветов. Однако на любом пути мы сталкиваемся с неприятным теоретическим результатом (или с отсутствием оного): никто не знает, как раскрасить карту, не перебрав для худшего случая все возможные раскраски с минимальным числом цветов. Большинство специалистов считает, что нет более быстрого метода раскрашивания карты, чем перебор всех вариантов. Иными словами, какой бы умной ни была ваша программа и как бы быстро она ни работала в среднем, найдутся карты с n вершинами, требующие к цветов, на раскраску которых программа затратит порядка kⁿ единиц времени. Возможно, кому-нибудь посчастливится найти алгоритм, и для худшего случая оказывавшийся не столь расточительным, но теоретики считают это маловероятным. Так что давайте займемся простой быстрой программой, а не суперсложной, которая вряд ли будет лучше.[62]

Предлагаемое решение основано на наблюдении, что если некоторый подграф нельзя раскрасить в k цветов, то и весь граф, очевидно, тоже нельзя раскрасить в к цветов. На каждом шаге нашего алгоритма мы пытаемся добавить к уже раскрашенному подграфу еще одну вершину. Если сделать это не удастся, текущий раскрашенный подграф перекрашивается всеми возможными способами с использованием тех же цветов. Если новую вершину добавить все же нельзя, число цветов увеличивается на единицу» поскольку найден подграф, не раскрашиваемый выделенными цветами. В описании алгоритма предполагается, что есть вектор цвет, содержащий цвета, приписанные каждой вершине. Логическая функция связь позволяет узнать, связана ли вершина i с вершиной j.

1. (Начальная установка.) Предположим, что в графе имеется числовершин вершин, что переменная старшийцвет содержит номер старшего из уже использованных цветов, а нуль показывает, что вершина еще не наделена цветом. Для всех вершин n установить цвет[n] равным нулю (т. е. сделать все вершины нераскрашенными). Установить старшийцвет равным нулю, а переменную равной единице.

2. (Основной цикл.) Пока текущаявершина не превзойдет числовершин, выполнять шаги с 3-го по 7-й. Этим шагом начинается цикл, который повторяется, пока не будут раскрашены все вершины. Перед началом каждого прохождения цикла все вершины от 1 до текущаявершина — 1 правильно раскрашены в старшийцвет цветов.

3. (Подготовка одного узла.) Увеличить цвет[текущаявершина] на единицу. Установить булеву переменную флагцикла равной значению отношения цвет[текущаявершина] <= старшийцвет. Теперь рассматриваемая вершина имеет ненулевой цвет, и необходимо проверить, совместима ли текущаявершина со своими соседями. Заметьте, что впервые добавляемая вершина всегда имеет нулевой цвет. Прибавляя единицу к нулю, мы наделяем вершину допустимым цветом. Пока цикла имеет значение истина, выполнять шаги 4 и 5.

4. (Проверка цвета смежных вершин.) Присвоить переменной флагцикла значение ложь и установить i равным единице. Пока i меньше, чем текущаявершина, выполнять шаг 5.

5. (Проверка цвета каждого соседа.) Если вершина i и текущаявершина связаны (т. е. если связь(i, текущаявершина) имеет значение «истина») и если цвет[i] и цвет[текущаявершина] равны, значит, текущаявершина имеет недопустимый цвет. В этом случае установить значение i равным текущаявершина, чтобы прервать цикл, начинающийся в шаге 4, увеличить цвет[текущаявершина] на единицу чтобы попробовать следующий цвет, и установить значение флагцикла равным значению отношения цвет[текущаявершина] <= старшийцвет. В противном случае просто увеличить i на единицу, чтобы проверить следующего соседа. Заметьте, что последнее присваивание переменной флагцикла перекроет присваивание в шаге 4, но может установить переменную флагцикла равной значению ложь. Далее, если начинающийся в шаге 4 цикл завершается нормально (т. е. без насильственного присваивания переменной текущаявершина значения i), произойдет выход из цикла, начинающегося в шаге 3. Важно, чтобы при проверке допустимости раскраски использовались лишь вершины, номера которых строго меньше, чем текущаявершина, поскольку вершины с большими номерами еще не раскрашены.

6. (Продвинуться или вернуться?) Если текущаявершина получила допустимый цвет, мы хотим перейти к следующей вершине; в противном случае необходимо отступить. Поэтому, если цвет [текущаявершина] > старшийцвет, установить цвет [текущаявершина] равным нулю и уменьшить значение текущаявершина на единицу; в противном случае увеличить значение текущаявершина на единицу. Заметьте, что цвета вершин с номерами большими, чем текущаявершина, по-прежнему нулевые и что, когда мы возвращаемся к уже раскрашивавшейся вершине, мы продолжаем продвигать ее цвет со значения, оставшегося от предыдущей обработки.

7. (Добавление цвета, если это необходимо.) Если вершина нулевая, увеличить старшийцвет на единицу и установить значение текущаявершина равным единице. Если мы вернулись к самому началу, число цветов необходимо увеличить.

Легко видеть, что данный алгоритм должен завершиться. В крайнем случае, он остановится, когда все вершины получат разные цвета. Также достаточно ясно, что перед началом каждого прохождения основного цикла все вершины от первой до (текущаявершина — 1) имеют допустимую раскраску. Чуть менее очевидно, что старшийцвет увеличивается только тогда, когда невозможно раскрасить некий начальный подграф выделенным числом цветов. Удостовериться в этом вам помогут эксперименты на небольших графах. Заметьте, что алгоритм правильно работает для пустого графа, для графов, все вершины которых изолированы, и для графов, все вершины которых связаны.

В нашей реализации мы используем Фортран. Ясно, что Фортран — очень бедный язык, с недостаточными возможностями определения данных и управления последовательностью действий. Однако мы выбрали его как раз для того, чтобы показать, что даже на неудобном языке можно написать хорошо структурированную, ясную программу. Теоретически каждую программу можно было бы написать на более новом, более выразительном языке; на практике большинству программистов время от времени приходится работать на архаичном языке, но плохие инструменты не могут служить оправданием для плохого программирования.

Логическую функцию связь на Фортране можно представить двумерным логическим массивом, в котором (i,j)-й элемент имеет значение истина тогда и только тогда, когда вершина i связана с вершиной j. Первый элемент ввода — это запись с количеством вершин раскрашиваемого графа. Затем читаются наборы записей, где каждый набор описывает связи одной вершины. Первая запись набора содержит номер вершины и количество ее соседей; в оставшихся записях в произвольном порядке перечисляются соседи. Признаком конца исходных данных служит нулевой номер вершины. Вершины можно описывать в произвольном порядке, а описание одной вершины можно разбивать на несколько частей. Когда вершина i связывается с вершиной j, вершина j автоматически связывается с вершиной i. Единственными возможными ошибками являются выход номера вершины за допустимые границы и попытка связать вершину с ней самой. Ниже воспроизводится реальная программа.

Исходные данные взяты с рис. 1 из гл. 3. Штаты перенумерованы сверху вниз; столбцы упорядочены слева направо. В каждой головной перфокарте справа присутствует название штата; вследствие заданного формата существенны только первые восемь литер карты. Для экономии места в книге данные разбиты на две колонки, но в остальном они точно соответствуют требованиям программы.

Выдача выглядит наилучшим образом, если ее напечатать АЦПУ и повесить на стену. Пропорции приведенной в книге выдачи несколько нарушают симметрию. Заметьте, что горизонтальная печать решения экономит много бумаги, без всякой потери информации. Первоначально мы хотели напечатать номера и цвета вершин вертикально, что делается несколько проще, но выдача при этом получается весьма неряшливой. Реальная выдача приведена на предыдущей странице.

Строки 1—19. Заголовок программы служит тем же целям, что и аннотация в научной статье. Вне зависимости от того, велика или мала программа, в ее начале должна присутствовать такого рода информация. В частности, в программе обязательна ссылка на соответствующую внешнюю документацию.

Строки 22—26. Если бы программа была побольше, перед определением данных следовало бы поместить больше материала по алгоритмическим вопросам. В нашем же случае тексту программы предшествует полный словарь. Поскольку размеры модулей не должны превышать нескольких страниц, мы предпочли толковый словарь, в котором переменные упоминаются группами в соответствии со своей ролью, важностью и местом употребления. Очевидно, количество пояснений в словаре зависит от других комментариев, но ни одна переменная не должна быть выпущена. Мы пытались сделать шестилитерные имена мнемоничными, однако нелегко бороться против одного из глупейших фортрановских правил.

Строки 62—89. Все переменные продекларированы, хотя в Фортране декларации не обязательны. Во-первых, лучше перестраховаться, а во-вторых, лучше увериться, что читающий программу точно знает наши намерения. Комментарии в строках 62—65 поясняют, почему мы отклоняемся от стандарта: к этому нас вынуждает компилятор; точно указаны изменения, которые могут потребоваться при выполнении программы на другой вычислительной установке. Во вводе/выводе использованы переменные номера каналов, так что если программа переносится на другую установку с другими соглашениями о номерах, для налаживания работы ввода/вывода потребуется только одно изменение.

Строки 92—98. Начиная с этого места, перемежаются абзацы комментариев на естественном языке и абзацы инструкций на Фортране. Не давайте комментарии слишком часто, иначе будет трудно уследить за порядком выполнения программы. Разумеется, ничто не может оправдать недостаток комментариев. В нашей программе 145 строк комментариев и 157 строк с инструкциями на Фортране. По общему правилу комментарии пишутся перед соответствующими инструкциями.

Строки 105—109. Помечать следует только инструкции CONTINUE и FORMAT. В Фортран-программе всегда много меток, и при отладке часто приходится перемещать их. Не накликайте беды, помечая самостоятельные инструкции, при перемещении которых легко ошибиться. По тем же причинам в одной строке закрывайте только один DO-цикл.

Строки 110—115. Проверка исходных данных — одновременно одна из самых скучных и самых важных обязанностей программы. Не доверяйте ничьим данным, даже своим собственным. Обратите внимание на инверсию смысла логических проверок в условных инструкциях. Подобная инверсия — обычное для Фортрана дело. Трудно выработать твердую схему для ступенчатой записи условных инструкций (ввиду отсутствия else), но имеющиеся в программе примеры показывают возможные варианты.

Строки 139-151. Метка 65 демонстрирует целесообразность расположения меток в порядке возрастания, с большим постоянным шагом. Проверка исходных данных, расположенная непосредственно перед меткой 65, добавлена после того, как при подготовке данных была допущена ошибка. Когда метки упорядочены, вставка дополнительных инструкций не вызывает затруднений. Обратите внимание также на использование переменной J. Она нужна потому, что стандартный Фортран не допускает употребления в индексных выражениях переменных с индексами. Только следуя всем, даже неприятным, правилам, можно гарантировать переносимость и правильность. Большинство компиляторов не требует временного использования J, но лучше быть готовым ко всему.

Строки 155-162. Комментарии должны разъяснять, почему инструкция делает то, что она делает; как это делается, обычно видно из самой инструкции.

Строки 196—211. Было бы излишним переписывать в программу из внешних документов весь алгоритм; читающего программу будут направлять к источникам соответствующие ссылки на литературу. Правда, для этого хорошую внешнюю документацию нужно иметь. О ней следует позаботиться до начала работы над программой.

Строки 238—239. Стоящая особняком инструкция перехода может показаться несколько странной. Ее существование объясняется тем, что структура программы в точности повторяет структуру алгоритма. «Поборники эффективности» могут ворчать, что в строке 226 достаточно заменить GOTO 220 на GOTO 170, экономя две строки исходного текста и одну-две микросекунды на каждое прохождение цикла. Так-то оно так, но можно ли экономить за счет понятности? Сколько микросекунд машинного времени нужно сэкономить, чтобы окупить 5 мин времени программиста?

Строки 277—301. Все форматы собраны в конце программы, чтобы не затемнять логику ее работы. Каждый класс инструкций ввода/вывода, каждый файл, канал, каждое обращение имеет свою последовательность меток. Эти последовательности не перемешиваются друг с другом и с обычными программными метками. Заметьте, что холлеритовы данные передаются посредством старомодных форматов nН, поскольку по стандарту Фортрана эти глупые счетчики необходимы, хотя большинство компиляторов их не требует.

На этом заканчивается обсуждение раскрашивания карт. Укажем, что на первоначальную разработку алгоритма ушло около 5 часов, написание программы заняло около 8 часов, ввод ее текста в системе с разделением времени занял около 3 часов, а тестирование и отладка потребовали около 2 часов. Большая часть тестового времени ушла на проверку соответствия между вводом и выводом. Две ошибки при вводе текста и две неправильно расположенные метки обнаружились либо компилятором, либо по нелепой первой выдаче. Дополнительная проверка ввода придумана во время подготовки тестовых данных. Алгоритм содержал один логический дефект, и его удалось вскрыть посредством первого же реального множества данных.

Эта задача иллюстрирует также важность документирования для будущей работы. Приведенный здесь алгоритм на самом деле разработан примерно за 6 месяцев до написания главы. Была формально доказана его правильность. Группа программистов, видевших и алгоритм, и доказательство, единодушно признали их совершенно безукоризненными. Но пока автор собирался сесть писать главу, какие-то жулики украли единственную копию алгоритма и доказательства (хотя трудно себе представить, для чего им эти бумаги). Пришлось потратить еще около 5 часов на восстановление первоначального хода мыслей; при этом снова была допущена логическая ошибка. Пусть же поразят компьютер этих жуликов вечные ошибки четности!

Кнут (Knuth D. E.). Estimating the Efficiency of Backtrack Programs. Mathematics of Computation, 29, 129, pp. 121—136, 1976.

Хотя для наихудшего случая время работы алгоритма раскраски карт экспоненциально зависит от размера исходного графа, среднее время обычно весьма невелико. Однако аналитический вывод среднего значения, видимо, превышает наши возможности. Кнут описывает метод для оценки скорости работы программ, действующих по методу перебора с возвратами. Оценка дается вручную после просчета некоторых тестовых случаев. Кнут приводит примеры, иллюстрирующие его метод.

Эппл, Хейкен (Appel К., Haken W.). Every Planar Map is Four Colorable. Bulletin of the American Mathematical Society, 82, 5, pp. 711—712, September 1976. Стин (Steen L. A.). Solution of the Four Color Problems. Mathematics Magazine, 49, 4, pp. 219—272, September 1976.

Иссяк еще один источник диссертаций. Эппл и Хейкен объявили о доказательстве истинности гипотезы о четырех красках. В момент написания данной главы доказательство циркулировало в рукописном виде, и несколько видных специалистов по комбинаторике считали, что, по-видимому, оно верно. К моменту выхода в свет нашей книги доказательство наверняка появится в математических журналах. Стин описывает метод доказательства и его значение для математики. ЭВМ интенсивно использовалась для разработки доказательства и для проверки 1936 случаев в окончательном варианте доказательства.

*Яглом И. М. Четырех красок достаточно. «Природа», 1977, № 6, с. 20—25.

*Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.

Это как раз та книга, с которой программисту полезно советоваться в трудных случаях. На стр. 449 содержится ссылка на статью с подробным обсуждением теоремы о четырех красках.

*Н. Вирт. Систематическое программирование. Введение. Пер. с англ. — М.: Мир, 1977. На наш взгляд было бы интересно испытать разные эвристики. Из п. 15 4 книги Н. Вирта читатель увидит, как можно механически получать программы, работающие по голой схеме перебора с возвратами.

* Партия переводчика. В 1978 г. был утвержден новый американский стандарт языка Фортран. Описываемый в нем язык получил название Фортран-77 (см. Катцан Г. Язык Фортран-77. Пер. с англ.— М.: Мир, 1982). Ознакомившись с приводимой ниже программой, читатель, разумеется, легко заметит новые возможности Фортрана. Поскольку программа получена прямолинейным переписыванием авторского варианта, трактовка новых возможностей не вызовет затруднений. По той же причине отсутствуют комментарии. Лишь два момента вызвали небольшие заминки при переписывании программы. Во-первых, в строке 141, видимо, допущена опечатка и вместо OR следует читать AND. Во-вторых, инструкции 232 и 237 GOTO 190 выполняют сразу две функции: завершают условную инструкцию и передают управление на начало цикла. Любопытно сопоставить их с инструкцией 239 GOTO 170, которой автор уделил немало внимания. Небезынтересно также сопоставить авторские замечания с новым вариантом программы (см. с. 254—256).