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

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

Инструментовка. Для решения задачи достаточно таких структур данных, как массивы и стеки, поэтому годится почти любой алгебраический язык высокого уровня с подходящими управляющими структурами. (Попытки записи решения на Фортране или Бейсике должны показать скудость этих языков.) С другой стороны, перебор с возвратами выглядит элегантно в рекурсивной формулировке. Поэтому, возможно, полезным окажется язык с рекурсивными процедурами. И рекурсия, и подходящие структуры данных имеются в языке Лисп.

Длительность исполнения. Одному исполнителю на 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.

*Абрамов С. А. Математические построения и программирование. М.: Наука, 1978.

*Харари Ф. Теория графов, гл. 12. Пер. с англ. — М.: Мир, 1973.

4. Печатник-подмастерье, или Автоматическое форматирование текста

Известно вам или нет, но с недавних пор еще одно тяжкое бремя свалилось с плеч человечества. Заботу о создании и размещении опечаток в тексте взяли на себя компьютеры. Там, где раньше линотипы отливали горячий свинец в строки, теперь небольшие, вполне доступные по цене компьютеры методами фотонабора выдают нескончаемые потоки готовых текстов. Жаль только, что с появлением новых эффективных методов уходит очарование доброго старого времени. Ну какой, скажите, интерес выискивать опечатки в воскресном номере Нью-Йорк Таймс, в которых и заключается весь юмор этого обширного собрания важных скучностей, если вы знаете, что компьютер способен делать ошибки в сотни раз быстрее, чем человек? Такова цена, которую приходится платить за прогресс.

Конечно, реальный прогресс заключен в том, что в издательском деле компьютер привлекается в качестве подмастерья, некоего чудесного помощника, способного выполнять черную работу быстро и — при аккуратном программировании — почти бесплатно. Программисты уже пользуются руководствами по вычислительной технике, изданными при помощи ЭВМ. Такие руководства часто очень неудобны для чтения из-за неудачного шрифта, которым снабжено печатающее устройство машины. Однако большинство людей и не подозревает, что многие журналы, газеты и книги также печатаются с помощью ЭВМ. Они выглядят гораздо привлекательнее благодаря тому, что машина не только редактирует и соответствующим образом располагает текст, но и управляет специальными периферийными фотонаборными устройствами. Последние, обладая десятками шрифтов различной гарнитуры, выдают готовую к изданию продукцию. Черновик настоящей книги также был подготовлен при помощи такой системы, и первые читатели были уверены, что держат в руках фотокопию реальной книги, а вовсе не некий аналог обычного машинописного экземпляра.

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