Журналы
Email: Пароль: Войти Регистрация
Мы продолжаем рассматривать псевдогеометрическую задачу коммивояжера. В частности, мы рассматриваем несколько вспомогательных алгоритмов, необходимых для реализации различных версий алгоритма «луковой шелухи». Мы не нашли в~литературе точного описания конкретных версий алгоритмов для геометрической версии (впрочем, в этом нет необходимости, поскольку исходные версии этих алгоритмов необходимо реализовать для псевдогеометрической версии), поэтому мы начинаем работу с геометрической версии.
Случайная генерация данных для вычислительных экспериментов соответствовала решаемой проблеме: для каждого из нескольких вариантов размерности задачи были проведены некоторые вычислительные эксперименты со случайно сгенерированными входными данными. Были рассчитаны следующие характеристики полученных результатов: среднее количество результирующих контуров для геометрического варианта; отношение решения с контурами к оптимальному решению; отношение решения псевдогеометрической версии, соответствующее порядку точек геометрической версии, к геометрическому решению.
Полученные результаты вычислительных экспериментов в целом приблизительно соответствуют ожидаемым значениям. (на англ.) С. 30-40.

We continue to consider the pseudo-geometric traveling salesman problem. Specifically, we are considering several auxiliary algorithms needed to implement different versions of the “onion husk” algorithm. We have not found in the literature an accurate description of specific versions of algorithms for the geometric version (however, this is not necessary, since it is necessary to implement the original versions for the pseudo-geometric version), so we start with the geometric version.
Random generation of data for computational experiments corresponded to the problem being solved.
For each of the some dimensional variants, some computational experiments were conducted with randomly generated input data.
The following characteristics were calculated: the average number of resulting contours for the geometric variant; the ratio of the solution with contours to the optimal solution; the ratio of the solution of the pseudo-geometric version corresponding to the order of points of the geometric version to the geometric solution.
The obtained results of computational experiments in general approximately correspond to the expected values.

Ключевые слова: оптимизационные проблемы, задача коммивояжера, эвристические алгоритмы, алгоритм «луковой шелухи», алгоритмы реального времени, Си++.
Keywords: optimization problems, traveling salesman problem, heuristic algorithms, ``onion husk'' algorithm, real-time algorithms, C++.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть