Неделю сижу, экспериментирую над задачей.

Задача всё та же, старая, как мир. Есть изображение символа, его надо распознать. Предполагаем, что оно уже в правильной ориентации и без наклона.

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

Для распознавания нужны шаблоны и оценочная функция, она же метрика. Насколько пациент похож на те или иные шаблоны. Нет ничего проще: возьмём и скажем, что поворот конца имеет некую цену r (условных единиц за градус), а перемещение — некую другую цену m (уёв за пиксел). Кроме того, ещё заметим, что иногда с буквами происходят всякие превращения, в результате чего скелет рвётся (+2 конца где-то рядом, или -1 сочленение +1 конец, или -2 сочленения), или появляются лишние чёрточки (опять же +2 конца, или +1 конец +1 солчленение). Поэтому также введём цену на пластические операции, исправляющие подобные дефекты.

Оопс.

Промежуточная задача. Есть два набора вершин. Их, как нетрудно заметить, всегда чётное число. Нужно разбить их на пары, чтобы никто не ушёл обиженным, и чтобы суммарная стоимость всех пар была минимальна.

Ничего не напоминает? А между тем это задача поиска максимального паросочетания в графе. Для двудольного графа решается за время O(mnlogn), где m — число рёбер, n — вершин, довольно простым алгоритмом. У нас граф был бы двудольный, если бы точки одного символа сопоставлялись только с точками другого. Но они могут сопоставляться и со своими соседями, как раз из-за пластических операций. А для произвольного графа алгоритм описывается на десятке страниц, решает за O(n^4). Приплыли.

С другой стороны, а какое мне дело до асимптотики? «Я не собираюсь жить вечно», как говорил Остап Бендер, у меня в каждом скелете максимум 10 точек, вместе с шаблоном будет, ну, скажем, 20. Да тут можно тупой (ну, или слегка оптимизированный) перебор забабахать. Плевать, что сложность в худшем (n-1)(n-3)(n-5)×…×3 ≃ O(n^(n/2)), этого будет достаточно, чтобы как минимум проверить гипотезу и подобрать веса (цены преобразований). А уж дальше, если схема покажет себя хорошо, профилировать и оптимизировать. Может быть, разобрать тот графовый алгоритм на десяти страницах. А может быть — переформулировать задачу как задачу линейной оптимизации и решать симплекс-методом.