Обобщение западных пожирающих алгоритмов

[mihailm]

У меня такой вот вопрос к Вам, Виктор B,
a когда будет обобщение восточных пожирающих алгоритмов? :):)

[vicvolf]

Source of the post
У меня такой вот вопрос к Вам, Виктор B,
a когда будет обобщение восточных пожирающих алгоритмов? :):)

Тогда, когда Вы их придумаете! Что не спиться?

[vicvolf]

Source of the post
Добрый вечер!
A теперь поговорим более подробно об анализе эффективности алгоритмов доминирующих векторов. Сначала проанализируем случай, когда целевая функция (ЦФ) бинарных переменных известна! Наиболее эффективным алгоритмом доминирующих векторов для бинарных переменных, c точки зрения количества вычислений, является радиальный алгоритм. Однако для его использования по сравнеию c общим алгоритмом и алгоритмом доминирующих векторов необходимо упорядочить переменные. Кроме того его можно использовать только, если ЦФ линейна.
Ранее я публиковал расчет количества вычислений ЦФ в радиальном алгоритме без учета спаренных вершин. Тогда получилось, что количество вычислений ЦФ независимо от числа переменных не превыщает 2. Сейчас делаю расчет количества вычислений ЦФ c учетом спаренных вершин и скоро представлю результаты!

C уважением Виктор B.

Добрый день!
Расчет количества вычислений ЦФ c учетом спаренных вершин представляет проблему. Дело в том, что даже для 6 переменных для оценки математического ожидания количества вычислений ЦФ надо рассмотреть 13 случаев, так как количество вычислений в данном случае колеблется от 1 до 13. Для того, чтобы понять почему это так - напомню сущность радиального алгоритма.
Сначала определяется выполнение условий ограничений на пожирающей последовательности в следующем порядке вершин (0,...0), (0.....1), (0,...1,1),....(1,...,1).
Как только условия ограничений перестают выполняться в одной из вершин пожирающей последовательности, то мы вычисляем ЦФ в последней вершине, где условия выполнялись и начинаем проверку выполнения условий в вершинах ряда, c количеством единиц в координате, равным количеству вершин в последней вершине пожирающей последовательности, где условия выполнялись и запоминаем его. Если ни в одной вершине ряда условия не выволняются, то алгоритм заканчивается и соответственно количество вычислений ЦФ в данном случае равно 1. Видите, сколько зависимых событий должно быть для этого выполнено!
Если в одной из вершин ряда условия ограничений выполняются, то ЦФ вычисляется 2-ой раз, сравнивается c ранее запомненным, и запоминается, если требуется и переходим на следующий ряд. Если там тоже условия ограничений будут выполняться, то вычислим ЦФ 3-ий раз, сравниваем и запоминаем, если требуется и.т.д. Для 6 переменных у нас 5 рядов и максимальное количество вычислений не превосходило бы 6, но без учета спаренных вершин. Однако, начиная c 2 по 4 ряд возможны спаренные вершины.
При 6 переменных максимальное количество спаренных вершин в ряду равно 3 (см. материал по спаренным вершинам выше в данной теме). Учитывая необходимость вычислений ЦФ в каждой спаренной вершине, мы получаем как раз максимальное число вычислений ЦФ:1+1+3+3+3+3+1=13, учитывая, что в 1 и 5 ряду спаренных вершин быть не может!

C уважением Виктор B.

[vicvolf]

Добрый вечер!
Закончил расчет количества вычислений целевой функции (ЦФ) для радиального алгоритма при известной ЦФ c учетом спаренных вершин. Как я и предполагал, математическое ожидание количества вычислений не превосходит 2. Расчет приводится ниже. [img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc.

Готов ответить на вопросы.

C уважением Виктор B.