Задача - коммивояжер
Cтраница 1
Задача коммивояжера является типичной задачей оптимизации, которую мржно решить с помощью метода ветвей и границ. [1]
Задача коммивояжера состоит в поиске гамильтонова цикла минимального общего веса в нагруженном графе. Алгоритм ближайшего соседа позволяет найти субоптимальное решение задачи коммивояжера. [2]
Задача коммивояжера ( travelling salesman problem) тесно связана с проблемой поиска Гамильтонова пути. Она формулируется так: найти самый короткий Гамильтонов путь для сети. [3]
Задача коммивояжера может быть поставлена следующим образом. Каков должен быть маршрут коммивояжера, если он начинает путешествовать из города, где он живет, посещает каждый город, ровно один раз и возвращается в свой город, причем общая длина его пути должна быть минимальной. [4]
Задача коммивояжера была описана выше ( § 3 гл. [5]
 |
Идеальная характеристика четырехбитового аналого-цифрового. [6] |
Задача коммивояжера является оптимизационной задачей, часто возникающей на практике. [7]
Задача коммивояжера является задачей целочисленного программирования. [8]
Задача коммивояжера тесно связана с несколькими другими задачами теории графов, обсуждаемыми в других частях этой книги. [9]
Задача коммивояжера является классической оптимизационной задачей. Суть ее заключается в следующем. [10]
Задача коммивояжера в принципе может быть решена с применением любой процедуры исчерпывающего поиска ( полного перебора), однако на практике для ускорения процесса поиска необходимы эвристики и другие соображения, использующие специфику этой задачи. Такое использование знания возможно лишь при наличии общих сведений о задаче или пространстве поиска. В общем случае задача разрешима в той степени, в которой исследование части пространства поиска дает существенную информацию о характере оставшейся части этого пространства. При попытке охарактеризовать пространство поиска может быть задано множество вопросов. Разбивается ли задача достаточно хорошо на совокупность более мелких подзадач. Существует ли точная, непротиворечивая информация о задаче. Ожидается ли, что в процессе решения задачи человек будет взаимодействовать с вычислительной машиной. [11]
Задача коммивояжера тесно связана с несколькими другими задачами теории графов, обсуждаемыми в других частях этой книги. [12]
Задачу коммивояжера удобно записывать в постановке, рассмотренной в разд. [13]
Задачу коммивояжера можно решать совместно с имитационным моделированием. Причем при большом числе населенных пунктов алгоритм двух вертолетов всегда дает решение, лучшее по сравнению с алгоритмом ближайшего непосещенного города и не уступающее по точности другим методам математического программирования. Это происходит потому, что оптимизация осуществляется двунаправленным одновременным просмотром. Алгоритм ближайшего непосещенного города начинает запутывать маршрут и при большом числе пунктов уводить его от оптимального, так как в конец маршрута заглянуть невозможно. Если иметь средства автоматического отображения маршрута ( их предоставляет Pilgrim), то неоптимальные участки сразу видны в результатах. [14]
Симметричную задачу коммивояжера можно рассматривать как задачу отыскания гамильтонова цикла минимальной стоимости во взвешенном неориентированном графе. Имея это в виду, легко доказать, что задача определения существования гамильтонова цикла в неориентированном графе преобразуется в задачу коммивояжера. [15]
Страницы: 1 2 3 4