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



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


Введение:
Одна из самых известных и важных задач транспортной логистики (и комбинаторной оптимизации) – задача коммивояжера или «задача о странствующем торговце». Также встречается название «задача китайского почтальона». Суть задачи сводится к поиску оптимального пути, проходящего через промежуточный пункты по одному разу и возвращающегося в исходную точку. К примеру, нахождение наиболее выгодного маршрута, позволяющего коммивояжеру посетить со своим товаром определенные города по одному разу и вернуться обратно. Мерой выгодности маршрута может быть минимальное время поездки, минимальные расходы на дорогу или минимальная длина пути.
Из истории задачи коммивояжера:
Одним из первых, кто сформулировал ранний вариант этой задачи, был выдающийся ирландский математик, физик и механик XIX в. – Уильям Роуэн Гамильтон. Ученый изучал симметрии икосаэдра (двадцатигранника) и в 1857 году предложил игру «Икосиан», цель которой заключалась в прохождении всех вершин додекаэдра (двенадцатигранника) ровно по одному разу и только по его ребрам, с последующим возвратом в отправную точку. Иными словами, нужно было найти так называемый гамильтонов цикл на графе с 20 узлами, в данном случае являющийся решением задачи и содержащий 20 ребер («двадцать» на древнегреческом «icosa», отсюда и название игры). Придуманную математиком головоломку продавали в Европе в виде доски с изображением додекаэдра и выемками на месте его вершин.
В 1930 году австрийско-американский математик Карл Менгер сформулировал задачу коммивояжера как «задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно». Современное название «задача коммивояжера» или «задача странствующего торговца» было предложено американским математиком Хасслером Уитни.
Во второй половине XX веке появились множества вариаций условий данной задачи, так Селмер Джонсон и Джордж Данциг сформулировали проблему в качестве задачи дискретной оптимизации, решив задачу в 49 городами, обосновав кратчайший маршрут. А в 1962 году китайский математик Мэй-Ку Куан изучал свою интерпретацию этой проблемы, получившей название «задача китайского почтальона». В его варианте почтальону требовалось разнести письма по кратчайшему маршруту на вверенном ему участке города, проходя по каждой улице лишь единожды или с минимальным числом повторов.
В 1960-1970 гг. исследование задачи коммивояжера было продолжено в теоретическом и практическом направлениях (изучались возможности ее прикладного применения в экономике, биологии, химии, информатике).
Рекорд по решению задачи коммивояжера установили в апреле 2006 года, когда было найдено решение для варианта с 85900 городами.

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

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




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

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