Рекурсивный алгоритм, определяющий группу чисел из массива, чтобы сумма=m

Автор темы cantyman67 (Bagira) 
ОбъявленияПоследний пост
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
ОбъявлениеКниги по математике и экономике в добрые руки!10.08.2023 09:45
06.07.2005 02:41
Swine-Heart algorithm's code
Спасибо большое Saha !!!
За вашу отзывчивость и желание помочь.
Поверьте ваши усилия не пройдут даром - ваш Swine-Heart algorithm's code будет детально рассмотрен и изучен, надеюсь наше сотрудничество на ниве знаний и во имя знаний - будет продолжаться.
С уважнием Bagira.
06.07.2005 03:00
Приглашение к участию обсуждения Swine-Heart algorithm's code
Надеюсь количество участников этой темы увеличится, отдельное спасибо также вам egor и maxal.
06.07.2005 03:20
это же бабл-гам! экспоненциальный к тому же
Во-первых, скушались все индексы [ i ], обычно код оборачивают во что-то типа [ code ] ... [ /code ], но на этом форуме оно не работает. ;-(

А во-вторых, это обычное динамическое программирование, ничего революционного. Проблема в том, что оно требует O(m) вычислений и столько же памяти. Т.е. приведенный алгоритм является экспоненциальным.
06.07.2005 03:22
нечего тут обсуждать
Динамическое программирование. Примерно тоже самое, что предлагал egor. Сложность экспоненциальная.
06.07.2005 20:21
Уверены ?
Цитата

maxal писал(а) :
А во-вторых, это обычное динамическое программирование, ничего революционного. Проблема в том, что оно требует O(m) вычислений и столько же памяти. Т.е. приведенный алгоритм является экспоненциальным.
Если не ошибаюсь, алгоритм является экспоненциальным, если входные его данные сидят в показателе степени какого-нибудь числа, - двойки, например. Причём здесь O(m) ? Это более чем удовлетворительная сложность ( разве что log может спустить на землю ) и она является полиномиальной. Причём здесь экспоненциальность ? А то что это динамическое программирование, - так я не спорю. Методы динамического программирвоания всегда отличались красотой. Во всем известной задаче на покрытие метод динамического программирования имеет действительно экспоненциальную сложность, однако оргинальность его идеи неоспорима.
P.S. Если точнее, в нашей задаче не O(m), а O(k*m), где k- длина массива.



Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means !
06.07.2005 21:57
конечно
Помните, что дано число m? Какая его длина? Очевидно, длина пропорциональна log(m).
Далее, m = 2^log(m) - вот вам и экспонента.

Другими словами, можете вы решить задачу для m=10^6, а для m=10^10 или для m=10^100 ? Боюсь, что последнее предложенному алгоритму не под силу. А вот, например, алгоритму описанному на http://www.mathforum.ru/forum/read/1/4870/4940/#4940
m=10^100 вполне по зубам. А все потому, что тот алгоритм полиномиальный.
Чуствуете разницу?

07.07.2005 23:32
Решение исходной задачи
В дополнение к предыдущим версиям решения исходной задачи предложенные egor- хочу предложить к обсуждению ещё 2 версии:

а)
precondition: рекурсивный алгоритм получает параметры: массив A, r=n ,Sum=m
postcondition: алгоритм выдаёт True или False

SUBSET-SUM (A, r, Sum)
1 if Sum = 0
2 then return True
3 if r < 1
4 then return False
5 return SUBSET-SUM (A, r - 1, Sum) or SUBSET-SUM (A, r - 1, Sum- A[r])


P.S. SUBSET-SUM (A, r - 1, Sum) <=>обработай массив величины=r - 1 в котором есть член A[r]
SUBSET-SUM (A, r - 1, Sum - A[r]) <=>обработай массив величины=r - 1 в котором отсутвует член A[r]
Это экспоненциальный алгоритм
T(n) = O(2^n).

б) итеративный алгоритм использует вспомогательный stack - M,
precondition: алгоритм получает параметры: массив A, r=n ,Sum=m
postcondition: алгоритм выдаёт True или False

SUBSET-SUM (A, r, Sum)
1 found = False
2 PUSH (M, (r, Sum))
3 while not found and not EMPTY-STACK (M)
4 do (r, Sum) = POP (M)
5 if Sum = 0
6 then found = True
7 else if r >= 1
8 then PUSH (M, (r - 1, Sum))
9 PUSH (M, (r - 1, Sum - A[r]))
10 return found

P.S. PUSH (M, (r - 1, Sum)) <=>обработай стэк M, величины=r - 1 в котором есть член A[r]
PUSH (M, (r - 1, Sum - A[r])) <=>обработай стэк M, величины=r - 1 в котором отсутвует член A[r]

Интересно ваше мнение форумчане-какие плюсы и минусы у каждого из этих 2 алгоритмов?

08.07.2005 00:28
Weird...
Цитата

maxal писал(а) :
Помните, что дано число m? Какая его длина? Очевидно, длина пропорциональна log(m).
Далее, m = 2^log(m) - вот вам и экспонента.
Что такое длина числа m ? Первый раз втречаюсь с таким понятием. И зачем нам какой-то log (m) совать в степень ?
Цитата

Другими словами, можете вы решить задачу для m=10^6, а для m=10^10 или для m=10^100 ? Боюсь, что последнее предложенному алгоритму не под силу.
Возможно. По крайней мере, я не проверял опытным путём, так что промолчу.
Цитата

А вот, например, алгоритму описанному на http://www.mathforum.ru/forum/read/1/4870/4940/#4940
m=10^100 вполне по зубам. А все потому, что тот алгоритм полиномиальный.
Чуствуете разницу?
Здесь я не решусь с вами спорить, но подозрения у меня есть. Во-первых, у вас числа два. Во-вторых, они оба взаимно простые. В-третьих, вы где-то там "не ограничили общность". Все эти три пункта, конечно, может и не ограничивают так называемой общности, и алгоритм действительно делает своё "полиномиальное" дело. Но уж больно халявно всё это выглядит... Может, предложите строго формализовыанный алгоритм, для произвольного набора чиел, а не для пары и т.п.? Тогда действительно можно будет посмотреть и положить конец дискуссиям. Знаете ли, сколько учусь, постоянно с недоверием отношусь к фразам "не ограничивая общности" ( как жизнь показывает, недаром ) Под этим, кажись, скрывается обыкновенная природная халявность. А если начать капать глкбже, там такое может вылезть... Много всяких людей отучивается от глубинной рутинной работы, останавливаясь на уровне сырой идеи. Жаль, но это, как правило, гроша не стоит.



Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means !
08.07.2005 00:52
это по незнанию
Цитата

Saha писал(а) :
Цитата

maxal писал(а) :
Помните, что дано число m? Какая его длина? Очевидно, длина пропорциональна log(m).
Далее, m = 2^log(m) - вот вам и экспонента.
Что такое длина числа m ? Первый раз втречаюсь с таким понятием. И зачем нам какой-то log (m) совать в степень ?

Ну, батенька, Вам надо почитать хотя бы основы теории сложности вычислений. Без знания их рассуждения о сложности становятся профанацией.
Можно начать с http://www.mccme.ru/free-books/matpros5.html или .

Вкратце: сложность алгоритма - есть функция от длины входа и выхода. Длина - число битов (0 и 1) требуемое для записи числа. Длина целого неотрицательного числа примерно равна двоичному логарифму из этого числа.

Далее, что является входом рассматриваемой задачи? Это числа m, n, и n чисел массива a[], скажем, максимальное из которых A. Таким образом, длина входа будет примерно log(m) + n*log(A). Откуда, грубо говоря, сложность полиномиального алгоритма для этой задачи может полиномиально зависеть от n и log(m), но не от m. Дело в том, что если сложность зависит полиномиально от m, то она зависит экспоненциально от длины m, так как m=2^log(m) - экспоненциальная функция от log(m).

Цитата

Цитата

Другими словами, можете вы решить задачу для m=10^6, а для m=10^10 или для m=10^100 ? Боюсь, что последнее предложенному алгоритму не под силу.
Возможно. По крайней мере, я не проверял опытным путём, так что промолчу.

А тут и проверять не надо. Невооруженным глазом видно, что в Вашем алгоритме используется массив размера m и цикл до m. При m=10^100 такие операции практически неосуществимы.

Цитата

Цитата

А вот, например, алгоритму описанному на
http://www.mathforum.ru/forum/read/1/4870/4940/#4940
m=10^100 вполне по зубам. А все потому, что тот алгоритм полиномиальный.
Чуствуете разницу?
Мы о какой задаче здесь говорим ? По этому адресу предложено именно решение моей задачи или задачи исходной темы форума ? ( sorry, в лом смотреть )

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

08.07.2005 20:17
Согласен
Ух ты-ы-ы ! Честное слово, введённое вами определние я слышу впервые ! И всё никак не могу взять в толк, причём здесь двоичное представление числа m, а не оно само. Но разъяснять не надо, я только убедился, что МЫ ДЕЙСТВИТЕЛЬНО РАЗГОВАРИВАЛИ НА РАЗНЫХ ЯЗЫКАХ : вы, видимо, всё это время посвящали меня в какие-то специальные моменты профессиональной теории алгоритмов ( я имел, конечно, дело с машинами Тьюринга, где встречалась длина входа как число единичек или тому подобной дряни - это хоть отдалённо с вашими словами соприкасается ? ), я же использовал самые обыкновенные понятия алгоритма как набора интуитивных операций, где основной вклад в сложность дают всевозможные циклы. Например, сортировка пузырька даёт O(n^2), быстрая сортировка даёт O(n*log n) и т.п. Теперь вы поняли, какими терминами я оперировал всё это время ? Именно с моей точки зрения алгоритм Харта имеет прекрасную полиномиальную сложность. Вопрос из любопытства : а зачем используются такие понятия, как длина числа ? Это принципиальный момент ? Это актуально в прикладной области или это бессмысленный пережиток чистой дискретной математики ? Спасибо за ваш ответ.
В общем, я бы попросил вас, если вам не сложно, предъявить здесь строго формализованный алгоритм, на который вы ссылаетесь. Фразы типа "рассмотрим два чиcла" или "не ограничивая общности" не производят должного эффекта. Остановиться на сырой идее и пропустить мимо себя якобы рутинную, черновую работу ( которую многие высокомерно считают ниже себя ) - это даже не пол дела. Увы, так всегда показывал мой опыт. Прикрываясь этими фразами, многие авторы учебников и лекторы просто дают волю своей халявности - обыкновенной человеческой халявности. Думаю, если здесь будет представлен точный алгоритм для произвольного набора чисел, тогда дискуссиям будет положен конец, и один из двух алгоритмов достойно займёт первое место по скорости выполнения.



Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means !
08.07.2005 21:05
не упорствуйте
Цитата

Saha писал(а) :
МЫ ДЕЙСТВИТЕЛЬНО РАЗГОВАРИВАЛИ НА РАЗНЫХ ЯЗЫКАХ : вы, видимо, всё это время посвящали меня в какие-то специальные моменты профессиональной теории алгоритмов ( я имел, конечно, дело с машинами Тьюринга, где встречалась длина входа как число единичек или тому подобной дряни - это хоть отдалённо с вашими словами соприкасается ? ), я же использовал самые обыкновенные понятия алгоритма как набора интуитивных операций, где основной вклад в сложность дают всевозможные циклы.

В том-то и дело, что язык один. Просто Вы пытаете "интуитивно" использовать понятия, о которых имеется слабое представление, в то время как у них существует чёткое определение.

Цитата

Например, сортировка пузырька даёт O(n^2), быстрая сортировка даёт O(n*log n) и т.п. Теперь вы поняли, какими терминами я оперировал всё это время ? Именно с моей точки зрения алгоритм Харта имеет прекрасную полиномиальную сложность.

НЕТ, НЕТ и еще раз НЕТ!
Алгоритмы O(n^2) и O(n*log n) для сортировки действительно являются полиномиальными, потому что n здесь - размер сортируемого массива (т.о. длина входа есть ~ n*log(A)).
В рассматриваемой задаче также есть массив длины n, но плюс к этому число m не является размером чего-либо, просто числом длины ~ log(m). Поэтому алгоритм, например, сложности O(n^2 * log(m)) для ее решения был бы полиномиальным, но алгоритм сложности O(n*m) является экспоненциальным, увы.

Цитата

Вопрос из любопытства : а зачем используются такие понятия, как длина числа ? Это принципиальный момент ? Это актуально в прикладной области или это бессмысленный пережиток чистой дискретной математики ? Спасибо за ваш ответ.

Конечно приципиальный! Люди хотят что-бы объём вычислений был соразмерен с объёмом данных. Если это так, то задача будет "решабельной" при любом объёме входных данным; нет - нет.

В этой связи стоит также упомянуть знаменитую проблему P != NP, за решение которой дают миллинон долларов. Наверное, не просто так.

Цитата

В общем, я бы попросил вас, если вам не сложно, предъявить здесь строго формализованный алгоритм, на который вы ссылаетесь. Фразы типа "рассмотрим два чиcла" или "не ограничивая общности" не производят должного эффекта.

Тогда увы. Если Вам так трудно найти и разобрать указанные понятия, то разжевывать я не собираюсь. И так уже наша дискуссия становится чрезчур утомительной.

Цитата

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

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

11.07.2005 00:43
Поищу статью
Цитата

Полиномиального алгоритма не будет. Это NP-полная задача. Когда я говорил "легко решается", я подразумевал случай фиксированного n. Для каждого фиксированного малого n можно указать полиномиальный алгоритм, но их сложность растет экспоненциально с ростом n.
Ну вот мы и пришли к благополучному завершению глупого спора. Свине-хартовский алг. удобен своей краткостью, простотой ( всего лишь два цикла ), не требует специальных вызовов функций, рекурсий и тому подобной дряни. И вообще код на уровне школьного понимания. Даст бог, двойной цикл сразу провалится в кэш и решит все проблемы быстродействия. Правда, в предельных случаях могут возникнуть проблемы с выделением памяти, но что поделать ? Да и сама природа задачи требует большого объёма памяти ( если числа астрономические ). А понятия NP, не NP - экономистов, химиков и остальных не интересует. O(k*m) - и точка ( с этим даже вы, maxal, не поспорили. А получается это действительно "интуитивным" подсчётом шагов в циклах ).
Видимо, именно в связи с вышесказанным алг. порадовал многих современников. Найду ссылку или статью - обязательно сошлюсь, там всё будет написано. Но это точно не моя фантазия, я сам держал текст статьи на англ. яз.. Удачи ! Bye ! :-)



Strength... is the only thing that matters in this world. Everything else is just a delusion for the weak. I'd say the end more than justifies the means !
16.07.2005 14:22
Псевдополиномиальность и историческое замечание
Листаю книгу Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи" (написана в 1978). В параграфе 4.2 (Задачи с числовыми параметрами и сильная NP-полнота) как раз подробно обсуждается задача о разбиении и алгоритм динамического программирования. К тому, что уже было сказано на форуме, можно добавить совсем чуть-чуть.

Описанный здесь алгоритм с двумя циклами - классический пример "псевдополиномиального по времени алгоритма" (временная функция ограничена сверху полиномом от двух переменных: длины входа и максимального числового параметра).

Историческое замечание.
Цитата

Гэри и Джонсон писали:
Оказывается, что задачу РЮКЗАК можно решить за псевдополиномиальное время с помощью метода динамического программирования. Этот метод, аналогичный методу, использовавшемуся при решении задачи РАЗБИЕНИЕ, изложен в работе [98]. Все известные нам алгоритмы с псевдополиномиальным временем работы основаны на этом методе.

[98] Dantzig, G. B. [1957], "Discrete-variable extremum problems," Operations Res. 5, 266-277.

31.03.2007 14:10
Рекурсивный алгоритм, определяющий группу чисел из массива, чтобы сумма=m
Option Base 1

Sub МассивСумма()
Dim isxArray()
Dim i As Integer
Dim j As Integer
Dim k As Integer
Dim a As Integer

Dim SodJach As Double
Dim pSum As Double
Dim XSum As Double

Dim str_msg As String


i = 0

Do
i = i + 1
SodJach = ActiveCell.Value
If ActiveCell.Value = 0 Then Exit Do
ReDim Preserve isxArray(i)
isxArray(i) = SodJach
ActiveCell.Offset(1, 0).Range("A1").Select
Loop 'Создан массив размером (i-1)

XSum = Sheets("Лист2").Range("B1")
iz = 0
For k = 1 To i - 2
For j = k + 1 To i - 1
pSum = isxArray(k) + isxArray(j)
If pSum = XSum Then
iz = iz + 1
ActiveSheet.Cells(1, iz + 5) = isxArray(k)
ActiveSheet.Cells(2, iz + 5) = isxArray(j)
str_msg = str_msg & isxArray(k) & ":" & isxArray(j) & ";"
End If
Next
Next
MsgBox "Слогаемые: " & str_msg, , _

str_msg = "" 'Выполнен перебор 2 слогаемых


If i - 1 = 3 Then Exit Sub
iz = 0
For k = 1 To i - 3
For j = k + 1 To i - 2
For a = j + 1 To i - 1
pSum = isxArray(k) + isxArray(j) + isxArray(a)
If pSum = XSum Then
iz = iz + 1
ActiveSheet.Cells(4, iz + 5) = isxArray(k)
ActiveSheet.Cells(5, iz + 5) = isxArray(j)
ActiveSheet.Cells(6, iz + 5) = isxArray(a)
str_msg = str_msg & isxArray(k) & ":" & isxArray(j) & ":" & isxArray(a) & ";"
End If
Next
Next
Next
MsgBox "Слогаемые: " & str_msg, , _

str_msg = "" 'Выполнен перебор для 3 слогаемых

End Sub
Для дальнейшего перебора на большее число слогаемых нужно добавлять циклы For Next. Программа написана в VBA для Exel (в столбце А начиная с ячейки A1 расположен одномерный массив, в ячейке B1 сумма m. Программа протестировна на практике без проблем. Кто предложит упростить на других языках или в сочетании языков упростить написание кода для увеличения числа слогаемых?
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти