Перевод статьи: Interesting Map Problems
Дон Кнут работает над 4-м томом «Искусство компьютерного программирования». Одна из глав посвящена «Диаграммам двоичных решений» и их применению, тема, которую я нахожу очень интересной. Кнут показывает, что разнообразные интересные задачи графов могут быть закодированы как Булевы формулы, а производные БДР представляют все возможные решения проблемы. Часто существует некий критерий оптимизации, и довольно легко извлечь «лучшее» решение из БДР простым алгоритмом динамического программирования.
Здесь мы покажем несколько примеров в виде лестницы, используя график, представляющий 48 смежных состояний, с узлом для каждого состояния и границей между двумя состояниями, если они имеют общую границу. Для каждой из карт, если вы щелкните по изображению, вы попадете в исходный документ в формате SVG. Вот график, на котором расположены узлы в заглавных буквах состояний:
Столичные туры
Предположим, вы хотите посетить столицу 48 штатов с требованием, чтобы вы проходили через каждый штат только один раз. (Другими словами, вы хотите найти гамильтонский путь на графике.) Как видно из вышеприведенной карты, если вы будете следовать по самому прямому маршруту между столицами штатов, то часто будете проезжать через другой штат, или, в случае проезда из Лэнсинга, штат Мичиган, в Мэдисон, штат Висконсин, вы проедете через озеро Мичиган. Вместо этого, вы должны выбрать кратчайший маршрут, который остается в пределах двух штатов для каждого этапа путешествия. Давайте назовем такой маршрут «Столичным туром». Вот схема допустимых маршрутов между штатами:
Основываясь на простом анализе, плюс усилия Кнута, мы можем сказать следующее:
- Все туры должны начинаться или заканчиваться в штате Мэн, так как у Мэна есть только один сосед. Мы будем использовать штат Мэн в качестве отправной точки.
- Все туры должны заканчиваться за пределами Нью-Йорка, так как это точка артикуляции.
- Всего существует 68 656 026 различных столичных туров.
Вот самый короткий столичный тур, общей протяженностью 11 698 миль:
Это самый длинный столичный тур, в общей сложности 18 040 миль:
Раскраска графиков
Еще один интересный класс проблем связан с раскраской карты. Правило заключается в том, что никакие два соседних состояния не могут иметь одинаковый цвет. Известный четырехцветный теорий утверждает, что любой плоскостной граф может быть раскрашен максимум четырьмя цветами.
Так как БДР кодирует все возможные решения булевой формулы, мы можем легко вычислить, сколько существует решений. Для окрашивания графов мы корректируем наши подсчеты, чтобы исключить симметрию из-за произвольного назначения значений цвета (4! симметричные случаи для 4-цветного окрашивания).
Для окраски смежных 48 состояний существует 533 816 322 048 возможных окрасок. (Это 1/2 числа, о котором сообщил Кнут, так как его карта включает Вашингтон как 49-й «штат», и ему может быть присвоен любой из двух цветов, не используемых для Мэриленда и Вирджинии). Вот несколько интересных примеров специальных раскрасок:
Сбалансированная раскраска, в которой каждый цвет используется ровно для 12 штатов. Таких раскрасок 12 554 677 864, что является удивительно высоким показателем 2,4% от всех возможных раскрасок.
Несбалансированная раскраска, в которой один из цветов (зеленый) используется как можно меньше (2 состояния). Существует всего 288 способов раскраски карты так, что один из цветов используется всего дважды.
Несбалансированная раскраска, при которой один из цветов (желтый) используется как можно меньше (18 состояний). Есть 71 002 368 способов окрасить карту так, чтобы один цвет использовался 18 раз.
Сочетание обоих. Раскрашивание с использованием цветов 2, 13, 15 и 18 раз. Эта последовательность 1) слева направо, использует каждый цвет подряд наименьшее возможное количество раз, и 2) справа налево, использует каждый цвет подряд наименьшее возможное количество раз. Существует 24 таких решения.
С точки зрения программ раскраски графов, карта 48 штатов США достаточно проста. Более сложную карту смотрите на веб-странице на сайте McGregor Graph.