|
Здравствуйте! Есть ли какой-то еще способ, ведь задача сама по себе довольно проста? задан 19 Сен '14 10:30 
maybe |
|
Цель: найти все возможные комбинации коэффициентов - Странная цель... У Вас 18 коэффициентов, которые принимают 11 значений... Итого имеете множество, содержащие $%11^{18}$% элементов... Если требуемому неравенству удовлетворяет $%0.001\%$%, то Вам надо выписать порядка $%10^{13}$% элементов... Если таки у Вас задача найти экстремум какого-то выражения, то такую задачу можно сводить к задаче дискретного (целочисленного) программирования и решать, например, методом ветвей и границ... отвечен 20 Сен '14 1:47 
all_exist @all_exist: я так понял, что 18 -- это число массивов, а сами они могут быть очень длинными. И нужно для каждого элемента массива проверять, что он не вышел за пределы, а это дело долгое.
(20 Сен '14 1:50)
falcao
@falcao, я так понял, что 18 -- это число массивов - я тоже так понял... на длину массива я выше не закладывался... Под числом элементов я имел в виду число наборов коэффициентов...
(20 Сен '14 2:08)
all_exist
@all_exist: тогда $%11^{18}$% -- это оценка числа операций для одноэлементного массива, то есть даже для коротких массивов длиной 10 получилось бы очень много.
(20 Сен '14 2:23)
falcao
@falcao, это число наборов коэффициентов... а уж каким условиям они удовлетворяют - это другой вопрос...
(20 Сен '14 2:26)
all_exist
@all_exist: вообще-то Вы правы -- там же при каждом таком наборе придётся проверять какие-то $%n$% условий, то есть произойдёт всего лишь умножение на величину порядка длины массива. Я как следует не вдумался, и мне показалось, что операций будет очень много. Здесь, конечно, число вариантов тоже большое, но не безумно большое.
(20 Сен '14 2:36)
falcao
|
Для задач такого типа чаще всего не известно каких-либо быстрых алгоритмов. Есть целая теория, которая занимается подобными вопросами. Мне кажется, что к данной задаче, скорее всего, какая-нибудь NP-полная, то есть задача "максимальной переборной сложности". Типа "задачи о рюкзаке" или чего-то подобного. Есть целые списки таких задач, про которые известно, что вопрос о "быстром" алгоритме эквивалентен знаменитой проблеме из теории вычислительной сложности, символически обозначаемой в виде P=NP. Здесь, судя по всему, даже для случая чисел 0, 1 вместо -5 .. 5, что-то подобное имеет место.