Diffusion algorithms and structural recognition optimization problems
Diffusion algorithms and structural recognition optimization problems
复制标题
扩散算法和结构识别优化问题
DOI：
10.1007/s10559-011-9300-z
复制
发表时间：
2011
影响因子：
0.5
通讯作者：
K. V. Antoniuka
中科院分区：
文献类型：
--
作者：
M. I. Schlesingera;K. V. Antoniuka
对所谓的扩散算法进行了形式化分析。它们经常用于结构识别，但理论研究很少。这些算法从它们优化由许多离散变量组成的函数的能力的角度进行了分析，这些函数被表示为许多项的和，每个项只依赖于两个变量。证明了在一定的停止条件下，扩散算法可以近似地求解具有任意预定义的非零误差的优化问题的某些子类。扩散算法所解决的问题包括所有所谓的无环和超模优化问题，以及其他一些求解算法未知的问题。
A formal analysis of so-called diffusion algorithms is performed. They are frequently used in structural recognition but are rather poorly theoretically studied. These algorithms are analyzed from the viewpoint of their ability to optimize a function of many discrete variables, which is represented as the sum of many terms each of which depends on only two variables. It is proved that, under some stop condition, a diffusion algorithm approximately solves certain subclasses of optimization problems with any predefined nonzero error. The totality of problems solved by diffusion algorithms includes all so-called acyclic and supermodular optimization problems and also some other problems for which solution algorithms are unknown.