Конкурс по реализации алгоритмов поиска кратчайших путей: различия между версиями

Конкурсы DIMACS по реализации алгоритмов (http://dimacs.rutgers.edu/Challenges/) представляют собой научные мероприятия, целью которых является оценка практической эффективности алгоритмов в экспериментальных условиях, что способствует эффективному распространению технологий и согласованию общих эталонных тестов для фундаментальных вычислительных задач. Эти конкурсы организует DIMACS – Центр дискретной математики и теории вычислительных систем (Center for Discrete Mathematics and Theoretical Computer Science). Одной из основных целей конкурсов DIMACS по реализации алгоритмов является разрешение вопросов определения производительности реалистичных алгоритмов, для которых наихудший случай оказывается чрезмерно пессимистичным, а вероятностные модели – слишком нереалистичными: экспериментальные подходы могут привести к получению алгоритмов с реалистичными показателями эффективности в случаях, когда их невозможно получить при помощи анализа. Эксперименты также позволяют приблизить алгоритмические вопросы к исходным задачам, которые стали стимулом для теоретических изысканий. Кроме того, они дают возможность проверить различные предположения о методах реализации и структурах данных. Они предоставляют возможность для разработки и тестирования экземпляров задач, генераторов экземпляров и иных методов тестирования и сравнения эффективности алгоритмов. И, наконец, они помогают технологиям сделать еще шаг вперед, предоставляя самые передовые подходы к реализации алгоритмов для освоения и внедрения другими людьми и организациями.