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