Октябрь 2017
 
Email

Искусство счета

 
Опубликовано 28.06.2010
 
 


Разработан компьютерный алгоритм, работающий на много порядков быстрее своего предшественника.

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

Все эти задачи при их кажущейся разнородности можно свести к единой форме: представить все статические составляющие исследуемых систем в виде точек, а отношение между ними – в виде соединительных линий (дуг). Такая схема в математике называется граф. Для примера: географическая карта Германии может быть представлена в виде 16 точек (по количеству земель в этой стране), попарно соединенных дугами, если данная пара земель имеет общую границу. Задача о раскраске карты получит тогда следующую формулировку: сколькими способами можно раскрасить точки графа при условии, что каждая дуга не может соединять точки одного цвета?

В общем виде проблема раскраски узлов графа выглядит так: сколькими разными способами может быть раскрашен произвольный граф при заданном фиксированном количестве цветов? Эта задача имеет огромное прикладное значение, но формулируется и решается самостоятельно, в отрыве от всех практических применений. На практике цвет того или иного узла может получать самые разные интерпретации: для карты это и есть цвет, для игры судоку – та или иная цифра, для шахматной доски – «состояние» поля (битое или небитое) и т.д.  Самый простой способ решить эту задачу –  последовательно перебрать с помощью компьютера все возможные варианты раскраски. Но даже для такого относительно простого случая, как карта Германии с ее шестнадцатью землями, при условии, например, четырех цветов, возникает около четырех миллиардов комбинаций. А упомянутая задача с шахматной доской потребует для своего решения несколько миллиардов лет. Ясно, что при таком подходе с реальной и по-настоящему сложной задачей не справится ни один компьютер в мире.  
 
 
Два из 1152 способов раскраски одной решетки (графа). Узлы, соединенные дугой, должны иметь разный цвет
Ученые Марк Тимме, Франк Ван Буссель, Денни Флигнер  из Института Макса Планка в Германии и их коллега Себастиан Штольценберг  из Корнельского университета (Итака, штат Нью-Йорк) разработали метод, с помощью которого подобного рода задачи стало возможно решать несравнимо быстрее, чем прежде. Их алгоритм справляется, например, с задачей про восемь шашек за несколько секунд.

Действует он примерно так. Компьютерная программа «не замахивается» сразу на весь граф, а действует подобно близорукому человеку. В каждый момент она наряду с «текущим» узлом графа рассматривает лишь один следующий узел. В первый момент она не может присвоить данному узлу никакого цвета, поскольку для этого ей понадобилось бы знать структуру ближайшего окружения данного узла. Вместо этого, оставив данный вопрос «на потом», программа составляет уравнение, в котором все до поры невыясненные моменты фигурируют как неизвестные величины. По мере продвижения по графу все связи становятся видимыми, а неизвестные величины обретают конкретные значения. При достижении последнего узла знание программы о графе становится исчерпывающим.

«Теперь, – говорит Марк Тимме, – мы смогли ответить на многие вопросы, прежде казавшиеся неразрешимыми, –  из области теории графов,  физики, вычислительной техники. В частности наш метод находит применение в исследовании антиферромагнетиков». В твердых антиферромагнетиках каждый атом обладает вращательным моментом (спином), который может принимать различные значения. Спины соседних атомов обычно принимают разные значения (вспомним о разных цветах соседних областей на карте). Отныне появилась возможность подсчитать количество всех допустимых распределений величин спина, что, скорее всего, позволит физикам выявить некоторые фундаментальные законы термодинамики твердых тел.
 

 
 
 
 
 
 
 
 
 
© "YOS" 2010-2011
ИНТМЕДИА