Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail ru) Аннотация Внастоящей статье рассматриваются эвристические методы принятия решений в различных задача
Вид материала | Задача |
Содержание2. Незавершённый метод ветвей и границ |
- Программа профилирующей дисциплины "теория игр и исследование операций" Содержание, 69.55kb.
- Аннотация рабочей программы дисциплины методы принятия управленческих решений По направлению, 115.63kb.
- Аннотация программы дисциплины «Методы принятия управленческих решений» Цели и задачи, 22.87kb.
- Анализ принятия управленческих решений, 54.28kb.
- Программа «Методы принятия решений». Гу-вшэ, 2010 г. Министерство экономического развития, 750.51kb.
- Аннотация рабочей программы дисциплины методы принятия управленческих решений для направления, 31.71kb.
- Автор повинен правильно оформити літературу. Удк 338., 87.87kb.
- Исследование по вопросу о коренных народах и праве на участие в процессе принятия решений, 537.75kb.
- Аннотация рабочей программы учебной дисциплины методология и методы исследований, 173.52kb.
- Электронное научное издание «Труды мгта: электронный журнал», 106.8kb.
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).