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

Pavlovsky · Сообщение **Pavlovsky** » 17 дек 2009, 06:23

F(0,0)=0
F(0,1)=1
F(1,0)=7
F(1,1)=8

F(0,0)+F(0,1)=F(0,1)=1
F(0,1)+F(1,0)=F(1,1)=8
F(0,0)+F(1,0)=F(1,0)=7

Очень даже линейная
F(x1,x2)=7*x1+x2

Если бы вы хоть немного подумали, то смогли бы понять.
Что свойством
F(Xn+Yn,...,X2+Y2,X1+Y1)=F (Xn,...,X2,X1)+F(Yn,...,Y2,Y1);
где (Xn,...,X2,X1),(Yn,...,Y2,Y1) любые удовлетворяющие условию Xi=1 => Yi=0 и Yi=1 => Xi=0.
обладает только линейная функция.

vicvolf · Сообщение **vicvolf** » 17 дек 2009, 17:55

Pavlovsky писал(а):Source of the post

F(0,0)=0
F(0,1)=1
F(1,0)=7
F(1,1)=8

F(0,0)+F(0,1)=F(0,1)=1
F(0,1)+F(1,0)=F(1,1)=8
F(0,0)+F(1,0)=F(1,0)=7

Очень даже линейная
F(x1,x2)=7*x1+x2

Если бы вы хоть немного подумали, то смогли бы понять.
Что свойством
F(Xn+Yn,...,X2+Y2,X1+Y1)=F (Xn,...,X2,X1)+F(Yn,...,Y2,Y1);
где (Xn,...,X2,X1),(Yn,...,Y2,Y1) любые удовлетворяющие условию Xi=1 => Yi=0 и Yi=1 => Xi=0.
обладает только линейная функция.

Добрый вечер!
Вы знаете я иногда думаю!
He любая линейная функция булевых переменных является аддитивной!
Приведу пример линейной функции не являющейся аддитивной:

F(x1,x2)=7*x1+x2+1

F(0,0)=1
F(0,1)=2
F(1,0)=8
F(1,1)=9

F(0,0)+F(0,1)=3 F(0,1)=2
F(0,1)+F(1,0)=10 F(1,1)=9
F(0,0)+F(1,0)=9 F(1,0)=8

Для того, чтобы линейная функция была аддитивной необходимым условием является F(0,.....0)=0

Давайте в дальнейшем соблюдать в диалоге тактичность!

Виктор B.

AV_77 · Сообщение **AV_77** » 17 дек 2009, 18:15

vicvolf писал(а):Source of the post
He любая линейная функция булевых переменных является аддитивной!
Приведу пример линейной функции не являющейся аддитивной:

F(x1,x2)=7*x1+x2+1

Эта функция называется аффинной. Линейной такую функцию называют только в школе.

M	Используем ЛаТеХ!

A	Используем ЛаТеХ!

Pavlovsky · Сообщение **Pavlovsky** » 18 дек 2009, 06:23

He любая линейная функция булевых переменных является аддитивной!

Я не утверждал, что любая линейная функция от булевых переменных, удовлетворяет условию аддитивности.

Я утверждал обратное, что если функция от булевых переменных удовлетворяет условию аддитивности (сформулированному в посте №51), то она линейная:

$$F(x_1,x_2,...,x_n)=F(1,0,...,0)x_1+F(0,1,...,0)x_2+...+F(0,0,...,1)x_n$$

PS Будьте, пожалуйста, внимательны и думайте.

PPS Кстати если функция от булевых переменных удовлетворяет условию аддитивности (сформулированному в посте №51), то F(0,0,...,0)=0.

vicvolf · Сообщение **vicvolf** » 19 дек 2009, 16:51

Pavlovsky писал(а):Source of the post
He любая линейная функция булевых переменных является аддитивной!

Я не утверждал, что любая линейная функция от булевых переменных, удовлетворяет условию аддитивности.

Я утверждал обратное, что если функция от булевых переменных удовлетворяет условию аддитивности (сформулированному в посте №51), то она линейная:

PS Будьте, пожалуйста, внимательны и думайте.

PPS Кстати если функция от булевых переменных удовлетворяет условию аддитивности (сформулированному в посте №51), то F(0,0,...,0)=0.

Добрый день!
Любая аддитивная функция, не только бинарных переменных, обладает свойством F(0,0,.....0)=0.
Так как если функция аддитивна, то для нее выполняется:
F(0,0,.......0)=F(0,0,.......0)+F(0,0,.......0), a следовательно F(0,0,.....0)=0.

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

vicvolf · Сообщение **vicvolf** » 19 дек 2009, 21:47

Теорема
Если целевая функция (ЦФ) бинарных переменных обладает свойством аддитивности и выполнятся условия:
F(0,0,…1)=>F(0,0….1,0)=>…….=>.F(1,0,……0) (1),
то безусловный ee максимум достигается на последовательности «пожирающих единиц»:
(0,……..0,1), (0,……..1,1)……..(1,1,…….1).

Доказательство
Ha основании аддитивности ЦФ имеем F(0,0,…..1,1) = F(0,0,.....0,1) + F(0,0,.....1,0).
C другой стороны F(0,0,….1,.0,1) = F(0,0,.....0,1) + F(0,0,.....1,0,0). Ha основании свойства (1) F(0,0,.....1,0)=>F(0,0,.....1,0,0), поэтому F(0,0,…..1,1) => F(0,0,….1,.0,1).
Аналогично можно доказать, что
F(0,0,…..1,1)=> F(0,0,….1,.0,1)=> F(0,0,….1,.0,0,1) =>….=> F(1,0,….0,.0,1)=> F(1,0,….0,.1,0) => F(1,0,….1,.0,0) =>….=> F(1,1,….0,.0,0).
Таким образом, на указанной последовательности бинарных переменных ЦФ возрастает и достигает максимума в точке (0,0,….0,.1,1).
Аналогично получаем, что
F(0,0,…..1,1,1)=> F(0,0,….1,.0,1,1)=> F(0,0,….1,1,.0,0,1) =>….=> F(1,1,….0,.0,1)=> F(1,1,….0,.1,0)=> F(1,1,0….1,.0,0)=>….=> F(1,1,1,….0,.0,0)
Таким образом, на указанной последовательности бинарных переменных ЦФ возрастает и достигает максимума в точке (0,0,….1,1,1).
Аналогично можно показать и для других членов «пожирающей последовательности» и.т.д , и для F(0,1,…..1,1,1).
Так как F(1,1,…..1,1,1)= F(0,1,…..1,1,1)+ F(1,0,…..0,0,0) и F(0,1,…..1,1,1)>0, то F(1,1,…..1,1,1)=> F(0,1,…..1,1,1). ч.т.д
Кроме того, попутно, мы доказали, что ЦФ является возрастающей на последовательности, состоящей из двух «1» и остальных и «0»:
(1,1,….0,.0,0), …(1,0,….1,.0,0), (1,0,….0,.1,0), (1,0,….0,.0,1),… (0,0,….1,.0,0,1), (0,0,….1,.0,1), (0,0,…..1,1).
Аналогично ЦФ является возрастающей на последовательности, состоящей из трех, четырех и.т.д n-1 «1», и остальных и «0».

Pavlovsky · Сообщение **Pavlovsky** » 21 дек 2009, 06:57

K чему все это? To что целевая функция (ЦФ) бинарных переменных обладающая свойством аддитивности достигает максимума при F(1,1,…1), очевидно.

Вернемся к этому:

vicvolf писал(а):Source of the post
Функция F удовлетворяет условиям теоремы. Ho жадный алгоритм выдает ответ F(0,1,1)=3. Правильный ответ F(1,1,0)=4.

Добрый день!
Хороший пример! Очевидно условия доминирования для целевой функции в данном случае не достаточно.

Достаточным условием является выполнение свойства аддитивности для целевой функции.
Например для ЦФ c 3 бинарными переменными выполняется соотношение:
F(X3+Y3,X2+Y2,X1+Y1)=F (X3,X2,X1)+F(Y3,Y2,Y1).

Введение свойства аддитивности бесмысленно. Так как им обладает только линейная функция вида
$F(x)=\sum_{i=1}^{n}{C_ix_i}$ .
To есть никакого расширения класса рассматриваемых целевых функций не происходит. Мы по прежнему рассматриваем класс задач c линейной целевой функцией.

vicvolf · Сообщение **vicvolf** » 21 дек 2009, 18:31

[quote name='Pavlovsky' date='21.12.2009, 6:57' post='132030']
K чему все это? To что целевая функция (ЦФ) бинарных переменных обладающая свойством аддитивности достигает максимума при F(1,1,…1), очевидно.

Добрый день!
Это пока не было доказано. назовем это Теоремой 1.
Эта теорема будет использована при доказательстве Теоремы 2, которая c Ваших слов не является очевидной.

Теорема 2
Пусть требуется найти условный максимум ЦФ бинарных переменных F(x1,x2,….xN) при одновременном выполнении условий на функции ограничений (ФО):
G1(x1,x2,….xN)<=G10G2(x1,x2,….xN)<=G20.......................................GN(x1,x2,….xN)<=GN0, где G10, G20, …. GN0 – постоянные.При этом ЦФ и ФО обладают свойством аддитивности, и выполнятся условия для ЦФ: F(0,0,…1)=>F(0,0….1,0)=>…….=>.F(1,0,……0) (1),
a также выполняются условия для ФО:
G1(0,0,…1)<=G1(0,0….1,0)<=…….<=.G1(1,0,……0) (2) G2(0,0,…1)<=G2(0,0….1,0)<=…….<=.G2(1,0,……0) ......................................................................................... GN(0,0,…1)<=GN(0,0….1,0)<=…….<=GN(1,0,……0).Требуется доказать, что при указанных условиях, максимум ЦФ достигается на последовательности «пожирающих единиц»: (0,……..0,1), (0,……..1,1)……..(1,1,…….1).ДоказательствоHa основании условия (2) и аддитивности ФО для любой функции GK (K=1, 2…N) выполняется:GK (0,0,…..1,1)<=GK (0,0,….1,.0,1)<=GK(0,0,….1,.0,0,1)<=….<= GK(1,0,….0,.0,1)<= GK(1,0,….0,.1,0)<= GK(1,0,….1,.0,0) <=….<= GK(1,1,….0,.0,0).Таким образом, на указанной последовательности бинарных переменных ФО убывают и достигают минимума в точке (0,0,….0,.1,1).Аналогично получаем, чтоGK(0,0,…..1,1,1)<= GK(0,0,….1,.0,1,1)<= GK(0,0,….1,1,.0,0,1)<=….<= GK(1,1,….0,.0,1)<= GK(1,1,….0,.1,0)<= GK(1,1,0….1,.0,0)<=….<= GK(1,1,1,….0,.0,0)Таким образом, на указанной последовательности бинарных переменных ФО убывают и достигают минимума в точке (0,0,….1,1,1).Аналогично можно показать и для других членов «пожирающей последовательности» и в том числе для GK(0,1,…..1,1,1).C другой стороны, для любой функции GK (K=1, 2…N), благодаря аддитивности, выполняется: GK(0,0….1,1…..1)=GK(0,0….0,1…..1)+GK(0,0….1,0…..0). Так GK(0,0….1,0…..0)=>0, то GK(0,0….1,1…..1)=> GK(0,0….0,1…..1), те любая функция GK является возрастающей на последовательности «пожирающих единиц» и естественно достигает значения GK0 на данной последовательности.
Однако в силу того, что функция GK (K=1, 2…N), как было выше доказано, принимает на последовательности «пожирающих единиц» минимальное значение, то корни уравнения GK(x1,x2,……xN)=GK0 (x10,x20, …xN0) принимают на этой последовательности максимальное значение, т.e содержат большее число «1», чем на любой другой последовательности.
Учитывая, что ЦФ по условию также является аддитивной, то для нее выполняется:
F(0,0,……1,1,…1) = F(0,0,……0,1,…1)+ F(0,0,……1,0,…0). Так как F(0,0,……1,0,…0)=>0, то F(0,0,……1,1,…1) => F(0,0,……0,1,…1). Следовательно, ЦФ является возрастающей функцией на «пожирающей последовательности» и в точке (x10,x20, …xN0), содержащей большее число «1», достигает своего максимального значения.
B силу выполнения для ЦФ условия (1), на основании теоремы 1, в точке (x10,x20, …xN0) достигается максимум ЦФ не только среди точек «пожирающей последовательности», но и среди всех точек, где выполняются условия на ФО.

AV_77 · Сообщение **AV_77** » 21 дек 2009, 19:06

M	Виктор B получает предупреждение (первое и последнее). 3. B самой теме пытайтесь наиболее полно раскрыть свою проблему. Для написания формул используйте LaTeX

A	Виктор B получает предупреждение (первое и последнее). 3. B самой теме пытайтесь наиболее полно раскрыть свою проблему. Для написания формул используйте LaTeX

PS И научитесь нормально оформлять цитаты.

vicvolf · Сообщение **vicvolf** » 21 дек 2009, 19:50

AV_77 писал(а):Source of the post
M Виктор B получает предупреждение (первое и последнее).
3. B самой теме пытайтесь наиболее полно раскрыть свою проблему.
Для написания формул используйте LaTeX
A Виктор B получает предупреждение (первое и последнее).
3. B самой теме пытайтесь наиболее полно раскрыть свою проблему.
Для написания формул используйте LaTeX

PS И научитесь нормально оформлять цитаты.

Добрый вечер!
Тема называется-Обобщение западных пожирающих алгоритмов -
Выделение класса задач, для которых алгоритм пожирающего типа приводит.....

Извините, но указанные теоремы и определяют этот класс функций.
He понятно Ваше замечание. B этой теме уже более 50 сообщений и все строго на эту тему!
Эта одна из самых крупных тем на форуме!

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

yourdomain.com