34681

Автор(ы): 

Ульянов М. В. (ИПУ РАН, Лаборатория 68) НЕАКТУАЛЬНАЯ ЗАПИСЬ

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Пленарный доклад

Название: 

Прогнозирование сложности индивидуальных задач коммивояжера

Наименование конференции: 

  • 16-я Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям «YM-2015», Красноярск

Наименование источника: 

  • Материалы 16-й Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям «YM-2015»

Город: 

  • Новосибирск

Издательство: 

  • ИВТ СО РАН

Год издания: 

2015

Страницы: 

15
Аннотация
В докладе излагается подход к прогнозированию трудоемкости конкретных постановок несимметричной задачи коммивояжера, решаемых классическим методом ветвей и границ. Вводится понятие сложности индивидуальной задачи, рассматривается обобщающее описание задач на основе матриц номеров порядка. Выдвигается гипотеза о корреляции спектра матрицы номеров порядка и числа вершин поискового дерева решений, порожденного методом ветвей и границ.

Библиографическая ссылка: 

Ульянов М.В. Прогнозирование сложности индивидуальных задач коммивояжера / Материалы 16-й Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям «YM-2015». Новосибирск: ИВТ СО РАН, 2015. С. 15.