Мультиэвристический подход к задачам дискретной оптимизации1



Скачать 475.48 Kb.
страница2/9
Дата17.01.2013
Размер475.48 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9

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).

1   2   3   4   5   6   7   8   9

Похожие:

Мультиэвристический подход к задачам дискретной оптимизации1 iconСитуационный подход к задачам поиска текстовой информации
Здесь тоже присутствуют идеи такого рода: будет использоваться некий набор экстралингвистических отношений, и эти экстралингвистические...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЭлементы дискретной математики
П. А. Корнилов, Н. И. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие. Ярославль: Изд-во ягпу им. К. Д....
Мультиэвристический подход к задачам дискретной оптимизации1 iconУрок по геометрии в 7-м классе на тему "Некоторые свойства прямоугольных треугольников"
Раздаточный материал: карточки с тестом, листы с чертежами к задачам самостоятельной работы, листы для ответов к задачам самостоятельной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛингвистические противоречия в терминологической системе дискретной математики
Именно таким путем язык может разрешить определяющее противоречие говорящего и слушающего, которое в терминологической системе дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconСборник упражнений для студентов математического факультета пединститута
В сборник включены упражнения по дискретной математике. Основная цель упражнений – отработка основных понятий дискретной математики,...
Мультиэвристический подход к задачам дискретной оптимизации1 icon"Построение конечно-разностных формул на границе дискретной области счёта"
При численном решении уравнений математической физики важным становится вопрос замены непрерывной области изменения аргумента дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconВ. П. Голубятников известный специалист в области геометрии, топологии и их приложений к задачам математического моделирования и к обратным задачам. Он опубликовал 160 научных работ, в том числе монографию Uniqueness q
«Uniqueness questions in reconstruction of multidimensional objects from tomography-type projection data», изданную в Голландии,...
Мультиэвристический подход к задачам дискретной оптимизации1 iconПрограмма курса Дополнительные главы дискретной математики для групп 318, 319 кафедры математической кибернетики
«Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛичностно-ориентированный подход к обучению иностранному языку
Личностный подход к обучающимся при организации учебно– воспитательного процесса
Мультиэвристический подход к задачам дискретной оптимизации1 iconМеждународный опыт в области инклюзивного образования: Норвегия
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org