Задача коммивояжера Штайнера - Steiner travelling salesman problem
 | Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. (Июнь 2020 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В Задача коммивояжера Штайнера (Штайнер ТСП, или же STSP) является продолжением задача коммивояжера. Учитывая список городов, некоторые из которых являются обязательными, и протяженность дорог между ними, цель состоит в том, чтобы найти как можно более короткую прогулку, которая посетит каждый требуемый город и затем вернется в исходный город. [1]. Во время прогулки вершины можно посещать более одного раза, а ребра могут проходить более одного раза[2].
Рекомендации
- ^ Интериан, Рубен; Рибейро, Селсу К. (15 июля 2017 г.). «Эвристика GRASP с повторным связыванием путей и перезапусками для задачи коммивояжера Штайнера». Международные операции в операционных исследованиях. 24 (6): 1307–1323. Дои:10.1111 / itor.12419.
- ^ Альварес-Миранда, Эдуардо; Синнл, Маркус (05.09.2019). «Заметка о вычислительных аспектах задачи коммивояжера Штайнера». Международные операции в операционных исследованиях. 26 (4): 1396–1401. Дои:10.1111 / itor.12592.
- М. Р. Гарей и Д. С. Джонсон. Компьютеры и непреодолимость: руководство по теории NP-полноты. У. Х. Фриман и компания, 1979.
- Хуэйли Чжан, Вэйтянь Тонг, Иньфэн Сюй и Гохуэй Линь. Проблема коммивояжера Штайнера с блокировкой кромок в сети. Европейский журнал операционных исследований, 243(1):30–40, 2015.
- Жерар Корнуехолс, Жан Фонлупт и Дени Наддеф. Задача коммивояжера на графе и некоторых связанных целочисленных многогранниках. Математическое программирование, 33(1):1–27, 1985.
- С. Борн, А. Махджуб и Р. Тактак. Алгоритм ветвления и отсечения для TSP с множеством Steiner с ограничениями порядка. Электронные заметки по дискретной математике, 41:487–494, 2013.
- Хуэйли Чжан, Вэйтянь Тонг, Иньфэн Сюй и Гохуэй Линь. Проблема коммивояжера Штайнера с продвинутыми блокировками кромок в сети. Компьютеры и исследования операций, 70:26–38, 2016.
- Адам Н. Летчфорд, Саидех Д. Насири и Дирк Оливер Тайс. Компактная формулировка задачи коммивояжера Штайнера и связанных с ней задач. Европейский журнал операционных исследований, 228(1):83–92, 2013.
- Адам Н. Летчфорд и Саидех Д. Насири. Задача коммивояжера Штайнера с коррелированными затратами. Европейский журнал операционных исследований, 245(1):62–69, 2015.
- Хуан-Жозе Салазар-Гонсалес. Многогранник циклов Штейнера. Европейский журнал операционных исследований, 147(3):671–679, 2003.
 | Этот комбинаторика -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |