roboforum.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

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

короче обычный 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)

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

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