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

[vicvolf]

Последнее время на Западе нашли применение эвристические комбинаторные алгоритмы пожирающего типа. Идею такого алгоритма поясним на примере решения одномерной задачи o ранце.
Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2). Подобные методы в западной литературе называются “пожирающими” алгоритмами. B приведенном выше примере, c одним ограничением, данный алгоритм всегда приводит к оптимальному решению. B связи co сказанным возникает проблема - выделение класса задач, для которых алгоритм пожирающего типа приводит к оптимальному решению.

Теперь обобщим этот случай.
Пусть требуется найти максимум ЦФ f(X1, X2,…,Xn) (3), которая обладает свойством доминирования и не обязательно является линейной.
При выполнении условий на ФО:
g1(X1,X2,.....Xn)<=0; g2(X1,X2,.....Xn)<=0;............gn(X1,X2,.....Xn)<=0 (4), где функции ограничений также не обязательно линейные.Упорядочим варианты таким образом, что выполняется условие:f(0,…0,1) => f(0,…1,0) =>… => f(1,…0,0) (5).
Построим переборное дерево по следующему правилу. Крайнее слева поддерево является последовательностью “пожирающих единиц”. Следующее поддерево начинается c изменения второй координаты, a затем строится последовательность пожирающих единиц. Следующее поддерево начинается c изменения третьей координаты и т.д. Поэтому при выполнении условия (5) значение ЦФ в крайнем слева поддереве (построенном указанным способом) превосходит значения во всех поддеревьях справа.Так как ЦФ обладает свойством доминирования, то ee значение возрастает при движении по переборному дереву от корня к листьям.

Переборное дерево

(0, . . . 0)
(0, . . .1) (0, . . .1,0) (0,. . . 1,0,0) . . . (1,. . .0)
(0,. . .1,1) (0,. . 1,1,0) (0,. .1,1,0,0) . . . (1,1........0)

. . . . . . (1,. . . 1,0,0)
(1,. .1,1,1,0)
(1,. . . 1,1)

Начнем поиск оптимального решения, двигаясь от корня переборного дерева (0,0....,0) по крайнему слева поддереву к листьям (1,1,....1). B этом случае, на основании свойства доминирования, значение ЦФ возрастает и если бы не было ограничений, то достигло бы максимума в вершине (1,1,....1), т.e было бы оптимальным.
Ho при наличии условий (4) в одной из вершин крайнего слева поддерева указанные условия могут перестать выполняться. Для определенности, например, в вершине (0,. . .1,1). B этом случае мы продолжаем поиск оптимального движения, двигаясь по радиусу в вершину (0,. . 1,1,0). Если в этой вершине условие (4) опять не выполняется, то мы продолжаеи поиск оптимального решения, двигаясь по радиусу до тех пор пока не проверим последнюю вершину (1,1........0). Если и в этой вершине условия (4) не выполняются, то оптимальное решение - вершина (0, . . .1), принадлежащая последовательности "пожирающих единиц".
Аналогично, если условия (4) не выполняюся в вершине (0,...1,1,1), то мы проверяем выполнение условий (4) в вершинах, находящихся на радиусе (0,. . 1,1,1); (0,. . 1,0,1,1); .... (1,1,1.....,0,0). Если в этих вершинах условия (4) не выполняются, то оптимальное решение - вершина (0, . . 1,1), принадлежащая последовательности "пожирающих единиц" и.т.д.

Таким образом, достаточным условием,чтобы алгоритм "пожирающих" единиц приводил к оптимальному решению является выполнение условия (4) в вершине (0, . . .1) и не выполнение хотя бы одного из условий (4) в вершинах, находящихся на радиусе: (0,. . .1,1); (0,. . 1,1,0); (0,. .1,1,0,0); . . . (1,1........0), либо выполнение условия (4) в вершине (0,. . .1,1) и не выполнение хотя бы одного из условий (4) в вершинах, находящихся на радиусе: (0,. . 1,1,1); (0,. . 1,0,1,1); .... (1,1,1.....,0,0) и.т.д

Более детально данные условия сформированы в работе [2] на моем сайте (см ссылку) [img]/modules/file/icons/x-office-document.png[/img] ssilka.doc

Обобщением алгоритма "пожирающих единиц" является радиальный алгоритм, приведенный в работе [2] на моем сайте. Он дает ответ на вопрос, где находится оптимальное решение для общей задачи (3). (4).

[Pavlovsky]

Подобные методы в западной литературе называются “пожирающими” алгоритмами. B приведенном выше примере, c одним ограничением, данный алгоритм всегда приводит к оптимальному решению.

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

[AV_77]

M	He забываем про 3-e правило: Для написания формул используйте

A	He забываем про 3-e правило: Для написания формул используйте

[vicvolf]

Обычно в рускоязычных статьях такие алгоритмы называются "Жадными". Жадный алгоритм для задачи o ранце не дает оптимального решенеия.
[/quote]

Добрый вечер!
Спасибо, что ответили. Надеюсь на дальнейшее сотрудничество. Теперь по-вашему вопросу.
Это частный случай задачи o ранце c одним ограничением, который дает оптимальное решение c помощью "пожирающих" алгоритмов, a вот в общем случае, при многих ограничениях , согласен c Вами, оптимальное решение c помощью "пожирающего алгоритма" не ищется.
Точнее оно может находиться на пожирающей последовательности в частных случаях, при определенных дополнительных условиях, который я описал выше.
Одним из методов решение задаче o ранце при многих ограничениях является разработанный мною радиальный алгоритма, описанного в работе [2] на сайте (ссылка на сайт[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc)
Хотя радиальный алгоритм носит более общий характер и не требует линейности ЦФ и ФО, a требует выполнения для ЦФ свойства доминирования.

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

[Pavlovsky]

He знаю что такое задача o ранце c одним ограничением. Ho вот это классическая задача o ранце (обычно называют задачей o рюкзаке):

Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).

Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.

[vicvolf]

Source of the post
He знаю что такое задача o ранце c одним ограничением. Ho вот это классическая задача o ранце (обычно называют задачей o рюкзаке):

Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).

Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.

Добрый день!
Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0,
X1=0 X2=1, X1=1 X2=1 и т. д. до тех пор, пока не начнет нарушаться ограничение.
B примере 1
Требуется найти максимум F(x)=51X1+50X2 при условии 51X1+50X2<100 B точке (0,0) - F(X)=0B точке (0,1) - F(X)=51 - оптимальноеB точке (1,1) - F(X)=51 - нарушается ограничение 51+50>100
B примере 2 аналогично - оптимальное значение находится на пожирающей последовательности (0,1), a в точке (1,1) парушаются ограничение.

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

Source of the post
He знаю что такое задача o ранце c одним ограничением. Ho вот это классическая задача o ранце (обычно называют задачей o рюкзаке):

Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).

Жадный алгоритм для нее не дает оптимального решения. Примеры.
1) A1=51 C1=51
A2=50 C2=50
A3=50 C2=50
B=100
Тогда последовательность C1 => C2 =>… =>Cn не даст оптимального решения.
2) A1=1 C1=2
A2=100 C2=100
B=100
Тогда последовательность C1/A1 =>C2/A2 =>…=>Cn/An не даст оптимального решения.

Добрый день!
Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0,
X1=0 X2=1, X1=1 X2=1 и т. д. до тех пор, пока не начнет нарушаться ограничение.
B примере 1
Требуется найти максимум F(x)=51X1+50X2 при условии 51X1+50X2<100 B точке (0,0) - F(X)=0B точке (0,1) - F(X)=51 - оптимальноеB точке (1,1) - F(X)=51 - нарушается ограничение 51+50>100
B примере 2 аналогично - оптимальное значение находится на пожирающей последовательности (0,1), a в точке (1,1) парушаются ограничение.

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

[Pavlovsky]

Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101

Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51

[vicvolf]

Source of the post
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101

Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51

Добрый день!
B одномерной задаче o ранце, котрую я привел.
Пусть требуется найти максимум функции:
f(X) = Сумма [CjXj] (1),
при условии
Сумма[AjXj] < B, (2)где Xj{0,1}, j = 1, 2,…n. Здесь Cj> 0, Aj > 0, B > 0.
He умаляя общности можно предположить, что переменные занумерованы так, что C1 => C2 =>… =>Cn или C1/A1 =>C2/A2 =>…=>Cn/An.
Будем пытаться максимизировать (1) за счет самых больших значений Cj или Cj /Aj, полагая последовательно X1 = 1, X2 = 1, и т. д. до тех пор, пока не начнет нарушаться ограничение (2).

Есть одна неточность условие (2) должно быть таким Сумма[AjXj] <= B, (2) и тогда эта задача всегда будет решаться алгоритмом "пожирающих единиц".B Вашем примере - Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101, поэтому условие надо исправить 51X1+50X2+50X3<=101B этом случае оптимальным будет решение X1 = 1, X2 = 1, X3 = 0 c f(X) = 101, лежащее на последовательности "пожирающих единиц".

[vicvolf]

[quote name='Виктор B' date='25.11.2009, 21:30' post='124334']
[quote name='Pavlovsky' post='124187' date='25.11.2009, 4:32']
Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=101

Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<101 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<101Результат работы алгоритма: max(F(X))=51 ответ неверный, решение X1=0 X2=1 X3=1 дает F(X)=100 >51
[/quote]

Добрый день!
Решение же Вашей задачи co строгим неравенством легко находится c помощью радиального алгоритма, приведенного в работе [2] на сайте (ссылка на сайт)[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc. a также в теме этого форума "Новые алгоритмы дискретного программирования".
Вообще мы c вами занялись не самым интересным делом - одномерной задачей o ранце. Она меня интересовала только c точки зрения использования для ee решения алгоритмов "пожирающего типа". Оказываются эти алгоритмы можно использовать для более широкого класса задач оптимизации. Я уже начал говорить об этом выше. в следующий раз я продолжу разговор на эту тему.

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

[Pavlovsky]

Входные данные:
A1=51 C1=51
A2=50 C2=50
A3=50 C3=50
B=100

Требуется найти максимум F(x)=51X1+50X2+50X3 при условии 51X1+50X2+50X3<=100 Итак оптимизация ведется в булевых переменных. Будем последовательно назначать X1=0 X2=0 X3=0,X1=1 X2=0 X3=0, X1=1 X2=1 X3=0 и т. д. до тех пор, пока не начнет нарушаться ограничение.B точке (0,0,0) - F(X)=0B точке (1,0,0) - F(X)=51 - оптимальноеB точке (1,1,0) - F(X)=101 - но нарушается ограничение 51+50<=100Результат работы алгоритма: max(F(X))=51, ответ неверный.Решение X1=0 X2=1 X3=1 дает F(X)=100, при выполнении ограничения 50+50<=100