roboforum.ru

Michael_K писал(а):Тогда формализуйте (и не меняйте условий на ходу ).

Даны:
- массив S из M положительных вещественных чисел, упорядоченный по возрастанию. Первый элемент массива - 1.0, все элементы меньше 10, элементы не повторяются
- положительное вещественное число R
- целое N большее нуля
- положительное вещественное число e

Найти:
массив D из n вещественных чисел, каждое из которых можно представить в виде s*(10^k), где s - один из элементов массива S, k - произвольное целое, такой, что n<=N, и |R-sum(D)|<=e.
Из множества решений выбрать либо массив минимальной длины, либо массив с минимальным значением |R-sum(D)|. Это критерий оптимизации решения, можно выбрать любой, или оба с произвольным приоритетом - на усмотрение реализатора алгоритма

Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче

Хм. Широко взяли....
Видимо, кроме переборов тут предложить нечего...
Куда перебирать и чем ограничивать - дело десятое - всегда найдется "плохой" набор данных.
Но попробовать можно.

blindman писал(а):Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче

Ну... OK.

цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм?

а то я ради интереса на ГА напишу ) если вариант второй..

Единственное, что не сделал - тормоз по количеству резисторов:

Resistance is: 575675677
Next resistor is 56.0 *10^ 7
Path: [560000000]
Resistance is: 15675677
Next resistor is 15.0 *10^ 6
Path: [560000000, 15000000]
Resistance is: 675677
Next resistor is 62.0 *10^ 4
Path: [560000000, 15000000, 620000]
Resistance is: 55677
Next resistor is 51.0 *10^ 3
Path: [560000000, 15000000, 620000, 51000]
Resistance is: 4677
Small resistance left, using search to solve for 4677
Solution: [560000000, 15000000, 620000, 51000, 27.0, 750.0, 3900.0] (7 elements, sum = 575675677.000000, dif = 0.000000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56757567.7
Next resistor is 56.0 *10^ 6
Path: [56000000]
Resistance is: 757567.7
Next resistor is 75.0 *10^ 4
Path: [56000000, 750000]
Resistance is: 7567.7
Small resistance left, using search to solve for 7567.7
Solution: [56000000, 750000, 1.0, 4.7, 62.0, 7500.0] (6 elements, sum = 56757567.700000, dif = 0.000000)

До поры до времени выбираем самые большие сопротивления, потом остаток тупо перебором.
Решает мгновенно, памяти жрет ноль, поскольку используются питоновские итераторы.

Добавлено спустя 3 минуты 48 секунд:
гггггг
Resistance is: 5.67432432432e+23
Next resistor is 56.0 *10^ 22
Path: [560000000000000000000000L]
Resistance is: 7.43243243244e+21
Next resistor is 68.0 *10^ 20
Path: [560000000000000000000000L, 6800000000000000000000L]
Resistance is: 6.32432432437e+20
Next resistor is 62.0 *10^ 19
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L]
Resistance is: 1.24324324367e+19
Next resistor is 12.0 *10^ 18
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L]
Resistance is: 4.32432436734e+17
Next resistor is 43.0 *10^ 16
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L]
Resistance is: 2.4324367338e+15
Next resistor is 24.0 *10^ 14
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L]
Resistance is: 3.24367338045e+13
Next resistor is 30.0 *10^ 12
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L]
Resistance is: 2.43673380454e+12
Next resistor is 24.0 *10^ 11
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L]
Resistance is: 36733804544.0
Next resistor is 36.0 *10^ 9
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L]
Resistance is: 733804544.0
Next resistor is 68.0 *10^ 7
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000]
Resistance is: 53804544.0
Next resistor is 51.0 *10^ 6
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000]
Resistance is: 2804544.0
Next resistor is 27.0 *10^ 5
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000, 2700000]
Resistance is: 104544.0
Next resistor is 10.0 *10^ 4
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000, 2700000, 100000]
Resistance is: 4544.0
Small resistance left, using search to solve for 4544.0
Solution: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000, 2700000, 100000, 24.0, 220.00000000000003, 4300.0] (16 elements, sum = 567432432432436700250112.000000, dif = 67108864.000000)

Duhas писал(а):цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм?
а то я ради интереса на ГА напишу ) если вариант второй..

Так, поразвлечься

Для практического применения у меня есть программа, там ограничены и разрядность исходных данных, и количество резисторов, так что вполне устраивает, без всяких ухищрений. Но интересно было бы найти хороший алгоритм в общем виде.

А вот и депф-лимит

>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Resistance is: 57543.0699997
Next resistor is 56.0 *10^ 3
Path: [56000000000L, 680000000, 62000000, 1200000, 56000]
Resistance is: 1543.06999969
Small resistance left, using search to solve for 1543.06999969
Max depth reached 6 [56000000000L, 680000000, 62000000, 1200000, 56000]
Solution: [56000000000L, 680000000, 62000000, 1200000, 56000, 1500.0] (6 elements, sum = 56743257500.000000, dif = 43.070000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Resistance is: 57543.0699997
Next resistor is 56.0 *10^ 3
Path: [56000000000L, 680000000, 62000000, 1200000, 56000]
Max depth reached 5 [56000000000L, 680000000, 62000000, 1200000, 56000]
Solution: [56000000000L, 680000000, 62000000, 1200000, 56000] (5 elements, sum = 56743256000.000000, dif = 1543.070000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Max depth reached 4 [56000000000L, 680000000, 62000000, 1200000]
Solution: [56000000000L, 680000000, 62000000, 1200000] (4 elements, sum = 56743200000.000000, dif = 57543.070000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Resistance is: 57543.0699997
Next resistor is 56.0 *10^ 3
Path: [56000000000L, 680000000, 62000000, 1200000, 56000]
Resistance is: 1543.06999969
Small resistance left, using search to solve for 1543.06999969
Solution: [56000000000L, 680000000, 62000000, 1200000, 56000, 43.0, 1500.0] (7 elements, sum = 56743257543.000000, dif = 0.070000)
>>>

Добавлено спустя 1 минуту 35 секунд:
Хотя и его можно допилить - сейчас только недолет возможен, а, может быть, перелет даст меньшую ошибку.

Добавлено спустя 28 минут 19 секунд:
Во, решает мгновенно :-р


Resistance is: 5.67432557568e+15
Next resistor is 56.0 *10^ 14
Path: [5600000000000000L]
Resistance is: 7.43255756775e+13
Next resistor is 68.0 *10^ 12
Path: [5600000000000000L, 68000000000000L]
Resistance is: 6.32557567754e+12
Next resistor is 62.0 *10^ 11
Path: [5600000000000000L, 68000000000000L, 6200000000000L]
Resistance is: 1.25575677543e+11
Next resistor is 12.0 *10^ 10
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L]
Resistance is: 5575677543.0
Next resistor is 51.0 *10^ 8
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L]
Resistance is: 475677543.0
Next resistor is 47.0 *10^ 7
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000]
Resistance is: 5677543.0
Next resistor is 56.0 *10^ 5
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000]
Resistance is: 77543.0
Next resistor is 75.0 *10^ 3
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000, 75000]
Resistance is: 2543.0
Small resistance left, using search to solve for 2543.0
Max depth reached 10 [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000, 75000]
Solution: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000, 75000, 150.0, 2400.0] (10 elements, sum = 5674325575677550.000000, dif = -7.000000)

dccharacter писал(а):До поры до времени выбираем самые большие сопротивления

Просто повезло.

Было бы какое-нибудь "990000001234", ваш алгоритм выбрал бы "самые большие" 9900 = 9100 + 750 + 47 + 3
Вместо очевидных 99 = 75 + 24 = 56 + 43

По-хорошему тестовые случаи выдумывать надо. И знать правильный оптимальный ответ, чтобы сравнить.

Resistance is: 9.90000001234e+11
Solution: [910000000000L, 75000000000L, 4700000000L, 300000000, 1.0, 33.0, 1200.0] (7 elements, sum = 990000001234.000000, dif = 0.000000)

blindman, попробуй свою шайтан машину?

Добавлено спустя 1 минуту 2 секунды:
мне уже надоело, а то можно было бы запустить параллельно этот алгоритм и поиск и на ночь оставить

Добавлено спустя 1 минуту 31 секунду:
Resistance is: 990.0
Small resistance left, using search to solve for 990.0
Solution: [240.0, 750.0] (2 elements, sum = 990.000000, dif = 0.000000)
>>> ================================ RESTART ================================
>>>
Resistance is: 9900.0
Small resistance left, using search to solve for 9900.0
Solution: [2400.0, 7500.0] (2 elements, sum = 9900.000000, dif = 0.000000)
>>> ================================ RESTART ================================
>>>
Resistance is: 99000.0
Next resistor is 91.0 *10^ 3
Path: [91000]
Resistance is: 8000.0
Small resistance left, using search to solve for 8000.0
Solution: [91000, 1200.0, 6800.0] (3 elements, sum = 99000.000000, dif = 0.000000)


черт, тролли

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

Но, на самом деле, Блайндман так переопределил задачу, что трудно что-то выдумать... Там же теперь значения резисторов внутри декады произвольные - фиг знает как они распределены, совпадений сумм с высокой вероятностью нет вообще и т.д.

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

Resistance is: 9900.0
Solution: [2400.0, 7500.0] (2 elements, sum = 9900.000000, dif = 0.000000)
>>> ================================ RESTART ================================
Resistance is: 99000.0
Solution: [91000, 1200.0, 6800.0] (3 elements, sum = 99000.000000, dif = 0.000000)

Чтобы такого не было, надо либо предварительно нормализовать исходное число, либо понятие "Small" сделать относительным