3. Папочка, а почему море синее? или Раскрашивание карты методом исчерпывающего поиска
3.
Папочка, а почему море синее?
или Раскрашивание карты методом исчерпывающего поиска
Чтобы на географической карте было удобно различать регионы, ее раскрашивают по следующему правилу: два региона должны быть окрашены в разные цвета, если их границы имеют более чем конечное число общих точек. (Обычно составители карт не страдают топологическими патологиями и не ищут вырожденных примеров, противоречащих здравому смыслу.) С другой стороны, картографам предстоит оплачивать типографские счета, поэтому, чем меньше цветов будет использовано, тем лучше. В частности, картографы, расписывающие карту как попало, распишутся лишь в своем легкомыслии: им придется использовать больше красок, чем это необходимо. Свои действия нужно планировать заранее. Итак, задача о раскрашивании карты сводится, в сущности, к определению минимального числа красок.
Для решения этой задачи обратимся к помощи компьютера. Тут нас подстерегают трудности: большинство ЭВМ лишено зрения, поэтому они не могут посмотреть на карту; к счастью, им нужно знать лишь, какие регионы являются соседями, т. е. смежны друг другу. Размер и форма регионов не влияют на раскраску, важно лишь наличие нетривиальных контактов между ними. Для представления отношения смежности полезно воспользоваться неориентированным графом.
Неориентированный граф состоит из конечного множества вершин и конечного множества ребер, связывающих вершины. Любые две вершины связаны не более чем одним ребром; не должно быть двух дублирующих друг друга ребер; кроме того, для рассматриваемой задачи мы запрещаем ребру связывать вершину с самой собой. На рис. 3.1 изображен неориентированный граф, представляющий первые 49 американских штатов. Ввести граф в ЭВМ несложно: достаточно перечислить все вершины, сопроводив каждую списком смежных ей вершин. Граф может не иметь вершин, а значит, и ребер; такой граф называется пустым. Вершина может быть изолированной, если нет ребер, связывающих ее с другими вершинами (примером тому могли бы служить Аляска и Гавайи); точно так же две части графа окажутся изолированными друг от друга, если нет ребер, их связывающих. Аналогия между картами и неориентированными графами столь тесна, что мы будем использовать эти понятия как равнозначные. Ну, а польза, приносимая графами, столь велика, что всем программистам следует иметь представление об их основных свойствах.

Рисунок 3.1. Топологическая карта Соединенных Штатов. Для нее достаточно четырех цветов. (WA — Вашингтон, OR — Орегон, CA — Калифорния, NV — Невада, ID — Айдахо, UT — Юта, AZ — Аризона, МТ — Монтана, WY — Вайоминг, СО — Колорадо, NM — Нью-Мексико, ND — Северная Дакота, SD — Южная Дакота, NE — Небраска, КА — Канзас, ОК — Оклахома, ТХ — Техас, MN — Миннесота, IA — Айова, МО — Миссури, AR — Арканзас, LA — Луизиана, WI — Висконсин, IL — Иллинойс, IN — Индиана, MS — Миссисипи, AL — Алабама, Ml — Мичиган, ОН — Огайо, KY — Кентукки, TN — Теннесси, GA — Джорджия, FL — Флорида, РА — Пенсильвания, WV — Западная Виргиния, VA — Виргиния, NC — Северная Каролина, SC — Южная Каролина, NY — Нью-Йорк, NJ — Нью-Джерси, DE — Делавэр, MD — Мэриленд, DC — округ Колумбия, VT — Вермонт, МА — Массачусетс, СТ — Коннектикут, WE — Мэн, NH — Нью-Гэмпшир, RI — Род-Айленд.)
Тема. Напишите программу, раскрашивающую карту в минимальное число цветов. Исходными данными служит список регионов с указанием соседей каждого региона. Результатом должен быть список регионов с приписанными им цветами и общее число использованных цветов. Обычно проще всего для обозначения регионов и цветов применить положительные числа, но куда приятнее (и полезнее для отладки), если допускается ввод более привычных названий. Исходные данные должны проверяться на непротиворечивость; выявляйте нелепые номера вершин и связанные с собой вершины. Постарайтесь сделать программу по возможности эффективной, иначе раскраска тяжелых случаев окажется для вас слишком дорогим удовольствием.
Указания исполнителю. Исходная карта не обязана быть планарной. В самом деле, вполне допустимыми крайними случаями служат карты, в которых любые два региона — соседи, и карты, в которых никакие два региона не являются соседями. Последний случай соответствует раскраске множества раздельных шаров, когда достаточно только одного цвета. Проверка планарности — важная тема информатики, ей посвящено немало статей. Возможно, вас заинтересует проверка гипотезы о четырех красках, утверждающей, что для любой планарной карты требуется не более четырех красок. Если вам удастся подтвердить или опровергнуть ее, вы сделаете себе имя[7].
Из ресурсов, требуемых данной задачей, самый важный — время. Конечно, нет смысла перебирать все возможные решения, поскольку их число быстро увеличивается с ростом числа регионов, а доля правильных решений (даже если таковых несколько) мала. Лучше воспользоваться методом перебора с возвратами. Начните с выбора некоторого региона и приписывания ему цвета. В дальнейшем переходите к соседнему нераскрашенному региону и пытайтесь приписать ему какой-нибудь из использованных цветов, совместимый с уже сделанной раскраской. (Может случиться, что раскрашивать больше нечего, тогда задача решена. Возможен и случай, когда не осталось нераскрашенных регионов, соседних с раскрашенными, т. е. попалась несвязная карта.) Если в некоторый момент новый регион не удается раскрасить, отступайте от уже раскрашенных регионов (в соответствии с порядком раскраски) до тех пор, пока не найдется регион, цвет которого можно изменить. Раскрасьте его в цвет, которого он ранее не имел, и снова продвигайтесь вперед. Если при отступлении вы возвратились в регион, раскрашенный первым, добавьте к своей палитре новый цвет и начните сначала.
Инструментовка. Для решения задачи достаточно таких структур данных, как массивы и стеки, поэтому годится почти любой алгебраический язык высокого уровня с подходящими управляющими структурами. (Попытки записи решения на Фортране или Бейсике должны показать скудость этих языков.) С другой стороны, перебор с возвратами выглядит элегантно в рекурсивной формулировке. Поэтому, возможно, полезным окажется язык с рекурсивными процедурами. И рекурсия, и подходящие структуры данных имеются в языке Лисп.
Длительность исполнения. Одному исполнителю на 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.
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОКЧитайте также
9.5. Вероятностный анализ методом Монте-Карло
9.5. Вероятностный анализ методом Монте-Карло До сих пор вы исходили из того, что компоненты проектируемых схем действительно имеют свои номинальные значения, что, к примеру, резистор, рядом с которым установлен индикатор значения 1 Ом, на самом деле имеет значение 1 Ом.
Составь лису методом «Перетащи и положи»
Составь лису методом «Перетащи и положи» Исходный файл: Makeafox-drag.fla Многие компьютерные игры созданы по подобию игрушек докомпьютерной эры. Одна из таких старых игрушек – "Mister Potato Head" (Господин картофельная голова). Она представляла собой набор пластиковых частей тела,
Море волнуется – раз!
Море волнуется – раз! Авторы: Сергей Цыпцын, Берто, ПаолоГлавной новостью первого дня конференции стала покупка пакета MudBox компанией Autodesk [Сергей Цыпцын находился на выставке в двух ипостасях: и как автор репортажа для «Компьютерры», и как лектор, приглашенный компанией
На море
На море Автор: Юрий РомановРоботы-моряки осваивают все больше военных специальностей. Первые дроны – боевые пловцы, предназначенные для охраны кораблей на рейде, через год-два заступят на службу.Вот беспилотный разведывательный и ударный самолет ВМС Cormorant («Большой
Для чего стартапы уходят в море — и почему это не решает всех земных проблем? Евгений Золотов
Для чего стартапы уходят в море — и почему это не решает всех земных проблем? Евгений Золотов Опубликовано 16 октября 2013 О драме в Баренцевом море наслышаны все, но сейчас за тысячи километров от неё, в вечно тёплых водах залива Сан-Франциско,
СОФТЕРРА: Организация информации: Как не утонуть в море данных?
СОФТЕРРА: Организация информации: Как не утонуть в море данных? Автор: Илья ШпаньковВероятно, мало найдется компьютерщиков, хоть раз в сердцах не назвавших Интернет «всемирной информационной свалкой». Впрочем, виновата в этом во многом не сама Сеть, а инструменты, с
Кивино гнездо: Море лжи и привет от «Автобазы» Киви Берд
Кивино гнездо: Море лжи и привет от «Автобазы» Киви Берд Опубликовано 12 декабря 2011 года Оба этих сюжета — нынешний «иранский» и давнишний, когда над Уралом сбили U-2, — похожи друг на друга как братья-близнецы во всём, что касается честности
Сергей Еремин Море возможностей
Сергей Еремин Море возможностей Приветствую всех читателей «Компьютерры», рад, что есть возможность пообщаться. Меня зовут Сергей Еремин, я работаю в департаменте стратегических технологий российского представительства Microsoft и занимаюсь проектами по поддержке
Тестирование методом «черного ящика»
Тестирование методом «черного ящика» Термин «черный ящик» относится к любым компонентам или частям системы, чьи внутренние функции скрыты от пользователя системы. При тестировании методом «черного ящика» главное внимание уделяется изучению результатов работы системы
Как Apple составит карты наших домов, и почему мы с радостью на это согласимся Андрей Письменный
Как Apple составит карты наших домов, и почему мы с радостью на это согласимся Андрей Письменный Опубликовано 29 марта 2013Новости о том, что какая-то из крупных компаний потратила энную сумму денег, чтобы присоединить к себе очередной стартап, настолько привычны, что им редко
Кивино гнездо: Море лжи и привет от "Автобазы"
Кивино гнездо: Море лжи и привет от "Автобазы" Автор: Киви БердОпубликовано 12 декабря 2011 годаОба этих сюжета - нынешний "иранский" и давнишний, когда над Уралом сбили U-2, - похожи друг на друга как братья-близнецы во всём, что касается честности участвующих в конфликте сторон.