Анализ задачи поиска кратчайшего пути с неполной информацией и обучениемAnalysis of the shortest path problem with incomplete information and learning
Соискатель:
Руководители
Прокопьев Олег Александрович (др. работы под рук-вом); Калягин Валерий Александрович (др. работы под рук-вом)
Члены комитета:
Бацын Михаил Владимирович (НИУ ВШЭ в Нижнем Новгороде, к.ф.-м.н., председатель комитета), Золотых Николай Юрьевич (ННГУ им. Н.И. Лобачевского, д.ф.-м.н., член комитета), Иванов Сергей Валерьевич (Московский авиационный институт, д.ф.-м.н., член комитета), Пардалос Панайот Милтиад (Университет Флориды, PhD, член комитета), Хачай Михаил Юрьевич (Институт математики и механики им. Н.Н. Красовского УрО РАН, д.ф.-м.н., член комитета)
Диссертация принята к предварительному рассмотрению:
12/12/2022
Диссертация принята к защите:
1/20/2023
Дисс. совет:
Совет по компьютерным наукам
Дата защиты:
3/3/2023
В этой работе мы рассматриваем одно- и многостадийные версии задачи поиска кратчайшего пути, в которых либо стоимости ребер, либо структура самой сети подвержены неопределенности. В обоих случаях проблема формулируется как динамическая или повторяющаяся игра с нулевой суммой между пользователем и злоумышленником. Пользователь пытается минимизировать свои (ожидаемые) потери за одну или несколько эпох принятия решений, в том время как злоумышленник максимизирует целевую функцию пользователя с помощью выбора определенным способом стоимостей ребер или их вероятностного распределения. Для первой модели (с неопределенностью весов ребер) получены линейные смешанно-целочисленные формулировки исходной задачи. Для второй модели (с неопределенностью структуры сети) доказана NP-трудность и построен эвристический алгоритм для общего случая. Обе модели проанализированы численно для нескольких классов синтетических тестовых примеров.
Диссертация [*.pdf, 1.22 Мб] (дата размещения 12/30/2022)
Резюме [*.pdf, 505.00 Кб] (дата размещения 12/30/2022)
Summary [*.pdf, 366.70 Кб] (дата размещения 12/30/2022)
Публикации, в которых излагаются основные результаты диссертации
Ketkov S.S., Prokopyev O.A. An approach to the distributionally robust shortest path problem (смотреть на сайте журнала)
Ketkov S.S., Prokopyev O.A. On greedy and strategic evaders in sequential interdiction settings with incomplete information (смотреть на сайте журнала)
Отзывы
Отзыв научного руководителя
- Отзыв Прокопьева О.А. (дата размещения 12/15/2022)
- Отзыв Калягина В.А. (дата размещения 12/15/2022)
Сведения о результатах защиты:
Комитет по диссертации рекомендовал присудить ученую степень кандидата наук с отличием (протокол №2 от 03.03.2023). Решением диссертационного совета (протокол №3 от 29.03.2023) присуждена ученая степень кандидата компьютерных наук с отличием.