Когда два алгоритма считаются «похожими»?

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

Когда говорят, что два приведенных алгоритма «похожи»?

Что я имею в виду под «похожим»? Допустим, два алгоритма называются схожими, если вы можете сделать одно из следующих утверждений в документе, не вводя в заблуждение и не раздражая рецензента (более подходящие определения приветствуются):

Пункт 1. «Алгоритм , аналогичный алгоритму B , также решает проблему X »$A$$B$$X$

Пункт 2. «Наш алгоритм аналогичен алгоритму »$C$

Позвольте мне сделать это немного более конкретным. Предположим, мы работаем с графовыми алгоритмами. Сначала некоторые необходимые условия, чтобы два алгоритма были похожи:

1. Они должны решать ту же проблему.
2. Они должны иметь ту же интуитивную идею высокого уровня.

Например, разговор о обходе графа, прохождении в ширину и в глубину удовлетворяет двум вышеуказанным условиям; для вычислений по кратчайшему пути алгоритм в ширину и алгоритм Дейкстры удовлетворяют двум вышеуказанным условиям (конечно, на невзвешенных графах); и т.п.

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

1. у них разные асимптотические показатели?
2. для специального класса графов, один алгоритм требует времени , в то время как другие требует O ( п 1 / 3 ) время?$\Omega(n)$$O(n^{1/3})$
3. у них разные условия завершения? (напомним, они решают одну и ту же проблему)
4. шаг предварительной обработки отличается в двух алгоритмах?
5. сложность памяти отличается в двух алгоритмах?

Редактировать: вопрос явно очень зависит от контекста и субъективно. Я надеялся, что приведенные выше пять условий, однако, позволят получить некоторые предложения. Я с удовольствием внесу дополнительные изменения в вопрос и предоставлю более подробную информацию, если необходимо получить ответ. Благодарность!

Трудно дать даже четкое определение «Алгоритм A похож на Алгоритм B». С одной стороны, я не думаю, что «они должны решать одну и ту же проблему» является необходимым условием. Часто, когда в статье говорится, что «алгоритм теоремы 2 подобен алгоритму B в теореме 1 », алгоритм A фактически решает проблему, отличную от задачи $A$$2$$B$$1$$A$$B$ , но имеет некоторые незначительные модификации для решения новой проблемы. ,

Даже попытка определить, что значит для двух алгоритмов быть одинаковыми, представляет собой интересную и сложную проблему. Смотрите статью "Когда два алгоритма одинаковы?" http://research.microsoft.com/~gurevich/Opera/192.pdf

Чаще всего это означает: «Я не хочу подробно описывать Алгоритм B, потому что все интересные детали практически идентичны тем, которые есть в Алгоритме A, и я не хочу выходить за пределы 10 страниц, и в любом случае срок подачи заявок составляет три часа ".

Если вы имеете в виду «похожий» в разговорном смысле, я думаю, что ответ Джеффа отражает то, что имеют в виду некоторые люди.

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

$A$$M$$\mathit{sem}: A \to M$$\mathit{sem}(P)$$P$$M$$M$$M$$\mathit{sem}(P)$$\mathit{sem}(Q)$ . Позвольте мне добавить, что я думаю, что каждый из пяти упомянутых вами критериев может быть математически формализован таким образом.

$M$$(M, \sqsubseteq)$$x \sqsubseteq y$$x$$y$$M$$\sqsubseteq$$\mathit{sem}(P) \sqsubseteq \mathit{sem}(Q)$ означает, что каждый след $P$ это след $Q$, Мы можем интерпретировать это как $P$ является более детерминированным, чем $Q$,

Затем мы могли бы спросить, можно ли количественно определить, насколько близки два алгоритма. В этом случае я бы предположил, что$M$должен быть наделен метрикой. Затем мы можем измерить расстояние между математическими объектами, которые представляют два алгоритма. Дополнительные возможности состоят в том, чтобы отобразить алгоритмы для измерения пространств или вероятностных пространств и сравнить их, используя другие критерии.

В более общем плане я хотел бы спросить - что вас волнует (в интуитивном выражении), что представляют собой математические объекты, представляющие эти интуитивные свойства, как я могу отображать алгоритмы на эти объекты и какова структура этого пространства? Я также хотел бы спросить, обладает ли пространство объектов достаточной структурой, чтобы допустить понятие сходства. Это тот подход, который я бы выбрал, исходя из семантики языка программирования. Я не уверен, что этот подход кажется вам привлекательным, учитывая совершенно разные культуры мышления в информатике.

В соответствии с ответом Джеффа, два алгоритма похожи, если автор одного из них ожидает, что автор другого может рецензировать ее статью.

Но в стороне от шуток, в теоретическом сообществе я бы сказал, что то, что решает алгоритм проблемы A, довольно касательно того, «похож» ли он на алгоритм B, который может решать совершенно другую проблему. A похож на B, если он «работает» из-за той же основной теоретической идеи. Например, является ли основной идеей в обоих алгоритмах то, что вы можете проецировать данные в гораздо более низкое размерное пространство, сохранять нормы с помощью леммы Джонсона-Линденштраусса, а затем выполнять поиск методом грубой силы? Тогда ваш алгоритм аналогичен другим алгоритмам, которые делают это, независимо от того, какую проблему вы решаете. Существует небольшое количество алгоритмических методов для работы в тяжелых условиях, которые можно использовать для решения широкого круга задач, и я думаю, что эти методы образуют центроиды многих наборов «похожих» алгоритмов.

Очень интересный вопрос и очень хороший документ Райан!

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

С технической точки зрения:

1. Райан уже указал, что оба алгоритма должны решать одну и ту же проблему . Можно пойти еще дальше и обобщить это понятие, сказав, что обычно достаточно доказать, что существует полиномиальное преобразование того же экземпляра, которое понятно алгоритму A, чтобы алгоритм B мог с ним справиться. Тем не менее, это будет на самом деле очень слабым. Я предпочитаю думать о сходстве в более сильном смысле.
2. Однако я бы никогда не ожидал, что два эквивалентных алгоритма будут иметь одну и ту же интуитивную идею - хотя, опять же, это определение, которое нелегко уловить. Более того, часто бывает так, что алгоритмы, которые считаются похожими, не следуют основному обоснованию. Рассмотрим, например, некоторые алгоритмы сортировки, которые, однако, возникли по-разному, следуя различным идеям. В качестве крайнего примера рассмотрим генетические алгоритмы, которые математическое сообщество обычно рассматривает просто как случайные процессы (и, следовательно, они эквивалентны по их мнению), которые затем моделируются и анализируются совершенно другим способом.
3. Более того, я бы даже обобщил это понятие, чтобы сказать, что другие технические детали, такие как условие завершения или этап предварительной обработки, не имеют большого значения. Но это не всегда так. См., Например, алгоритм Дейкстры против поиска с равномерной стоимостью или случай против алгоритма Дейкстры . Оба алгоритма настолько близки, что большинство людей не видят различий, но различия (будучи техническими) были очень важны для автора этой статьи. То же самое происходит с этапом предварительной обработки. Если вы знакомы с$N$-пазл, а затем заметьте, что$^*$алгоритм поиска с использованием манхэттенского расстояния или $(N^2-1)$Базы данных аддитивных шаблонов фактически расширяют одно и то же количество узлов в абсолютно одинаковом порядке, и это делает оба алгоритма (и их эвристику) строго эквивалентными в очень сильном смысле, тогда как первый подход не имеет предварительной обработки, а второй имеет значительные накладные расходы, прежде чем начать решать конкретный экземпляр. Однако, как только ваши базы данных шаблонов рассматривают более симулированные взаимодействия, между ними возникает огромный разрыв в производительности, так что это определенно разные идеи / алгоритмы.
4. На самом деле, я думаю, что большинство людей будут оценивать алгоритмы по их назначению и производительности . Следовательно, асимптотическая производительность является хорошим показателем сходства между программами. Однако имейте в виду, что эта производительность не обязательно является типичным случаем, поэтому, если два алгоритма имеют одинаковую асимптотическую производительность, но на практике ведут себя по-разному, вы, вероятно, придете к выводу, что они разные. Убедительным доказательством в этом отношении будет то, что оба алгоритма имеют одинаковую производительность как по времени, так и по памяти (и это, как сказал Суреш, делает DFS и BFS выглядеть по-разному). В случае, если это утверждение не звучит убедительно для вас, пожалуйста, обратитесь к превосходной (и очень рекомендуемой книге): Программирование ВселеннойСет Ллойд. На странице 189 он ссылается на список с более чем 30 показателями сложности, которые можно использовать, чтобы рассматривать алгоритмы как разные.

Так что же делает алгоритмы похожими / разными? На мой взгляд (и это чисто умозрительно), главное различие заключается в том, что они предлагают вам. Многие, многие (многие!) Алгоритмы отличаются лишь несколькими техническими особенностями, когда служат одной и той же цели, так что типичный случай различен для разных диапазонов ввода. Однако самое большое из всех различий - это (на мой взгляд) то, что они предлагают вам. Алгоритмы имеют разные возможности и, следовательно, свои сильные и слабые стороны. Если два алгоритма выглядят одинаково, но могут быть по-разному расширены, чтобы справиться с разными случаями, то я бы пришел к выводу, что они разные. Однако часто два алгоритма выглядят практически одинаково, так что вы можете считать их одинаковыми ... пока кто-то не придет с принципиальным отличием, и вдруг они совершенно разные!

Извините, мой ответ был в конце концов так долго ...

Ура,

Любое упоминание о сходстве без определения подобия метрики не очень хорошо определены. Есть много способов, которыми два алгоритма могут быть похожи:

Quicksort и Mergesort решают очень похожие проблемы, но для этого они используют разные алгоритмы. Они имеют схожую алгоритмическую сложность (хотя их производительность в худшем случае и использование памяти могут различаться). Quicksort и Mergesort похожи на Bubblesort, однако Bubblesort имеет очень разные показатели производительности. Если вы игнорируете статистику сложности, Quicksort, Mergesort и Bubblesort все находятся в одном классе эквивалентности. Однако, если вас волнует алгоритмическая сложность, тогда Quicksort и Mergesort намного больше похожи друг на друга, чем Bubblesort.

Динамическое программирование Смита-Уотермана и сравнение HMM-последовательностей пытаются решить проблему совмещения двух последовательностей. Тем не менее, они принимают разные входные данные. Смит-Уотерман принимает две последовательности в качестве входных данных, а сравнения HMM-последовательностей принимают HMM и последовательность в качестве входных данных. Обе выходные последовательности выравнивания. С точки зрения мотивирующих идей, оба они похожи на расстояние редактирования Левенштейна , но только на очень высоком уровне.

Вот некоторые критерии, по которым два алгоритма можно назвать схожими:

1. Типы ввода / вывода
2. Алгоритм / сложность памяти
3. Предположения о типах входных данных (например, только положительные числа или стабильность с плавающей запятой)
4. Вложенные отношения (например, некоторые алгоритмы являются частными случаями других)

Критическое решение о значении сходства остается. Иногда вас волнует сложность алгоритма, иногда нет. Поскольку определение сходства зависит от контекста обсуждения, термин «подобный алгоритм» не является четко определенным.