Original at http://www.cs.cmu.edu/~bryant/boolean/maps.html

Интересные Проблемы Карт

Вот некоторые переводы этой страницы на другие языки: Дональд Кнут работает над Томом 4 Искусство программирования для ЭВМ . Одна из глав на Binary Decision Diagrams и их приложений, предмет, который я нахожу очень интересным. Кнут показывает, что множество интересных задач по графам может быть закодировано как булевые формулы, а производная BDD представляет все возможные пути решения этих проблем. Часто есть какой-то критерий оптимизации, и это довольно легко извлечь - "лучшее" решение от BDD, с помощью простого алгоритма динамического программирования.

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

Туры по столице

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

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

Вот самый короткий тур по столицам, на общую сумму 11,698 миль:

Здесь самый длинный тур по столицам, на общую сумму 18,040 миль:

График раскраски

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

Так как BDD кодирует все возможные решения в булевой формуле, мы можем легко вычислить, сколько решений есть. Для раскраски графа, мы регулируем наши счетчики, чтобы устранить симметрию из-за произвольного присвоения значений цветов (4! Симметричных случая для 4-раскрасок).

Для окрашивания 48 смежных штатов, есть 533,816,322,048 возможных расцветок. (Это 1/2 число сообщает Кнут, поскольку его карта включает в Вашингтоне, округ Колумбия, как 49-го "состояния", и он может быть назначен любой из двух цветов, не используемых для Мэриленд и Вирджиния.) Вот некоторые интересные примеры специальные раскраски:

С точки зрения программ раскраски графа, карта США из 48 штатов довольно проста. Для более сложной карты, можно зайти на веб - страницу , на McGregor графике.


Рэндал Э. Брайант Последнее изменение: Вт 19 января 2010 7:48:18 EST