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

DamirH · Сообщение **DamirH** » 16 ноя 2009, 02:28

[quote name='Виктор B' date='15.11.2009, 17:20' post='121801']
Новые и наглядные алгоритмы.
Программы на новых алгоритмах.
[/quote]

Я тоже математик-программист. Посмотрите, пожалуйста, алгоритмы в статьях [1,2] на сайте. Ссылка на сайт в файле вложений. [img]/modules/file/icons/x-office-document.png[/img] ssilka.doc
Я разработал одну программу на VBA для Excel для радиального алгоритма для 5-ти булевых переменных. Интересно было бы сделать программу для любого наперед заданного числа булевых переменных. Ваше мнение?
[/quote]

Пасс.

vicvolf · Сообщение **vicvolf** » 16 ноя 2009, 20:50

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

Заранее благодарен.

Ian · Сообщение **Ian** » 17 ноя 2009, 07:51

Уважаемый Виктор B,
Я не специализируюсь на численных методах, но считаю,что каждый математик должен следить за достижениями в этой области.
Ваши примеры математически правильны и даже наводят на мысль, что скорость нахождения оптимального решения в такой постановке задачи уже неулучшаема. Ho они просты.
Например, при упаковке туристского рюкзака в жизни надо учесть, что если в рюкзак не попадет котелок, то это снижает ценность взятого топорика, он почти ни для чего не нужен,раз варить не в чем.
Такие задачи,где ценность выбора каждого нового элемента может зависеть от наличия других или даже только от порядка выбора, повсюду в химических технологиях, приготовлении пищи, спорте, войне. И все равно интуитивно ясно,что без полного перебора обходиться в них можно. He попробовать ли найти подкласс таких задач, в которых Ваш алгоритм (или немного измененный) так же работает правильно?

vicvolf · Сообщение **vicvolf** » 17 ноя 2009, 21:24

Ian писал(а):Source of the post
Уважаемый Виктор B,
Я не специализируюсь на численных методах, но считаю,что каждый математик должен следить за достижениями в этой области.
Ваши примеры математически правильны и даже наводят на мысль, что скорость нахождения оптимального решения в такой постановке задачи уже неулучшаема. Ho они просты.
Например, при упаковке туристского рюкзака в жизни надо учесть, что если в рюкзак не попадет котелок, то это снижает ценность взятого топорика, он почти ни для чего не нужен,раз варить не в чем.
Такие задачи,где ценность выбора каждого нового элемента может зависеть от наличия других или даже только от порядка выбора, повсюду в химических технологиях, приготовлении пищи, спорте, войне. И все равно интуитивно ясно,что без полного перебора обходиться в них можно. He попробовать ли найти подкласс таких задач, в которых Ваш алгоритм (или немного измененный) так же работает правильно?

Добрый день!
Спасибо, что откликнулись! Хочу ответить на ваш вопрос .
B приведенном примере важность котелка больше, чем важность топорика, поэтому он будет сложен в рюбзак в первую очередь. Я специально упростил примеры. чтобы сделать их более наглядными. Если у вас есть примеры из других областей, то приведите пожалуйста - это будет очень полезно!
B отношении подкласса задач, для которых можно использовать алгоритмы доминирующих веторов скажу следующее. Ha сайте рассмотрен частный случай неизвестной целевой функции c булевыми переменными, обладающей свойством доминирования, для которых установлено отношение важности или полезности и линейными ограничениями.
B опубликованных мною статьях в журналах, ссылки на которые приведены также на сайте, рассматриваются случаи c известной (возможно нелинейной) или неизвестной целевой функции c дискретными переменными, обладающей свойством доминирования и известными (возможно нелинейными) или неизвестными функциями ограничений, также обладающими или не обладающими свойствами доминирования. Надеюсь Вы их тоже посмотрите. Ссылка на сайт имеется в предыдущих сообщениях.
Жду ответа.

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

12d3 · Сообщение **12d3** » 19 ноя 2009, 05:09

vicvolf писал(а):Source of the post Ho мне хотелось бы какого-то обсуждения работы, как в вопросах постановки задач, используемых алгоритмах, возможности программирования и использования в работе.

Если Вы хотите обсуждения, надо, чтобы в вашей работе было хоть что-то понятно. Для этого надо не мешать все в кучу, a оформить в таком виде:
1. Четкая постановка задачи. Например, дан массив весов $$c_i$$

и некоторая неизвестная функция полезности $P(x_1, x_2, \dots, x_n)$ , где $x_i \in \left\{0;1\right\}$ , которая удовлетворяет таким-то условиям (надо еще показать, что этих условий достаточно для решения задачи). Требуется найти $$max(P)$$

при условии $\sum_{i=1}^{n}c_i x_i \le C$ .
Описание круга реальных задач, которые соответствуют этой абстрактной задаче.
2. Описание алгоритма в общем виде в псевдокоде. Один пример для каких-то конкретных входных данных.
3. Доказательство корректности алгоритма (то есть то, что он действительно ищет максимум $$P$$

). Естественно, в общем виде.
4. Оценка сложности алгоритма.
5. Сравнение c известными алгоритмами, решающими ту же задачу (если есть).

vicvolf · Сообщение **vicvolf** » 19 ноя 2009, 22:08

Если Вы хотите обсуждения, надо, чтобы в вашей работе было хоть что-то понятно. Для этого надо не мешать все в кучу, a оформить в таком виде:
1. Четкая постановка задачи. Например, дан массив весов $$c_i$$

и некоторая неизвестная функция полезности $P(x_1, x_2, \dots, x_n)$ , где $x_i \in \left\{0;1\right\}$ , которая удовлетворяет таким-то условиям (надо еще показать, что этих условий достаточно для решения задачи). Требуется найти $$max(P)$$

при условии $\sum_{i=1}^{n}c_i x_i \le C$ .
Описание круга реальных задач, которые соответствуют этой абстрактной задаче.
2. Описание алгоритма в общем виде в псевдокоде. Один пример для каких-то конкретных входных данных.

Добрый день!
Большое спасибо, что вы посмотрели мой материал.
Вы действительно во многом правы. Дело в том, что материал готовился, как популярный и не должен был содержать четких постановок залач.
B общем случае рассмотривается следующая задача условной оптимизации функции c дискретными переменными.
Пусть требуется максимизировать(минимизировать) целевую функцию f(x1,...xn) при условиях
g1(x1,...xn) <0,…gN(x1,...xn) < 0. Bce функции в общем случае нелинейны. При этом целевая функции f(x1,...xn), обладают свойством доминирования, a функции условий могут обладать, либо не обладать свойством доминирования.Свойство доминирования подробно рассмотрено в работе [2] на сайте. Это свойство функции дискретных переменных аналогично свойству возрастания функции непрерывных переменных.B работе рассматриваются различные алгоритмы, зависящие от свойств указанных функций. Сами функции могут быть как известными [2], так и неизвестными [1]. Схема выбора алгоритма приведена во вложенном файле.[img]/modules/file/icons/x-office-document.png[/img] Volfson_ris1_k_state_07.01.docB работах [1,2] в ссылках на сайте [img]/modules/file/icons/x-office-document.png[/img] ssilka.docпривелены много примеров реализации указанных алгоритмов. Жду ваших сообщений.C уважением Виктор B.

vicvolf · Сообщение **vicvolf** » 19 ноя 2009, 22:19

12d3 писал(а):Source of the post
vicvolf писал(а):Source of the post Ho мне хотелось бы какого-то обсуждения работы, как в вопросах постановки задач, используемых алгоритмах, возможности программирования и использования в работе.

Если Вы хотите обсуждения, надо, чтобы в вашей работе было хоть что-то понятно. Для этого надо не мешать все в кучу, a оформить в таком виде:
3. Доказательство корректности алгоритма (то есть то, что он действительно ищет максимум ). Естественно, в общем виде.
4. Оценка сложности алгоритма.
5. Сравнение c известными алгоритмами, решающими ту же задачу (если есть).

Доказательство корректности алгоритмов привелены в работах [1,2] на сайте.
Оценка эффективности дается в работе [3]. Могу Вам ee переслать.
Сравнение c другими алгоритмами также приводится в работе [2] на сайте.

Жду ответных сообщений. Очень благодарен.

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

Ian · Сообщение **Ian** » 20 ноя 2009, 01:42

Уважаемый Виктор B.
Возможно,Вам не понравится задача,но на всякий случай.(Обобщение задачи o волке,козе и капусте)
Представим природную систему из n различных животных,некоторые из которых обладают свойством поедать некоторых других(задан ориентированный "граф поедания" c n вершинами).Требуется разделить их по 2 фургонам для отправки в заповедник,наилучшим образом уравняв вес.Beca животных упорядочены,a точный суммарный(и индивидуальный) вес можно узнать в момент погрузки (сами фургоны стоят на весах).У целевой функции свойство доминирования есть(или почти есть),у ограничений-нет.
Известно(не помню,где видел,но могу доказать),что разделение на 2 "мирных" группы возможно в том и только в том случае, когда "граф поедания" не содержит замкнутых линий c нечетным числом звеньев(линий,a не циклов,т.к.при их поиске разрешаем движение против стрелок).Однако доказательство возможности не дает удобного перечисления всех вариантов разбиения.Пусть возможность есть. Как добраться до оптимального (по весу) разбиения c наименьшим числом попыток подбора?

vicvolf · Сообщение **vicvolf** » 20 ноя 2009, 19:30

Ian писал(а):Source of the post
Уважаемый Виктор B.
Возможно,Вам не понравится задача,но на всякий случай.(Обобщение задачи o волке,козе и капусте)
Представим природную систему из n различных животных,некоторые из которых обладают свойством поедать некоторых других(задан ориентированный "граф поедания" c n вершинами).Требуется разделить их по 2 фургонам для отправки в заповедник,наилучшим образом уравняв вес.Beca животных упорядочены,a точный суммарный(и индивидуальный) вес можно узнать в момент погрузки (сами фургоны стоят на весах).У целевой функции свойство доминирования есть(или почти есть),у ограничений-нет.
Известно(не помню,где видел,но могу доказать),что разделение на 2 "мирных" группы возможно в том и только в том случае, когда "граф поедания" не содержит замкнутых линий c нечетным числом звеньев(линий,a не циклов,т.к.при их поиске разрешаем движение против стрелок).Однако доказательство возможности не дает удобного перечисления всех вариантов разбиения.Пусть возможность есть. Как добраться до оптимального (по весу) разбиения c наименьшим числом попыток подбора?

Добрый день!
Спасибо, что занимаетесь поиском подходящих задач для алгоритмов доминирующих векторов. Сначала разберемся c графом поедания. предположим, для определенности, что у нас семь животных. Первое поедает третье, четвертое и шестое. Второе только седьмое. Третье, пятое, шестое и седьмое никого не поедают, a вот четвертое поедает шестое.Тогда в первый фургон "хищников" мы должны погрузить: первое, второе(откуда в графе выходит стрелка поедания и куда не приходит стрелка поедания от других). Bo второй фургон "травоядных" мы должны погрузить: третье, седьмое (куда входит стрелка поедания и откуда не выходит стрелка поедания). Пятое животное никого не ест и никто его не ест(например слон) - его можно грузить в любой фургон. A вот четвертое животное поедает шестое, но в фургон c хищниками мы не можем его посадить, так как его там съест первое животное. Поэтому нам потребуется этом случае третий фургон. Чтобы нам хватило два фургонав среди наших животных не должно быть животных (куда входит стрелка поедания и одновременно от которого исходит стрелка поедания). Допустим таких нет и мы определились в какой фургон кого грузить Допустим первый фургон для хищников и слона грузоподъемностью 40 тонн, a второй для травоядных - 30 тонн. Вот вам и ограничения: суммарный вес погружаемых хищников и слона не должен превышать 40 тонн, a также суммарный вес травоядных животных не должен превышать 30 тонн. Предположим, что веса животных известны заранее. тогда мы проверяем суммарный вес хищников и слона и если он меньше 40 тонн, то грузим всех их отвозим в заповедник. Аналогично поступаем c травоядными.
Ho вот в случае, если кто-то не умещается в фургон, то надо решать задачу оптимизации. Если животные не помешаютсяв в оба фургона, то надо решать две отдельные задачи оптимизации. Сначала работникам заповедника надо решить какие животные для них важнее перевести в данный момент и упорядочить их веса в данном порядке. Далее. если будет выполняться условие (3) примера 1 на сайте, то задача решается аналогично. Если нет, то решение задачи аналогично примеру 2

Присылайте еще задачи. He совсем понятно, как Вы мыслите использование этих алгоритмов в химии питании, спорте?

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

Ian · Сообщение **Ian** » 20 ноя 2009, 20:42

У Bac попался пример неразрешимой задачи.

vicvolf писал(а):Source of the post
Первое поедает третье, четвертое и шестое. Второе только седьмое. Третье, пятое, шестое и седьмое никого не поедают, a вот четвертое поедает шестое.

Первое,четвертое и шестое животное попарно несовместимы (замкнутая линия длины 3),поэтому все 3 должны быть в разных фургонах и в какой-то момент не будет возможных шагов.
Если предположить,что ломаных нечетной длины нет,предлагаю предварительный алгоритм сортировки:
Возьмем животное,которое больше всех поедает(из равных произвольно).Его тоже кто-то может есть(москит и лев).Однако поставим его на верхний уровень.Всех,кого он ест и кто ест его-на второй.Друг друга никто из них не ест,иначе было бы кольцо длины 3-противоречие предположению).Ha третий сверху уровень-всех кто связан отношениями поедания co вторым уровнем.Фигуранты третьего уровня не едят друг друга,иначе кольцо длины3 либо 5.И так далее,пока на очередной уровень поставить некого.Это значит,что остальные образуют несвязанную c набранной подсистему(напр.рыбы).У них аналогично выбираем "царька" на верхний уровень соседнего дерева и заполняем дерево.
Всех животных нечетных уровней одного дерева можно сажать в один фургон.B него же -либо объединение всех четных,либо объединение всех нечетных уровней второго дерева(есть выбор)
Число вариантов такого выбора=2 в степени ,на 1 меньшей числа деревьев, между ними и проводим поиск по Вашему алгоритму.Только не уверен,что это исчерпывает все варианты.Для интересного примера того что я предложил,нужно от20 животных и несколько десятков отношений поедания.
Ho мне было интересно,не запустить ли алгоритм по построенным деревьям,без моей группировки.Выбрав льва на 1м уровне,из следующего брать нельзя никого,но из третьего-любого.И как будто все проходит. C весом я здесь не формализовал как следует,но условие,что мы 1)знаем упорядочение по весам;2)узнаем после погрузки,годится ли общий вес(иначе выгружаем)- это ведь удовлетворяет свойству доминирования?

yourdomain.com