Remkomplekty.ru

IT Новости из мира ПК
7 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Задача коммивояжера паскаль

Исходник решения задачи коммивояжера методом Прима на C++ и Методом ветвей и границ на Pascal

Задача коммивояжера является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы.

Постановка задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3.. n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы привести задачу к научному виду, введём некоторые термины. Итак, города перенумерованы числами j принадлежит Т=(1,2,3.. n ). Тур коммивояжера может быть описан циклической перестановкой t =( j 1 , j 2 . j n , j 1 ), причём все j1 .. jn – разные номера; повторяющийся в начале и в конце j 1 , показывает, что перестановка зациклена. Расстояния между парами вершин С ij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t , чтобы минимизировать функционал

Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.

Во-первых, в постановке С ij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех j принадлежит Т:

С ij >= 0; C jj =бесконечность

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i , j :

и удовлетворять неравенству треугольника, т.е. для всех:

С ij + С jk >= C ik

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если С ij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную — в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжера все туры t =( j 1 , j 2 . j n , j 1 ) и t ‘=( j 1 , j n . j 2 , j 1 ) имеют разную длину и должны учитываться оба. Разных туров очевидно ( n -1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j 1 , а оставшиеся n -1 номеров переставим всеми ( n -1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t ‘.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро ( i , j ) проведено, если С ij =0 и не проведено, если С ij =1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную задачу коммивояжера можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра ( i , j )= С ij . Найти гамильтонов цикл минимальной длины.

В несимметричной задаче коммивояжера вместо “цикл” надо говорить “контур”, а вместо “ребра” — “дуги” или “стрелки”.

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

Решение задачи коммивояжера жадным алгоритмом

Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Посмотрим, как поведет себя при решении задачи коммивояжера жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

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

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть f B — настоящий минимум, а f A — тот квазиминимум, который получен по алгоритму. Ясно , что f A / f B >=1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

где, как обычно в высшей математике, E>=0, но, против обычая, может быть очень большим. Величина E и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность E.

Предположим теперь, что имеется алгоритм А решения задачи коммивояжера, погрешность которого нужно оценить. Возьмем произвольный граф G ( V , E ) и по нему составим входную матрицу задачи коммивояжера:

1,если ребро ( i , j ) принадлежит Е

1+ n E в противном случае

Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и f B = n . Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, непереборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+ n E. Но тогда f A E ( n -1)+(1+ n E) так что f A / f B =1+ n E т.е. превосходит погрешность E на заданную неравенством (5). О величине ? в нашем рассуждении мы не договаривались, так что E может быть произвольно велик.

Таким образом доказана следующая теорема.

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

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (4).

Если оно соблюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде, чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно ли начертить одной линией открытый конверт? Рис.2 показывает, что можно (цифры на отрезках показывают порядок их проведения). Закрытый конверт (рис.3.) одной линией нарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья – вершинами.

Когда через точку проводится линия, то используется два ребра – одно для входа в вершину, одно – для выхода. Если степень вершины нечетна – то в ней линия должна начаться или кончиться. На рис. 3 вершин нечетной степени две: в одной линия начинается, в другой – кончается. Однако на рис. 4 имеется четыре вершины степени три, но у одной линии не может быть четыре конца. Если же нужно прочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четную степень.

Верно и обратное утверждение: если все вершины имеют четную степень, то фигуру можно нарисовать одной незамкнутой линией. Действительно, процесс проведения линии может кончиться, только если линия придет в вершину, откуда уже выхода нет: все ребра, присоединенные к этой вершине (обычно говорят: инцидентные этой вершине), уже прочерчены. Если при этом нарисована вся фигура, то нужное утверждение доказано; если нет, удалим уже нарисованную часть G ‘. После этого от графа останется одна или несколько связных компонент; пусть G ‘ – одна из таких компонент. В силу связности исходного графа G , G ‘ и G » имеют хоть одну общую вершину, скажем, v . Если в G » удалены какие-то ребра, то по четному числу от каждой вершины. Поэтому G » – связный и все его вершины имеют четную степень. Построим цикл в G » (может быть, не нарисовав всего G ») и через v добавим прорисованную часть G » к G ‘. Увеличивая таким образом прорисованную часть G ‘, мы добьемся того, что G ‘ охватит весь G .

Эту задачу когда-то решил Эйлер, и замкнутую линию, которая покрывает все ребра графа, теперь называю эйлеровым циклом. По существу была доказана следующая теорема.

Эйлеров цикл в графе существует тогда и только тогда, когда (1) граф связный и (2) все его вершины имеют четные степени.

Вот Исходник задачи коммивояжера методом ветвей и границ Процедурки писал не я, а Гари Дарби. Скажем ему Спасибо. что нам время сэкономил, а то я уж хотел сам писать.
Кстате если Вам оказался интересным или полезным этот материал, то хорошо, т.к. для Вас и стараюсь. У меня есть ещё сырой материал, если Вы мне сообщите то я постараюсь его выложить(дописать,переписать,разобрать) как можно скорее.
Исходник рабочий — сам дописывал.

X Международная студенческая научная конференция Студенческий научный форум — 2018

НАХОЖДЕНИЕ КРАТЧАЙШЕГО ПУТИ (ЗАДАЧА КОММИВОЯЖЕРА) МЕТОДОМ ПЕРЕБОРА В СРЕДЕ ПРОГРАММИРОВАНИЯ ПАСКАЛЬ-АВС

Приведем классическую постановку задачи.Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3, . ,n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Читать еще:  Сортировка выбором паскаль

Чтобы привести задачу к математическому виду, введём некоторые термины. Итак, города перенумерованы числами jТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2. jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1,показывает, что перестановка зациклена. Расстояния между парами вершин Сijобразуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

Относительно математизированной формулировки ЗК необходимо сделать два замечания.

Во-первых, в постановке Сijозначали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ:

(последнее равенство означает запрет на петли в туре),

симметричными, т.е. для всех i,j:

и удовлетворять неравенству треугольника, т.е. для всех:

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому различают два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную – в противном случае.

Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1,j2. jn,j1) и t’=(j1,jn. j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

В терминах теории графов симметричную ЗК можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.

В несимметричной ЗК вместо “цикл” надо говорить “контур”, а вместо “ребра” ‒ “дуги” или “стрелки”.

Некоторые прикладные задачи формулируются как ЗК, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но их решать более сложно.

Следующий алгоритм, после алгоритма прямого перебора, ”жадный” алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

Рис. 1. ‒ Сеть, представляющую узкий ромб, и найденный “жадным” алгоритмом тур

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 1, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

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

К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода.

Общая идея метода: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной.

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

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

Опишем решение задачи методом перебора или “brute-force enumeration” ‒ “перебор животной силой”, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с N городами требует при полном переборе рассмотрения (N-1)!/2 туров в симметричной задаче и (N-1)! туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро (табл. 1), однако быстродействие современных ПК позволяет справиться с этой задачей.

Решения задачи коммивояжёра Pascal

Автор: Пользователь скрыл имя, 06 Марта 2013 в 17:14, курсовая работа

Краткое описание

Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок.
Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.

Оглавление

Введение
1.Теоретическое обоснование решения задачи коммивояжёра;
2.Пример решения задачи коммивояжёра одним из методов;
3.Решение задачи коммивояжёра средствами MS Excel;
4.Алгоритм решения задачи;
5.Листинг программы для решения задачи.
Литература

Файлы: 1 файл

kursovaja.doc

Министерство образования и науки Российской Федерации

ГОУ ВПО Магнитогорский государственный технический университет

СП «Многопрофильный колледж»

Направление подготовки «Металлургия, машиностроение и автоматизация»

к курсовому проекту по дисциплинам:

Математические методы и Технология разработки программных продуктов

КП. 230105.24.00. 00. ПЗ

группы ПРК – 07 – 9

Введение

1.Теоретическое обоснование решения задачи коммивояжёра;

2.Пример решения задачи коммивояжёра одним из методов;

3.Решение задачи коммивояжёра средствами MS Excel;

4.Алгоритм решения задачи;

5.Листинг программы для решения задачи.

Литература

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

Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояние между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задача коммивояжёра. Также существует обобщение задачи. Так называемая обобщённая задача коммивояжёра.

Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.

Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок.

Математическое программирование — область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.

Один из разделов математического программирования — линейным программированием. Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.

Большой вклад в систематическое развитие комбинаторных методов был произведен Г. Лейбницем (диссертация «Комбинаторное искусство»), Я. Бернулли (работа «Искусство предположений»), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейб-ница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций – методу производящих функций. В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Читать еще:  Массив string паскаль

Разделы комбинаторики:

— Перечислительная комбинаторика

— Структурная комбинаторика

— Экстремальная комбинаторика

— Теория Рамсея

— Вероятностная комбинаторика

— Топологическая комбинаторика

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

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

-метод ближайшего соседа

-метод включения ближайшего города

-метод самого дешёвого включения

-метод минимального остовного дерева

-метод имитации отжига

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.

Существует также постановки, в которых задача коммивояжера становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает x. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

Формулируется следующим образом:

Пункты обхода плана последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.

Алгоритм прост в реализации, быстро выполняется, но, как и другие «жадные» алгоритмы, может выдавать неоптимальные решения. Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения. Другой вариант оценки решения заключается в использовании алгоритма нижней граничной оценки (lower bound algorithm).

Для любого количества городов в задаче коммивояжёра можно подобрать такое расположение городов (значение расстояний между вершинами графа и указание начальной вершины), что алгоритм ближайшего соседа будет выдавать наихудшее решение.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,1,3..n и вернуться в первый город. Расстояния между городами известны.

Итак, города перенумерованы числами jÎТ=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2. jn,j1), причём все j1..jn – разные номера; повторяющийся в начале и в конце j1, показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jÎТ:

(последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j:

и удовлетворять неравенству треугольника, т.е. для всех:

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому различать вариант задачи коммивояжёра: симметричную задачу, когда условие (3) выполнено, или несимметричный — в противном случае. Условия (2)-(4) по умолчанию считаются выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжёра все туры t=(j1,j2. jn,j1) и t’=(j1,jn. j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

На первом и последнем месте в циклической перестановке номер будет j1, а оставшиеся n-1 номеров будет (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём). В терминах теории графов симметричную задачу коммивояжёра можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины. В несимметричной задаче коммивояжёра вместо «цикл» надо говорить «контур», а вместо «ребра» — «дуги» или «стрелки».

Задача коммивояжера — метод ветвей и границ

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера (англ. «Travelling salesman problem», TSP). Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Кто и когда впервые начал исследовать задачу коммивояжера неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик XIX в. – Уильям Гамильтон. Здесь мы рассмотрим замкнутый вариант задачи (т.е. такой, когда в итоге мы возвращаемся в исходную точку) и ее решение методом ветвей и границ.

Общий план решения задачи коммивояжера

Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующий алгоритм (последовательность действий):

  1. Построение матрицы с исходными данными.
  2. Нахождение минимума по строкам.
  3. Редукция строк.
  4. Нахождение минимума по столбцам.
  5. Редукция столбцов.
  6. Вычисление оценок нулевых клеток.
  7. Редукция матрицы.
  8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
  9. Вычисление итоговой длины пути и построение маршрута.

Более подробно эти этапы решения задачи о бродячем торговце раскрыты ниже.

Подробная методика решения задачи коммивояжера

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие – «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

3. Редукция строк

Производим редукцию строк – из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4. Нахождение минимума по столбцам

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

5. Редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

И так по всем нулевым клеткам:

7. Редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку, соответствующую обратному пути, ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

8. Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.

Если все отрезки пути найдены (или найдены еще не все отрезки, но оставшаяся часть пути очевидна) – переходим к пункту 9.

9. Вычисление итоговой длины пути и построение маршрута

Найдя все отрезки пути, остается только соединить их между собой и рассчитать общую длину пути (стоимость поездки по этому маршруту, затраченное время и т.д.). Длины дорог соединяющих города берем из самой первой таблицы с исходными данными.

В нашем примере маршрут получился следующий: 42314.

Читать еще:  Виды сортировки паскаль

Общая длина пути: L = 30.

Практическое применение задачи коммивояжера

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

Решение задачи коммивояжера онлайн

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

© Копирование материала допустимо только при указании прямой гиперссылки на источник: Галяутдинов Р.Р.

НАХОЖДЕНИЕ КРАТЧАЙШЕГО ПУТИ (ЗАДАЧА КОММИВОЯЖЕРА) МЕТОДОМ ПЕРЕБОРА В СРЕДЕ ПРОГРАММИРОВАНИЯ ПАСКАЛЬ-АВС

Транскрипт

1 НАХОЖДЕНИЕ КРАТЧАЙШЕГО ПУТИ (ЗАДАЧА КОММИВОЯЖЕРА) МЕТОДОМ ПЕРЕБОРА В СРЕДЕ ПРОГРАММИРОВАНИЯ ПАСКАЛЬ-АВС Мещеряков Д.А., Растеряев Н.В. Донской государственный технический университет (ДГТУ) Ростов-на-Дону, Россия FINDING THE SHORTEST PATH (TRAVELING SALESMAN PROBLEM) BRUTE FORCE IN THE PROGRAMMING ENVIRONMENT PASCAL-ABC Meshcheryakov D. A., Rasteryaev N.V. Don state technical University (DSTU) Rostov-on-Don, Russia Задача коммивояжера (ЗК) является одной из знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и её, как Великую теорему Ферма пытались решить многие математики. В своей области (оптимизации дискретных задач) ЗК служит своеобразным полигоном, на котором испытываются всё новые методы. Приведем классическую постановку задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3. n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? Чтобы привести задачу к математическому виду, введём некоторые термины. Итак, города перенумерованы числами j Т=(1,2,3..n). Тур коммивояжера может быть описан циклической перестановкой t=(j1,j2. jn,j1), причём все j1..jn разные номера; повторяющийся в начале и в конце j1,

2 показывает, что перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал L = L ) n ( t = C j k jk +1 (1) Относительно математизированной формулировки ЗК необходимо сделать два замечания. Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех j Т: Сij 0; Cjj= (2) k =1 (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j: Сij= Сji, (3) и удовлетворять неравенству треугольника, т.е. для всех: Сij+ Сjk Cik. (4) В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если Сij не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно другую). Поэтому различают два варианта ЗК: симметричную задачу, когда условие (3) выполнено, и несимметричную в противном случае. Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры t=(j1,j2. jn,j1) и t =(j1,jn. j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.

3 Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t. Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если Сij=0 и не проведено, если Сij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём). В терминах теории графов симметричную ЗК можно сформулировать так: Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины. В несимметричной ЗК вместо цикл надо говорить контур, а вместо ребра дуги или стрелки. Некоторые прикладные задачи формулируются как ЗК, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но их решать более сложно. Следующий алгоритм, после алгоритма прямого перебора, жадный алгоритм алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. Жадным этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.

4 Рис. 1. Сеть, представляющую узкий ромб, и найденный жадным алгоритмом тур Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию иди в ближайший (в который еще не входил) город. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 1, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм иди вы ближайший город выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур. В пользу процедуры иди в ближайший можно сказать лишь то, что при старте из одного города она не уступит стратегии иди в дальнейший. К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода. Общая идея метода: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу в задаче минимизации, сверху в задаче максимизации) для этих классов, чтобы иметь возможность

5 отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной. Из рассмотренных методов программно реализуем метод перебора, так как жадный алгоритм, как показано выше, часто приводит к неверному ответу, а метод ветвей и границ достаточно сложен для программирования. Нахождение кратчайшего пути методом перебора. Классическим примером переборной задачи и служит задача коммивояжера. Пусть дано множество из N городов, расстояния между которыми известны. В каком порядке должен посетить их коммивояжер, заезжая в каждый город лишь один раз, чтобы общий пройденный путь был кратчайшим? Опишем решение задачи методом перебора или brute-force enumeration перебор животной силой, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с N городами требует при полном переборе рассмотрения (N-1)!/2 туров в симметричной задаче и (N-1)! туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро (табл. 1), однако быстродействие современных ПК позволяет справиться с этой задачей. Таблица 1 5! 10! 15! 20! 25! 30! 35! 40! 45! 50!

10 64 Чтобы проводить полный перебор в ЗК, нужно научиться (разумеется, без повторений) генерировать все перестановки заданного числа m элементов. Предполагаемыми решениями здесь являются перестановки из N городов. Из них нужно выбрать ту, которая даст наименьшую суммарную длину маршрута.

6 Первое, что нужно сделать, решая задачу коммивояжера, это организовать генерацию перестановок. Занумеруем города числами от 1 до N. Все перестановки можно получить, выбирая из множества [2..N] один элемент всевозможными способами и присоединяя к нему поочередно перестановки и из оставшихся элементов. Это рекурсивный алгоритм, т.к. для построения перестановок из N элементов он нуждается в перестановках из N-1 элемента. Первый элемент в сгенерированной перестановке всегда 1, т.к. мы предполагаем, что автотранспортное предприятие расположено в нем и отсюда начинается маршрут. Последний элемент в перестановке также 1, потому что маршрут считается замкнутым транспорт возвращается в город с номером 1. Добавим, что единственная перестановка из одного элемента это сам элемент. Реализуем алгоритм в среде Паскаль-ABC. Запрограммируем получение перестановок в виде рекурсивной процедуры. Расчет проведен для следующей симметричной матрицы С6х6 расстояний между городами. Таблица Множество переставляемых элементов сделаем параметром процедуры. Другим параметром будет позиция перестановки, которая заполняется данным вызовом процедуры. Все перестановки будем поочередно строить во внешнем массиве из N целых чисел, за исключением числа 1.

7 Процедура Comm строит перестановки в массиве А. Перестановка готова, когда S=[]. Процедура дополнена подсчетом длины пути, заданного перестановкой, и выбором самого короткого из них. Для хранения кратчайшего из построенных маршрутов и его длины воспользуемся внешними переменными Аmin и Lmin. Расстояния между городами записаны в двумерном массиве Dist. Листинг программы приведен на рис. 2. Рис. 2. Листинг в среде Паскаль-ABC программы нахождения замкнутого маршрута с минимальной длиной пути

8 В результате решения по данной программе получен оптимальный замкнутый маршрут (рис. 3) движения коммивояжера: , длина пути которого составляет =36 условных единиц. Рис. 3. Результаты решения задачи коммивояжера

9 Оптимальный замкнутый маршрут с минимальной длиной пути можно изобразить в виде следующего графа (рис. 4) Рис. 4. Оптимальный замкнутый маршрут с минимальной длиной пути По подобному алгоритму может быть получен разомкнутый маршрут движения с минимальной длиной пути с заданными начальным и конечным пунктами назначения. Кроме этого под элементами матрицы С понимаются любые затраты (финансовые, временные и т.п.), сумму которых при движении по маршруту необходимо минимизировать.

Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×