Какой самый удивительный алгоритм вы знаете?

283
26

спросил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
1
Лучший ответ
294

Глобальное выравнивание Linear Space поразило меня, когда я впервые узнал об этом. Поскольку составлять таблицы в Quora сложно, мой ответ не оправдает алгоритм. Тем не менее, я обобщу ключевые понятия в своем ответе.

Алгоритм глобального выравнивания позволяет генерировать выравнивание с минимальным расстоянием редактирования между двумя строками. Например, допустим, у вас есть две строки:

ABCDEFGHIJK

addefghsjk

Глобальное выравнивание что-то вроде:

До н.э. Дефх и Дж.К.
D-Defgh S JK

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

Канонический алгоритм глобального выравнивания использует динамическое программирование для его решения:

Алгоритм Нидлмана – Вунша - Википедия

По сути, если вы выравниваете две строки, одну строку длиной m, а другую длиной n, вы генерируете таблицу размером m на n и итеративно заполняете каждый элемент таблицы. Временная сложность оказывается O (mn) или квадратичной. Кроме того, поскольку вы генерируете таблицу размером m на n, сложность пространства также O (mn), опять же квадратичная.

Однако, с некоторым колдовством, вы можете фактически уменьшить сложность пространства до O (m) или O (n).

Алгоритм Хиршберга - Википедия

Первое наблюдение состоит в том, что, хотя для вычисления выравнивания может потребоваться сохранение всей таблицы динамического программирования m-на-n, вычисление только оценки требует только двух строк таблицы динамического программирования. Если мы только вычисляем счет до среднего столбца, мы можем сделать это за O (mn) времени и O (m) или O (n) пространства.

Второе наблюдение состоит в том, что, если мы перевернем строки и вычислим балл до среднего столбца, мы получим столбец баллов, который при добавлении в средний столбец из предыдущего наблюдения сгенерирует ячейку с минимальным баллом. Позиция ячейки с минимальной оценкой - это то место, где проходит оптимальное решение.

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

В целом сложность времени со всей этой рекурсией заканчивается O (mn + mn / 2 + mn / 4 + ...) = O (2mn) = O (mn). Однако сложность пространства всегда оказывается линейной, поскольку для каждого рекурсивного шага требуется только линейное пространство.

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
231

Оптимизация роя частиц (PSO).

Это алгоритм стохастической оптимизации, который моделирует, как стая птиц ищет еду / воду. Сила этого алгоритма в том, что вы можете использовать его для задач многомерной оптимизации, которые не обязательно являются выпуклыми!

Основные работы этого метода следующие:

вы начинаете с ряда частиц (индивидуумов), которые будут коллективно искать ваш глобальный оптимум. Положение каждой частицы в пространстве поиска определяется N-мерным вектором (в зависимости от того, для чего вы оптимизируете) и представляет собой потенциальное решение проблемы. Частицы инициализируются в случайные положения, а затем им разрешено «летать»! На каждой итерации положение и скорость каждой частицы обновляются на основе: собственного «показателя соответствия» частицы. Средний балл за весь рой. Инерция → и это волшебство. Он может контролировать, насколько на скорость частицы влияет самость (а) или весь рой (б). Идея состоит в том, что в начале поиска вы хотите «исследовать» как можно большую часть своего пространства, чтобы вы меньше влияли на средний уровень роя. Вы итеративно увеличиваете влияние населения, так что в процессе поиска вы позволяете своему рой сходиться (или «эксплуатировать») решение.

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

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

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

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
175

Быстрый обратный квадратный корень

алгоритм, который оценивает 1 / √ x. Эта операция используется в цифровой обработке сигналов для нормализации вектора.

Алгоритм наиболее известен своей реализацией в 1999 году в исходном коде Quake III Arena.

  1. float Q_rsqrt( float number )
  2. {
  3. long i;
  4. float x2, y;
  5. const float threehalfs = 1.5F;
  6. x2 = number * 0.5F;
  7. y = number;
  8. i = * ( long * ) &y; // evil floating point bit level hacking
  9. i = 0x5f3759df - ( i >> 1 ); // what the f**k?
  10. y = * ( float * ) &i;
  11. y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  12. // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
  13. return y;
  14. }

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
102

Низкоэнергетическая адаптивная кластеризационная иерархия (алгоритм LEACH): -

Большинство из вас не слышали об алгоритме LEACH. Итак, позвольте мне представить вам этот алгоритм, который имеет решающее значение в беспроводных сенсорных сетях.

LEACH - это энергосберегающий алгоритм для беспроводной сенсорной сети, предложенный Хайнцельманом, Чандракасаном и Балакришнаном. В LEACH сенсорные узлы образуют кластеры, а головки кластеров действуют как маршрутизаторы для приемника. Это сэкономит энергию, поскольку передача будет осуществляться только головками кластеров (CH), а не всеми узлами датчиков. Оптимальное количество CHs оценивается в 5% от общего количества узлов. В LEACH выбор головки кластера осуществляется в два этапа.

1. Фаза настройки

На этапе настройки каждый узел генерирует случайное число от 0 до 1. Если случайное число меньше

пороговое значение, то этот узел становится CH. Пороговое значение рассчитывается на основе следующего уравнения [1]

это дано ниже:

Здесь p - желаемый процент голов кластеров, а r - текущий раунд, G - группа узлов, которые не были CH в последних раундах. Сенсорный узел, выбранный в качестве канала CH в предыдущем раунде, не будет выбран в следующих раундах, пока все остальные узлы в сети не станут заголовками кластеров.

2. Устойчивая фаза

В устойчивой фазе узлы отправляют свои данные в заголовок кластера с использованием расписания TDMA (множественного доступа с временным разделением). Расписание TDMA выделяет временные интервалы для каждого узла. CH собирает данные и отправляет их на базовую станцию.

Так работает LEACH. Это помогает экономить электроэнергию и пропускную способность, которые являются двумя основными ограничениями ресурсов при развертывании беспроводных сенсорных сетей.

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
95

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

Вы можете следить за подачей здесь:

Лекс Мачина (@Lex_Machina_) | щебет

Я надеюсь вернуться и обнародовать все детали о том, как это работает когда-нибудь.

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
77

Это должно быть одним из моих любимых:

Нейронный алгоритм для художественного стиля

Этот алгоритм генерирует красивое «искусство», как это:

Как оно работает?

Вы даете глубокой нейронной сети исходное изображение, рисунок / рисунок, стиль которого вы хотите имитировать, и изображение со случайным шумом (patische). Вы тренируете нейронную сеть так, чтобы патчи сохраняли «контент» исходного изображения и максимально приближались к стилю изображения стиля.

Это делается путем обучения нейронной сети минимизировать сумму потери контента и потери стиля. Чтобы вычислить потерю контента, мы пропускаем исходное изображение и изображение через сеть классификации изображений и суммируем евклидово расстояние между промежуточными представлениями этих изображений (т.е. выходы промежуточных слоев). Чтобы вычислить потерю стиля, мы пропускаем изображение стиля и патчи через сеть, вычисляем расстояния между матрицами Грама (умножение матрицы и ее транспонирование, подходящее для сбора информации о текстуре) промежуточных слоев.

Это все довольно просто, но создает удивительно убедительные образы. Это может даже сделать видео! Следует задаться вопросом, является ли создание искусства уникальной человеческой способностью.

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
55

Алгоритм сортировки гения!

Парень на 4chan опубликовал этот алгоритм, который использует функцию сна для сортировки чисел:

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
39

Я должен был бы пойти с быстрым преобразованием Фурье (БПФ).

Одним из основных применений этого алгоритма является умножение двух полиномов. Математически мы хотим определить C (x) = A (x) ⋅ B (x) C (x) = A (x) ⋅ B (x) C (x) = A (x) \ cdot B (x)

A (x) = a 0 + a 1 x + a 2 x 2 +… + тревога A (x) = a 0 + a 1 x + a 2 x 2 +… + тревога A (x) = a_0 + a_1x + a_2x ^ 2 + \ ldots + a_nx ^ n

B (x) = b 0 + b 1 x + b 2 x 2 +… + bnxn B (x) = b 0 + b 1 x + b 2 x 2 +… + bnxn B (x) = b_0 + b_1x + b_2x ^ 2 + \ ldots + b_nx ^ n

C (x) = A (x) ⋅ B (x) = c 0 + c 1 x +… + c 2 nx 2 n C (x) = A (x) ⋅ B (x) = c 0 + c 1 x +… + C 2 nx 2 n C (x) = A (x) \ cdot B (x) = c_0 + c_1x + \ ldots + c_ {2n} x ^ {2n}

Наивный метод полиномиального умножения с использованием дистрибутивного свойства взял бы O (n 2) O (n 2) O (n ^ 2). Но можем ли мы сделать лучше?

Первая блестящая идея исходит из того факта, что существует два способа представления многочлена A (x) A (x) A (x)

Используя его коэффициенты a 0, a 1,…, ana 0, a 1,…, a a_0, a_1, \ ldots, a_n Используя его значения A (x 0), A (x 1),…, A (xn) A (x 0), A (x 1),…, A (xn) A (x_0), A (x_1), \ ldots, A (x_n) для любого набора различных точек x 0, x 1,…, xnx 0 , x 1,…, xn x_0, x_1, \ ldots, x_n

Это второе представление исходит из того факта, что любой многочлен степени nnn может быть однозначно представлен своими значениями в любых n + 1 n + 1 n + 1 различных точках (известный частный случай этого факта состоит в том, что «две точки определяют уникальную прямую «).

Мы уже знаем, что если мы используем представление (1) для умножения многочленов, это займет O (n 2) O (n 2) O (n ^ 2) время. Но что, если мы используем представление (2)?

При условии, что у нас есть 2 n + 1 2 n + 1 2n + 1 различных точек, умножение полиномов сводится к умножению каждого значения для каждой точки, давая новый набор из 2 n + 1 2 n + 1 2n + 1 значений, которые полностью представляют умноженный полином. Математически для каждой точки xixi x_i C (xi) = A (xi) ⋅ B (xi) C (xi) = A (xi) ⋅ B (xi) C (x_i) = A (x_i) \ cdot B (x_i) )

Следовательно, если мы используем представление (2), умножение полиномов теперь занимает только O (n) O (n) O (n) время!

Но сразу возникает другая проблема. Если нам дано представление коэффициента, как нам взять представление коэффициента (1) и преобразовать его в представление значения (2)? Наивным методом было бы взять n + 1 n + 1 n + 1 баллов и оценить многочлен в каждой из этих точек, получая время выполнения O (n 2) O (n 2) O (n ^ 2), которое не будет достаточно хорош. Как нам лучше?

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

Чтобы увидеть это, давайте посмотрим, что произойдет, если мы решим оценить наш многочлен в положительно-отрицательных парах:

± x 0, ± x 1,…, ± xn / 2 - 1 ± x 0, ± x 1,…, ± xn / 2 - 1 \ pm x_0, \ pm x_1, \ ldots, \ pm x_ {n / 2 - 1}

Обратите внимание, что для этого набора точек вычисления для A (xi) A (xi) A (x_i) и A (- xi) A (- xi) A (-x_i) совпадают для всех четных степеней A (x) A (x) A (x).

Это особенно важно, потому что каждый многочлен можно разбить на следующую декомпозицию:

A (x) = A e (x 2) + x A o (x 2) A (x) = A e (x 2) + x A o (x 2) A (x) = A_e (x ^ 2) + xA_o (х ^ 2)

где A e A e A_e представляют четные коэффициенты мощности и A o A o A_o представляют нечетные коэффициенты мощности.

Вот пример такого разложения:

3 + 4 x + 6 x 2 + 2 x 3 + x 4 + 10 x 5 = (3 + 6 x 2 + x 4) + x (4 + 2 x 2 + 10 x 4) 3 + 4 x + 6 x 2 + 2 x 3 + x 4 + 10 x 5 = (3 + 6 x 2 + x 4) + x (4 + 2 x 2 + 10 x 4) 3 + 4x + 6x ^ 2 + 2x ^ 3 + x ^ 4 + 10x ^ 5 = (3 + 6x ^ 2 + x ^ 4) + x (4 + 2x ^ 2 + 10x ^ 4)

Из-за четности выбранных точек для любых ± xi ± xi \ pm x_i вычисления, необходимые для A (xi) A (xi) A (x_i), могут быть переработаны при вычислении A (- xi) A (- xi) A (-x_i).

A (xi) = A e (x 2 i) + xi A o (x 2 i) A (xi) = A e (xi 2) + xi A o (xi 2) A (x_i) = A_e (x_i ^ 2 ) + x_iA_o (x_i ^ 2)

A (- xi) = A e (x 2 i) - xi A o (x 2 i) A (- xi) = A e (xi 2) - xi A o (xi 2) A (-x_i) = A_e ( x_i ^ 2) - x_iA_o (x_i ^ 2)

Итак, давайте сделаем шаг назад и проанализируем то, что мы только что сделали.

Мы только что взяли задачу оценки степени nnn полинома и свели ее к оценке двух полиномов A e (x A e (x A_e (x))) и A o (x) A o (x) A_o (x), каждая из степеней n / 2 n / 2 n / 2, всего лишь n / 2 n / 2 n / 2 балла. Таким образом, наша первоначальная проблема размера n n n теперь состоит из двух подзадач размером n / 2 n / 2 n / 2, причем каждая подзадача требует линейной арифметики времени.

Это полезный график, который показывает, чего мы только что достигли:

Если бы мы могли рекурсивно, рекуррентное отношение выглядело бы так:

T (n) = 2 T (n / 2) + O (n) T (n) = 2 T (n / 2) + O (n) T (n) = 2T (n / 2) + O (n)

который дает время работы O (n log n) O (n log ⁡ n) O (n \ log n), что является огромным улучшением по сравнению с нашим предыдущим O (n 2) O (n 2) O (n ^ 2) ,

Но как мы возвращаемся?

Большая проблема заключается в том, что нам нужны оценки n / 2 n / 2 n / 2 x 2 0, x 2 1,… x 2 n / 2 - 1 x 0 2, x 1 2,… xn / 2 - 1 2 x_0 ^ 2, x_1 ^ 2, \ ldots x_ {n / 2 - 1} ^ 2 сами по себе являются положительно-отрицательными парами. Но как мы можем сделать квадратное число отрицательным? И чтобы решить эту проблему, вот следующая блестящая идея: мы расширяем область наших точек, чтобы включить комплексные числа.

Чтобы выяснить, какой набор комплексных чисел нам нужно включить в наш набор из nnn начальных точек, давайте рассмотрим, какая пара нам понадобится, если мы хотим оценить полином 4 степени (n = 4 n = 4 n = 4) в точке 1.

Мы можем расширить этот процесс до любого набора из nnn точек, и мы можем видеть, что исходный набор из nnn точек, которые мы должны выбрать для оценки нашего полинома, - это n-е комплексные корни единицы или множество решений для zzz, которые удовлетворяют zn = 1 zn = 1 z ^ n = 1.

И теперь из-за этого специального набора точек 1, z, z 2,… zn - 1 1, z, z 2,… zn - 1 1, z, z ^ 2, \ ldots z ^ {n - 1} где z = e 2 π inz = e 2 π inz = e ^ {\ frac {2 \ pi i} {n}}, рекурсия работает отлично, и теперь мы можем оценить многочлен в nnn точках в O (O (O (n log) n) n log ⁡ n) n \ log n) время (небольшая деталь здесь в том, что изначально я сказал, что нам нужно n + 1 n + 1 n + 1 точек, чтобы однозначно идентифицировать полином, и на практике простая точка, такая как x = 0 x = 0 x = 0 добавляется, но эта дополнительная точка не влияет на время работы этого алгоритма). Этот алгоритм, который мы разработали для преобразования многочлена из представления коэффициентов в представление значений, представляет собой быстрое преобразование Фурье.

Таким образом, на высоком уровне, в контексте умножения многочленов А (х) А (х) А (х) и В (х) В (х) В (х), это то, что мы делали до сих пор:

Выбранные точки в соответствии со сложными корнями единицы для оценки наших полиномов A (x) A (x) A (x) и B (x) B (x) B (x) Оценили эти полиномы в этих точках, используя быстрое преобразование Фурье. Определяли основанное на значении представление нашего получающегося полинома C (x) C (x) C (x), просто умножая представления точечных значений каждого полинома A (x) A (x) A (x) и B (x) B ( х) Б (х)

Теперь у нас есть последний кусок головоломки. У нас есть представление C (x) C (x) C (x), основанное на значениях, но как мы можем преобразовать это обратно в представление коэффициентов. Этот тип преобразования называется интерполяцией.

И действительно, одна из самых удивительных вещей в БПФ состоит в том, что мы можем использовать тот же процесс, инвертированный для определения представления коэффициента из представления значения.

Оказывается, что мы можем решить проблему интерполяции, просто вызвав тот же алгоритм БПФ, но заменив каждую точку z z z на z - 1 z - 1 z ^ {- 1} и нормализуя результат на n n n.

Основная причина этой работы заключается в линейной алгебраической интерпретации БПФ. Что мы действительно делаем, когда оцениваем многочлен, так это то, что мы умножаем наше представление коэффициентов на специальную матрицу, называемую матрицей Вандермонда.

А в случае БПФ с выбором точек в качестве комплексных корней единицы используемая матрица в итоге становится специальной матрицей, называемой матрицей ДПФ.

И с этим линейным алгебраическим представлением, с такими свойствами, что матрица DFT является ортогональной, а обратная - это транспонированная сопряженность этой матрицы, нормированная на nnn, мы можем видеть, что процесс перехода от представления значения к представлению коэффициента так же прост как умножение на обратную матрицу ДПФ или с алгоритмической точки зрения, вызов алгоритма БПФ с заменой каждой точки zzz на z - 1 z - 1 z ^ {- 1} и нормализацию результата на nnn.

Положите кратко:

<значения> = БПФ (<коэффициенты>, z z z)

<коэффициенты> = 1 n 1 n \ frac {1} {n} БПФ (<значения>, z - 1 z - 1 z ^ {- 1})

Итак, подведем итог: умножить два полинома A (x) A (x) A (x) и B (x) B (x) B (x):

Выбранные точки в соответствии со сложными корнями единицы для оценки наших полиномов A (x) A (x) A (x) и B (x) B (x) B (x) Оценили эти полиномы в этих точках, используя быстрое преобразование Фурье. Определяли основанное на значении представление нашего получающегося полинома C (x) C (x) C (x), просто умножая представления точечных значений каждого полинома A (x) A (x) A (x) и B (x) B ( x) B (x) Получить представление коэффициента, применяя обратное БПФ

Весь этот алгоритм является O (n log n) O (n log ⁡ n) O (n \ log n), что значительно лучше, чем наивное решение O (n 2) O (n 2) O (n ^ 2).

Похоже, что мы сделали довольно много, чтобы просто умножить многочлены, но у БПФ есть приложения, выходящие за рамки простого умножения многочленов (что, кстати, также довольно полезно). Алгоритм в основном создал всю область обработки сигналов, которая является основой практически для всех современных технологий, которые мы видим сегодня. Этот алгоритм позволил сделать огромный прорыв во всех этих технологиях, которые основаны на передаче информации через сигналы.

Алгоритм никогда не перестает поражать меня своими идеями, которые он объединяет. Это действительно невероятно, что люди смогли разработать такой сложный алгоритм, который оказался чрезвычайно полезным.

Вот классный пример того, как рекурсия в FFT разворачивается:

Для получения дополнительной информации о теории и реализации алгоритма БПФ ознакомьтесь с разделом 2.6 учебника по работе с алгоритмами Кристоса Пападимитриу, Санджоя Дасгупты и Умеша Вазирани: Алгоритмы

ответил(а) 2020-05-08T16:00:32+03:00 1 год, 2 месяца назад
Ваш ответ
Введите минимум 50 символов
Чтобы , пожалуйста,
Выберите тему жалобы:

Другая проблема