Geum.ru

Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail ru) Аннотация Внастоящей статье рассматриваются эвристические методы принятия решений в различных задача

Вид материалаЗадача

Содержание


2. Незавершённый метод ветвей и границ
Подобный материал:
1   2   3   4   5   6   7

2. Незавершённый метод ветвей и границ


Метод ветвей и границ будем описывать для произвольной ЗДО, однако, где это необходимо, будем приводить примеры МВГ для самой известной из рассматриваемой нами задач – ЗКВ. При этом будем употреблять следующие названия:
  • «случайная ЗКВ» – когда все элементы матрицы ЗКВ генерируются как случайная величина с заданным законом равномерного распределения;
  • «метрическая ЗКВ» – когда случайно генерируются координаты всех городов как точек единичного квадрата (с равномерным распределением обеих координат), а элементы матрицы ЗКВ суть расстояния между соответствующими точками. При этом очевидно выполнение следующего дополнительного условия, условия симметричности матрицы относительно главной диагонали: aij=aji для всех возможных i и j.9
  • «псевдо-метрическая ЗКВ»10 – когда все элементы матрицы метрической ЗКВ после генерации дополнительно умножаются на некоторое случайное число, формируемое по заданному нормальному закону распределения с μ=1.

В последние годы наиболее часто встречаются публикации, посвящённые метрической ЗКВ. Это объясняется, в первую очередь, тем обстоятельством, что один шаг алгоритма МВГ «в среднем» упрощает матрицу случайной ЗКВ значительно больше, чем матрицу метрической ЗКВ. По мнению автора, псевдо-метрическая ЗКВ, в литературе практически не рассматривавшаяся, значительно более интересна:
  • во-первых, она стоит ближе всего к различным практическим задачам;
  • во-вторых, именно здесь могут быть проверены различные эвристики, не связанные с использованием расположения городов на плоскости;
  • и, в-третьих, один шаг МВГ здесь также «в среднем не очень сильно» упрощает рассматриваемую матрицу ЗКВ.11

Как было отмечено выше, классическая публикация по применению МВГ в ЗКВ – [4]; будем ниже слово «граница» употреблять согласно этой публикации. Однако в [4] рассматривался только алгоритм, который заканчивается нахождением оптимального решения. А выше уже было отмечено, что в худшем случае МВГ работает не более эффективно, чем простейшие переборные алгоритмы.12

На практике же точное решение ЗКВ путём применения только алгоритмов, описанных в [4], удаётся получить крайне редко.13 Немного улучшает ситуацию применение различных программистских «хитростей» (например – специальных структур данных для быстрейшего выполнения очередного шага МВГ). Фактически каждая из этих программистских «хитростей» сама является новой эвристикой – дополнительно к тем, которые описаны в [4].14 Однако всё вышесказанное относится только к точному решению ЗКВ (и других ЗДО) и пока практически не имеет отношения к рассматриваемым нами anytime-алгоритмам. Для перехода к описанию таких алгоритмов введём сначала следующие определения.

Будем далее называть правой задачей очередного шага МВГ задачу, полученную при уменьшении размерности. Например, в ЗКВ таковой является та подзадача, в которой мы обязательно включаем в выбираемый маршрут дугу между двумя рассматриваемыми городами, а в задаче вершинной минимизации НКА – подзадача, когда мы обязательно включаем рассматриваемый блок в выбираемое множество блоков. Другую альтернативу – т.е. когда принимается временное решение об отсутствии некоторого элемента в оптимальном решении (например, когда в ЗКВ мы обязательно не включаем в выбираемый маршрут дугу между двумя выбранными городами) – назовём, соответственно, левой задачей очередного шага МВГ. Смысл всех модификаций МВГ (для любой ЗДО) состоит в том, что с помощью некоторых эвристик мы добиваемся того, чтобы вероятность наличия оптимального решения была больше для правой задачи, чем для левой – ведь размерность правой задачи на 1 меньше, чем левой.

Несложная эвристика, преобразующая завершённый МВГ в незавершённый (а именно на основе незавершённого МВГ и формируются все anytime-алгоритмы данной статьи), заключается в следующем. Каждый раз при получении очередной правой задачи (назовём её задачей T) мы фактически строим последовательность правых задач (ППЗ) – т.е. саму задачу T, правую задачу задачи T, правую задачу правой задачи задачи T, и так далее. Естественно, каждый раз строятся (и включаются в список задач для потенциального решения в последующем) и соответствующие левые задачи – левая задача задачи T, левая задача правой задачи задачи T, и так далее. Описанный процесс заканчивается:
  • либо при получении тривиальной задачи (задачи нулевой размерности) – в этом случае мы запоминаем её решение (границу, получаемый к моменту её постановки тур, и т.п. характеристики) в качестве текущего на данный момент времени псевдо-оптимального решения нашего anytime-алгоритма;
  • либо при получении в какой-либо задаче достаточно большой границы – например, большей, чем имеющееся на данный момент времени псевдо-оптимальное решение.15

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

Итак, мы описали простой процесс построения anytime-алгоритма на основе некоторого конкретного варианта МВГ. Вряд ли такое преобразование описано здесь впервые (оно действительно очень несложно), однако конкретных ссылок у автора настоящей статьи нет. Важно отметить, что данный процесс возможен именно потому, что любая правая задача имеет размерность меньше, чем соответствующая ей левая. Отметим также, что данный алгоритм – построение ППЗ – используется в качестве под-алгоритма не только для незавершённого МВГ (как в данном разделе), но и для т.н. алгоритма турнирного самообучения (см. ниже, в разделе 5).