Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания
Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за п...
Збережено в:
| Дата: | 2011 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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| id |
irk-123456789-84180 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-841802015-07-04T03:02:17Z Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания Шлезингер, М.И. Антонюк, К.В. Кибернетика Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за певних умов зупинки алгоритм дає наближений розв’язок певних підкласів задач вказаного формату з довільною заздалегідь заданою ненульовою похибкою. Множина задач, що наближено розв’язується алгоритмом, містить у собі всі так звані ациклічні і супермодулярні задачі, для яких відомі алгоритми розв’язку, і деякі інші задачі, для яких алгоритми розв’язку не були відомі. 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. 2011 Article Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84180 004.93’1:519.157 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Шлезингер, М.И. Антонюк, К.В. Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания Кибернетика и системный анализ |
| description |
Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який теоретично мало досліджений. Виявлено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що за певних умов зупинки алгоритм дає наближений розв’язок певних підкласів задач вказаного формату з довільною заздалегідь заданою ненульовою похибкою. Множина задач, що наближено розв’язується алгоритмом, містить у собі всі так звані ациклічні і супермодулярні задачі, для яких відомі алгоритми розв’язку, і деякі інші задачі, для яких алгоритми розв’язку не були відомі. |
| format |
Article |
| author |
Шлезингер, М.И. Антонюк, К.В. |
| author_facet |
Шлезингер, М.И. Антонюк, К.В. |
| author_sort |
Шлезингер, М.И. |
| title |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_short |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_full |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_fullStr |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_full_unstemmed |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| title_sort |
анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2011 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84180 |
| citation_txt |
Анализ алгоритмов диффузии для решения оптимизационных задач структурного распознавания / М.И. Шлезингер, К.В. Антонюк // Кибернетика и системный анализ. — 2011. — Т. 47, № 2. — 3-20. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT šlezingermi analizalgoritmovdiffuziidlârešeniâoptimizacionnyhzadačstrukturnogoraspoznavaniâ AT antonûkkv analizalgoritmovdiffuziidlârešeniâoptimizacionnyhzadačstrukturnogoraspoznavaniâ |
| first_indexed |
2023-10-18T19:28:22Z |
| last_indexed |
2023-10-18T19:28:22Z |
| _version_ |
1796147051884445696 |