Здравствуйте!
Проблема такая: имеется 18 массивов одинаковой величины, также есть 18 коэффициентов от -5 до 5, на которые мы умножаем массивы. Цель: найти все возможные комбинации коэффициентов, при которых все элементы суммарного массива не превышают заданного числа по модулю.
На данный момент на решение данной задачи грубым перебором выходит 11 ЛЕТ!!!

Есть ли какой-то еще способ, ведь задача сама по себе довольно проста?
Спасибо.

задан 19 Сен '14 10:30

изменен 19 Сен '14 11:56

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Для задач такого типа чаще всего не известно каких-либо быстрых алгоритмов. Есть целая теория, которая занимается подобными вопросами. Мне кажется, что к данной задаче, скорее всего, какая-нибудь NP-полная, то есть задача "максимальной переборной сложности". Типа "задачи о рюкзаке" или чего-то подобного. Есть целые списки таких задач, про которые известно, что вопрос о "быстром" алгоритме эквивалентен знаменитой проблеме из теории вычислительной сложности, символически обозначаемой в виде P=NP. Здесь, судя по всему, даже для случая чисел 0, 1 вместо -5 .. 5, что-то подобное имеет место.

(19 Сен '14 20:49) falcao
10|600 символов нужно символов осталось
0

Цель: найти все возможные комбинации коэффициентов - Странная цель... У Вас 18 коэффициентов, которые принимают 11 значений... Итого имеете множество, содержащие $%11^{18}$% элементов... Если требуемому неравенству удовлетворяет $%0.001\%$%, то Вам надо выписать порядка $%10^{13}$% элементов...

Если таки у Вас задача найти экстремум какого-то выражения, то такую задачу можно сводить к задаче дискретного (целочисленного) программирования и решать, например, методом ветвей и границ...

ссылка

отвечен 20 Сен '14 1:47

@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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×938
×851

задан
19 Сен '14 10:30

показан
388 раз

обновлен
20 Сен '14 2:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru