Более быстрое решение головоломки

Вы можете представить себе, что компьютеры хорошо решают головоломки, но задача сложнее, чем вы думаете. Сопоставление с образцом довольно просто, если у вас указанная ориентация. Если вы попробуете это сделать, когда не знаете, как удерживать детали, вы скоро обнаружите проблему.

Если вы думаете, что решаете скупую головоломку, примите во внимание, что новейший алгоритм может обработать 10 000 деталей за 24 часа — это в три раза больше прошлогоднего рекорда в 3300 деталей. Эндрю Галлахер из Корнельского университета в Итаке, штат Нью-Йорк, улучшил стандартный подход, скопировав то, что люди делают, находя группы элементов, которые лучше всего подходят друг другу, и оттуда двигаясь дальше.

Пазл из 9600 деталей решен!

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

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

Используемый алгоритм — это жадный древовидный метод и новая мера сходства фигур. Мера подобия основана на хорошо известном расстоянии Махаланобиса, которое масштабирует расстояние между распределениями по их дисперсии. Новая мера сравнивает части, используя градиент интенсивности около края, масштабируемый ковариацией цветового канала. Жадная сборка на основе дерева строит минимальное остовное дерево с ограничениями, чтобы убедиться, что только одна часть размещается напротив другой. Чтобы сделать проблему разрешимой, используется эвристика, чтобы найти приблизительное решение в разумные сроки.

Вы можете увидеть алгоритм в действии в следующих двух видеороликах:

Велосипед из 600 предметов

Йосемити, 600 частей

Если вы думаете, что головоломки немного легкомысленны, то обратите внимание, что аналогичные алгоритмы можно использовать для объединения измельченных документов — в соответствии с недавним вызовом DARPA.

Настоящий вопрос в том, можете ли вы добиться большего?

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