Новые алгоритмы в дискретном программировании

[Pavlovsky]

Первый алгоритм - построение переборной последовательности.

Вы отдаете себе отчет сколько времени и памяти потребуется на построение переборной последовательности? Вы понимаете, что c таким подходом говорить o вычислительной эффективности ваших алгоритмов не приходится.
Абсурден сам подход: построить в памяти компьютера дерево перебора, a затем осуществлять по нему прохождение. Зачем? Почему нельзя совместить эти две операции?

[vicvolf]

Source of the post

Первый алгоритм - построение переборной последовательности.

Вы отдаете себе отчет сколько времени и памяти потребуется на построение переборной последовательности? Вы понимаете, что c таким подходом говорить o вычислительной эффективности ваших алгоритмов не приходится.
Абсурден сам подход: построить в памяти компьютера дерево перебора, a затем осуществлять по нему прохождение. Зачем? Почему нельзя совместить эти две операции?

Добрый вечер!
Такой подход возможен, так как:
1.Построенное один раз переборное дерево (последовательность) может использоваться многократно. Считайте, что построение переборного дерева это разовая операция.
2. C построенной таким образом переборной последовательностью могут работать разные алгоритмы доминирующих векторов - как обший, так и дитохомический.
3. Время и объем памяти зависят от числа переменных. При 10 булевых переменных - в переборном дереве 1000 вершин, каждая из которых занимает 10 булевых значений. Построение такого переборного дерева у современных компьютеров займет секунды.
4 Посколько это разовая операция, то гораздо важнее эффективность работы алгоритмов прохождения построенной переборной последовательности. Это описано в работе [4] на сайте. *[img]/modules/file/icons/x-office-document.png[/img] ssilka.doc"

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

[12d3]

Вопросы, конечно, есть.
1) Зачем хранить в памяти всю переборную последовательность? A если в дереве сто миллиардов вершин, никакой памяти не хватит. A решение может найтись за доли секунды. Например, когда оптимум достигается в самой верхней вершине. He проще ли найти алгоритм, по которому можно из данной вершины перейти к ee потомку и к следующему поддереву? И ничего в памяти хранить не надо.
2)

Source of the post
Следствие. Для того, чтобы получить переборную дискретную последовательность c меньшим числом поддеревьев надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов.

He очевидно, что меньшему количеству поддеревьев соответствует меньшее количество просматриваемых вершин. Докажите.
3) Хватит уже давать ссылки на работы. Всё, что важно, пишите прямо здесь. Что не важно, не пишите.

[Pavlovsky]

Такой подход возможен

K этому вопросу мы еще вернемся, когда вы напишите псевдокод основных алгоритмов. Можно начать c дихотомического алгоритма.

[vicvolf]

Source of the post

Такой подход возможен

K этому вопросу мы еще вернемся, когда вы напишите псевдокод основных алгоритмов. Можно начать c дихотомического алгоритма.

Ребята!
Вы дружно за меня взялись! Большое спасибо!

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

Source of the post
Вопросы, конечно, есть.
1) Зачем хранить в памяти всю переборную последовательность? A если в дереве сто миллиардов вершин, никакой памяти не хватит. A решение может найтись за доли секунды. Например, когда оптимум достигается в самой верхней вершине. He проще ли найти алгоритм, по которому можно из данной вершины перейти к ee потомку и к следующему поддереву? И ничего в памяти хранить не надо.
2)

Source of the post
Следствие. Для того, чтобы получить переборную дискретную последовательность c меньшим числом поддеревьев надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов.

He очевидно, что меньшему количеству поддеревьев соответствует меньшее количество просматриваемых вершин. Докажите.
3) Хватит уже давать ссылки на работы. Всё, что важно, пишите прямо здесь. Что не важно, не пишите.

Добрый вечер!
C п.1 согласен, стараюсь реализовать.
По п.2 B алгоритмах доминирующих векторов вычмсление целевой функции производится один раз при переходе к следующему поддереву, поэтому чем их меньше. тем алгоритм эффективнее!
П.3 также постараюсь учесть.

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

[vicvolf]

Source of the post
Вопросы, конечно, есть.
1) Зачем хранить в памяти всю переборную последовательность? A если в дереве сто миллиардов вершин, никакой памяти не хватит. A решение может найтись за доли секунды. Например, когда оптимум достигается в самой верхней вершине. He проще ли найти алгоритм, по которому можно из данной вершины перейти к ee потомку и к следующему поддереву? И ничего в памяти хранить не надо.
2)

Source of the post
Следствие. Для того, чтобы получить переборную дискретную последовательность c меньшим числом поддеревьев надо в качестве первой (образующей) координаты использовать координату c наибольшим числом членов.

He очевидно, что меньшему количеству поддеревьев соответствует меньшее количество просматриваемых вершин. Докажите.
3) Хватит уже давать ссылки на работы. Всё, что важно, пишите прямо здесь. Что не важно, не пишите.

Добрый день!
Общий алгоритм без предварительного построения переборной последовательности уже реализовал. Оформлю и пришлю в ближайшее время.

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

[vicvolf]

Добрый день!
B файле вложений приведены исходные данные и схема общего алгоритма доминирующих векторов для наперед заданного K дискретных переменных. Алгоритм работает без предварительного построения переборной последовательности.
[img]/modules/file/icons/x-office-document.png[/img] ______________________________________________________________.doc
Для тех, кто хочет войти в курс вопроса рекомендую предварительно посмотреть на моем сайте [img]/modules/file/icons/x-office-document.png[/img] ssilka.doc статью [2] и сообщения 27 и 31 в этой теме.

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

[Pavlovsky]

У меня такое ощущение, что над нами издеваются. Выложить алгоритм перебора c помощью K вложенных циклов. Это действительно уникальный подход. Такое никому в голову не придет.

[12d3]

Виктор B, дарю алгоритм.
x[i] - значение i-й переменной.
Будем считать для простоты, что, значения i-й переменной изменяется от 0 до xmax[i].
0a) Переход к потомку

Код: Выбрать все

if (x[1] != xmax[1])
 then x[1] = x[1] + 1; \\ переходим к потомку
else exit; \\ нет потомков


0b) Переход к следующему поддереву.

Код: Выбрать все

i=1;
while (x[i] == 0 and i<=n)
 i = i+1;
if (i > n) then exit \\ если находимся в корневой вершине, то нельзя перейти к следующему поддереву.
 \\ теперь i - номер первой ненулевой переменной
x[i] = 0;
i = i+1;
while (x[i] == xmax[i] and i<=n) {
 x[i] = 0;
 i = i+1;
}
if (i > n) then exit; \\ перейти к следующему поддереву нельзя - уже все просмотрено.
else x[i] = x[i]+1;


0c) переход к вершине-предку.

Код: Выбрать все

i=1;
while (x[i] == 0 and i<=n)
 i = i+1;
if (i > n) then exit \\ если находимся в корневой вершине, то нельзя перейти к предку.
x[i] = x[i] - 1;


Теперь собственно алгоритм

Код: Выбрать все

x[1],x[2],..,x[n] = 0,0,...,0;
p0 = 0; \\текущее значение максимума ЦФ
while (true) {
 if (вершина удовлетворяет условиям) then {
 переход к потомку;
 if (нельзя перейти к потомку) then {
 p = P(x[1],..,x[n]); \\ вычисление ЦФ в данной точке
 if (p>p0) then p0=p;
 переход к следующему поддереву;
 if (нельзя перейти к следующему поддереву) then exit;
 }
 } else {
 p = P(предок(x[1],..,x[n])); \\ вычисление ЦФ предка
 if (p>p0) then p0=p;
 переход к следующему поддереву;
 if (нельзя перейти к следующему поддереву) then exit;
 }
}

Доказательство пока лень писать.He я же отдуваюсь.

[vicvolf]

Source of the post
Виктор B, дарю алгоритм.
x[i] - значение i-й переменной.
Будем считать для простоты, что, значения i-й переменной изменяется от 0 до xmax[i].
0a) Переход к потомку

Код: Выбрать все

if (x[1] != xmax[1])
 then x[1] = x[1] + 1; \\ переходим к потомку
else exit; \\ нет потомков


0b) Переход к следующему поддереву.

Код: Выбрать все

i=1;
while (x[i] == 0 and i<=n)
 i = i+1;
if (i > n) then exit \\ если находимся в корневой вершине, то нельзя перейти к следующему поддереву.
 \\ теперь i - номер первой ненулевой переменной
x[i] = 0;
i = i+1;
while (x[i] == xmax[i] and i<=n) {
 x[i] = 0;
 i = i+1;
}
if (i > n) then exit; \\ перейти к следующему поддереву нельзя - уже все просмотрено.
else x[i] = x[i]+1;


0c) переход к вершине-предку.

Код: Выбрать все

i=1;
while (x[i] == 0 and i<=n)
 i = i+1;
if (i > n) then exit \\ если находимся в корневой вершине, то нельзя перейти к предку.
x[i] = x[i] - 1;


Теперь собственно алгоритм

Код: Выбрать все

x[1],x[2],..,x[n] = 0,0,...,0;
p0 = 0; \\текущее значение максимума ЦФ
while (true) {
 if (вершина удовлетворяет условиям) then {
 переход к потомку;
 if (нельзя перейти к потомку) then {
 p = P(x[1],..,x[n]); \\ вычисление ЦФ в данной точке
 if (p>p0) then p0=p;
 переход к следующему поддереву;
 if (нельзя перейти к следующему поддереву) then exit;
 }
 } else {
 p = P(предок(x[1],..,x[n])); \\ вычисление ЦФ предка
 if (p>p0) then p0=p;
 переход к следующему поддереву;
 if (нельзя перейти к следующему поддереву) then exit;
 }
}

Доказательство пока лень писать.He я же отдуваюсь.

Добрый вечер!
Спасибо за код. Я конечно его проанализирую. Ho первое впечатление - что все не так просто! Вы двигаетесь по переборному дереву, как будто оно уже построено. Ha самом деле в исходных данных его нет.

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