В математике и информатике , А.Н. алгоритмическая методика [1] является общим подходом к реализации процесса или вычислений . [2]
Общие техники
Существует несколько широко известных алгоритмических методов, которые предлагают проверенный метод или процесс для проектирования и построения алгоритмов. В зависимости от цели могут использоваться различные методы, которые могут включать в себя поиск , сортировку , математическую оптимизацию , удовлетворение ограничений , категоризацию , анализ и прогнозирование . [3]
Грубая сила
Грубая сила - это простой исчерпывающий метод, который оценивает все возможные результаты, чтобы найти решение. [4]
Разделяй и властвуй
Метод « разделяй и властвуй » рекурсивно разбивает сложные проблемы на более мелкие подзадачи. Затем каждая подзадача решается, и эти частичные решения объединяются для определения общего решения. Этот метод часто используется для поиска и сортировки. [5]
Динамический
Динамическое программирование - это систематический метод, при котором сложная проблема рекурсивно декомпозируется на более мелкие перекрывающиеся подзадачи для решения. В динамическом программировании результаты перекрывающихся подзадач сохраняются локально с использованием метода оптимизации, называемого мемоизацией . [6]
Эволюционный
Эволюционный подход разрабатывает варианты решения , а затем, в манере , подобной биологической эволюции, выполняет ряд случайных изменений или комбинации этих решений и оценивает новые результаты в отношении фитнес - функции. Наиболее подходящие или многообещающие результаты выбираются для дополнительных итераций, чтобы достичь общего оптимального решения. [7]
Обход графа
Обход графа - это метод поиска решений проблем, который можно представить в виде графиков . Этот подход является широким, и включает в себя поиск в глубине , поиска в ширину , обход дерева , и множество вариаций конкретных , которые могут включать в себя локальные оптимизации и исключая пространство поиска , которые могут быть определены , чтобы быть не оптимальными или не представляется возможными. Эти методы могут использоваться для решения множества проблем, включая задачи поиска кратчайшего пути и ограничения. [8]
Жадный
Жадный подход начинается с оценкой один возможный исхода из множества возможных исходов, а затем выполняет поиск локально для улучшения по этому результату. При обнаружении локального улучшения процесс повторяется и снова локально ищет дополнительные улучшения, близкие к этому локальному оптимуму. Жадный метод, как правило, прост в реализации, и эти серии решений можно использовать для поиска локальных оптимумов в зависимости от того, где начался поиск. Однако жадные методы не могут определить глобальный оптимум для всего набора возможных результатов. [9]
Эвристический
Эвристический подход использует практический метод , чтобы достичь немедленного решения не гарантированно будет оптимальным. [10]
Обучение
В методах обучения используются статистические методы для категоризации и анализа без явного программирования. Контролируемое обучение , бесконтрольное обучение , обучение с подкреплением , и глубокими учебные методы включены в этой категории. [11]
Математическая оптимизация
Математическая оптимизация - это метод, который можно использовать для вычисления математического оптимума путем минимизации или максимизации функции. [12]
Моделирование
Моделирование - это общий метод абстрагирования реальной проблемы в рамках или парадигмы, которые помогают в решении. [13]
Рекурсия
Рекурсия - это общий метод разработки алгоритма, который вызывает сам себя с все более простой частью задачи до одного или нескольких базовых случаев с определенными результатами. [14] [15]
Смотрите также
- Разработка алгоритмов
- Характеристики алгоритмов
- Теория вычислений
Заметки
- ^ "техника | Определение техники на английском языке по Оксфордским словарям" . Оксфордские словари | Английский . Проверено 23 марта 2019 .
- ^ Cormen, Thomas H .; Leiserson, Charles E .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). Введение в алгоритмы . MIT Press. п. 9. ISBN 9780262032933.
- ^ Скиена, Стивен С. (1998). Руководство по разработке алгоритмов: Текст . Springer Science & Business Media. ISBN 9780387948607.
- ^ «Что такое грубая сила? Определение в Webopedia» . www.webopedia.com . Проверено 23 марта 2019 .
- ^ Бентли, Джон Луи; Шамос, Майкл Ян (1976). «Разделяй и властвуй в многомерном пространстве». Материалы восьмого ежегодного симпозиума ACM по теории вычислений . STOC '76. Нью-Йорк, Нью-Йорк, США: ACM: 220–230. DOI : 10.1145 / 800113.803652 .
- ^ Беллман, Ричард (1966-07-01). «Динамическое программирование». Наука . 153 (3731): 34–37. DOI : 10.1126 / science.153.3731.34 . ISSN 0036-8075 . PMID 17730601 .
- ^ Коэльо Коэльо, Карлос А. (1999-08-01). «Комплексный обзор методов многокритериальной оптимизации на основе эволюции». Знания и информационные системы . 1 (3): 269–308. DOI : 10.1007 / BF03325101 . ISSN 0219-3116 .
- ^ Кумар, Нитин; Уэйн, Кевин (2014-02-01). Алгоритмы . Эддисон-Уэсли Профессионал. ISBN 9780133799101.
- ^ «жадный алгоритм» . xlinux.nist.gov . Проверено 23 марта 2019 .
- ^ «эвристический» . xlinux.nist.gov . Проверено 23 марта 2019 .
- ^ Виттен, Ян Х .; Франк, Эйбе; Холл, Марка А .; Пал, Кристофер Дж. (2016-10-01). Data Mining: практические инструменты и методы машинного обучения . Морган Кауфманн. ISBN 9780128043578.
- ^ Марлер, RT; Арора, JS (2004-04-01). «Обзор методов многокритериальной оптимизации для проектирования». Структурная и междисциплинарная оптимизация . 26 (6): 369–395. DOI : 10.1007 / s00158-003-0368-6 . ISSN 1615-1488 .
- ^ Скиена, Стивен С. (1998). Руководство по разработке алгоритмов: Текст . Springer Science & Business Media. ISBN 9780387948607.
- ^ «рекурсия» . xlinux.nist.gov . Проверено 23 марта 2019 .
- ^ «Программирование - Рекурсия» . www.cs.utah.edu . Проверено 23 марта 2019 .
Внешние ссылки
- Алгоритмический дизайн и методы - edX
- Алгоритмические методы и анализ - Карнеги-Меллон
- Алгоритмические методы для массивных данных - MIT