Search

Show simple item record

dc.contributor.authorШуть, Василий Николаевич
dc.contributor.authorБычинский, Д. И.
dc.contributor.authorСахарук, М. Г.
dc.coverage.spatialБрест
dc.date.accessioned2021-03-26T08:06:34Z
dc.date.available2021-03-26T08:06:34Z
dc.date.issued2002
dc.identifier.citationШуть, В. Н. Эффективный алгоритм приближенного решения метрической задачи коммивояжера / В. Н. Шуть, Д. И. Бычинский, М. Г. Сахарчук // Вестник Брестского государственного технического университета. Серия: Физика, математика, химия. – 2002. – № 5. – С. 73–75.
dc.identifier.urihttps://rep.bstu.by/handle/data/12516
dc.description.abstractВ данной статье предлагаются алгоритмы приближенного решения задачи коммивояжера. Первый алгоритм развивает известную идею построения маршрута по остовному дереву минимального веса. Дерево дополняется ребрами, соответствующими вторым ближайшим расстояниям для висячих вершин. Затем циклы в графе последовательно соединяются в единый маршрут. На промежуточных шагах используется локальный поиск. Готовый маршрут подвергается анализу с целью выявления путей его улучшения. Второй алгоритм ограниченной области предлагает способ быстрого и эффективного построения маршрута. Образование начального контура происходит путем включения крайних вершин (если проводить аналогию с картой и городами: самый северный, самый южный, самый восточный и самый западный город), не принадлежащих маршруту. Приведены результаты численного эксперимента сравнения двух вышеуказанных методов, которые подтвердили уникальность обоих алгоритмов с точки зрения максимальной оптимизации длины маршрута (первый метод) и скоростью выполнения (второй метод), необходимой для быстрого решения масштабных задач.
dc.language.isoru
dc.publisherБрГТУ
dc.titleЭффективный алгоритм приближенного решения метрической задачи коммивояжера
dc.typeСтатья (Article)
dc.identifier.udc681.3


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record