Задача коммивояжера или «задача о странствующем торговце». Также встречается название «задача китайского почтальона»


Определение, условия и методы решения задач коммивояжера



Скачать 61,64 Kb.
страница2/3
Дата11.12.2022
Размер61,64 Kb.
#196522
ТипЗадача
1   2   3
Связанные:
задача коммивояжера

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

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

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

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

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

  • метод минимального остовного дерева — поиск маршрута ведется на графе.

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

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

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

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


Скачать 61,64 Kb.

Поделитесь с Вашими друзьями:
1   2   3




База данных защищена авторским правом ©psihdocs.ru 2023
обратиться к администрации

    Главная страница