Алгоритмическая техника - Википедия - Algorithmic technique

В математика и Информатика, алгоритмическая техника[1] это общий подход к реализации процесса или вычисление.[2]

Общие техники

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

Грубая сила

Грубая сила это простой, исчерпывающий метод, который оценивает все возможные результаты, чтобы найти решение.[4]

Разделяй и властвуй

В разделяй и властвуй Методика рекурсивно разбивает сложные проблемы на более мелкие подзадачи. Затем каждая подзадача решается, и эти частичные решения объединяются для определения общего решения. Этот метод часто используется для поиска и сортировки.[5]

Динамический

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

Эволюционный

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

Обход графа

Обход графа это метод поиска решений проблем, который можно представить как графики. Это широкий подход, включающий поиск в глубину, поиск в ширину, обход дерева и многие конкретные варианты, которые могут включать локальную оптимизацию и исключение пространств поиска, которые могут быть определены как неоптимальные или невозможные. Эти методы могут использоваться для решения множества проблем, включая: кратчайший путь и проблемы удовлетворения ограничений.[8]

Жадный

А жадный подход начинается с оценки одного возможного результата из набора возможных результатов, а затем локально ищет улучшения этого результата. При обнаружении локального улучшения процесс повторяется и снова локально ищет дополнительные улучшения вблизи этого локального оптимума. Жадный метод, как правило, прост в реализации, и эти серии решений можно использовать для поиска локальных оптимумов в зависимости от того, где начался поиск. Однако жадные методы могут не определить глобальный оптимум для всего набора возможных результатов.[9],

Эвристический

А эвристический Подход использует практический метод для немедленного достижения решения, не гарантирующего оптимального.[10]

Учусь

Учусь методы используют статистические методы для выполнения категоризации и анализа без явного программирования. Контролируемое обучение, обучение без учителя, обучение с подкреплением, и глубокое обучение техники включены в эту категорию.[11]

Математическая оптимизация

Математическая оптимизация - это метод, который можно использовать для вычисления математического оптимума путем минимизации или максимизации функции.[12]

Моделирование

Моделирование это общий метод абстрагирования реальной проблемы в рамках или парадигма что помогает с решением.[13]

Рекурсия

Рекурсия - это общий метод разработки алгоритма, который вызывает сам себя с все более простой частью задачи до одного или нескольких базовых случаев с определенными результатами.[14][15]

Смотрите также

Примечания

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

внешняя ссылка