Подбор резисторов из ряда

Michael_K

Я ожидал, что в "оригинальной задаче" написано что-то вроде:

Цитата:

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

Ответ не засчитывается если он побитно не совпадает с заранее известным.

Требуемый резистор передается в формате double, строкой, вычисляется побитно.

Точность не превышает 200 десятичных разрядов.

Что-то в таком духе. Ну то есть более формально, с деталями реализации.

blindman писал(а):

Одно из условий - N задано. Решение должно содержать не более N элементов.

Ага. Я это как-то прощелкал, но принципиально ничего почти не меняется...
Лишнее ограничение - это хорошо.

Добавлено спустя 13 минут 13 секунд:
интересно. Любой трехзначный номинал может быть собран из не более чем трех резисторов E24. Любой четырехзначный - из не более четырех.

blindman

Michael_K, конечно, такие оптимизации хороши. Но недостаток есть - неприменимость к параллельному соединению. :crazy:

Michael_K

Ой... вот тебе и "оригинальная задача"

При произвольном соединении резисторов возможны интересные варианты.
Например:

Код:

---*----1----*----2----*---
   |         |         |
   |         3         |
   |         |         |
   *----4----*----5----*

dccharacter

blindman писал(а):

Понятно. Когда мне надо найти решение, я отправляю вам исходные данные, а вы публикуете ответ

Ну а как еще
Я думал я неоднократно говорил, что используется поиск с эвристикой.

blindman

Michael_K писал(а):

При произвольном соединении резисторов возможны интересные варианты.

Я такое в виду не имел.
Просто если не делать предположений о рядах (кроме того, что они периодичны, только экспонента меняется), то решив задачу для последовательного соединения, переход к решению параллельного соединения делается заменой сопротивлений на проводимости.

dccharacter писал(а):

я неоднократно говорил, что используется поиск с эвристикой

Пока что я вижу только, что он хуже, чем перебор.

Michael_K

blindman писал(а):

Michael_K писал(а):

При произвольном соединении резисторов возможны интересные варианты.

Я такое в виду не имел.

А составители задачи :wink:

?
Допускается произвольное соединение или только последовательно-параллельное?

blindman писал(а):

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

Это-то понятно, но задача, по-моему, далека от той, что вы изначально заявили.

Хотя (на первый взгляд) все равно поразрядно считается, только более утомительно...

Добавлено спустя 17 секунд:
P.S.
Все таки, если не секрет, можно оригинал увидеть?

dccharacter

я не понимаю, что ты называешь перебором? если полный перебор, то это bsf (поиск в ширину), но тогда любая валидная эвристика сделает этот перебор в разы быстрее.
Или ты по какой-то формуле делаешь? Тогда это не перебор.

Michael_K

dccharacter писал(а):

если полный перебор, то это bsf (поиск в ширину)

Поиск может быть не только "в ширину"... (и обычно его называют BFS).

blindman

dccharacter писал(а):

что ты называешь перебором? если полный перебор

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

Michael_K писал(а):

можно оригинал увидеть?

сам придумал. честно

dccharacter

blindman писал(а):

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

ну тогда мой алгоритм делает заведомо меньше итераций
можешь вывести время и количество итераций, затраченных на поиск решения?

Добавлено спустя 8 минут 1 секунду:

Michael_K писал(а):

dccharacter писал(а):

если полный перебор, то это bsf (поиск в ширину)

Поиск может быть не только "в ширину"... (и обычно его называют BFS).

да, я неправильно написал. поиск останавливается при нахождении решения. полный перебор, по определению, нет.
просто bsf найдет гарантированно оптимальное решение, а dsf - почти гарантированно неоптимальное.

Добавлено спустя 6 минут 5 секунд:

Michael_K писал(а):

Не понимаю я этого...

По-моему, во-первых, всегда достижима абсолютная точность.
(ряд резисторов бесконечный, а точность мантиссы ограничена).
Откуда в последнем, например, "тесте" взялось 9.1, если 6.18368996675e+13 - кончается вообще на два нуля ??? Еще и ошибка какая-то осталась!

все числа для теста я генерил рандомно random.random()*10^n, где n - пятнадцать, что ли.
проверка на достижение результата включает точность, у меня она задана 0.1
поскольку я начинал решить задачу с реальными наборами резисторов, у меня резисторы начинаются с 1.0
опять же, ничего не стоит (ну правда, ничего!) сделать множители резисторов и дробными, и вообще, не степенями десятки, а, например, степенями восьмерки.

Michael_K писал(а):

Во-вторых, по-моему, имеет смысл выкинуть плавающую точку нафиг. Считать только мантиссу в целых чмслах или даже как строку. Так увеличится скорость, не будет потерь точности и не нужно будет делать всякие "финты ушами".

В-третьих, я почти убежден, что считать можно последовательно-поразрядно.
Например, в ряду 1,2,3,...,99,100 все значения набираются из одного или двух резисторов из ряда E24, кроме значения 96 - для него надо три резистора. До тысячи - ни одной четверки не попадается!

То есть по предрасчитанной коротенькой табличке мы сразу можем откинуть два-три старших разряда мантиссы. Без поиска вообще!

Я бы рассматривал число, грубо говоря, как строку, которую надо разбить на подстроки с известными весами из словаря-алфавита. Это даст очень быстрый, абсолютно точный, и близкий к оптимальному результат. Я почти уверен, что исключения будут, но их будет немного и их можно тупо изначально зашить.

Не даст это абсолютный и точный результат, так как 5.6+6.8=12.4, твой алгоритм учитывает 2.4, но забывает про старший разряд - 1.

Michael_K

Брр...

dccharacter писал(а):

мой алгоритм делает заведомо меньше итераций

Возможно. Но для начала хорошо бы определиться, что такое итерация. Тем более при сравнении разных алгоритмов.

dccharacter писал(а):

Не даст это абсолютный и точный результат, так как 5.6+6.8=12.4, твой алгоритм учитывает 2.4, но забывает про старший разряд - 1.

Чё?

"Словарь" уже из десяти строк, очевидно, разложит любую вообще мантиссу до любой точности. Возможно неоптимально, но абсолютно точно. Ну то есть берешь тупо по одной цифре и безо всякого поиска (!!!) фигачишь "124" -> "1","2","4" -> "1" "2" "1"+"3" -> 100+20+1+3 - четыре резистора. Неоптимально, но быстро.

Чем больше строк в "словаре", тем оптимальнее будет результат. Причем "оптимальность" растет очень быстро с ростом "словаря".
Например при двухсимвольном словаре "124" разложится на "1" и "24" - то есть на те же два резистора сравнением всего двух вариантов ("1" и "24" - два резистора) и ("12" и "4" - три резистора).
А если словарь будет включать в себя трехзначные строки, то ответ найдется вообще без сравнений.
Получить все трехзначные строки - элементарно (да и можно тупо вбить в программу предрасчитанный массив).

blindman писал(а):

сам придумал. честно

Верю. Тогда формализуйте (и не меняйте условий на ходу

).

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

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

Предлагаю сгенерить тестовый кейс. А лучше "генератор тестового кейса"...

dccharacter

For 124 (precision 0.1):
Target: 124
Solution: 123.9 , resistors used: [120.0, 3.9] , size: 2
Error is: 0.1 (0.080645%)
Nodes expanded: 2

For 124 (precision 0.001):
Target: 124
Solution: 124.0 , resistors used: [120.0, 2.0, 2.0] , size: 3
Error is: 0.0 (0.000000%)
Nodes expanded: 10

Добавлено спустя 2 минуты 5 секунд:
Итерация - это шаг вниз по следующей ветке дерева. Состоит одна итерация из проверки следующего значения на соответствие задаче и на генерацию потомков узла дерева.

Michael_K

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

Цитата:

Поиск в ширину, наверное, неплох, да... если по памяти ограничений нет.

И эта... Что-то ваш "гарантированный" алгоритм не нашел "гарантированно оптимальное" решение... по крайней мере во втором случае.

dccharacter

Ну с эвритикой игрался, не то накрутил
чо сразу троллить-то
For 124:
Target: 124
Solution: 124.0 , resistors used: [24.0, 100.0] , size: 2
Error is: 0.0 (0.000000%)
Nodes expanded: 701
Короче плохо все это, расстроился я
Правильно говорят "Знал бы эвристику, жил бы в Сочи"

Michael_K

Да это я так... не злобно

Я понимаю, что поиск в ширину - неплохой вариант. Я про это, по-моему, сразу и написал....

roboforum.ru

Подбор резисторов из ряда

Кто сейчас на конференции