• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Menu

Article

Анализ точности решения задачи коммивояжера с помощью «антижадного» алгоритма

Чусовлянкин А. А., Морозенко В. В.

In this paper the new "anti-greedy" algorithm for the Traveling Salesman Problem is under investigation. The idea of "anti-greedy" algorithm is consequent elimination of the longest edges from graph according to two rules: every node of the graph should have two incident edges as a minimum; the graph should not have cycles with less than n edges. This algorithm finds out more exact solutions than famous polynomial algorithms, especially for non-Euclidean graphs.