Полная версия

Главная arrow Информатика arrow Введение в курс метрической теории и метрологии программ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ВЫЧИСЛИТЕЛЬНАЯ И ИНФОРМАЦИОННАЯ СЛОЖНОСТЬ ЗАДАЧ (временные характеристики программ)

3.1. Вычислительная сложность решения задач

3.1.1. Объемные характеристики программ (алгоритмическая сложность) не дают представления о трудоемкости вычислений. Есть много задач, для которых существуют простые алгоритмы с короткими программами, но требующие для решения фантастически огромного времени. Встречаются, напротив, задачи с громоздкими программами, но небольшими временными затратами. Поэтому для более полной оценки вычислительного процесса необходима дополнительная характеристика.

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

Более реалистичные оценки, например, «в среднем», получить очень трудно: частота решения разных задач того или иного класса обычно недостаточна.

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

Чтобы конкретизировать дальнейшее изложение, рассмотрим ряд примеров таких задач. Первый. Известная задача коммивояжера, имеющая множество формулировок в различных приложениях: требуется посетить п городов, побывав в каждом ровно по одному разу; вернуться в исходный пункт и при этом затратить минимальную сумму на поездку, складывающуюся из затрат на переезды между парами городов. Эти затраты заранее известны и заданы в виде матрицы |ягу|, где

ац - стоимость проезда между ними. Очевидно, что возможных исходных пунктов поездки будет п, а продолжение пути из каждого из них имеет (п - 1)! вариантов. Таким образом, общее количество маршрутов

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

Щу|| длина программы относительно невелика даже для больших значений п). Итак, /(я) * пп.

По установившейся терминологии различают массовые и индивидуальные задачи. Приведенный выше пример - это массовая задача,

однако если задать конкретную числовую матрицу Щу ||, то получим

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

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

выбора в этой задаче экспоненциально - пп~2, где п - число клиентов. Однако в данном случае временная сложность решения задачи имеет величину

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

Эдмондс предложил следующий критерий для классификации дискретных задач [13]. Массовая задача считается легкорешаемой, если существует алгоритм, позволяющий решать любую индивидуальную задачу за число шагов, не превышающее значение некоторого полинома от количества входных данных:

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

Табл. 4 и 5 дают наглядное представление о различии этих двух типов задач [13, 14].

Таблица 4

Время решения задач (один шаг соответствует одной микросекунде)

'^^Размерность

п

Сложность'^

20

50

100

200

500

1000

1000 п

0,02 с

0,05 с

0,1 с

0,2 с

0,5 с

1000 п log п

0,09 с

0,3 с

0,6 с

1,5 с

4,5 с

Юс

100 п

0,04 с

0,25 с

1 с

25 с

2 мин

10 п

0,02 с

1 с

Юс

1 мин

21 мин

2,7 ч

п

23

0,0001 с

0,1 с

2,7 ч.

3-104 век

2й

1 с

35 лет

3-104 век

з«

58 мин

2-109 век

Таблица 5

Влияние роста производительности ЭВМ (один час работы ЭВМ)

Производи-

^''''~'\_дельность

Сложность

Современные

ЭВМ

ЭВМ, в 100 раз более быстрые

ЭВМ, в 1000 раз более быстрые

п

Ni

100 Л^1

1000 А^1

1

п

N2

юлъ

31,6 N2

3

п

N3

4,64 N3

10 #3

5

п

N4

2,5 N4

4 N4

2"

N5

N5 + 6,64

N5+ 10

з”

N6

Л^б + 4,19

N6 + 6,3

Критерий Эдмондса считается очень грубым, но для задач большой размерности деление их по сложности на полиномиальные и экспоненциальные весьма четко разграничено. При п = 50, как видно из табл. 4 и 5, задачи с t(n) = 2 и более практически неразрешимы. Рост быстродействия ЭВМ по сравнению с современными на два-три порядка не дает заметного роста размерности при решении задач с экспоненциальной временной сигнализирующей (табл. 5). Из табл. 4 видно, что с ростом п влияние постоянного множителя при степенных функциях на время решения t(n) уменьшается.

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

Для этого вновь обратимся к легкорешаемым задачам.

• Проверка планарности графа.

Эта задача возникает, например, при разработке печатных плат. При этом проводники, реализующие заданную электрическую схему, не должны пересекаться.

Первый алгоритм, предложенный для ее решения, имел вычислительную сложность t(n)~n6. Позднее последовательно были предложены методы с t(n) ~ п2, t{n) ~ п log п и, наконец, t(n) ~ п.

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

Задача заключается в максимизации потока между источником и стоком. Для ее решения Фордом и Фалкерсоном был разработан алгоритм, имеющий сложность t(ri) ~г?.

  • • Широко известная задача сортировки массива из п элементов имеет t{n) ~ п log п. Это нетрудно показать, используя процедуру дихотомического поиска.
  • • Эйлеров цикл на графе представляет собой замкнутый путь, содержащий все его ребра, каждое из которых можно пройти строго один раз. Если п - число ребер, то временная сложность решения данной задачи t{ri) ~ п.
  • • Задача о нахождении кратчайших расстояний между всеми парами вершин графа имеет t(n) ~ я3.
  • • Последний пример из этого класса - задача линейного программирования, алгоритм решения которой (симплекс-метод), строго говоря, не гарантировал полиномиальной сходимости, однако успешно применялся на практике. Только в 1979 г. советский математик Л. Ха- чиян предложил для решения общей задачи линейного программирования полиномиальный алгоритм, существенно отличающийся от симплекс-метода и, в частности, объясняющий практический успех последнего. Временная сложность этой задачи /(и) ~ п2,5 + п3.

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

Таких задач много (тысячи) и все они источником своего возникновения имеют экономику, производство и различные области техники. Поэтому практическим решением проблемы, если на текущий момент не известен приемлемый приближенный метод, может быть только компромиссное решение по формулировке поставленной задачи. Но это оказывается возможным лишь в том случае, если природа трудностей понятна на самой ранней стадии проекта. В действительности, идентификация труднорешаемости для многих коллективов разработчиков ПО может оказаться непосильной. Неосознанная попытка решить в рамках проекта ИС одну из таких задач чревата бесполезными затратами большого количества времени. Поэтому разработчикам ПО весьма необходимо знакомство с основными результатами теории труднорешаемых задач, чтобы уметь пользоваться хотя бы их каталогами (наподобие книги М. Гэри и Д. Джонсона [13]) для избежания таких ловушек.

3.1.3. Разнообразие формулировок труднорешаемых задач огромно. Отсутствие единой точки зрения на проблемы сложности было сдерживающим фактором как теории, так и практики построения алгоритмов. Фундамент теории сложности задач выбора заложил американский математик С. Кук, который позволил по-новому взглянуть на некоторые аспекты проблемы.

Прежде всего, для упрощения ее анализа, он выделил один класс задач перебора, одновременно весьма актуальных для практики. Чтобы познакомиться с принципом его классификации, представим себе, не вдаваясь в детали конструкции, две вычислительные машины (ВМ). Первая - «однопроцессорная» с достаточно богатыми ресурсами; вторая - параллельного действия, состоящая из произвольно большого числа «однопроцессорных» ВМ. Задача относится к классу Р (РоНпо- гша1), если она разрешима за полиноминальное время на ВМ первого типа, и к классу № (Т^опбе1еггшш8бс роНпогта1), если ее решение за полиномиальное время возможно только на ВМ второго типа (последнюю называют также недерминированной машиной).

Приведем несколько примеров. Если каждый из п маршрутов

коммивояжера, задаваемых матрицей п х п, будет одновременно про-

2

считан на ВМ второго типа, то потребуется не более п шагов каждому «процессору». Следовательно, общее время решения полиномиально, и задача относится к №-классу. Приведенный критерий может быть заменен эквивалентным: если для проверки правильности любого варианта решения переборной задачи требуется полиномиальное время, то мы имеем дело с №-задачей.

Возьмем задачу о раскраске «-вершинного графа в к цветов. Она выполнена правильно, если смежные вершины имеют разные цвета. Всего способов раскраски, очевидно, будет кп. Требуется узнать, является ли предложенный вариант правильным. Для этого необходимо просмотреть все ребра графа: если вершины каждого из них имеют разный цвет - раскраска правильна; в противном случае - ответ будет отрицательным. Так как каждый граф задается матрицей смежности п х п, а число его ребер не превосходят «2, то алгоритм проверки будет полиномиальный.

Последний пример: проверка правильности решения булева уравнения /(х12,...х„) = 0, записанного, например, в нормальной конъ-

2

юнкгивной форме (НКФ). Для этого потребуется не более п дизъюнк- ций и п конъюнкций, т. е. /(«) ~ п +п.

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

Одним из важных понятий, также введенных в теорию С. Куком, является сводимость одной задачи выбора к другой. Более конкретно: считается, что переборная задача 1 сводится к переборной задаче 2, если метод решения задачи 2 за полиномиальное время можно преобразовать в метод решения задачи 1.

Замечательным результатом применения техники сводимости, которая оказалась довольно простой, явилось открытие полиномиальной сводимости любой задачи из класса № к задаче о разрешимости булева уравнения

где

В некотором смысле это «самая труднорешаемая» задача (что не противоречит, впрочем, и нашей интуиции). Однако вскоре было обнаружено, что это далеко не единственный случай: число таких задач оказалось огромным (более тысячи) и каждая из них может быть полиномиально сведена к другой. Они образуют (в силу свойства транзитивности) класс эквивалентности, в котором любая задача так же трудна, как и решение булева уравнения. Такие задачи называют ЫР-полными или универсальными (последний термин введен советским математиком Л.А. Левиным, который открыл эти задачи почти одновременно и независимо от С. Кука).

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

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

Рассмотрим один пример, демонстрирующий технику сводимости, а именно: задача решения булева уравнения полиномиально сводится к задаче о клике графа. Клика - это подмножество попарно соединенных вершин: 3-клика образует треугольник; 4-клика - четырехугольник с двумя проведенными в нем диагоналями и т. д.

Возьмем булеву функцию

и построим граф, вершинам которого присвоим обозначения переменных, входящих в / (рис. 1).

Рис. 1

Все пары переменных, не входящих в одну скобку, за исключением случая xj и х/ (/ = 1, 2, 3), соединим ребрами, как сделано на рис. 1. Видно, что имеется всего две 3-клики. Одна из них образована вершинами х1?х2,хз, другая - х1? Х2, хз. Им соответствует решение: XI = = х2 = хз = 1 и XI = 1; хг - 0; хз = 0. Рассмотрев табл. 6 всех значений

3

/= 2 (она легко получается непосредственно из формулы), видим, что наша задача решения булева уравнения сводится к задаче существования 3-клики. Время сводимости, очевидно, полиномиально.

Таблица 6

/

0

0

0

0

1

0

0

1

XI

0

0

0

0

1

1

1

1

*2

0

0

1

1

0

0

1

1

хз

0

1

0

1

0

1

0

1

В общем случае, если число булевых переменных п, оно будет пропорционально полиному

т. е. числу всех пар переменных в уравнении, которым можно сопоставить ребра графа (в соответствии с правилом в вышеприведенном примере).

В заключение этого пункта обратим внимание на то, что все утверждения относительно ИР-класса, приведенные выше, относятся к массовым (общим) задачам. Большинство индивидуальных задач могут решаться за полиномиальное время, в то время как соответствующие им массовые являются труднорешаемыми.

3.1.4. Выше уже упоминалось о тысячах дискретных задач оптимизации. Феномен такого количества не может быть объяснен результатом любительского творчества, хотя бы в силу их математической сложности. Он свидетельствует об исключительной прикладной ценности и актуальности данных задач. Вот только начало списка: оптимизация водоснабжения; оптимизация надежности резервированием; многокритериальное проектирование ирригационных сетей; размещение данных в памяти суперкомпьютера; оптимизация размещения автобусных остановок; составление расписаний (в том числе авиаперевозок); оптимизация химических процессов; проектирование сверхбольших интегральных схем и печатных плат и т. д.

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

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

Рассмотрим два популярных метода практического решения данной задачи. Первый, называемый имитацией отжига, предложен в 1983 г. [33]. Его идея состоит в выборе подходящей физической системы (аналога), динамику состояний которой можно было бы истолковать как процесс решения этой задачи. Например, изменение фазового состояния вещества, скажем, переход из жидкого состояния в кристаллическое, сопровождается тем, что одна из его главных характеристик- энергия - принимает абсолютное минимальное значение. При этом требуется, чтобы процесс охлаждения был медленным (технология отжига), иначе вместо кристаллической структуры получается аморфная масса, энергия которой больше минимально возможной.

Если все п потенциальных маршрутов коммивояжера рассматривать как «расплав», то просмотр их с использованием случайного выбора и сортировки по убыванию можно толковать как «охлаждение», результатом которого будет минимальный маршрут.

Рассмотрим более детально алгоритм имитации этого процесса, т. е. «медленного охлаждения». Обозначим города буквами А, В, С, Д Е, известные расстояния между ними как Я(А, В), /?(Д Е) и т. д.

Выберем наугад первый замкнутый маршрут: пусть это будет С, Е, М, К, Д С. Тогда его длина составит

Используя какой-либо случайный механизм (например, функцию генерации случайных чисел), сделаем в нашем маршруте перестановку двух городов, скажем Е и F: С, Д М, К, Е, ..., X, С. Получим новый маршрут с длиной пути

отличающийся от исходного на

Если он короче, т. е. АВ < 0, то принимается безоговорочно (с вероятностью единица) за исходный, и только с вероятностью

если А/? > 0. В новом маршруте, принятом за исходный, опять переставляются случайным образом два города и весь процесс повторяется; если он отклонен, то в качестве исходного берется предыдущий маршрут. Имитация отжига состоит в том, чтобы медленно (имеется в виду, конечно, относительная медленность) от маршрута к маршруту уменьшать значение параметра 0, выполняющего роль температуры.

В пределе, когда 0 будет очень мала (0 ~ 0), разность АЯ тоже стремится к нулю, что означает получение оптимального маршрута.

В рассмотренном алгоритме основную роль для уменьшения времени решения играет выбор режима снижения «температуры» 0.

Обратимся ко второму методу, т. е. новому методу дискретной оптимизации, основанному на имитации самоорганизации биологических муравьев. Начнем с аннотации к статье [15], в которой говорится: «Колония муравьев может рассматриваться как многоагентная система, в которой каждый агент функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов поведение всей системы получается на удивление разумным... Муравьиные алгоритмы с успехом применяются для решения таких сложных комбинаторных задач оптимизации, как: задача коммивояжера, задача маршрутизации транспорта, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых графиков, задача календарного планирования и др.».

Первая публикация на эту тему появилась в 1996 г., а уже в 2003 г. ее автор Марко Дориго был удостоен одной престижной международной премии в знак признания перспективности метода.

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

Рассмотрим эксперимент с муравьями, показывающий, как их кооперативное поведение обеспечивает нахождение кратчайшего маршрута к пище [15]. Приведенный на рис. 2 симметричный мост соединяет гнездо муравьев с пищей путями разной длины. В начале эксперимента обе ветви выбирались одинаково, а спустя некоторое время все муравьи двигались только по краткому пути АЕШ. Это легко понять, вспомнив, что вначале биологические секреты, выделяемые муравьями, на обоих путях отсутствовали. Поэтому их выбор был равновероятен. Однако коротким путем АЕШ муравьи быстрее возвращались с пищей в гнездо, количество меток на нем было гораздо больше. Наконец, спустя небольшое время действие положительной обратной связи приводит к тому, что короткий путь становится единственным.

Рис. 2

Рассмотрим более подробно реализацию этого подхода для решения задачи коммивояжера.

Поиск минимального маршрута происходит итеративно несколькими муравьями одновременно. Исходя из накопленного опыта применения метода, принято число муравьев назначать равным количеству городов, причем каждый из них начинает свой маршрут из «своего города». Каждый муравей рассматривается как отдельный независимый «коммивояжер», решающий свою задачу; за одну итерацию алгоритма он обходит полный маршрут коммивояжера.

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

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

Перейдем теперь к параметризации модели. Переход из города / в городу зависит от табу-списка, видимости и следа секрета.

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

Видимость - это величина, обратная расстоянию: , где

Ду - расстояние между городами / и у; цгу - локальная информация:

чем ближе город, тем целесообразнее включить его в маршрут обхода.

След виртуальных секретов на ребре (/у) - это мера целесообразности посетить город у из города /, подтвержденная опытом колонии. В отличие от видимости, являющейся константой для индивидуальной задачи, распределение секретов по ребрам меняется после каждой итерации, отражая приобретенный муравьями опыт.

Количество виртуальных секретов на ребре (у) в итерации / обозначим через Ту (/).

Вероятность перехода к-го муравья из города / в город у на итерации / принимается равной

где а>0и(3>0 - регулируемые параметры, задающие интенсивность следа секрета и видимость при выборе маршрута. При а = 0 выбирается ближайший город. Если (3 = 0, то работает лишь положительная обратная связь, приводящая к быстрому вырождению маршрутов к одному решению.

На основе опыта работы с этим методом рекомендуется выдерживать р>0.

Завершив маршрут, к-й муравей откладывает на ребре (/,/)

- количество секрета, где 7*(/)- маршрут муравья к на итерации /; Ьк (/) - длина маршрута 1к^) ()>0 - регулируемый параметр.

Для исследования всех маршрутов необходимо обеспечить испарение секрета. Это обеспечивается правилом, запись которого имеет вид

где т - количество муравьев в колонии. В начале решения задачи концентрация секрета принимается равной небольшому числу т0.

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

Этот класс алгоритмов дискретной оптимизации быстро совершенствуется и успешно конкурирует с алгоритмом имитации отжига и другими эвристическими методами [15].

2

Временная сложность его /(я) ~ п .

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>