algorithm - Traveling salesman (TSP): what is the Relation with number of vertices and length of the found route? -


i know there many algorithms (exact or approximate) implement traveling salesman problem.

i know relation between number of vertices (i.e., places visit) , length of route found these algorithms.

intuitively, less number of vertices, shorter route is. but, can 1 give me math relation between number of vertices , length of route found @ least 1 of existing traveling salesman algorithms?

thanks in advance.

in general given n nodes, let set of costs defined c = { c(i, j) = cost traverse edge node n(i) n(j) : 0 ≤ i, j < n , i, j integers}.

a naive bounding of closed circuit path total distance bounded below n*min(c) , above n*max(c) min(c) minimum cost traverse edge between 2 nodes, , max(c) maximum cost traverse edge between 2 nodes.

if looking shortest path not in circuit becomes (n-1)*min(c) , (n-1)*max(c) respectively.

beyond that, there variety of methods getting better upper bounds , better lower bounds.


Comments

Post a Comment

Popular posts from this blog

IF statement in MySQL trigger -

this query code in mysql trigger. if 1=2 select 'yes'; else select 'no'; end if; but has following error: if '1'='2' select 'yes' error code: 1064. have error in sql syntax; check manual corresponds mysql server version right syntax use near 'if '1'='2' select 'yes'' @ line 1 0.000 sec what solution?
Read more

c++ - What does MSC in "// appease MSC" comments mean? -

i run across // appease msc in c++ comments, e.g. here : const int& array::operator[](int offset) const { int mysize = getitssize(); if (offset >= 0 && offset < getitssize()) return ptype[offset]; throw xboundary(); return ptype[offset]; // appease msc! } what msc stand ? the author means microsoft's compiler, more formally known msvc.
Read more

android - MPAndroidChart - How to add Annotations or images to the chart -

i working latest mpandroidchart library , looking way add annotations or images clickable. example: once data reaches value event occurs want able display user - there multiple events can occur annotations (not sure if right word) or image added @ point in chart. any pointers welcome. check documentation of yaxis . focus on setspacetop(...) , setaxismaxvalue(...) methods. for background: bar-shadow , disable calling: barchart.setdrawbarshadow(false) or change color: bardataset.setbarshadowcolor(int color)
Read more