Методы решения задачи о Коммивояжере

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

· Полный перебор;

Полный перебор (либо способ «грубой силы») — способ решения задачки методом перебора всех вероятных вариантов. Сложность полного перебора находится в зависимости от количества всех вероятных решений задачки. Если место решений очень велико, то полный перебор может не дать результатов в течение пары лет либо даже веков.

· Случайный перебор Методы решения задачи о Коммивояжере;

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы при помощи какого-нибудь случайного механизма, то решение находится очень стремительно, так что можно отыскивать решение неоднократно и запоминать «рекорд», т. е. лучшее из встретившихся решений. Этот доверчивый подход значительно улучшается, когда удается учитывать в Методы решения задачи о Коммивояжере случайном механизме перспективность тех либо других выборов, т. е. сочетать случайный поиск с эвристическим способом и способом локального поиска. Такие способы используются, к примеру, при составлении расписаний для Аэрофлота.

· Скупые методы (способ наиблежайшего соседа, способ включения наиблежайшего городка, способ самого дешевенького включения);

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

Рис. 3

· Способ малого остовного дерева (древесный метод);

В базе метода лежит утверждение: «Если справедливо неравенство треугольника, то для каждой цепи правильно, что расстояние от начала до конца цепи меньше (либо равно) суммарной длины всех ребер цепи». Это обобщение расхожего убеждения, что ровная короче кривой. Древесный метод для решения задачки коммивояжера Методы решения задачи о Коммивояжере будет последующим: строится на входной сети задачки коммивояжера кратчайшее остовное дерево и умножаются все его ребра. В итоге получаем граф — связный с верхушками, имеющими только четные степени. Потом строится эйлеров цикл, начиная с верхушки 1, цикл задается списком вершин. Просматривается список вершин, начиная с 1, и зачеркивается любая верхушка, которая повторяет Методы решения задачи о Коммивояжере уже встреченную в последовательности. Остается тур, который и является результатом метода.

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

· Способ имитации отжига.

Экзотичное заглавие данного метода связано с способами имитационного моделирования в статистической физике, основанными на технике Монте-Карло Методы решения задачи о Коммивояжере. Исследование кристаллической решетки и поведения атомов при неспешном остывании тела привело к возникновению на свет вероятностных алгоритмов, которые оказались очень действенными в комбинаторной оптимизации. В первый раз это было увидено в 1983 году. Сейчас этот метод является пользующимся популярностью как посреди практиков благодаря собственной простоте, гибкости и эффективности, так и посреди Методы решения задачи о Коммивояжере теоретиков, так как для данного метода удается аналитически изучить его характеристики и обосновать асимптотическую сходимость. Метод имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого метода для текущего решения ik в его округи N(ik) выбирается некое решение j и, если разность по Методы решения задачи о Коммивояжере мотивированной функции меж новым и текущим решением не превосходит данного порога tk, то новое решение j подменяет текущее. В неприятном случае выбирается новое примыкающее решение. На практике используются разные модификации более действенных способов:

· Способ веток и границ;

Способ веток и границ предложен в 1963 году группой создателей Дж. Литлом Методы решения задачи о Коммивояжере, К. Мурти, Д. Суини, К. Кэролом. Обширно применяемый вариант поиска с возвращением, практически является только особым личным случаем способа поиска с ограничениями4. Ограничения в этом случае основываются на предположении, что на огромном количестве вероятных и частичных решений задана некая функция цены и что необходимо отыскать наилучшее решение, т.е. решение с Методы решения задачи о Коммивояжере меньшей ценой. Для внедрения способа веток и границ функция цены должна владеть тем свойством, что стоимость хоть какого частичного решения не превосходит цены хоть какого расширения этого частичного решения (Заметим, что почти всегда функция цены неотрицательна и даже удовлетворяет более сильному требованию). Настолько большой фуррор внедрения данного способа разъясняется Методы решения задачи о Коммивояжере тем, что создатели первыми направили внимание на широту способностей способа, отметили значимость использования специфичности задачки и сами пользовались специфичностью задачки коммивояжера.

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

· Способ генетических алгоритмов;

«Отцом-основателем» генетических алгоритмов считается Джон Холланд, книжка которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследовательских работ. Генетический метод — это эвристический метод поиска, применяемый для решения задач оптимизации Методы решения задачи о Коммивояжере и моделирования оковём случайного подбора, комбинирования и варианты разыскиваемых характеристик с внедрением устройств, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического метода является акцент на внедрение оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой подобна роли скрещивания в живой природе. Генетические методы служат, приемущественно, для Методы решения задачи о Коммивояжере поиска решений в многомерных местах поиска.

· метод муравьиной колонии.

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

2.4 Способ веток и границ

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

(1) Построение матрицы с начальными данными.

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

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

(4) Нахождение Методы решения задачи о Коммивояжере минимума по столбцам.

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

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

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

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

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

Подробная методика решения

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

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

1. Построение матрицы с начальными данными

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

Таблица 1

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

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

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

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

Таблица 2

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

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

Таблица 3

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

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

Таблица 4


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

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

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

Таблица Методы решения задачи о Коммивояжере 5

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

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

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

Таблица 6

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


Таблица 7

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

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

Таблица 8

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

Таблица 9

8. если полный путь еще не найден, перебегаем к пт 2, если найден к Методы решения задачи о Коммивояжере пт 9

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

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

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

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

В нашем примере маршрут Методы решения задачи о Коммивояжере вышел последующий: 4 → 2 → 3 → 1 → 4.

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


Заключение

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

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


Перечень использованной литературы

1. Кирсанов М.Н. «Графы в Maple», М. Физматлит, 2007.

2. Зыков А.А. «Основы Методы решения задачи о Коммивояжере теории графов» , М. «Вузовская книга», 2014

3. Уилсон Р. «Введение в теорию графов» , М. «Мир», 2010

4. Берж К. "Теория графов и ее применение", М., ИЛ, 2008;

5. Гарднер М. "Математические досуги", М. "Мир", 2009(глава 35);

6. "В помощь учителю арифметики", Йошкар-Ола, 2011 (ст. "Исследование частей теории графов");

7. Олехник С.Н., Нестеренко Ю.В., Потапов М.К Методы решения задачи о Коммивояжере. "Древние занятные задачки", М. "Наука", 2008;

8. Гарднер М. "Математические головоломки и утехи", М. "Мир",2012;

9. Оре О. "Графы и их внедрения", М. "Мир", 2011;

10. Зыков А.А. "Теория конечных графов", Новосибирск, "Наука", 2009;

11. Реньи А., "Трилогия о арифметике", М., "Мир", 2010.

Расположено на Allbest.ru


metodi-udaleniya-pogodnih-effektov-osnovannie-na-fizicheskih-modelyah.html
metodi-ulashtuvannya-gdrozolyac-pd-plitkove-pokrittya-referat.html
metodi-upravleniya-energosberezheniem.html