Алгоритм поиска оптимального сочетания параметров\ресурсов по идеальному значению
- Войдите на сайт для отправки комментариев
Втр, 09/09/2014 - 15:26
Доброго дня! Задача в следующем:
Есть "идеальная" комбинация значений которые мы хотим получить, это может быть 100 значений, но для простоты возьмем 3, к примеру: 30 40 70.
И есть массив значений которыми мы располагаем, для простоты пусть их будет 3:
1) 10 10 10
2) 40 20 60
3) 25 50 30
Здача скомбинировать имеющиеся значения так, чтобы они были как можно ближе к искомому. При этом можно брать значения с множетелем, например: 0.3* (1)+0,2*(2)+(3) и т.п.
На прктике значений будет больше чем 3, возможно пару десятков, поэтому перебирать все возможные комбинации и сравнивать с эталонным, и затем выбрать вариант с наименьшим расхождением - это может затянутся на долго...
Уверен что есть более локоничное решение, т.к. по сути это задача на поиск оптимального маршрута и т.п, к сожалению под рукой нет справочника по логистике, хотя в институте помню решали подобные задачки вручную, значит формула существует.
Помогите разобраться с алгоритмом\логикой решения такой задачи.
Спасибо.
Может это у меня от недосыпания, но я прочитал Вашу задачу так:
есть n-количество чисел. Как определить что они отвечают требованиям x и y? Причем все параметры могут меняться по рандому.
,Спасибо за ответ) Нет наборы параметров не меняются, просто в реальности это будет не 3 параметра, а 33 например. Ладно, приведу более ясный пример, раскрыв прикладной смысл:
К примеру нам нужно получить раствор 3 микроэлементов в заданной пропорции (например 30 70 50), но самих элементов в растворимой форме у нас нет, есть только их соединения в различной форме, это то что мы имеем. Скажем у нас есть 5 соединений которые мы можем использовать, они содержат нужные нам элементы в следующей пропорции:
10 20 10
30 50 40
50 70 70
50 10 30
40 40 40
Наша задача смешать эти соединения в таком соотношении, чтобы полученный раствор содержал элементы в пропорции, наиболее соответствующей искомой (30 70 50)
Надеюсь сейчас все предельно ясно, чувствую что существует определенный алгоритм решения этих задач, т.к. они должны встречаться не так редко, но никак не соображу какой.
вот задачки в школе задают))
может все-таки на математический форум?
)) Так задача то прикладная, я же описал конкретный пример, где нужен такой калькулятор, а математический форум пусть даже и даст ответ, но он будет выглядеть как формула ничего не говорящая (мне по крайней мере) о логике работы. Например формула pid регулятора
Но перевести её в массивы, циклы и переменные все равно что заново вывести.
Поэтому мне нужна не формула, а общую логику, а как этот алгоритм обернуть в код, это я уже постарась сообразить.
Попробуйте сначала решить задачку на сортировку чисел в заданой последовательности. А потом вас осенит как делать выборки для получения заданной суммы.
если учесть, что это задача может и не иметь решения (т.е невозможно, используя существующие соединения, получить раствор с нужными параметрами), то все сведется к подбору с максимально допустимым отклонением. т.е численные методы, к примеру, метод ньютона в n-мерном пространстве.
в любом случае без серьезной матобработки не обойтись, шапкозакидательство не пройдет. у меня диплом был по трехмерному подбору, так затраты на матобеспечение/программирование делились примерно 50/50
Выяснил что подобные задачи относятся с линейному программированию и решаются Симплекс-методом или методом Гаусса.. Найти понятное описание этих методов это задачка та еще... На первом курсе мы решали матрицы этими способами, но снова вникать в это ой как не хочется... Надеюсь найти понятный кусок кода а лучше библиотеку в идеале)
Может кто-то знает где почитать как решается Симплекс и гаусс именно в программировании, т.е. на языке логических операторов,
Интуиция мне подсказывает, что это NP-полная задача и решается только перебором вариантов.
Матрицей можно решить систему линейных уравнений, а здесь не вижу СЛУ.
Ну почему же? можнно составить ряд ограничений (неравенств) и целевую функцию. Перебор вариантов конечно будет, но в ограниченном диапазоне, что и делает симплекс.
Ну почему же? можнно составить ряд ограничений (неравенств) и целевую функцию. Перебор вариантов конечно будет, но в ограниченном диапазоне, что и делает симплекс.
ой, ну так и делайте тогда. только пометочку себе сделайте avr не шибко приспособлены под математику.
А интересно, как господа собрались искать нецелые коэффициенты перебором? Точность ограничивать? А из каких соображений? Волюнтаризм понимаете!
Задачка пошти тривиальная. Называется разложение вектора по базису. Доступно - http://ru.onlinemschool.com/math/library/vector/basis_expansion/ Ваша "идеальная" комбинация - раскладываемый вектор N-мерный, в примере N=3, а из "массива значений" т.е. массива векторов (которых у Вас похоже >>N) необходимо отобрать N линейно независимых. Здесь по сути перебором с составлением и решением систем уравнений. Вполне решабельно. Как отобрали независимые - ОК, составили из них матрицу, обратили, перемножили с идеальным вектором и получили решение. Точное причем. Остальные вектор из массива значений - в топку, они тока размажут решение в множество решений. Плохой случай - нет нужного числа линейно независимых. Здесь прийдется определятся что такое у Вас "чтобы они были как можно ближе к искомому" в математическом виде. Это даст возможность записать целевую функцию и искать её минимум известным путем - дифференцировать по частичным производным и т.д. Перед этим полезно понизить размерность вектора за счет исключения линейно зависимых координат.
Тока всё это явно не AVR-овская задача. А симплекс-метод не мучте, он из дискретной оптимизации, где есть в условии неравенства-ограничения. У Вас их нет.
Лучшее решение - поймать толкового студента. Это 1-й курс вышки инженерных специальностей.
Logik
Спасибо!
Вот только этот способ не подразумевает ограничений, а они необходимы хотябы за тем, что количество раствора может быть равно 0 (раствор не используется), но не может быть отрицательным.
Т.е. в у казанном на том сайте примере, должны быть ограничения хотя бы: x,y>=0
"Как можно ближе к искомому" в моем понимании, это задаваемая погрешность (k).
ТОгда это будут неравенства:
x+y>p-(0,5*k);
x+y<p+(0,5*k)
А это уже нужно решать симплексом, верно?