Cтраница 4
Так как решение задачи коммивояжера является гамильтоновым циклом, то мы будем пытаться исключить любое решение, состоящее более чем из одного цикла. [46]
Легко построить пример симметричной задачи коммивояжера, для которой эта нижняя оценка сколь угодно сильно отличается от / ( ZG), т.е. разность I ( ZQ) - / ( Ti) сколь угодно велика. Выбирая параметр q сколь угодно большим, получим, что разность / ( ZQ) - - / ( 2 - i) сколь угодно велика. [47]
Например, в задаче коммивояжера допустимыми ребрами являются ребра, образующие гамильтоновы циклы. В разделе 6.31 допустимыми множествами являются покрывающие деревья. [48]
Статья [40] посвящена полиматричной задаче коммивояжера, а [180] и [239] - задачам составления расписаний. В [188] приведены некоторые оценки сложности задачи выделения максимальных точек из конечного множества. [49]
Рассмотрите, как решена задача коммивояжера методом исключения подциклов в разд. [50]
Рассмотрите, как решена задача коммивояжера методом задания маршрутов в разд. [51]
Рассмотрите, как решена задача коммивояжера в разделе 13.6 с помощью алгоритма частичных циклов. При условии что цикл проходит через все города, можно в качестве начального пункта взять любой город. Примите, что цикл начинается в городе 2, и примените алгоритм. [52]
Растущая клеточная структура для задачи коммивояжера представляет из себя вначале кольцо из трех ячеек нейронов. Каждый нейрон характеризуется двумерным вектором w (, определяющим его положение на плоскости. Каждому нейрону в кольце приписывается также своя величина погрешности st, которая вначале полагается равной нулю. [53]
Ввиду того, что открытая задача коммивояжера несколько более сильно связана с задачей о кратчайшем остове, чем замкнутая, мы начнем с рассмотрения сначала этой задачи, отложив на конец раздела обсуждение тех небольших изменений, которые необходимо сделать в замкнутой ( обычной) задаче коммивояжера. [54]