O SOLUŢIE APROXIMATIVĂ A PROBLEMEI COMIS-VOIAJORULUI FOLOSIND UN SET DE EURISTICI

Dmitri TERZI

Abstract


A fost dezvoltată și investigată experimental o metodă de soluționare a problemei comis-voiajorului folosind un set de euristici. Complementaritatea, polinomialitatea algoritmică și semnificația practică a euristicii au fost principalele criterii pentru includerea ei într-un set pentru a aborda spre crearea unei metode precise de rezolvare a problemelor cu o dimensiune suficient de mare într-un timp rezonabil.

 

AN APPROXIMATE SOLUTION TO THE TRAVELING SALESMAN PROBLEM  USING A SET OF HEURISTICS

A method of solving the commissioner's problem using a set of heuristics was developed and investigated experimentally. Complementarity, algorithmic polynomiality and the practical significance of heuristics were the main criteria for including it in a set in order to approach the creation of a precise method of solving many problems in a reasonable time.


Keywords


traveling salesman problem, heuristic algorithm, approximate solution.

Full Text:

PDF

References


ПАПАДИМИТРИУ, Х., СТАЙГЛИЦ, К. Комбинаторная оптимизация: Алгоритмы и сложность. Москва: Мир, 1985.

https://www.swmath.org/software/983

ЧУСОВЛЯНКИН, А.А., МОРОЗЕНКО, В.В. Анализ точности и времени решения задачи коммивояжера с по-мощью "антижадного" алгоритма. В: Вестник Пермского университета. Математика. Механика. Инфор-матика. Вып. 4(35), 2016.

АСАНОВ, М., БАРАНСКИЙ, В., РАСИН, В.В. Дискретная математика: графы, матроиды, алгоритмы. СПб.: Лань, 2010.

КОНОНОВ, А.В., КОНОНОВА, П.А. Приближенные алгоритмы для NP-трудных задач. Новосибирск: РИЦ НГУ, 2014.

МУДРОВ, В.И. Задача о коммивояжере. Москва: Знание, 1969.

http://www.maps-of-europe.com/maps/maps-of-moldova/political-and-administrative-map


Refbacks

  • There are currently no refbacks.