Russian Qt Forum
Ноябрь 22, 2024, 14:39 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 2 [3]   Вниз
  Печать  
Автор Тема: большое количество комбинаций и выбор оптимального решения  (Прочитано 25840 раз)
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #30 : Сентябрь 08, 2016, 10:15 »

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

Грубо получается: P * (K * Bp), P - это продукты, Bp - кол-во бочек для продукта P, К - кол-во комбинаций проверки.
Например, если Р=10, Bp (грубо в половину) =5, K = 10..20 step 0.1 = 100, то имеем: 10 * 5 * 100, всего 5000 вычислений.
Секунда? Полсекунды?
Улыбающийся
« Последнее редактирование: Сентябрь 08, 2016, 10:19 от Racheengel » Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
ssoft
Программист
*****
Offline Offline

Сообщений: 584


Просмотр профиля
« Ответ #31 : Сентябрь 08, 2016, 12:34 »

Ну как-то складывается впечатление что, мол, да тут легко, общих фраз вполне достаточно Улыбающийся Я так не считаю, задачка трудная (хотя возможно и стандартная).

Основная сложность в четком определении
- перечня варьируемых параметров и области их определения - в данном случае 9 переменных из области [10...20].
- целевой функции, которая рассчитывается по варьируемым параметрам - это может быть остатки сырья, стоимость оставшегося сырья и т.д.
- ограничивающих параметров - например, ограниченный объем сырья (не более N бочек) и т.п.

Как только есть метод расчета целевой функции с проверкой на выполняемые ограничения, можно использовать любой понравившийся метод оптимизации, например, отсюда http://www1.icsi.berkeley.edu/~storn/code.html или взять готовый продукт http://www.iosotech.com/ru/products.htm или Mathcad.
Записан
demal
Чайник
*
Offline Offline

Сообщений: 53


Просмотр профиля
« Ответ #32 : Сентябрь 08, 2016, 21:51 »

вот с ограничениями в условии задачи и трудности - нет ограничения на количества сырья. А в этом случае ничего кроме как тупого перебора не остается.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #33 : Сентябрь 09, 2016, 06:58 »

- целевой функции, которая рассчитывается по варьируемым параметрам - это может быть остатки сырья, стоимость оставшегося сырья и т.д.
Это не катит для комбинаторики. Напр какой-то путь на предпоследнем шаге худший - но после выполнения последнего шага оказался лучшим.

вот с ограничениями в условии задачи и трудности - нет ограничения на количества сырья. А в этом случае ничего кроме как тупого перебора не остается.
Ну что ж так быстро-то программист опускает руки?  Вроде еще не "пользователь Qt" Улыбающийся

Кажется понял как решать, вот набросок
Код
C++ (Qt)
// структура элемента
struct CReminder {
std::vector<int> mRem;   // остатки по каждому сырью (0..999)
int mSum;                       // сумма остатков
int mTblIndex;                 // индекс в предыдущей таблице
std::vector<int> mAdd;   // число произведенных продуктов по каждому сырью
};
 
// подсчет новых остатков
int TryAdd( const CReminder & rem, std::vector<int> & data )
{
 int result = 0;
 assert(rem.,Rem.size() == data.size());
 for (size_t i = 0; i < data.size(); ++i) {
   int a = rem.mRem[i];
   if (data[i])
     a = (a + data[i]) % 1000;
   result += a;
 }  
 return result;
}
 
// шаг (вычисление остатков при производстве 1 продукта)
void Step( int productNo, const std::vector<float> & num, std::vector<int> & data )
{
assert(data.size() == NUM_RAW);
std::fill(data.begin(), data.end(), 0);
 
for (size_t i = 0; i < NUM_RAW; ++i)  // по всем видам сырья
 data[i] = std::remainder(GlobalTable[productNo][i] * num[i], BARREL_SIZE) / BARREL_SIZE * 1000;
}
 
void Process1Product( int productNo )
{
  int numRaw = 0;
  for (size_t i = 0; i < NUM_RAW; ++i)  // кол-во сырья для этого продукта
    if (GlobalTable[productNo][i]) ++numRaw;
 
 float limit[2] = { DEF_LOW_LIMIT,  // 10
                         DEF_HI_LIMIT } // 20
 if (numRaw > 1) limit[0] = 0.0f;
 
 int rawIndex = 0;
 Process1ProductRecursive(productNo, 0, rawIndex, numRaw, limit);        
}
 
Ну все расписать не смогу - там довольно много. Смысл в том что вложенные переборы (Recursive) только по столбцу когда продукт использует 2 или больше сырья. Остальное как говорилось раньше - тот же контейнер остатков, только по всем видам сырья
Записан
kuzulis
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2812


Просмотр профиля
« Ответ #34 : Сентябрь 09, 2016, 09:16 »

Ого, да тут целый матан. Шо-то я забыл уже все, программирование отупляет.  Подмигивающий
Записан

ArchLinux x86_64 / Win10 64 bit
ksv-uk
Гость
« Ответ #35 : Сентябрь 09, 2016, 09:37 »

Igors, спасибо большое за ваше участие. В программу пока не вникаю, тут с алгоритмом сначала нужно разобраться.

Пытаюсь вникнуть в вашу идею.Пишу пока без глубокого осмысления (первая прикидка). Если все верно понял, вы предлагаете(описываю словесно):

1) В цикле идем от 1 до 100 ((20-10/0.1=100). Если диапазон решений будет другой, соотв. границы будут другие
2) Берем 1 продукт, ищем остатки сырья 4, без учета целых бочек (заносим остатки в массив№1 (массив 9(кол-во сырья) на 100 (вариантов))
3) Берем 2 продукт , ищем остатки сырья 1, 3, 8 без учета целых бочек (заносим остатки в массив №2)
и.т.д для всех продуктов.
В итоге получаем 9 массивов (9Х100) в которых будут сохранены остатки сырья, если бы производили продукты отдельно друг от друга.
Теперь нужно получить суммы остатков.
1) цикл по видам сырья (1 до 9)
2) цикл по массивам (1 до 9)
3) цикл по вариантам (1 до 100)

Получается 9*9*100 = 8100

Ищем комбинацию с наименьшим остатком по всем видам сырья.

По моему что-то напутал, ушел в размышления... Непонимающий
« Последнее редактирование: Сентябрь 09, 2016, 09:41 от ksv-uk » Записан
ssoft
Программист
*****
Offline Offline

Сообщений: 584


Просмотр профиля
« Ответ #36 : Сентябрь 09, 2016, 09:57 »

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

В этом варианте не решается задача нахождения минимума, а реализуется последовательное выравнивание остатков, при этом результат будет зависеть от порядка рассмотрения продуктов. Но действительно, если это прикладная задача, то можно ограничится таким подходом. Если нужно точное решение, то так решить не получится.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #37 : Сентябрь 09, 2016, 10:12 »

Ого, да тут целый матан. Шо-то я забыл уже все, программирование отупляет.  Подмигивающий
Ага, "сборки", "ключики", std::срань и.т.п. - где уж тут чего-то помнить  Улыбающийся

Пытаюсь вникнуть в вашу идею.
Она не моя. Есть классическая "задача о монетках"
Цитировать
Есть N разных монет, напр 1 (рубль), 2, 5 и.т.п. Требуется набрать нужную сумму из минимального кол-ва монет.
Казалось бы - ну без перебора никак. Но лучшее решение есть. Захотите - нагуглите, вещь известная.

Здесь я пытался сделать то же самое. Для каждого продукта есть "таблица остатков" (контейнер). Элемент хранит остатки по каждому сырью и суммарный. Индекс элемента совпадает с суммарным остатком. Напр 5-й элемент имеет mSum = 5. Остатки меряем от 0 до 999 для одного продукта, для 10 продуктов от 0 до 9999. Пустые эл-ты (такого остатка еще не было) помечаем напр mSum = -1

Process1Product перебирает все комбинации "по столбцу". Напр продукт 7 использует 3 вида сырья. На какой-то итерации 3 циклов у нас напр 5.0, 4.2, 8.1 по каждому сырью - переводим их в остатки (как если бы все бочки еще целые). Пытаемся добавить эти остатки к каждому в предыдущей таблице остатков. При этом всякий раз по mSum мы попадаем на какой-то индекс в новой таблице. Если он пустой - записываем туда новый эл-т, иначе просто ничего не делаем - такой остаток уже есть, неважно как он получен.

Update: деталь реализации. После вычисления mSum провериться был ли уже такой при производстве данного продукта. Чтобы избегать дороговатой операции "добавить к каждому"
« Последнее редактирование: Сентябрь 09, 2016, 10:38 от Igors » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #38 : Сентябрь 09, 2016, 10:32 »

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

Да, и вообще-то интересно как написать "общий for" для перебора в столбце. Ну вот, сейчас опять пойдет "вода"  Улыбающийся
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #39 : Сентябрь 09, 2016, 10:56 »

не надо "каждый с каждым" - остатки то суммируются...
выиграем мизер, потеряем время..
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #40 : Сентябрь 09, 2016, 11:46 »

не надо "каждый с каждым" - остатки то суммируются...
выиграем мизер, потеряем время..
Пусть есть 2 продукта юзающих 2 вида сырья (одни и те же). После вычисления первого продукта имеем остатки, (по первому и второму сырью) напр
Цитировать
(20%. 45%)
(32%. 91%)
и.т.д (первый котейнер)
А для второго продукта
Цитировать
(11%. 12%)
(32%. 21%)
и.т.д (второй котейнер)
Новые комбинации остатков могут образоваться при сложении каждого эл-та первого контейнера с каждым эл-том второго. Поэтому "каждый с каждым" - квадратичный перебор
Записан
Racheengel
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2679


Я работал с дискетам 5.25 :(


Просмотр профиля
« Ответ #41 : Сентябрь 09, 2016, 21:33 »

После того, как для первого продукта остатки посчитались, их надо добавлять к последующим рассчетам и с их учетом подбирать следующие расходы для продуктов 2, 3 и пр.
Записан

What is the 11 in the C++11? It’s the number of feet they glued to C++ trying to obtain a better octopus.

COVID не волк, в лес не уйдёт
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #42 : Сентябрь 10, 2016, 08:24 »

После того, как для первого продукта остатки посчитались, их надо добавлять к последующим рассчетам и с их учетом подбирать следующие расходы для продуктов 2, 3 и пр.
На это ответ уже был
Это не катит для комбинаторики. Напр какой-то путь на предпоследнем шаге худший - но после выполнения последнего шага оказался лучшим.
Записан
Страниц: 1 2 [3]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.082 секунд. Запросов: 22.