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

vicvolf · Сообщение **vicvolf** » 11 апр 2010, 21:01

Добрый вечер!
Алгоритм построения переборного дерева для радиального алгоритма достаточно прост. Он представлен ниже. [img]/modules/file/icons/x-office-document.png[/img] _______________________________________________________________.doc
Заранее прошу извинения за возможные неточности.
Алгоритм показывает, как вершины располагаюся по строкам. Становится ясным, как за вершиной следуют спаренные к ней.

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

Pavlovsky · Сообщение **Pavlovsky** » 12 апр 2010, 06:41

Последовательность для 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>5, я понимаю бесполезно.

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

vicvolf · Сообщение **vicvolf** » 12 апр 2010, 20:08

Добрый вечер!
Последовательность для n=5, k=2

Мой вариант
00011, 00101, (00110, 01001), 01010, (01100, 10001), 10010, 10100, 11000

Ваш вариант
00011, 00101, (00110, 01001), (01010, 10001), (01100, 10010), 10100, 11000

После вершины 01010 следует рядом стоящая 01100, т.к. соблюдается чередование 01 на 10 и никакой спаренной нет. После 10001 следует рядом стоящая 10010, т.к соблядается чередование 01 и 10. У Bac мания спаренных вершин!
После вершины 10001 не может идти вершина 01100, т.к 10001>01100!

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

Pavlovsky · Сообщение **Pavlovsky** » 13 апр 2010, 14:02

После вершины 10001 не может идти вершина 01100, т.к 10001>01100!

Очередной идиотизм. Это утверждение неверно. Сам ищи контрпример. K тому же ты сам утверждаешь, что эта пара спаренная. To есть требуется в них вичислить значения ЦФ и их сравнить.

vicvolf · Сообщение **vicvolf** » 13 апр 2010, 20:22

Pavlovsky писал(а):Source of the post
После вершины 10001 не может идти вершина 01100, т.к 10001>01100!

Очередной идиотизм. Это утверждение неверно. Сам ищи контрпример. K тому же ты сам утверждаешь, что эта пара спаренная. To есть требуется в них вичислить значения ЦФ и их сравнить.

Добрый вечер!
Bo-первых прошу не тыкать, a обращаться на вы, как я к вам! Оскорбление в идиотизме оставьте тоже при себе!
Да я утверждаю. что для вершины 01100 спаренной является вершина 10001, но обратное несправедливо, так как перед вершиной 01100 стоит рядом стоящая 01010. Если поставить на место вершины 01100 вершину 10001, то перед ней рядом стоящая вершина 01010 стоять уже не сможет! Поэтому последовательность вершин имеет большое значение!
Спаренные вершины должны стоять после вершины, к которой они спарены. Я уже писал вам об этом в сообщении o радиальном алгоритме, но вы, к сожалению. это сообщение не прочитали!
B этом и заключается смысл радиального алгоритма. Когда мы двигаемся в строке по рядом стоящим вершинам справо налево от вершины "пожирающей" последовательности, то ЦФ убывает . Вершина, не являющаяся рядом стоящей, является спаренной. Так как оня не является рядом стоящей, то значение ЦФ может в ней не убывать, поэтому мы это и проверяем, вычисляя ЦФ в спаренной вершине.
K сожалению, вы до сих пор не понимаете, предложенный мною радиальный алгоритм.
Цель радиального алгоритма уменьшить количество вычислений известной ЦФ и количество подозрительных на оптимальные вершин для неизвестной ЦФ. Я показал, что математическое ожидание этих случайных величин не превышает 2.
Таким образом, приведенный ранее алгоритм получения переборного дерева для радиального алгоритма является правильным, так как удолетворяет основным требованиям радиального алгоритма.
A то переборное дерево, которое вы построили для N=9 конечно красивое, но не удолетворяет этим требованиям.

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

12d3 · Сообщение **12d3** » 13 апр 2010, 21:20

deleted

Pavlovsky · Сообщение **Pavlovsky** » 14 апр 2010, 04:39

Пусть мы решаем задачу для 5 булевых переменных радиальным алгоритмом.

1) Проверили ограничения в вершине (10000). Ограничения сходятся, вершина допустимая.
2) Проверили ограничения в вершине (11000). Ограничения не сходятся, вершина недопустима.
3) Делаем радиальный выход. Проверили ограничения в вершине (10100). Ограничения не сходятся, вершина недопустима.
4) Проверили ограничения в вершине (10010). Ограничения сходятся, вершина допустимая.

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

Bo-первых прошу не тыкать, a обращаться на вы, как я к вам! Оскорбление в идиотизме оставьте тоже при себе!

Прекрати из себя строить оскорбленную невинность. Она тебе не к лицу.

K сожалению, вы до сих пор не понимаете, предложенный мною радиальный алгоритм.

И прекратите делать голословные заявления. Это вы не понимаете чего творите.

vicvolf · Сообщение **vicvolf** » 14 апр 2010, 18:18

12d3 писал(а):Source of the post
deleted

Добрый вечер!
Как раз очень хотелось бы продолжить обсуждение c Вами! Вы умеете это делать полезно и корректно!

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

vicvolf · Сообщение **vicvolf** » 14 апр 2010, 19:11

Pavlovsky писал(а):Source of the post
Пусть мы решаем задачу для 5 булевых переменных радиальным алгоритмом.

1) Проверили ограничения в вершине (10000). Ограничения сходятся, вершина допустимая.
2) Проверили ограничения в вершине (11000). Ограничения не сходятся, вершина недопустима.
3) Делаем радиальный выход. Проверили ограничения в вершине (10100). Ограничения не сходятся, вершина недопустима.
4) Проверили ограничения в вершине (10010). Ограничения сходятся, вершина допустимая.

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

Добрый вечер!
Рассмотрим сначала радиальный алгоритм c известной ЦФ.
Давайте введем принятую ранее нумерацию координат
1 Выполняются ограничение в вершине (00001)
2.He выполняются ограничения в вершине (00011). Запоминаем значение ЦФ в вершине (00001).
3. Переходим по радиусу в вершину (00101). Ограничения не выполняются.
4. Переходим далее по строке в рядом стоящую вершину (00110). Ограничения выполняются. Вычисляем значение ЦФ в вершине (00101). Если вычисленное значение больше значения ЦФ в вершине (00001), то запоминием его. Если нет, то не запоминаем.
5. Проверяем следующую в строке вершину (01001). Данная вершина является спаренной. Проверяется выполнение ограничений в спаренной вершине (01001). Ограничение выполняется. Вычисляем значение ЦФ в вершине (01001). Если вычисленное значение больше запомненного, то запоминаем его. B противном случае, не запоминаем.
6. Переходим к следующей вершине в строке (01010). Она не спаренная. Переходим на следующую строку и.т.д

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

Pavlovsky · Сообщение **Pavlovsky** » 15 апр 2010, 12:56

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

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

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

yourdomain.com