Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания
Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за п...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84180 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862620021029601280 |
|---|---|
| author | Шлезингер, М.И. Антонюк, К.В. |
| author_facet | Шлезингер, М.И. Антонюк, К.В. |
| citation_txt | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за певних умов зупинки алгоритм дає наближений розв’язок певних підкласів задач вказаного формату з довільною заздалегідь заданою ненульовою похибкою. Множина задач, що наближено розв’язується алгоритмом, містить у собі всі так звані ациклічні і супермодулярні задачі, для яких відомі алгоритми розв’язку, і деякі інші задачі, для яких алгоритми розв’язку не були відомі.
A formal analysis of so-called diffusion algorithms is performed. They are frequently used in structural recognition but are rather poorly theoretically studied. The algorithms are analyzed from the viewpoint of their ability to optimize a function of many discrete variables, which is presented as a sum of many terms, each of them depending only on two variables. It is proved that under a certain stop condition, the diffusion algorithm solves approximately certain subclasses of optimization problems with any pre-defined nonzero error. A domain of problems are solvable by diffusion algorithms includes all so-called acyclic or supermodular optimization problems as well as some other problems, for which solution algorithms were not known.
|
| first_indexed | 2025-12-07T13:20:18Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84180 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T13:20:18Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шлезингер, М.И. Антонюк, К.В. 2015-07-03T15:48:17Z 2015-07-03T15:48:17Z 2011 Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84180 004.93’1:519.157 Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за певних умов зупинки алгоритм дає наближений розв’язок певних підкласів задач вказаного формату з довільною заздалегідь заданою ненульовою похибкою. Множина задач, що наближено розв’язується алгоритмом, містить у собі всі так звані ациклічні і супермодулярні задачі, для яких відомі алгоритми розв’язку, і деякі інші задачі, для яких алгоритми розв’язку не були відомі. A formal analysis of so-called diffusion algorithms is performed. They are frequently used in structural recognition but are rather poorly theoretically studied. The algorithms are analyzed from the viewpoint of their ability to optimize a function of many discrete variables, which is presented as a sum of many terms, each of them depending only on two variables. It is proved that under a certain stop condition, the diffusion algorithm solves approximately certain subclasses of optimization problems with any pre-defined nonzero error. A domain of problems are solvable by diffusion algorithms includes all so-called acyclic or supermodular optimization problems as well as some other problems, for which solution algorithms were not known. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания Аналіз алгоритмів дифузії для розв’язання оптимізаційних задач структурного розпізнавання Diffusion algorithms and structural recognition optimization problems Article published earlier |
| spellingShingle | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания Шлезингер, М.И. Антонюк, К.В. Кибернетика |
| title | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_alt | Аналіз алгоритмів дифузії для розв’язання оптимізаційних задач структурного розпізнавання Diffusion algorithms and structural recognition optimization problems |
| title_full | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_fullStr | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_full_unstemmed | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_short | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_sort | анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84180 |
| work_keys_str_mv | AT šlezingermi analizalgoritmovdiffuziidlârešeniâoptimizacionnyhzadačstrukturnogoraspoznavaniâ AT antonûkkv analizalgoritmovdiffuziidlârešeniâoptimizacionnyhzadačstrukturnogoraspoznavaniâ AT šlezingermi analízalgoritmívdifuzíídlârozvâzannâoptimízacíinihzadačstrukturnogorozpíznavannâ AT antonûkkv analízalgoritmívdifuzíídlârozvâzannâoptimízacíinihzadačstrukturnogorozpíznavannâ AT šlezingermi diffusionalgorithmsandstructuralrecognitionoptimizationproblems AT antonûkkv diffusionalgorithmsandstructuralrecognitionoptimizationproblems |