Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания
Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за п...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2011 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84180 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. |
Репозитарії
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 |