Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.

  • A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Анализ задачи поиска кратчайшего пути с неполной информацией и обучениемAnalysis of the shortest path problem with incomplete information and learning

Члены комитета:
Бацын Михаил Владимирович (НИУ ВШЭ в Нижнем Новгороде, к.ф.-м.н., председатель комитета), Золотых Николай Юрьевич (ННГУ им. Н.И. Лобачевского, д.ф.-м.н., член комитета), Иванов Сергей Валерьевич (Московский авиационный институт, д.ф.-м.н., член комитета), Пардалос Панайот Милтиад (Университет Флориды, PhD, член комитета), Хачай Михаил Юрьевич (Институт математики и механики им. Н.Н. Красовского УрО РАН, д.ф.-м.н., член комитета)
Диссертация принята к предварительному рассмотрению:
11.12.2022
Диссертация принята к защите:
20.01.2023
Дисс. совет:
Совет по компьютерным наукам
Дата защиты:
2.03.2023
В этой работе мы рассматриваем одно- и многостадийные версии задачи поиска кратчайшего пути, в которых либо стоимости ребер, либо структура самой сети подвержены неопределенности. В обоих случаях проблема формулируется как динамическая или повторяющаяся игра с нулевой суммой между пользователем и злоумышленником. Пользователь пытается минимизировать свои (ожидаемые) потери за одну или несколько эпох принятия решений, в том время как злоумышленник максимизирует целевую функцию пользователя с помощью выбора определенным способом стоимостей ребер или их вероятностного распределения.  Для первой модели (с неопределенностью весов ребер) получены линейные смешанно-целочисленные формулировки исходной задачи. Для второй модели (с неопределенностью структуры сети) доказана NP-трудность и построен эвристический алгоритм для общего случая. Обе модели проанализированы численно для нескольких классов синтетических тестовых примеров.
Диссертация [*.pdf, 1.22 Мб] (дата размещения 30.12.2022)
Резюме [*.pdf, 505.00 Кб] (дата размещения 30.12.2022)
Summary [*.pdf, 366.70 Кб] (дата размещения 30.12.2022)

Отзывы
Отзыв научного руководителя
Сведения о результатах защиты:
Комитет по диссертации рекомендовал присудить ученую степень кандидата наук с отличием (протокол №2 от 03.03.2023). Решением диссертационного совета (протокол №3 от 29.03.2023) присуждена ученая степень кандидата компьютерных наук с отличием.