Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: (метод Гомори) Помогите какой алгоритм выбрать  (Прочитано 18169 раз)
0 Пользователей и 1 Гость смотрят эту тему.
VanLeo
Гость
« : 22-05-2008 08:12 » 

Такая вот задача:
Есть массив чисел (предположим "1,2,3,4,5") и несколько целевых параметров (предположим "3 и 9").
Суть задачи: необходим алгоритм, который бы перебирал массив таким образом, чтобы
1. сумма отобранных элементов массива был равен целевому параметру, т.е. 1 + 2 = 3.
2. отобранные элементы исключаются из массива (чтоб одни и те же элементы не учитывались при расчете для более одного целевого параметра), а для оставшихся (3,4,5) снова проводился отбор, чтобы получить число 9: 4+5=9.

Прошу подсказать в направлении анализа, может формула уже есть, а напишу я сам. 
« Последнее редактирование: 06-08-2008 19:51 от Алексей1153++ » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 22-05-2008 09:13 » 

считать придётсям перебором сочетаний. Когда найдено нужное сочетание, запоминаем куда нибудь, а числа удаляем из массива (например, заменить там числа "невалидными значениями", которые никогда в алгоритме не учавствуют, либо "сжать" массив, удалив числа)

и по новой искать начинаешь
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #2 : 22-05-2008 09:17 » new

перебор сочетаний , имхо, удобно производить при помощи длинного двоичного числа:
если массив имеет N байт, то "двоичный" массив будет (N+8)/8 байт .
Биты двоичного массива будут показывать, какие числа сейчас в наборе (единичные биты соответствуют позиции цифры в главном массиве).
Ну а перебор сочетаний сводится к инкреминированию длинного двоичного числа - это уже не так сложно Улыбаюсь
Записан

Sands
Помогающий

ua
Offline Offline

« Ответ #3 : 22-05-2008 11:47 » 

Алексей1153++, Перебор сочетаний вещь хорошая, но если сразу удалять числа, то по идее можно нарваться на ситуацию, когда некоторое число нельзя будет "собрать".
В приведенном примере все хорошо, а вот если на наборе "1,2,3,4,5" предложить собрать параметры 6 и 8, тогда перебором первое подходящее для 6 буде 5 и 1, а после их удаления из 2, 3, и 4 8 мы никак не получис, хотя если из базового выбрать сначала 2 и 4 для 6, то из 3 и 5 мы получим 8.
Или ты имел ввиду перебор с откатами?
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 22-05-2008 11:52 » 

Sands, соответственно, счётчики сочетаний надо с нуля пускать

сжимать массив полезно, кстати, будет ) Когда много искать наборов. А если немного - просто на невалидные значения менять
« Последнее редактирование: 22-05-2008 11:54 от Алексей1153++ » Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #5 : 22-05-2008 11:55 » 

Sands, аа, я понял, про что ты , ага, придётся с откатами
Записан

Sands
Помогающий

ua
Offline Offline

« Ответ #6 : 22-05-2008 12:00 » 

И все таки интересно, может реально сюда многокритериальную оптимизацию в целых числах прикрутить. Тогда метод Гомори применить и получить результат?
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #7 : 22-05-2008 17:29 » 

что за метод такой ? )
Записан

Sands
Помогающий

ua
Offline Offline

« Ответ #8 : 22-05-2008 17:59 » 

Алексей1153++, Ну если искать максимум функции на некоторой непрерывной области в RxR, тогда можно применять Симплекс-метод, ну или другие, а вот если имеем дискретную одбласть(как в данном случае), тогда задачу решают методом Гомори(их аж 3). Навскидку я их не приведу, но тут просили дать направление поиска, вот я и даю ))
ЗЫ RxR тут использовано для примера. В общем случае, конечно же имеем R^n
« Последнее редактирование: 22-05-2008 18:03 от Sands » Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #9 : 22-05-2008 19:14 » 

Пусть x1,x2,...xN - ето числа в массиве, а b1,b2,...,bM - это множество целевых параметров
тогда можно записать следующее

a11*x1+a12*x2+...+a1N*xN = b1
a21*x1+a22*x2+...+a2N*xN = b2
.............................
aM1*x1+aM2*x2+...+aMN*xN = bM

но ето еще не все, чтобы избежать повторного использования одних и тех же чисел, допишем условия

a11+a21+...+aM1 <= 1
a12+a22+...+aM2 <= 1
...................
a1N+a2N+...+aMN <= 1

"меньше или равно" здесь использовано потому, что как видно из примеров некоторые цифры могут вообще не использоваться ни в одной сумме
и еще к етому всему добавятся условия

aij >= 0 i = 1..M, j = 1..N

А критерий максимизации будет иметь вид

(a11+a21+...+aM1)*x1+(a12+a22+...+aM2)*x2+...+(a1N+a2N+...+aMN)*xN -> max

ну и решать ето все в целых числах, понятно, что относительно

aij i = 1..M, j = 1..N
« Последнее редактирование: 22-05-2008 19:32 от Sands » Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #10 : 23-05-2008 11:24 » 

Excel, в принципе, сможет решить такую задачу

в экселе, правда, придётся попотеть над организацией задания условий для поиска решения, ну а решит он в момент
« Последнее редактирование: 06-08-2008 19:47 от Алексей1153++ » Записан

Sands
Помогающий

ua
Offline Offline

« Ответ #11 : 23-05-2008 12:37 » 

Алексей1153++, Да, задание условий - ето небольшая проблема, бОльшая проблема в том, что данный метод не дает гарантий правильности результата, потому как на практике он мной не опробован, ибо придуман был совсем недавно ))
В связи с етим может получиться, что автор темы потратит время, а результата не достигнет. Потом будет расстраиваться.
Я б на его месте сходил бы с етой идеей к преподавателю(если ето задача учебная), а если рабочая - тогда брейнсторм на работе с коллегами.
Записан
sam_
Гость
« Ответ #12 : 17-12-2008 16:24 » 

можно каким-нибудь образом решить задачу методом Гомори в другой среде? допустим matlab
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines