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

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

«Приложения сегодня требуют всё более быстрых компьютеров для решения проблемы, таких как распределение ресурсов, машинное обучение и анализ структуры белка, и все эти проблемы в своей основе тесно связаны с задачей раскраски графов, — утверждает адъюнкт-профессор Georgia Tech Ариджит Райчудхури (Arijit Raychowdhury). — Однако мы, по большей части, достигли пределов возможностей современных цифровых компьютерных процессоров. Некоторые из этих проблем настолько вычислительно трудны, что могут потребовать нескольких недель компьютерного времени».

В подробностях об этой работе рассказывается в статье, опубликованной журналом Scientific Reports. Новая система использует сеть электронных колебательных контуров, имитирующую нейронную сеть человеческого мозга, где вычисления выполняются коллективно, а не центральным процессором.

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

«Если предположить, что каждая фаза соответствует другому цвету, такая система по сути будет естественным образом имитировать решение проблемы раскраски графа», — отмечает Райчудхури.

Авторами была создана небольшая сеть осцилляторов для решения задачи раскраски графа с аналогичным числом объектов (узлов или вершин). Она позволила получить теоретическое подтверждение существования подобия между раскраской графов и естественной динамикой связанных колебательных систем.

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