В поисках правильного импульса
Насколько полезна линейность для подсчета массивных случаев.
Иногда нас интересует обзор всей системы как более целостная точка зрения. Эта точка зрения порождает общие впечатления, побуждающие нас делать то или иное дело. Однако эти импульсы производятся после первого обзора всей окружающей среды, чтобы прийти к очень сложным выводам.
В этом посте я покажу механизм, который поможет нам понять, как находить десятки взаимосвязанных проблем и как с ними справляться.
Прежде всего, это Импульс X (t) = δ (t); что означает: возвращает 1, если t равно 0, в противном случае - 0.
Наш особый интерес не будет заключаться в работе с условной функцией, но мы заинтересованы в работе со структурой, которую мы можем складывать и умножать. По этой причине мы собираемся представить его в виде суммы косинусов, как описано в этой книге [1]:
Это означает, что мы не можем работать с изолированным импульсом ...
Мы также не строим пики с помощью выводимых функций.
Итак, легко построить свою собственную импульсную функцию,
from math import pi, cos, sin
class Impulse:
def __init__(self, period, U=0, m=80):
self.m = m
self.period = period
self.sc = {}
self.ss = {}
self.sc[0] = -U
for k in range(1,m):
self.sc[k] = 1 / (m-1) / (1-U)
def __call__(self, item):
S = 0.0
for i in self.sc.keys():
S += self.sc[i] * cos(i * item * 2*pi / self.period)
for i in self.ss.keys():
S += self.ss[i] * sin(i * item *2*pi / self.period)
return S
Мы можем немного поиграть с новым параметром, который я поставил:
>>> X0 = Impulse(20) >>> X0(0) 0.9999999999999987 >>> X0(1) -0.012658227848101278 >>> X1 = Impulse(20, U = X0(1)) >>> X1(0) 1.0001582278480998 >>> X1(1) 0.00015822784810127707 >>> [round(X0(t), 2) for t in range(21)] [1.0, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, 1.0] >>> [round(X1(t), 2) for t in range(21)] [1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 1.0]
Это означает, что мы всегда можем внести небольшие улучшения, которые помогут уточнить формулы в зависимости от того, для чего они нам нужны.
Включение линейных операций
Что действительно интересно, так это то, что мы можем умножить сигнал на шкалу, переместить его и добавить еще один сигнал. Итак, вот предложение:
def clone(self):
result = Impulse(self.period, m=1)
result.m = self.m
result.ss = self.ss.copy()
result.sc = self.sc.copy()
return result
def scale(self, value):
for k in self.ss.keys():
self.ss[k] *= value
for k in self.sc.keys():
self.sc[k] *= value
def shift(self, x=0, y=0):
factor = 2*pi/self.period
if not 0 in self.sc.keys():
self.sc[0] = y
else:
self.sc[0] += y
for k in self.sc.keys() :
b = self.sc[k]
a = self.ss[k] if k in self.ss.keys() else 0
self.ss[k] = a * cos(-k*x*factor) - b * sin(-k*x*factor)
self.sc[k] = a * sin(-k*x*factor) + b * cos(-k*x*factor)
for k in self.ss.keys():
if k in self.sc.keys():
continue
self.ss[k] *= cos(-k*x*factor)
self.sc[k] = self.ss[k] * sin(-k*x*factor)
def __add__(self, other):
result=self.clone()
result.period = self.period
for k in other.ss.keys():
if not k in result.ss.keys():
result.ss[k] = 0
result.ss[k] += other.ss[k]
for k in other.sc.keys():
if not k in result.sc.keys():
result.sc[k]=0
result.sc[k] += other.sc[k]
return result
Итак, теперь мы можем протестировать это следующим образом:
>>> X = Impulse(20) >>> Y = X.clone() >>> [round(X(t), 2) for t in range(21)] [1.0, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, 1.0] >>> [round(Y(t), 2) for t in range(21)] [1.0, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, -0.01, 1.0] >>> X.scale(2) >>> Y.shift(1, .01) >>> [round(X(t), 2) for t in range(21)] [2.0, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, -0.03, 2.0] >>> [round(Y(t), 2) for t in range(21)] [-0.0, 1.01, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0]
На этом этапе мы могли бы хорошо заметить, что добавляемые нами сигналы всегда должны иметь один и тот же период, потому что наша функция суммирования не вычисляет максимальный общий делитель двух периодов, и также возможно, что мы заинтересованы в представлении сигналов прямоугольной формы. , вместо импульсов, как показано в библиографии…, но для целей этого поста мы останемся здесь.
Поиск более интересных приложений
Представьте, что мы хотим знать, сколькими способами мы можем найти подмножества чисел в коллекции, способные добавить ровно одно количество.
Например: в [1, 1, 3, 4] мы можем достичь # {[1, 1, 3], [1, 4]} = 2 случаев, когда сумма элементов их сборок составляет ровно 5.
В [3] мы видим определение задачи о ранце:
Итак, мы видим, что от того, что рассчитывается, отличается то, что оно возникает, если есть случай, когда мы подумали о подсчете количества случаев. Когда доходит до установления разницы, существует соглашение, заключающееся в включении символа # и упоминании о том, что мы вычисляем диез.
Итак, #KNAPSACK означает: сколько подмножеств может добавить ровно одно количество.
В [3] мы можем решить другую известную проблему, представьте, что у нас есть набор чисел, можем ли мы разделить их на две части, при суммировании каждой части результат будет одинаковым?
Пример, давайте воспользуемся нашим классом…
def sharpPartition(*L):
X = Impulse(sum(L)+1, m=100)
for Z in L:
Y = X.clone()
Y.shift(Z)
X.shift(-Z)
X += Y
return round(X(0)/2)
В приведенном выше коде мы сдвигаем получившийся сигнал влево и вправо, чтобы наконец добавить. В t = 0 мы найдем удвоенное количество разделов, как в #Partitions [1, 2, 3] = # {({1, 2}, {3}), ({3}, {1, 2 })} / 2 = 1
So,
>>> sharpPartition(1,2,3) 1 >>> sharpPartition(1, 2, 3, 5) 0
Есть ли связь между #Partitions и #Knapsack? В [3] мы можем достичь этого отношения:
Таким образом, нам нужно только определение раздела в той же нотации:
Итак, код может быть таким:
def sharpKnapsack(value, *L):
L2 = list(L[:])
L2.append(value +1)
L2.append(sum(L) + 1 - value)
return sharpPartition(*L2)
Итак, мы можем провести несколько простых тестов ...
>>> sharpKnapsack(5, 2, 3) 1 >>> sharpKnapsack(3, 2, 3, 1) 2
Вы можете найти больше, чем проблемы, описанные в [3], вы можете найти больше в [2] с другими эквивалентностями ...
Если бы все было так красиво ...
Как я объяснил в следующем посте,
не золото все блестит. Поэтому от наших моделей могут быть как хорошие, так и плохие новости. Исходя из моих собственных обозначений, мы могли бы создать как ручные инструкции для решения большинства проблем #NP, описанных в [2], но мы должны рассматривать эти вещи только приблизительно, используя методы, описанные в этом посте.
Есть вероятность, что нам может потребоваться более точное представление импульса, чтобы результат счета был более точным.
Преимущество установки фиксированного количества слагаемых состоит в том, что оно не зависит от размера ввода, но зависит от диапазона значений, которые они используют.
Итак, давайте изучим этот код:
def sharpSumZero(summands, *E):
I = Impulse(2*max(E)*len(E), U = 0, m = summands)
for X in E:
I2 = I.clone()
I2.shift(x = X)
I += I2
I.shift(y = -I(0.5)) #S1
if round(I(0),0) > 0:
I.scale(round(I(0), 0) / I(0)) #S2.
else:
I.shift(y = 1 - I(0))
return int(round(I(0),0))
В этом случае мы считаем, сколько подмножеств суммируют ровно ноль. Для этого мы использовали два специальных блока # S1 и # S2, чтобы улучшить результаты.
Итак, давайте проверим это с помощью этой записи: L = [1] + [-1]*40 , которая представляет собой -1 и 40 способов добавить его до нуля. Таким образом, правильный результат - 41 (с учетом пустого множества).
>>> sharpSumZero(800, *([-1]+([1]*40))) 190 >>> sharpSumZero(1600, *([-1]+([1]*40))) 41 >>> sharpSumZero(3200, *([-1]+([1]*40))) 772850686
Как видите, есть диапазон, в котором он работает идеально (например, проблемы с переобучением и недостаточным подбором). Необходимо учитывать пределы ошибок, с которыми работают наши библиотеки, а также пределы ошибок, с которыми работает ряд Фурье, представляющий импульс. В противном случае результаты могут быть предсказуемыми.
использованная литература
[1] Оппенгейм, А. Виллски, А., Наваб, С. (2016) Сигналы и системы. Нойда: Пирсон, 2016.
[2] Гарей, М., Джонсон, Д. (2009) Компьютеры и неразрешимость. Нью-Йорк [u.a]: Freeman, 2009.
[3] Карп Р. М. (1972) Сводимость комбинаторных проблем. Р. Э. Миллер и Дж. У. Тэтчер (редакторы), Сложность компьютерных вычислений, издательство Plenum Press, Нью-Йорк, 85–103.
