roboforum.ru

Помогите решить задачку. Надо придумать алгоритм набора произвольного сопротивления Rx из N последовательно соединенных резисторов стандартных номиналов. Пока решаю перебором, но надо что-то пошустрее.

Простейший алгоритм - на каждом шаге берем максимальное сопротивление R из ряда, не большее Rx. Затем присваиваем Rx=Rx-R, и повторяем. Останавливаемся при достижении заданной точности, или после N итераций. Хотя это конечно и быстро, но по сравнению с перебором во многих случаях дает либо более длинные цепочки при той же точности, либо меньшую точность при той же длине цепочки.

Гуглить
Линейное программирование
Симплекс-метод

ЕМНИП

Добавлено спустя 5 минут 19 секунд:
Кстати, у вас перебор оптимизирован? например, когда перебираем цепочки, все время храним "чемпиона" - самую лучшую из найденных. Перебирая остальные, заранее отбрасываем цепочки которые достигли той же длины. Такая простецкая оптимизация очень часто разгоняет переборные алгоритмы в десятки раз.

"Задача о ранце", не? Ну, вариация...
Вы реализовали "Жадный алгоритм"
Не существует оптимального решения.

Добавлено спустя 43 секунды:
N - какого порядка?

Добавлено спустя 2 минуты 8 секунд:
А может и не "задача о ранце".... Хм...

Добавлено спустя 4 минуты 20 секунд:

elmot писал(а):когда перебираем цепочки, все время храним "чемпиона" - самую лучшую из найденных.

Это называется Метод ветвей и границ http://ru.wikipedia.org/wiki/%D0%9C%D0% ... 0%B8%D1%86

elmot писал(а):когда перебираем цепочки, все время храним "чемпиона" - самую лучшую из найденных. Перебирая остальные, заранее отбрасываем цепочки которые достигли той же длины.

Да, такое есть. Но все равно скорость очень быстро падает с ростом длины ряда.

Michael_K писал(а):Не существует оптимального решения.

Это понятно.

Какого порядка цифры? Ряд резисторов действительно "стандартный" (в нем можно найти закономерность?)...
Он неограничен в обе стороны? (то есть от пикоом до тераом )
Если ряд не очень длинный, то, вероятно, имеет смысл дополнить его наборами всех "пар резисторов" (троек, четверок и т.д.)
А потом уже натравить ваш "жадный" алгоритм.

И чем ограничен перебор? Числом резисторов в цепочке? Точностью попадания в значение?

А какой интерес? Академический? Или практчиеский? Если практический, то плясать надо от:
1) Числа резисторов -> чем меньше, тем лучше
2) Наличия резисторов -> Давно замечено, что всегда не хватает резисторов 1К, 4К7, 10К и т.д., но полно всяких 1К2, 6К2 и т.д.
3) Точности -> Зачем мне подбирать на пуллап связку резисторов 5245Ом, если я могу воткнуть любой в диапазоне 2К-10К???

dccharacter, а ссылка тут при чем тут каким боком?

Michael_K, задача общего характера. То есть ряд бесконечный. И да, он именно стандартный. Уже для E24 размер массива с парами будет внушительным.

Максимальная точность и минимальное число резисторов при количестве резисторов не больше N. Приоритет у точности.

Добавлено спустя 1 минуту 31 секунду:
dccharacter, задача это. математическая

Шкала логарифмическая (приблизительно). То есть, грубо, можно подбирать значения "слева направо".
Полный перебор - это алгоритм с отсечениями в небольшом диапазоне (перебор от Rx/2 до Rx - для ряда E24 это "всего" 7 или 8 значений).
Надо покумекать...

короче обычный bsf поиск всегда найдет оптимальное решение с точки зрения и точности и количества резисторов.

Добавлено спустя 1 час 37 секунд:
Без эвристики на больших значениях время поиска стремилось к бесконечности. Приделал простенькую эвристику, которая сперва проверяла резисторы, максимально близкие к искомому значению. Считает почти мгновенно:

Please enter target resistance: 575675677
Solution: 575675677.0 , resistors used: (1.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 2200000.0, 160000.0, 15000.0, 620.0, 56.0)
Error is: 0.0 (0.000000)

Добавлено спустя 3 минуты 27 секунд:
Please enter target resistance: 56757567.7
Solution: 56757567.7 , resistors used: (1.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 2000000.0, 150000.0, 7500.0, 62.0, 4.7)
Error is: 0.0 (0.000000)

dccharacter писал(а):короче обычный bsf поиск всегда найдет оптимальное решение

Вы как отличаете оптимальное решение от неоптимального?

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

blindman писал(а): То есть ряд бесконечный. )

а я хотел ГА предложить... если на конечных рядах работать..

в андроид маркете есть готовые приложения (наша и забугорная)