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

Восьмой конкурс DIMACS по реализации алгоритмов, проведенный DIMACS – Центром дискретной математики и теории вычислительных систем (Center for Discrete Mathematics and Theoretical Computer Science), был посвящен эвристикам для симметричной задачи коммивояжера. Организаторами конкурса, начавшегося в июне 2000 года, стали Дэвид Джонсон, Лайл Макгиох, Фред Гловер и Сезар Рего. В его рамках изучалось современное состояние дел в области эвристик для задачи коммивояжера, а исследователи протестировали широкий спектр реализаций на общем (и крайней разнообразном) наборе экземпляров входных данных. Конкурс продолжался вплоть до 2007 года, а новые результаты все еще принимаются на сайте www.research.att.com/~dsj/chtsp. Обзор результатов на 2002 год был приведен в книге Джонсона и Макгиоха [5].

Для каждого экземпляра, для которого тестировалась эвристика, участники сообщали название используемой машины, полученную длину маршрута, пользовательское время процесса и, при наличии таких данных, объем использованной памяти. Некоторые эвристики невозможно было применить ко всем экземплярам – либо в силу исходно геометрической природы этих эвристик, либо из-за чрезмерно большого размера экземпляра. Чтобы получить возможность сравнения времени выполнения эвристик на разных машинах, участники выполняли эталонную эвристику (предоставленную организаторами) на экземплярах разных размеров. Затем время выполнения эталонного образца использовалось для нормализации (хотя бы приблизительной) наблюдаемого времени выполнения эвристик участников.