Re: Можно ли оптимизировать? | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Простым циклом вроде никак, рекурсией без труда.
|
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Да нет, и циклом без проблем. Только смысла в полном переборе мало. Тут он не ищет суммы, просто перебирает все варианты, но печатает всегда лишь выборку из 16 штук (для оценки скорости перебора). Если задать размер массива в 4 то как раз и получим все искомые выборки.
Например для набора из 200 случайных целых чисел 1+INT(RAND()*1000), поиска суммы 5000 и точности поиска в 1% (т.е. по сути алгоритм генерирует некоторый набор решений в диапазоне от 4950 до 5000, хотя на практике в него обычно попадает и "абсолютно точное решение", т.к. оно, как правило, существует для такого набора чисел) время завершения составляет порядка 16 секунд. Да, алгоритм может и не найти "абсолютно точное" решение, даже если оно и существует. И он очень сильно "просядет" по времени, если в наборе будут не целые, а вещественные числа (в таком случае лучше их заранее округлить, а потом из найденных решений подобрать то, которое не нарушит условие <= искомая_сумма). ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Этот код работает неправильно. Если задать lnSize = 5, то в выводе нет например суммы "1,3,5"
|
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Исходя из вышесказаного (о времени перебора) я думаю упрощу свой алгоритм к следующему виду:
1) Сортирую элементы массива значений по убыванию. 2) Беру первый элемент, если он больше "предела" тогда отбрасываю. 3) Беру первый подходящий и добавляю к нему первый же попавшийся подходящий по спису снизу. 4) И так пока не доберусь до "предела". Изьянов куча зато хоть знаю как сделать. Главная проблема в том, что если взяв, первое попавшееся большое подходящее число, потом можно и не подобрать к нему пару не превысив "предел". А вот с элементов в конце списка верояно можна было бы подобрать и вариант получше. Эвристикой попахивает. Я бы проще глазами всё увидел, чем машинный перебор. Исправлено 1 раз(а). Последнее : travelFox, 21.10.11 11:48 |
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Я же написал, что специально ограничил вывод только 16-ю значениями, чтобы можно было тестировать время перебора для больших размерностей - хочешь видеть все, убери IF (но тогда печать вариантов и прокрутка экрана будут просто дикими для размеров больше 8-10).
2 travelFox Поскольку раздел не основной, я и не стал сразу приводить реализацию алгоритма поиска из википедии (т.к. это неспортивно ). Вечерком могу выложить. ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
Рома Сообщений: 1079 Дата регистрации: 06.06.2001 |
Это один из алгоритмов решения NP-сложных задач - по науке это называется жадный (greedy) алгоритм со стратегией "первый подходящий" (first fit strategy) Исходя из логики задачи я бы его улучшил таким образом (стратегия best fit)
Сортировка массива значений по возрастанию может дать другой результат (как лучше так и хуже) - можно выполнить алгоритм и для этого варианта и потом выбрать лучший из двух результатов. В любом случае это будет быстрее полного перебора возможных вариантов - понятное дело цена за это - всего лишь приблизительный результат Исправлено 2 раз(а). Последнее : Рома, 21.10.11 16:11 |
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Вот потому и интересно было бы от автора темы увидеть некоторый генератор начальных условий (не суть важно - в массиве, или в курсоре, важны единые параметры - в частности RAND(1) или нечто подобное для заполнения - чтобы каждый раз на любой машине получалися одинаковые начальные условия).
Вот потом и можно будет заняться реализацией разнообразных алгоритмов - и сравнением их скорости/точности/красивости ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
Рома Сообщений: 1079 Дата регистрации: 06.06.2001 |
Ну вот моя реализация - случайный поиск с использованием стратегии по улучшению результата, которую я описывал выше.
Также там есть обычный brute force - для сравнения. Фокса под рукой сейчас нет - на C# написано. |
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Роман, но это не та задача - это именно что "выбрать РОВНО A элементов из массива размерностью N". А автор уже уточнил, что на самом деле ему нужно "выбрать ЛЮБОЕ число элементов из массива размерностью A" - это очень близко к формулировке задачи о сумме подмножества. Единственное существенное отличие - нужно не просто проверить факт существования такого подмножества для ТОЧНОЙ суммы, а найти элементы составляющие подмножество с суммой МЕНЬШЕ ИЛИ РАВНОЙ заданной сумме, но, конечно же, пытаясь максимизировать искомую сумму - в идеале выходя на "точную" сумму.
При том очень существенным для выбора алгоритма является какие именно числа в массиве, сколько их там и какая именно "сумма" требуется - для вещественных, если их не округлять и не приводить таким образом к некоторым "масштабированным целым", или просто для "больших целых" и алгоритм динамического программирования, и предложенный мной алгоритм приближённого поиска потребует кучу памяти - для "динамического" алгоритма, например, потребуется массив размером n*s, где n это число элементов, а s - искомая сумма. Если же в массиве есть и отрицательные числа, то наверное придётся расширять s до размера SUM(положительных) + ABS(SUM(отрицательых)). Для алгоритма приближённого поиска требуется всего 1 большой "набор" (он же массив), но его размер приближается к s, где s это искомая сумма. Т.е. для поиска элементов на сумму 150 потребуется существенно меньше и памяти и времени, чем для поиска элементов на сумму 150000. ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
Рома Сообщений: 1079 Дата регистрации: 06.06.2001 |
"ЛЮБОЕ число элементов" - это, я так понимаю, любое ПОДМНОЖЕСТВО элементов? Тогда берем A = 1..N, где A - размер подмножества, N-размер исходного массива. То есть, для решения второй задачи нужно максимум N раз решить первую - из последовательности этих решений мы сможем выбрать лучшее. Значит, если мы можем найти (хотя бы приближенно) решение первой задачи за полиномиальное время, то и вторая будет решаться тоже за полиномиальное время. Если же под "ЛЮБОЕ число элементов" подразумевается новое множество, в которое элементы исходного множества могут входить ЛЮБОЕ число раз - тогда все равно можно свести эту задачу к задаче о подмножествах, так как "ЛЮБОЕ число раз", подозреваю, конечное число (в реальной жизни по другому не бывает - все ресурсы ограничены). |
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Да, любое подмножество.
Да, в википедии описано псевдо-полиноминальное решение методом динамического программирования - его же реализации я видел на rsdn (на паскале ) и ещё где-то. Плюс полиномиальное "приближённое" решение, плюс ссылка на некое "For the case that each xi is positive and bounded by the same constant, Pisinger found a linear time algorith". Полное решение перебором потребует проверки 2^N вариантов, что непрактично для больших N (для фокса уже размер 20 хорошо тормозит, для шарпа, думаю, можно чуть побыстрее сделать, но всё одно размеры исходного массива в 50-100 будут неподъёмными)... ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
В общем раз более желающих нема, приведу фоксовую реализацию вышеупомянутого алгоритма
------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
PaulWist Сообщений: 14625 Дата регистрации: 01.04.2004 |
Игорь.
Поясни смысл:
или это надо понимать как "описка". ------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Преклоняюсь перед Вашим трудолюбием. Читаю-изучаю Ваш труд.
|
Re: Можно ли оптимизировать? | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Та я ж писал - это "на коленке" писанный код. Конечно ALL там не нужен, т.к. он и так по умолчанию подразумевается для SCAN. Вообще этой "проверки" в алгоритме не предусмотрено, просто она вполне логична - зачем шерстить элементы которые априори "неподходят". Да и индекс вместо ORDER BY из той-же оперы... "Подпилить" в этом коде есть чего
"Трудолюбия", кстати, этот код особого не требует - просто буквально переводится алгоритм (представляя курсоры как наборы/массивы/списки), потом по минимуму сводится в 1 команду то что ранее было как 2-3-4 разных команды (IF переходит в FOR условие, создание набора + слияние с другим - в один SELECT ... UNION) и т.п. Там даже имена курсоров сохранены как в описании алгоритма Ну а дописать кусочек который помимо суммирования ещё и запоминает собственно элементы в memo-поле - дело техники. ------------------ WBR, Igor |
Re: Можно ли оптимизировать? | |
---|---|
Рома Сообщений: 1079 Дата регистрации: 06.06.2001 |
Для полноты картины добавил к тесту Игоря еще один из алгоритмов, использующих динамическое программирование.
В кратце - сначала находим "близкое" решение простым жадным алгоритмом, а уже оставшуюся сумму пытаемся получить из разложения на два множества - положительное и отрицательное (для их построения и используется динамическое программирование). Переводил его из C (ссылка на оригинал - в коментариях) - надеюсь, что все правильно. |
Re: Можно ли оптимизировать? | |
---|---|
travelFox Автор Сообщений: 344 Откуда: Червоноград Дата регистрации: 22.02.2011 |
Вобщем я намутил следующее. Не знаю как там на счет эфективности но как-то с горем пополам работает.
И ещё вопрос: при выводе результата пишет все 100 елементов массива даже те у которых нет чисельного значение (.F.). Следующий мой код матерится что данные не совпадают.
[i]Исправлено 11 раз(а). Последнее : travelFox, 17.11.11 00:12 |
© 2000-2024 Fox Club  |