Читать курсовая по математике: "Задача о коммивояжере и ее обобщения" Страница 2

(Назад) (Cкачать работу)

Рассмотрим снова плоскость t, x, где t – дискретный аргумент, принимающий значения 0,1, 2, …, N, соответствующие этапам путешествия торговца. Значит t = 0 соответствует его начальному положению в городе номер 1, t = 1 – переходу из города номер 1 в город, который он выбрал первым для посещения, и т.д., t = N означает последний этап его путешествия – возвращение в город номер 1. Аргумент x теперь также принимает дискретные значения 1,2, …, N (Рисунок 1.1). Соединим точку (0, 1) с точками (1,1), (1, 2), …(1, N) и длинам отрезков, соединяющих эти точки, припишем значения f(x1,xj). Далее точки (1, s) – узлы, лежащие на первой вертикали, мы соединим со всеми уздами второй вертикали, длинам отрезков мы припишем значения f(xs, xk) и т.д. точки (N-1, s) соединим с точкой (N,1).В результате мы построили некоторый граф, каждая ломанная которого, соединяющая точку (0,1) сточкой (N,1), описывает путь коммивояжера. Нашу задачу мы можем теперь сформулировать следующим образом. Среди всех ломанных, принадлежащих этому графу и соединяющих точки (0,1) и (N,1) и удовлетворяющих условию (α), найти ломанную кратчайшей длины. Условие (α) состоит теперь в том, что искомая ломанная пересекает (в узле) каждую из прямых x = i один и только один раз. Таким образом, задача о коммивояжере формулируется более привычным для нас языком.

Рассмотрим узел P, лежащий на третьей вертикали (Рисунок 1.2). Если бы условие (α) отсутствовало, то выбор траектории, которая соединяет точку P с точкой (N, 1), не зависел бы от того пути, который привел нас в точку P. В данном случае ситуация иная, и если два коммивояжера находятся в точке P, но один из них пришел в это состояние, двигаясь вдоль траектории, проходящей через точку Q, а второй через точку R, то их состояния существенно отличаются друг от друга.

Коммивояжер, который двигался по второй траектории , уже побывал в городах номер 2 и номер 5 и в будущем он уже не имеет права снова заезжать в эти города. Что касается коммивояжера, который двигался вдоль первой траектории, то он побывал в городах номер 3 и номер 6; он не имеет права возвращаться в эти города, но зато он еще обязан посетить города номер 2 и номер 5 и т. Д.

Поскольку функция f(xi, xj) определена на конечном множестве точек, то и функция l(х1,…,xN) также определена на конечном множестве точек.

Следовательно, задача определения минимума функции l сводится к перебору некоторого конечного множества значений этой функции, и проблема носит чисто вычислительный характер. Однако именно вычислительные трудности здесь огромны.

Легко подсчитать, что число возможных вариантов (число значений функции l) равно (N — 1)!. Таким образом, непосредственно перебрать и сравнить между собой все возможные пути, по которым может следовать бродячий торговец, для достаточно большого количества городов практически невозможно.

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

Похожие работы