Релиб / Программирование / Программирование / Задача простая - решение сложное / Latest Posts

RE: Задача простая - решение сложное

Polirom — Mon, 23 Sep 2002 12:50:00 GMT

Спасибо за советы. Неплохая идея с битами, я попробую ее реализовать. В действительности мне нужны не все комбинации (мат. языком - сочитания), а те, которые удовлетворяют некоторое условие. По сути, эти комбинации являются шифром более сложного объекта, окончательный вид которого можно определить только полным перебором.
Для тех, кому интересно что делает эта прога, могу посвятить несколько строчек:
Сейчас существуют много программ, даже проектов, посвященных решению всем известных нонограмм - японских кроссвордов. Но до сих пор я не встретил, полного решения этой проблемы, тоесть проги которая может решить любую нонограмму, в широком смысле этого слова (решается или не решается, одно или много решений, как убить неоднозначность, решение поисковых задач, и т. п.) Поэтому я решил посвятить лишнее время созданию более углубленного алгоритма (алгоритмов), который(е) мог бы быстро все порешать (Может в будущем получится не плохая РешалкА). Но поскольку я не програмист, а математик, у меня возникают большие трудности в реализации своих идей.
Люди, если кто-то заинтерисовался, и имеет лишнее время, приглашаю к сотрудничеству! А может, знаете тех, кто тоже "болеет" этим - забейте стрелу!(Я не исключаю, возможности совмещения полезного с прятным: вместе немного заработать). Только так: Я НУЖДАЮСЬ НЕ В РЕКЛАМЕ, А В ПОДДЕРЖКЕ!

RE: Задача простая - решение сложное

t1k — Mon, 23 Sep 2002 11:45:00 GMT

2 Disketka:
нет у него другая проблема, ему не все нужны, а только некоторые.
поэтому простым прибавлением бита к предыдущему результату не получится. Надо после каждого прибавления подсчитывать количество включенных битов, и если оно равно определенному числу тогда один из результатов найден.

RE: Задача простая - решение сложное

Mavr — Mon, 23 Sep 2002 09:01:00 GMT

Что ломаешь-то? Может проблема не в оптимизации данного алгоритма, а в принципе подхода, может и не стоит все комбинации перебирать.

RE: Задача простая - решение сложное

Disketka — Mon, 23 Sep 2002 07:06:00 GMT

Перестановки бинарных разрядов на k - позициях - не что иное, как обычный десятичный счет от 0 до 2^к-1.
Начинаешь считать в цикле, а смотришь в двоичном виде.
А быстрее как?
Ведь это просто скорость вывода* на константу. Все равно выводить результаты надо.
Или тебе определенные комбинации нужны?
1)Посмотри книжку
М.О. Асанов "Дискретная оптимизация".
2)Растяни циклы.
3)Перейди на циклы с пост-условиями.
4)Всегда сравнивай с нулем.
5)Перепиши куски на ассемблере.

RE: Задача простая - решение сложное

t1k — Thu, 19 Sep 2002 12:05:00 GMT

проблема в том, что результатов очень много

c из n по к

n!/(k!*(n-k)!) максимальное количество когда k = n/2

поищи в yandex "генерация перестановок" приводятся некоторые алгоритмы
или в google "permutation generation"

Задача простая - решение сложное

Polirom — Wed, 18 Sep 2002 14:25:00 GMT

Предистория.
В процессе создания одной непростой проги, я встретился с проблемой ее быстродействия. После некоторых тестов, оказалось, что тормозит часть ядра основного алгоритма. Но оптимизировать ее оказалось не так уж и просто. Некие ошибки, исправить конечно удалось, но общая картина от этого не изменилась.
Я задался вопросом: можно ли вообще физически ускорить этот фрагмент алгоритма (или придумать другой более быстрый)?
Так как я новичок в решении таких задач, я хочу обратится к професионалам в этом деле (или просто за советом).

В чем суть задачи.
Сгенерировать все комбинации из k элементов на n позициях. (Пример: k=2, n=4 : 1100, 1010, 1001, 0101, 0110, 0011)

Какое должно быть решение.
Из всех существующих алгоритмов придумать самый быстрый.

Вопросы в тему.
Каким образом можно обосновать, что алгоритма быстрее данного, в решении некоторой задачи, нет?
Какие существуют методы (или проги) с помощью которых можно ускорить существующий алгоритм?