Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания
Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за п...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84180 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84180 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| spellingShingle |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания Шлезингер, М.И. Антонюк, К.В. Кибернетика |
| title_short |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_full |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_fullStr |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_full_unstemmed |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_sort |
анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| author |
Шлезингер, М.И. Антонюк, К.В. |
| author_facet |
Шлезингер, М.И. Антонюк, К.В. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Аналіз алгоритмів дифузії для розв’язання оптимізаційних задач структурного розпізнавання Diffusion algorithms and structural recognition optimization problems |
| 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.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84180 |
| citation_txt |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. |
| 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 |
| first_indexed |
2025-12-07T13:20:18Z |
| last_indexed |
2025-12-07T13:20:18Z |
| _version_ |
1850855777226457088 |