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 писал(а):Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче
Единственное, что не сделал - тормоз по количеству резисторов:
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 писал(а):цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм? а то я ради интереса на ГА напишу ) если вариант второй..
Так, поразвлечься
Для практического применения у меня есть программа, там ограничены и разрядность исходных данных, и количество резисторов, так что вполне устраивает, без всяких ухищрений. Но интересно было бы найти хороший алгоритм в общем виде.
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)
Блайндман же в самом первом сообщении написал про "жадный алгоритм" - который берет максимальное возможное значение. Что он далек от оптимума, хотя и быстрый, конечно.
Но, на самом деле, Блайндман так переопределил задачу, что трудно что-то выдумать... Там же теперь значения резисторов внутри декады произвольные - фиг знает как они распределены, совпадений сумм с высокой вероятностью нет вообще и т.д.
Боюсь, что кроме прямого перебора (с разумными отсечениями) - хоть вширь, хоть вглубь, хоть наискосок теперь уже ничего не спасет...
).
