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

[vicvolf]

Source of the post
Bce-таки запутался c нумерацией. Поэтому придется задать вопрос заново.


1. Проверяем ограничение в вершине (00001). Ограничение выполняется. Вычисляем ЦФ, сравниваем, запоминаем.
2. Проверяем ограничение в вершине (00011). Ограничение не выполняется.
3. Переходим по радиусу. Проверяем ограничение в вершине (00101). Ограничения не выполняются.
4. Проверяем ограничение в вершине (00110). Ограничения не выполняются.
5. Проверяем ограничение в вершине (01001). Ограничения не выполняются.
6. Проверяем ограничение в вершине (01010). Ограничения выполняются. Вычисляем ЦФ, сравниваем, запоминаем.

Что дальше делает алгоритм?

Добрый вечер!
Продолжаю
7.Переходим к следующей вершине (01100). Вершина не спаренная. Переходим на следующую строку.

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

[Pavlovsky]

7.Переходим к следующей вершине (01100). Вершина не спаренная. Переходим на следующую строку.

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

[vicvolf]

Source of the post
Понятно. Пусть в строках из трех единиц и более ограничения не выполняются для всех вершин. Какой ответ тогда даст алгоритм?

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

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

[vicvolf]

Добрый вечер!
Я понимаю к чему вы ведете-после вершины (01010) надо проверить спаренную вершину (10001), в которой может достигаться максимум! Радиальный алгоритм работает верно! Неверно указаны спаренные вершины!

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

[vicvolf]

Source of the post
Последовательность для n=5, k=2

ВикторВ
00011, 00101, 00110, 01001, 01010, 01100, 10001, 10010, 10100, 11000

Как должно быть. B скобках указаны спаренные вершины
00011, 00101, (00110, 01001), (01010, 10001), (01100, 10010), 10100, 11000

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

Вот решетка доминирования для n=9, k=3

Добрый вечер!
Согласен c автором сообщения-алгоритм по упорядочиванию вершин нуждается в корректировке. Кстати - в решетке доминирования надо стрелки развернуть вниз! Путаница c нумерацией координат.

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

[vicvolf]

Добрый вечер!
Сегодня я размещаю на форуме материал по эффективности алгоритма пожирающего типа.[img]/modules/file/icons/x-office-document.png[/img] ___________________________________.doc. Материалы по пожирающему алгоритму приведены в более ранних сообщениях данной темы.
Эффективность данного алгоритма значительно выше общего алгоритма и дихотомического алгоритмов доминирующих векторов.
Эффективность пожирающего алгоритма сравнима только c эффективностью радиального алгоритма, который также рассмотрен в данной теме. Однако радиальный алгоритм может быть использован значительно шире для тех случаев, когда оптимальное решение находится за пределами «пожирающей» последовательности.

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

[vicvolf]

Добрый вечер!
Размещаю на форуме сравнительную эффективность общего и "пожирающего" алгоритмов доминирующих векторов для бинарного случая.[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________.doc
Данные алгоритмы рассмотрены выше в сообщениях данной темы.

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

[ron_oster]

Добрый Вечер!

Спасибо за материал.

Буду изучать.

[vicvolf]

Source of the post
Добрый Вечер!

Спасибо за материал.

Буду изучать.

Добрый вечер!
Сегодня я размещаю в данной теме материал по сравнительной эффективности всех алгоритмов доминирующих векторов (бинарный случай).[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________.doc
Материалы по самим алгоритмам доминирующих векторов приведены выше в данной теме.

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

[vicvolf]

Добрый вечер!
Сегодня я размещаю в теме "Достаточное условие нахождения оптимального решения на пожирающей последовательности".
Пусть ЦФ бинарных переменных P(XN,………X1) является аддитивной (линейной) функцией, a для ФО - GI(XN,………X1), где I =1, ….N, выполняется условие доминирования. Пусть переменные X1, …., XN упорядочены таким образом, что выполняется условие P(0,……,1)=> P(0,……1,0)=>…….=> P(1,……,0) (1).
Тогда, если в вершине (0,…1,..,1) пожирающей последовательности, координаты которой имеют I-1 единиц, все условия на ФО выполняются, a ни в одной вершине I строки, состоящей из вершин, координаты которых содержат I единиц, условия на ФО не выполняются, то оптимальной является вершина (0,…1,..,1) пожирающей последовательности, координаты которой имеют I-1 единиц. Если в вершине (1,…,1) все условия на ФО выполняются, то эта вершина пожирающей последовательности является оптимальной.
Данное условие является следствием теоремы o сходимости радиального алгоритма.[img]/modules/file/icons/x-office-document.png[/img] ___________________________________________________.doc
Пример приведен в ссылке.[img]/modules/file/icons/x-office-document.png[/img] ____________________________________________________________________________________.doc
C уважением Виктор B.