Компьютерная реализация задачи о коммивояжере

Размещено на http://www.allbest.ru/

Днепропетровский национальный университет им. О. Гончара

КОМПЬЮТЕРНАЯ РЕАЛИЗАЦИЯ ЗАДАЧИ О КОММИВОЯЖЕРЕ

Б.А. Бигеев, к.т.н.

Аннотация

экономический задача коммивояжер компьютерный

В статье представлены математическая постановка и компьютерная реализация известной экономической задачи о коммивояжере. Разработан оригинальный алгоритм решения задачи, обеспечивающий получение оптимального маршрута с минимальными экономическими затратами.

Ключевые слова: задача о коммивояжере, маршрут, алгоритм, экономические затраты.

Annotation

The article gives the mathematical definition and computer realization of a well-known economic task about a commercial traveler. The unique algorithm of coving the problem that provides the fully satisfactory rout with minimum economic costs.

Введение

В статье представлена задача о коммивояжере - бродячем торговце, который покинул город (которому мы присваиваем имя «С»), объехав еще N городов и вернулся снова в город с именем «С». В его распоряжении есть дороги, соединяющие эти города. Он должен выбрать свой маршрут - порядок посещения городов так, чтобы путь, который ему надлежит пройти, был минимальным. Основное условие этой задачи состоит в том, что в каждом городе коммивояжер может побывать только 1 раз - это условие будем называть условием (?). Естественно, что расстояние между двумя городами - функция f(x_i, x_j) - определено. Добавление города с именем «С» расширяет сферу практического применения в экономике задачи о коммивояжере.

Функция f(x_i, x_j) может означать не только расстояние, но и, например, время, издержки в пути; да и сам коммивояжер может быть некоторым транспортным средством, развозящем товары поN пунктам доставки.

Математическая постановка задачи

Длина l пути S определяется формулой

. ⁽¹⁾

а) Сумма в выражении (1) распространена по всем индексам i, j, удовлетворяет условию (?).

б) Путь из пункта i в пункт j может не совпадать по затратам пути из пункта j в пункт i. Это значит, что

. (2)

Эта задача не удовлетворяет принципу оптимальности Беллмана и не может решаться методами динамического программирования. Но функция f(x_i, x_j) и функция пути l(x₁,…,x_N) в этой задаче определены на конечном множестве точек, следовательно задача сводится к перебору всех возможных маршрутов и проблема носит чисто вычислительный характер. Однако именно вычислительные трудности здесь огромны: число возможных маршрутов между N пунктами доставки равно N!.

Техническая постановки задачи

1. Имеется N пунктов доставки, куда следует завести заданные объемы грузов.

2. Имеется «Матрица расстояний» между пунктами доставки.

3. Имеется «Матрица весов» для каждого пути, отражающая характер дорог, их пропускную способность и загруженность.

4. Расходы на преодоление пути между пунктами i и j вычисляются по формуле:

(3)

где G_ij - вес транспортного средства с грузом, соответствующим участку пути между пунктами i и j.

l_ij - длина пути между пунктами i и j.

v_ij - весовой коэффициент участка пути между пунктами i и j.

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

Найти оптимальный порядок обхода пунктов доставки, чтобы затраты на доставку были минимальными.

На данном этапе разработки компьютерной реализации число пунктов доставки ограничено, N Ј 9.

Результаты

Задача о коммивояжере принципиально состоит из двух вычислительных процессов.

Первый процесс это генерация перестановок (возможных маршрутов) из N элементов по N. Количество таких перестановок, как уже было сказано, составляет N!.

Второй процесс это вычисление затрат на преодолении текущего маршрута.

Процедура генерации перестановок относится к числу исключительно сложных программистских задач. Нами разработаны два алгоритма генерации перестановок. В первом алгоритме члены натурального ряда от 1 до N! преобразуются в соответствующие перестановки. Второй алгоритм построен на использовании рекуррентного вызова процедур. Это означает, что при генерации перестановок процедура N раз вызывает сама себя. И каждый такой вызов дожжен не начинать процесс заново, а продолжить предыдущее. Оба алгоритма характеризуются высоким уровнем программирования.

Мы установили, что генератор по первому алгоритму дает выигрыш при использовании устаревших компьютеров с малой оперативной памятью. На современной технике второй алгоритм дает 40-ка процентный выигрыш во времени. Следует также подчеркнуть, что каждый из алгоритмов обладает исключительной производительностью: 9! перестановок (362880) он генерирует на современном компьютере за 5 - 6 секунд. Текст одной из процедур приведен ниже.

Sub Perestanovki()

' Перебор всех перестановок из n элементов по n

' достигается путем преобразования натурального ряда

' чисел от 1 до n! в перестановки

Dim n As Integer

Dim a As String

Dim p(10), po(10), pf(10) As Long

' p(n) - целевой массив

' pо(n) - контрольный массив

n = Cells(1, 1).Value

Application.ScreenUpdating = False

' первичные присвоения

J = 1

For i = 1 To n

J = J * i

pf(i) = J ' накопление факториалов от 1 до n

Next i

k = J

Cells(5, 1) = J

m = 1

For i = 1 To k ' цикл от 1 до n!

For J = 1 To n

po(J) = J ' числа от 1 до n

Next J

ii = i

For J = n - 1 To 2 Step -1

' элемент натурального ряда делится в цикле

' последовательно на (n-1)!, (n-2)!,..., 2!,

' чтобы получить первые n-2 индекса

kk = pf(J)

L = Int((2 * (ii - 1) + 1) / (2 * kk)) + 1

ii = ii - kk * (L - 1)

jk = n - J

If jk > 1 Then

t = 0

For LL = 1 To n

If po(LL) > 0 Then

t = t + 1

If t = L Then

L = LL

Exit For

End If

End If

Next LL

End If

p(jk) = L

po(L) = 0

Next J

' получение двух последних индексов

m = 3 - m ' m принимает значения 1,2,1,2,...

ji = m

For J = 1 To n

ij = po(J)

If ij > 0 Then

p(n + 1 - ji) = ij

ji = 3 - ji

End If

Next J

' свертка массива p(n) для компактно печати

a = ""

For J = 1 To n

a = a & Trim(Str(p(J)))

Next J

Next i

End Sub

Программа, реализующая расчет затрат на преодолении маршрута зависит от экранной реализации процесса вычислений, от размещения исходных данных. Вот примерный вид листа Excel с данными к задаче.

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

Выводы

? разработаны два оригинальных алгоритма генерации перестановок из N элементов по N, производительность которых составляет примерно 80000 перестановок в секунду;

? разработана техническая схема задачи о коммивояжере. При этом учтены длины и класс дорог, изменение веса груза в процессе его развозки по пунктам, а также норму затрат транспортного средства. Все это реализовано в виде программного модуля расчета затрат;

? программа автоматически настраивается на количество пунктов доставки по объему исходных таблиц (в рамках ограничений от 1 до 9);

? программа может использоваться не только для доставки грузов на пункты доставки, но и сбор грузов от производителей (например, для объезда молочных ферм), если грузы доставки брать со знаком минус;

? обеспечена наглядность представления результатов расчета;

? использован индикатор работы программы, что особенно важно при длительных расчетах

Список использованных источников

1. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: «Наука», Главная редакция физико-математической литературы, 1978. 352 с.

2. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Главная редакция физико-математической литературы изд-ва «Наука», 1977.

3. Гавурин М.К. Лекции по методам вычислений. М.: Главная редакция физико-математической литературы изд-ва «Наука», 1971.

4. Кузин Л.Т. Основы кибернетики: В 2-х т. Т.2. Основы кибернетических моделей: Учеб. пособие для вузов. - Энергия, 1979. 584 с.

5. Марюта А.Н., Смирнов С.А. Эвристический системный анализ экономики: Монография. - Днепропетровск: Наука и образование, 2004. 294 с.

Размещено на Allbest.ru