Алгоритм розв’язування супермодулярних (max, +) задач розмітки із самоконтролем на основі субградієнтного спуску
Вантажиться...
Дата
2022-06
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Дану роботу присвячено алгоритму, який для будь-якої поданої на вхід (max ,+) задачі розмітки з цілочисельними якостями надасть одну з двох відповідей: або опти- мальну розмітку, або “задача не супермодулярна”, і ця відповідь гарантовано буде коректною. Самоконтроль полягає у тому, що не користувач вирішує, на яке питання треба відповісти, а сам алгоритм вирішує, що потрапляє у зону його компетентно- сті. Іншою особливістю алгоритму є те, що він не потребує відомої впорядкованості міток для супермодулярних задач. Гарантію скінченної кількості кроків надає вико- ристання субградієнтного спуску і цілочисельність ваг вершин та ребер.
Опис
Ключові слова
(max ,+), задачі розмітки, супермодулярні задачі розмітки, самоконтроль у розпізнаванні образів, дискретна оптимізація, графові моделі, структурне розпізнавання образів
Бібліографічний опис
Хоменко, Р. О. Алгоритм розв’язування супермодулярних (max, +) задач розмітки із самоконтролем на основі субградієнтного спуску : магістерська дис. : 113 Прикладна математика / Хоменко Руслан Олександрович. – Київ, 2022. – 60 с.