Интересные проблемы с картой

Ссылка на источник: http://www.cs.cmu.edu/~bryant/boolean/maps.html

Интересные проблемы с картой

Дон Кнут работает над четвертым томом «Искусство компьютерного программирования» (Art of Computer Programming). Одна из глав посвящена двоичным диаграммам решений и их приложениям, и эта тема мне очень интересна. Кнут показывает, что множество интересных графовых задач может быть закодировано в виде булевых формул, а полученный BDD представляет все возможные решения проблемы. Часто существует некоторый критерий оптимизации, и довольно просто извлечь «лучшее» решение из BDD с помощью простого алгоритма динамического программирования.

Здесь мы показываем несколько примеров, используя график, представляющий 48 смежных состояний, с узлом для каждого состояния и ребром между двумя состояниями, если они имеют общую границу. Для каждой из карт, если вы нажмете на изображение, вы получите исходный документ в формате SVG. Вот график, на котором расположены узлы в столицах штатов:


Столичные туры

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

Основываясь на простом анализе плюс усилия Кнута, мы можем сказать следующее:

  • Все туры должны начинаться или заканчиваться в штате Мэн, так как Мэн имеет только одного соседа. Мы будем использовать Мэн в качестве отправной точки.
  • Все туры должны заканчиваться за пределами Нью-Йорка, так как это точка артикуляции.
  • Всего 68,656,026 различных туров по столице.

Вот кратчайший тур по столице, в общей сложности 11 698 миль:

Вот самая длинная экскурсия по столице на общую сумму 18 040 миль:

Раскраска графика

Другой интересный класс проблем связан с раскрашиванием карты. Правило состоит в том, что никакие два соседних состояния не могут иметь одинаковый цвет. Знаменитая Теорема о Четырех Цветах гласит, что любой плоский граф может быть раскрашен максимум четырьмя цветами.

Поскольку BDD кодирует все возможные решения для булевой формулы, мы можем легко вычислить, сколько существует решений. Для раскраски графа мы корректируем наш счетчик, чтобы исключить симметрии из-за произвольного назначения значений цвета (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 штатов США довольно проста. Для более сложной карты см. Веб-страницу на графике МакГрегора.


Randal E. Bryant

Leave a Reply

Your email address will not be published. Required fields are marked *