Optimal Labelling Problems, their Relaxation and Equivalent Transformations

Abstract

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

The optimal labeling problem is considered, which is a generalization of the known Constraint Satisfaction Problem, and its relaxed simplification. Two approaches for the relaxed labeling optimization are described as well as their advantages and shortcomings. A direction of future researches is suggested.

Розглянуто оптимізаційну задачу розміток, що узагальнює відому задачу про сумісність обмежень, та її розмиту модифікацію. Описано два підходи до пошуку оптимальної розмитої розмітки, їх переваги і недоліки. Наведено напрями подальших досліджень.