Технический форум по робототехнике.
blindman » 20 мар 2013, 17:02
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)|. Это критерий оптимизации решения, можно выбрать любой, или оба с произвольным приоритетом - на усмотрение реализатора алгоритма
Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче
Michael_K » 20 мар 2013, 18:03
Хм. Широко взяли....
Видимо, кроме переборов тут предложить нечего...
Куда перебирать и чем ограничивать - дело десятое - всегда найдется "плохой" набор данных.
Но попробовать можно.
blindman писал(а):Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче
Ну... OK.
Duhas » 20 мар 2013, 18:15
цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм?
а то я ради интереса на ГА напишу ) если вариант второй..
dccharacter » 20 мар 2013, 18:22
Единственное, что не сделал - тормоз по количеству резисторов:
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)
blindman » 20 мар 2013, 19:28
Duhas писал(а):цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм?
а то я ради интереса на ГА напишу ) если вариант второй..
Так, поразвлечься
Для практического применения у меня есть программа, там ограничены и разрядность исходных данных, и количество резисторов, так что вполне устраивает, без всяких ухищрений. Но интересно было бы найти хороший алгоритм в общем виде.
dccharacter » 20 мар 2013, 22:09
А вот и депф-лимит
>>> ================================ 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)
Michael_K » 20 мар 2013, 22:45
dccharacter писал(а):До поры до времени выбираем самые большие сопротивления
Просто повезло.
Было бы какое-нибудь "990000001234", ваш алгоритм выбрал бы "самые большие" 9900 = 9100 + 750 + 47 + 3
Вместо очевидных 99 = 75 + 24 = 56 + 43
По-хорошему тестовые случаи выдумывать надо. И знать правильный оптимальный ответ, чтобы сравнить.
dccharacter » 20 мар 2013, 22:58
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)
черт, тролли
Michael_K » 20 мар 2013, 23:11
Блайндман же в самом первом сообщении написал про "жадный алгоритм" - который берет максимальное возможное значение. Что он далек от оптимума, хотя и быстрый, конечно.
Но, на самом деле, Блайндман так переопределил задачу, что трудно что-то выдумать... Там же теперь значения резисторов внутри декады произвольные - фиг знает как они распределены, совпадений сумм с высокой вероятностью нет вообще и т.д.
Боюсь, что кроме прямого перебора (с разумными отсечениями) - хоть вширь, хоть вглубь, хоть наискосок
теперь уже ничего не спасет...
blindman » 21 мар 2013, 03:11
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" сделать относительным