Как мы можем классифицировать различные алгоритмы?

Question

Как мы можем классифицировать различные алгоритмы?

Я слышал различные названия: алгоритмы «разделяй и властвуй», детерминированные алгоритмы, вероятностные алгоритмы, алгоритмы на месте и т.

Они формируют какую-либо иерархию классификации?

Пожалуйста, предоставьте мне любую ссылку.

Answer 1

Существует несколько различных классификаций алгоритмов:

Как они решают проблемы

Классические алгоритмы:

• Разделяй и властвуй например, бинарный поиск
• жадные алгоритмы , такие как поиск максимума в списке или максимальное распределение заданий с невзвешенными значениями заданий.
• Динамическое программирование , например, LCS
• Возврат , как 8 ферзей, и все алгоритмы NPC.
• СортировкаАлгоритмы , сортировка имеет специфическую методологию и используется в широком диапазоне
• Линейное программирование
• График Алгоритмы

Не классические:

• Случайные прогулки
• Генетический алгоритм
• Марковская цепь
• Алгоритмы аппроксимации
• Нейронная сеть, ...

Но эти алгоритмы являются детерминированными или недетерминированными средствами для каждого прогона на конкретномна входе они получат один и тот же результат (детерминированный) или другой результат (недетерминированный).

Также у этих алгоритмов слишком много разных проблем, и в каждой из проблем используется гибрид всех алгоритмов, например, TSP в евклидовом графе.может быть аппроксимирован с помощью алгоритмов DFS и графа, и случайного блуждания, .... иATSP (TSP в асимметричных графах) можно аппроксимировать комбинацией линейного программирования и некоторых алгоритмов продвинутых графов.

Но существует известная классификация проблем, и мы можем расширить ее на алгоритмы, которые по времени сложны (также память, но в наши дни память не имеет значения как время):

• P
• NP
• NPC
• NPC сильный
• NP Hard
• co-NP
• ...

Answer 2

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

Некоторые подробности приведены здесь - http://www.scriptol.com/programming/algorithms-classification.php

Answer 3

Вы можете взглянуть на хранилище алгоритма Stony Brook . Это классификация алгоритмов, основанная на ее целях.

Answer 4

Существует огромное количество схем классификации алгоритмов, некоторые более полезные, чем другие (для примера очень глупой схемы, рассмотрите возможность классификации по контрольной сумме описания алгоритма!), И это является следствием того, что классификации не так уж и много фундаментальное свойство алгоритмов, а не то, что мы знаем о них. Классификация знаний очень сложна и имеет тенденцию приводить ко многим пересекающимся классификациям; Вся область построения таких классификаций называется онтологией. (Забавно, слово «онтология» также прикреплено к машиночитаемым схемам классификации на таких языках, как OWL.)

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

Answer 5

Вы можете классифицировать алгоритмы по своему желанию, так как это лучше всего подходит для ваших целей.Предложенная вами классификация контуров, которая классифицирует алгоритмы в соответствии с их схемой, выглядит хорошо.Другим подходом будет классифицировать их по назначению: сортировка, поиск, умножение и т. Д. Другой подход может классифицировать их по сложности: O (1), O (n), O (log n), O (n ^).3 ) и т. Д. Каждый отдельный алгоритм, который вы хотите классифицировать, будет вписываться в любую из этих схем классификации.

Вы можете определить иерархическую схему классификации, если вам это нужно: сортировка / случайные входы, сортировка /почти отсортированные входы, сортировка / почти несортированные входы.

Но не существует единой правильной или неправильной схемы классификации для алгоритмов, то, что вы выберете, должно зависеть от того, что вы намереваетесь делать с ним.1008 * Что касается веб-ссылок, я оставлю их другим.