|
|
|
новичок
участник
Last Login: 23.09.2002 12:47
Сообщ.: 2,
Visits: 23
|
|
Предистория.
В процессе создания одной непростой проги, я встретился с проблемой ее быстродействия. После некоторых тестов, оказалось, что тормозит часть ядра основного алгоритма. Но оптимизировать ее оказалось не так уж и просто. Некие ошибки, исправить конечно удалось, но общая картина от этого не изменилась.
Я задался вопросом: можно ли вообще физически ускорить этот фрагмент алгоритма (или придумать другой более быстрый)?
Так как я новичок в решении таких задач, я хочу обратится к професионалам в этом деле (или просто за советом).
В чем суть задачи.
Сгенерировать все комбинации из k элементов на n позициях. (Пример: k=2, n=4 : 1100, 1010, 1001, 0101, 0110, 0011)
Какое должно быть решение.
Из всех существующих алгоритмов придумать самый быстрый.
Вопросы в тему.
Каким образом можно обосновать, что алгоритма быстрее данного, в решении некоторой задачи, нет?
Какие существуют методы (или проги) с помощью которых можно ускорить существующий алгоритм?
|
|
|
|
|
Supreme Being
участник
Last Login: 12.02.2004 16:41
Сообщ.: 1 756,
Visits: 19 372
|
|
проблема в том, что результатов очень много
c из n по к
n!/(k!*(n-k)!) максимальное количество когда k = n/2
поищи в yandex "генерация перестановок" приводятся некоторые алгоритмы
или в google "permutation generation"
|
|
|
|
|
Junior Member
участник
Last Login: 27.02.2003 8:42
Сообщ.: 11,
Visits: 122
|
|
Перестановки бинарных разрядов на k - позициях - не что иное, как обычный десятичный счет от 0 до 2^к-1.
Начинаешь считать в цикле, а смотришь в двоичном виде.
А быстрее как?
Ведь это просто скорость вывода* на константу. Все равно выводить результаты надо.
Или тебе определенные комбинации нужны?
1)Посмотри книжку
М.О. Асанов "Дискретная оптимизация".
2)Растяни циклы.
3)Перейди на циклы с пост-условиями.
4)Всегда сравнивай с нулем.
5)Перепиши куски на ассемблере.
|
|
|
|
|
Supreme Being
участник
Last Login: 28.10.2004 6:50
Сообщ.: 236,
Visits: 2 597
|
|
| Что ломаешь-то? Может проблема не в оптимизации данного алгоритма, а в принципе подхода, может и не стоит все комбинации перебирать.
|
|
|
|
|
Supreme Being
участник
Last Login: 12.02.2004 16:41
Сообщ.: 1 756,
Visits: 19 372
|
|
2 Disketka:
нет у него другая проблема, ему не все нужны, а только некоторые.
поэтому простым прибавлением бита к предыдущему результату не получится. Надо после каждого прибавления подсчитывать количество включенных битов, и если оно равно определенному числу тогда один из результатов найден.
|
|
|
|
|
новичок
участник
Last Login: 23.09.2002 12:47
Сообщ.: 2,
Visits: 23
|
|
Спасибо за советы. Неплохая идея с битами, я попробую ее реализовать. В действительности мне нужны не все комбинации (мат. языком - сочитания), а те, которые удовлетворяют некоторое условие. По сути, эти комбинации являются шифром более сложного объекта, окончательный вид которого можно определить только полным перебором.
Для тех, кому интересно что делает эта прога, могу посвятить несколько строчек:
Сейчас существуют много программ, даже проектов, посвященных решению всем известных нонограмм - японских кроссвордов. Но до сих пор я не встретил, полного решения этой проблемы, тоесть проги которая может решить любую нонограмму, в широком смысле этого слова (решается или не решается, одно или много решений, как убить неоднозначность, решение поисковых задач, и т. п.) Поэтому я решил посвятить лишнее время созданию более углубленного алгоритма (алгоритмов), который(е) мог бы быстро все порешать (Может в будущем получится не плохая РешалкА). Но поскольку я не програмист, а математик, у меня возникают большие трудности в реализации своих идей.
Люди, если кто-то заинтерисовался, и имеет лишнее время, приглашаю к сотрудничеству! А может, знаете тех, кто тоже "болеет" этим - забейте стрелу!(Я не исключаю, возможности совмещения полезного с прятным: вместе немного заработать). Только так: Я НУЖДАЮСЬ НЕ В РЕКЛАМЕ, А В ПОДДЕРЖКЕ!
|
|
|
|