Кафедра математичного моделювання та аналізу даних (ММАД)
Постійне посилання на фонд
Сайт кафедри: http://mmda.ipt.kpi.ua/
Переглянути
Перегляд Кафедра математичного моделювання та аналізу даних (ММАД) за Ключові слова "(max ,+)"
Зараз показуємо 1 - 1 з 1
Результатів на сторінці
Налаштування сортування
Документ Відкритий доступ Алгоритм розв’язування супермодулярних (max, +) задач розмітки із самоконтролем на основі субградієнтного спуску(КПІ ім. Ігоря Сікорського, 2022-06) Хоменко, Руслан Олександрович; Водолазський, Євгеній ВалерійовичДану роботу присвячено алгоритму, який для будь-якої поданої на вхід (max ,+) задачі розмітки з цілочисельними якостями надасть одну з двох відповідей: або опти- мальну розмітку, або “задача не супермодулярна”, і ця відповідь гарантовано буде коректною. Самоконтроль полягає у тому, що не користувач вирішує, на яке питання треба відповісти, а сам алгоритм вирішує, що потрапляє у зону його компетентно- сті. Іншою особливістю алгоритму є те, що він не потребує відомої впорядкованості міток для супермодулярних задач. Гарантію скінченної кількості кроків надає вико- ристання субградієнтного спуску і цілочисельність ваг вершин та ребер.