Вы на НеОфициальном сайте факультета ЭиП

На нашем портале ежедневно выкладываются материалы способные помочь студентам. Курсовые, шпаргалки, ответы и еще куча всего что может понадобиться в учебе!
Главная Контакты Карта сайта
 
Где мы?

Реклама


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

Просмотров: 2776 Автор: admin

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

 

Основные цели

  • понять, как можно решить задачу коммивояжера с использованием алгоритма муравья
Теоретическая справка

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

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

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

 

Кроме отслеживания текущего и следующего города на пути (поля curCity и nextCity) каждый муравей также должен учитывать города, которые уже были посещены (массив tabu) и длину пройденного пути. Общая длина пути сохраняется в поле tourLength.

Двумерный массив, distance, содержит предварительно рассчитанные расстояния от одного города до всех других. Уровни фермента сохраняются в массиве pheromone. Каждый двумерный массив в алгоритме использует первый индекс в качестве начала грани, то есть исходного города, а второй - в качестве конечного

6. Щелкните по меню «Города, Расположить случайно», откроется процедура mnuCityRandomClick. Текст функции должен содержать три базовых действия, которые требуются для подготовки алгоритма муравья.

Первое действие - это создание городов. Для каждого города, который требуется создать (количество задано константой МАХ_С1TIES) генерируются произвольные числа для координат по осям х и у, которые затем сохраняются в запись текущего города.

Второе действие — во время создания городов одновременно очищаются массивы distance и pheromone.

Третье действие  — это предварительный расчет расстояний между всеми городами, которые были созданы. Расстояние вычисляется с помощью обычной двумерной геометрии координат (теорема Пифагора).

Наконец, инициализируется массив ant. При этом муравьи  равномерно распределяются по всем городам. Для этого используется переменная to в качестве счетчика псевдо цикла. Когда значение переменной to становится равным номеру последнего города, она возвращается к первому городу (городу 0), и процесс повторяется.

 

Скачать  Решение задачи коммивояжера met-ant01.zip [350,34 Kb] (cкачиваний: 110)


Информация

Комментировать статьи на нашем сайте возможно только в течении 60 дней со дня публикации.

Популярные новости

Статистика сайта



Rambler's Top100



 
Copyright © НеОфициальный сайт факультета ЭиП