Logo    
Деловая газета CitCity.ru CITKIT.ru - все об Open Source Форумы Все публикации Учебный центр Курилка
CitForum    CITForum на CD    Подписка на новости портала Море(!) аналитической информации! :: CITFORUM.RU
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

18.01.2017

Google
WWW CITForum.ru
С Новым годом!
2006 г.

Методика приближенного определения кратчайшего полного пути

Владимир Коднянко, Королевство Delphi
Введение
Хорошо известна следующая задача. Имеется N городов T[0] .. T[N-1]. Расстояние между каждой парой T[i], T[j] определяется длиной соединяющего их отрезка
a.png

где А – матрица расстояний между городами. Необходимо указать кратчайший маршрут, который начинается городом T[0], проходит через города T[1] .. T[n-2] и заканчивается городом T[N-1].

В теоретическом плане задача решается легко: достаточно перебрать все перестановки городов T[1] .. T[n-2] на маршруте и выбрать ту из них, которая доставляет кратчайший путь. Однако этот метод при существующих возможностях ПК дает результат за приемлемое время вычислений (от нескольких секунд до минуты), если N<10. С дальнейшим увеличением N быстродействие комбинаторного метода быстро снижается и его нельзя использовать в практических расчетах.

Среди других методов решения подобных практических задач (к ним, в частности, можно отнести близкую к рассматриваемой задачу коммивояжера) обычно используют единственный альтернативный метод ветвей и границ (МВГ). Считается, что он обеспечивает точное решение за минимальное время вычислений. Метод, действительно, хорошо работает на "учебных" примерах, однако, как показали эксперименты с МВГ на практических (логистических) примерах решения рассматриваемой задачи, его быстродействие сильно зависит от вида матрицы А и в большинстве случаев МВГ не гарантирует результативности в приемлемое время даже при N=15.

При всей известности задачи не удалось ни в научной литературе, ни в Интернет найти быстрых методов, которые позволили бы приближенно решить задачу с достаточной для практики точностью до 10% за приемлемое время.

Ниже рассмотрено несколько сравнительно быстрых приближенных эвристических методов решения задачи, которые удовлетворяют упомянутому условию. Методы реализуют процессы поиска базового маршрута и последующего его улучшения. При их описании использованы терминология теории графов и средства языка Object Pascal среды Delphi.

1 Методы нахождения базового маршрута
Метод 1.1 («жадный», Greedily). Сначала на графе, образованном матрицей А, отыскивается и включается в маршрут вершина (город) T[k] , которая ближе всех к начальной. Далее отыскивается самая близкая к T[k] из числа еще не включенных в маршрут и т. д. В результате получается приближенное решение задачи – базовый маршрут.

Метод 1.2 («деревянный», Woody). Сначала в маршрут включаются две вершины начальная T[0] и конечная T[N-1]. Далее отыскивается вершина, которая характеризуется наименьшим расстоянием D(T[i]+T[k]) + D(T[k]+T[j]) — D(T[i] + T[j]), где i = 0, j = N-1, k – номера еще не включенных в маршрут вершин. Найденная вершина помещается в маршрут (0, k, N-1). На следующем шаге отыскивается вершина L, которая характеризуется наименьшим расстоянием DL от звена (0, k), и вершина M, имеющая наименьшее расстояние DM от звена (k, N-1). Среди L и M выбирается та, которая имеет наименьшее из DL и DM, и включается внутрь своего звена (0, k) или (k, N-1). Пусть это вершина M с номером m. Теперь маршрут состоит из трех звеньев (0, k), (k, m), (m, N-1). Процесс продолжается до тех пор, пока есть не включенные в маршрут вершины.

Метод 1.3 (простейший, Simply). Промежуточные вершины в маршрут включаются случайным образом. В частности, базовым будет допустимый маршрут G[i] = i.

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

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

Метод 2.2 (удаление петлей, CrossDeleting). Часто текущий маршрут содержит петли. Например, на рисунке 1 цепочка вершин 5-7-3-8-2-4 образуют петлю. Петля начинается с левой по ходу маршрута вершины отрезка 5-7 и заканчивается правой вершиной отрезка 2-4. Существование петли определяется наличием пересекающихся отрезков маршрута. Если внутреннюю цепочку петли повернуть в противоположном направлении, то есть заменить указанную цепочку на 5-2-8-3-7-4, то петля исчезнет (рисунок 2), а маршрут станет короче. Метод отличается чрезвычайно высоким быстродействием и высокой эффективностью.

Loop.gif
Loop2.gif
Рисунок 1. Маршрут с петлей
Рисунок 2. Улучшенный маршрут

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

Метод 2.4 (комбинированный, CorrectPath). После нахождения какого-нибудь базового маршрута G к нему применялась комбинированная процедура улучшения по методам 2.1 – 2.3. Хотя метод 2.2 является частным случаем метода 2.3, его все равно применяли из-за высокого быстродействия и способности к эффективному разворота цепочек из любого числа звеньев. Метод имеет код:

procedure CorrectPath(N: Integer; var G: TIntVec; var Path: Integer);

begin
  repeat
  until not Permutations(N,G) and not ChainTurnings(N,G) and

        not CrossDeleting(N,G) and not MoveTops(N,G);
  Path:= PathByG(N,G); // расчет длины маршрута
end;
3 Приближенные комбинированные методы нахождения кратчайшего маршрута
Применив три метода 1.1, 1.2, 1.3 расчета базового маршрута и комбинированный метод 2.4 их улучшения, получили три приближенных метода расчета маршрута:

метод 3.1:

procedure GreedilyCorrect(N: Integer; var G: TIntVec; var Path: Integer);
begin

  Greedily(N,G);
  CorrectPath(N,G,Path);
end;

метод 3.2:

procedure WoodyCorrect(N: Integer; var G: TIntVec; var Path: Integer);

begin
  Woody(N,G);
  CorrectPath(N,G,Path);
end;

и метод 3.3:

procedure SimplyCorrect(N: Integer; var G: TIntVec; var Path: Integer);

begin
  Simply(N,G);
  CorrectPath(N,G,Path);
end;

В экспериментах с методами 3.1–3.3 установлено, что ни один из них не является предпочтительным. В зависимости от матрицы А лучший результат с равной вероятностью мог дать любой из этих методов (интересно, что даже простейший базовый маршрут G[i] = i после улучшений нередко трансформировался в самый короткий маршрут, что свидетельствует о том, что решение задачи практически не зависит от выбора базового маршрута). Поэтому в качестве рабочего применяли комбинированный метод 3.4 (комбинация всех), суть которого состоит в последовательном применении методов 3.1–3.3 к матрице А с последующим выбором лучшего маршрута среди сформированных этими методами.

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

Для оценки точности метода 3.4 при больших значениях N (N>22) процедуру RecoursiveMethod применить нельзя, поэтому составлена процедура Rand многократного применения метода 3.3 к одной и той же матрице А с различными случайными базовыми маршрутами. Процедура последовательно формирует маршруты до тех пор, пока последний лучший маршрут не повторится 5 раз подряд. Нельзя сказать, что такой способ позволяет найти самый короткий маршрут. Однако результаты работы процедуры дают интуитивную уверенность в том, что сравнение «быстрого» результата с результатом длительной работы метода 3.4 имеет достаточно высокую вероятность корректности за неимением точных методов. Уверенность в этом подкреплена весьма важным выводом, который получен после обработки сотен различных матриц для N<23. Он состоит в полном совпадении результатов, полученных с использованием точной процедуры RecoursiveMethod и приближенной Rand (т. е. для данных N процедура Rand всегда находила точное решение задачи).

Скриншот интерфейса разработанной в среде Delphi 6 программы показан на рисунке 3.

Рисунок 3. Интерфейс программы

В качестве примера на рисунке представлен кратчайший маршрут из вершины 0 в вершину 13 (N = 14) для матрицы расстояний, которая показана на рисунке 4.

Matr.png

Рисунок 4. Матрица расстояний

На рисунках 5-10 показаны результаты расчета маршрутов и их протяженности (Комб и Rand) для случайного расположения городов при помощи быстрой процедуры комбинированного метода 3.4 и процедуры Rand. В последней колонке таблиц приведена процентная погрешность метода 3.4, которую рассчитывали по формуле 100 (Комб-Rand)/Комб, %.

Tab10.png
Tab20.png
Tab30.png
Рисунок 5
Рисунок 6
Рисунок 7
Tab40.png
Tab60.png
Tab90.png
Рисунок 8
Рисунок 9
Рисунок 10

В результате экспериментов с несколькими сотнями матриц расстояний для различных N, получены данные, которые свидетельствуют, что независимо от количества N городов погрешность метода 3.4 никогда не превосходила 8% при N<101. Средняя погрешность составила 2%, что вполне приемлемо для практики.

На основании обработки многочисленных расчетных данных получена формула ориентировочной оценки быстродействия метода 3.4. Среднее время t (с) расчета на компьютере с процессором Intel 1400 кратчайшего маршрута с N городами составило

t.png

Так, для N = 100 среднее время расчета маршрута составляет 4 секунды. Для практически используемых N<31 это время не превосходит 0,1 с.

К материалу прилагаются файлы:

Размещение рекламы — тел. +7 495 4119920, ICQ 232284597

Подписка на новости IT-портала CITForum.ru
(библиотека, CITKIT.ru, CitCity)

Новые публикации:

24 декабря

CITKIT.ru:

  • Новогодние поздравления
  • Сергей Кузнецов. Цикл Операционные системы: Ностальгия по будущему:

  • Алексей Федорчук. OpenSolaris 2008.11 Release

  • Сергей Голубев:

  • Евгений Чайкин aka StraNNik (Блогометки):

    17 декабря

  • С.Д.Кузнецов. Базы данных. Вводный курс

    10 декабря

    CITKIT.ru:

  • OpenSolaris 2008.11 Release

  • Альтернативные ОС: две грустные истории (С.Кузнецов)
  • Nokia N810 — доведение до ума
  • CitCity:

  • Платформа 2009: заоблачные перспективы Microsoft

    4 декабря

  • Лекция С.Д.Кузнецова Понятие модели данных. Обзор разновидностей моделей данных

    CITKIT.ru:

  • OpenSolaris 2008.11 Release. Первые впечатления

  • Linux vs FreeBSD: продолжим "Священные войны"?

  • Nokia N810 as is

  • Индульгенция для FOSS

  • Друзья СПО'2008

    26 ноября

  • Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

    CitCity:

    CITKIT.ru:

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • 19 ноября

  • Проблемы экономики производства крупных программных продуктов

  • Язык модификации данных формата XML функциональными методами

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Заметки к книге:

  • FreeBSD: монтирование сменных устройств и механизм HAL
  • Текстовый редактор ee

    12 ноября

  • Правило пяти минут двадцать лет спустя, и как флэш-память изменяет правила (Гоц Грейф, перевод: Сергей Кузнецов)

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:
  • OSS в России: взгляд правоведа (В.Житомирский)

  • Новая статья из цикла С.Голубева "Железный марш":

    29 октября

  • О некоторых задачах обратной инженерии

  • Веб-сервисы и Ruby

  • Тестирование web-приложений с помощью Ruby

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

  • PuppyRus Linux - беседа с разработчиком (С.Голубев)

  • Сергей Кузнецов. Заметка не про Linux

    22 октября

  • Обзор методов описания встраиваемой аппаратуры и построения инструментария кросс-разработки

    CITKIT.ru:

  • Сергей Кузнецов. Почему я равнодушен к Linux

  • Глава из книги А.Федорчука
    Сага о FreeBSD:
  • Что надо иметь
    3. Базовые познания

    CitCity:

  • Управление IT-инфраструктурой на основе продуктов Microsoft

    15 октября

  • Методы бикластеризации для анализа интернет-данных

    CitCity:

  • Разъемы на ноутбуках: что они дают и зачем их так много?
  • AMD Puma и Intel Centrino 2: кто лучше?

    CITKIT.ru:

  • Новый цикл статей С.Голубева
    Железный марш:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    8 октября

  • Автоматизация тестирования web-приложений, основанных на скриптовых языках
  • Опыт применения технологии Azov для тестирования библиотеки Qt3

    Обзоры журнала Computer:

  • SOA с гарантией качества
  • Пикоджоуль ватт бережет
  • ICT и всемирное развитие

    CitCity:

  • Пиррова победа корпорации Microsoft

    CITKIT.ru:

  • Главы из книги А.Федорчука
    Сага о FreeBSD:

    Статья из архива:

  • Я живу в FreeBSD (Вадим Колонцов)

    Новые Блогометки:

  • Перекройка шаблона Blogger или N шагов к настоящему
  • Blogger. Comment style
  • Screenie или глянцевый снимок экрана

    2 октября

    CITKIT.ru:

  • Сага о FreeBSD (А. Федорчук)

    Zenwalk: пакет недели

  • Банинг — интеллектуальное развлечение (С.Голубев)

    CitCity:

    25 сентября

  • Клермонтский отчет об исследованиях в области баз данных

    CITKIT.ru:

  • Пользователям просьба не беспокоиться... (В.Попов)

  • Снова про ZFS: диск хорошо, а два лучше
  • Командная оболочка tcsh (А.Федорчук)

    Zenwalk: пакет недели

    17 сентября

  • T2C: технология автоматизированной разработки тестов базовой функциональности программных интерфейсов
  • Технология Azov автоматизации массового создания тестов работоспособности

    CITKIT.ru:

  • FreeBSD: ZFS vs UFS, и обе-две — против всех (А.Федорчук)

    Zenwalk: пакет недели

  • Дачнет — практика без теории (С.Голубев)

    10 сентября

  • За чем следить и чем управлять при работе приложений с Oracle
  • Планировщик заданий в Oracle
    (В.Пржиялковский)

    CITKIT.ru:

  • Microsoft: ответный "боян" (С.Голубев)

  • Причуды симбиоза, или снова "сделай сам" (В.Попов)

  • Файловые системы современного Linux'а: последнее тестирование
  • Zsh. Введение и обзор возможностей
    (А.Федорчук)

    Описания пакетов Zenwalk: Zsh, Thunar, Thunar-bulk-rename, Xfce4-places-plugin, Xfce4-fsguard-plugin

    Блогометки:

  • Google Chrome
  • Лончер для ASUS Eee PC 701

    3 сентября

    CITKIT.ru:

  • Заметки о ядре (А.Федорчук):

    Добавлены описания пакетов Zenwalk: Galculator, Screenshot, Gnumeric, Pidgin

    В дискуссинном клубе:

  • И еще о Википедии и Google Knol

  • Лекция для начинающего линуксоида (С.Голубев)

    26 августа

  • Транзакционная память (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Открыт новый проект Zenwalk: пакет недели

  • Статья Текстовые процессоры и их быстродействие: конец еще одной легенды?

    21 августа

    CITKIT.ru:

  • Почему школам следует использовать только свободные программы (Ричард Столлман)
  • Беседа Сергея Голубева с учителем В.В.Михайловым

  • Википедия или Гуглезнание? Приглашение к обсуждению (Алексей Федорчук)
  • Народная энциклопедия от Google (StraNNik)

  • Обзор Mandriva 2009.0 Beta 1 Thornicrofti
  • Новичок в Линукс: Оптимизируем Mandriva 2008.1

  • Книга Zenwalk. Приобщение к Linux:

    13 августа

    CitCity:

  • Мирный Atom на службе человеку. Обзор платы Intel D945GCLF с интегрированным процессором
  • Обзор процессоров Intel Atom 230 на ядре Diamondville

  • iPhone - год спустя. Скоро и в России?

    CITKIT.ru:

  • Интермедия 3.4. GRUB: установка и настройка (из книги Zenwalk. Приобщение к Linux)

    6 августа

  • СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности? (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • Интермедия 2.2. Что неплохо знать для начала (из книги Zenwalk. Приобщение к Linux)

  • И снова про шрифты в Иксах (А.Федорчук)

  • 20 самых быстрых и простых оконных менеджеров для Linux

  • Дело о трех миллиардах (С.Голубев)

    30 июля

  • OLTP в Зазеркалье (Пересказ: С. Кузнецов)

    CitCity:

  • Будущее BI в облаках?
  • Тиражные приложения и заказная разработка. Преимущества для заказчика
  • Дискуссия со сторонниками заказной разработки

    CITKIT.ru:

  • Новые главы книги Zenwalk. Приобщение к Linux:
  • Глава 8. Пакеты: средства установки, системы управления, системы построения
  • Глава 9. Zenwalk: репозитории, пакеты, методы установки

    23 июля

    CITKIT.ru:

  • Все против всех. 64 vs 32, Intel vs AMD, tmpfs vs ext3
  • Две головы от Intel

  • Zenwalk: обзор штатных приложений (глава из книги "Zenwalk. Приобщение к Linux")

  • Нормально, Григорий...

    16 июля

    Обзоры журнала Computer:

  • Перспективы и проблемы программной инженерии в XXI веке
  • Большие хлопоты с большими объемами данных
  • Перспективы наноэлектроники

    CITKIT.ru:

  • Интермедия о лицензиях (А.Федорчук. "Zenwalk. Приобщение к Linux")

  • Есть ли будущее у KDE?

  • Linux в школе: альтернативный вариант в задачах

  • Шифр (приключения агента Никодима)

    10 июля

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия вступительная. Linux или GNU/Linux? Как вас теперь называть?
  • Глава 5. Среда Xfce
  • Глава 6. Xfce: приложения и плагины

  • ZUR (Zenwalk User Repository) FAQ

    2 июля

  • Персистентность данных в объектно-ориентированных приложениях (С. Кузнецов)

    CITKIT.ru:

  • Новые разделы книги А. Федорчука Zenwalk. Приобщение к Linux:
  • Интермедия 1.2. Дорога к Zenwalk'у. Период бури и натиска
  • Интермедия 3.3. Немного о Linux'е и "железе"
  • Глава 4. Настройка: инструментами и руками
  • Интермедия 4.1. Zenpanel и конфиги: поиски корреляции

  • Интервью с Жан-Филиппом Гийоменом, создателем дистрибутива Zenwalk

  • Linux в школе: первые итоги (С. Голубев)

    25 июня

    CITKIT.ru:

  • Zenwalk. Приобщение к Linux (А. Федорчук)

  • Логика и риторика (С.Голубев)

  • Технология Tru64 AdvFS

  • Ханс Райзер предлагает отвести полицейских к телу Нины

    18 июня

  • Проекты по управлению данными в Google (Пересказ: С. Кузнецов)

    CITKIT.ru:

  • ОС и поддержка "железа": мифы и реальность (А. Федорчук)

  • Linux в школе: другие дистрибутивы

  • Пинок (С. Голубев)

    4 июня

  • Ландшафт области управления данными: аналитический обзор (С. Кузнецов)

    CITKIT.ru:

  • Linux в школе: слово заинтересованным лицам

  • SlackBuild: пакеты своими руками

  • Linux от компании Novell. Установка и обзор openSUSE Linux

    Все публикации >>>




  • IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

    Информация для рекламодателей PR-акции, размещение рекламы — тел. +7 495 4119920, ICQ 232284597 Пресс-релизы — pr@citcity.ru
    Послать комментарий
    Информация для авторов
    Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
    Copyright © 1997-2000 CIT, © 2001-2007 CIT Forum
    Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...