Экспериментальные методы анализа алгоритмов

Ключевые слова и синонимы

Экспериментальная алгоритмистика; эмпирические алгоритмы; эмпирический анализ алгоритмов; разработка алгоритмов

Постановка задачи

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

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

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

Экспериментальный анализ алгоритмов охватывает оба этих подхода, сочетая чувствительность теоретического и инструментарий эмпирического. Эффективность алгоритмов и программ можно измерить экспериментально в соответствии с большим количеством индикаторов эффективности, включая традиционную для теоретического подхода стоимость доминирующих операций; операции в узких местах, отнимающие значительный объем времени; обновления структур данных; количество команд; стоимость обращений к памяти. Исследователь в области экспериментального анализа выбирает индикаторы эффективности, наиболее подходящие для масштаба и области действия конкретного предмета исследования. Разумеется, в исследованиях алгоритмов метрикой может служить не только время; тот же подход может использоваться для анализа других аспектов – таких как качество решения или объем требуемой памяти.

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

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

Применение

Экспериментальный анализ алгоритмов используется для изучения исследовательских задач, имеющих корни в теории вычислительных систем. К примеру, они могут возникать при анализе алгоритмов для среднего случая в одномерной задаче об упаковке контейнеров. Результатами экспериментального анализа являются открытие новых теорем об эффективности оптимального алгоритма; получение новых асимптотических границ на эффективность аппроксимационных алгоритмов для среднего случая; расширение теоретических результатов на новые модели входных данных; а также создание новых алгоритмов с более строгими гарантиями аппроксимации. Еще одним примером может служить экспериментальное обнаружение типа поведения при фазовом переходе для случайных экземпляров задачи выполнимости 3КНФ-формул, которое привело к нахождению новых способов характеризации сложности экземпляров задачи.

Еще одним вариантом применения экспериментальной алгоритмистики является поиск более реалистичных моделей вычислений, а также разработка новых алгоритмов, лучше работающих на этих моделях. Кроме того, можно найти примеры разработки новых моделей вычислений на основе памяти, дающих более точные прогнозы времени вычисления, чем традиционные модели стоимости операций в единицу времени. Использование этих моделей позволило исследователям найти новые алгоритмы, эффективные относительно использования кэша и операций ввода-вывода, которые используют свойства иерархии памяти для существенного сокращения времени исполнения. Экспериментальный анализ также используется для разработки и выбора алгоритмов, наилучшим образом работающих на практике; наиболее подходящих для конкретных категорий входных данных; а также наиболее устойчивых к плохому качеству входных данных.

Наборы данных

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

Ссылки на код

В сети Интернет есть немало репозиториев исходного кода, необходимых для поддержки экспериментальных исследований. Они обычно организованы в соответствии с конкретными комбинаторными задачами или классами задач. Репозиторий алгоритмов Стивена Скиены в университете Stony Brook University (www.cs.sunysb.edu/~algorith/) содержит обширную коллекцию формулировок задач и описаний алгоритмов, а также множество ссылок на алгоритмы в реализованном виде.

Литература

Литература по алгоритмам, содержащая примеры экспериментальных исследований, очень обширна. Некоторые примеры публикаций, включающих советы и комментарии по применению экспериментальной методологии в контексте алгоритмических исследований, приведены в списке. Упомянутые в нем журналы и материалы семинаров поддерживают исследования по экспериментальному анализу алгоритмов. Экспериментальные работы также появляются на более традиционных площадках алгоритмических исследований – таких как SODA (ACM/IEEE Symposium on Data Structures and Algorithms – Симпозиум ACM/IEEE по структурам данных и алгоритмам), Algorithmica и ACM Transactions on Algorithms.

1. ACM Journal of Experimental Algorithmics. Launched in 1996, this journal publishes contributed articles as well as special sections containing selected papers from ALENEX and WEA. Visit www. jea.acm.org, or visit portal.acm.org and click on ACM Digital Library/Journals/Journal of Experimental Algorithmics

2. ALENEX. Beginning in 1999, the annual workshop on Algorithm Engineering and Experimentation is sponsored by SIAM and ACM. It is co-located with SODA, the SIAM Symposium on Data Structures and Algorithms. Workshop proceedings are published in the Springer LNCS series. Visit www.siam.org/meetings/ for more information

3. Barr, R.S., Golden, B.L., Kelly, J.P., Resende, M.G.C., Stewart, W.R.: Designing and reporting on computational experiments with heuristic methods. J. Heuristic 1 (1), 9-32 (1995)

4. Cohen, P.R.: Empirical Methods for Artificial Intelligence. MIT Press, Cambridge (1995)

5. DIMACS Implementation Challenges. Each DIMACS Implementation Challenge is a year-long cooperative research event in which researchers cooperate to find the most efficient algorithms and strategies for selected algorithmic problems. The DIMACS Challenges since 1991 have targeted a variety of optimization problems on graphs; advanced data structures; and scientific application areas involving computational biology and parallel computation. The DIMACS Challenge proceedings are published by AMS as part of the DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Visit dimacs.rutgers.edu/Challenges for more information

6. Johnson, D.S.: A theoretician's guide to the experimental analysis of algorithms. In: Goodrich, M.H., Johnson, D.S., McGeoch, C.C. (eds.) Data Structures, Near Neighbors Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 59. American Mathematical Society, Providence (2002)

7. McGeoch, C.C.: Toward an experimental method for algorithm simulation. INFORMS J. Comp. 1(1), 1-15(1996)

8. WEA. Beginning in 2001, the annual Workshop on Experimental and Efficient Algorithms is sponsored by EATCS. Workshop proceedings are published in the Springer LNCS series