traveling salesman - Does the optimum solution of a TSP remain the optimum even after skipping a few cities? -


let's know global optimum solution 100-city standard travelling salesman problem. now, lets salesman wants skip on 5 of cities. tsp have re-solved? sequence of cities obtained deleting cities previous optimum solution global optimum new 95-city tsp?

updated: replaced counterexample euclidean instance.

great question.

no, if remove cities, original sequence of cities not remain optimal. here counterexample:

enter image description here

the node coordinates are:

0 0 4 0 4 2 2.6 3 10 3 4 4 4 6 0 6

here optimal tour:

enter image description here

now suppose don't need visit node 5. if "close up" original tour, resulting tour has cost of 21.94:

enter image description here

but optimal tour has cost of 21.44:

enter image description here

(if want remove 5 cities instead of 1, put 5 cities close way on right.)


Comments

Post a Comment

Popular posts from this blog

php - How to add and update images or image url in Volusion using Volusion API -

actually have store importing products store product data insert , update image or image url not insert , update. this xml code name datapro.txt. <products_joined> <productcode>3710_012t</productcode> <vendor_partno>eah5450silent/di/1gd3(lp)</vendor_partno> <productname>test product ta</productname> <hideproduct>n</hideproduct> <stockstatus>20</stockstatus> <lastmodified>1/5/2016 10:25:00 am</lastmodified> <lastmodby>2</lastmodby> <productweight>0.9</productweight> <productprice>100</productprice> <productmanufacturer>asus tek</productmanufacturer> <vendor_price>32.69</vendor_price> <numproductssharingstock>0</numproductssharingstock> <categoryids>107</categoryids> <producturl>http://tebkq.mvlce.servertrust.com/productdetails.asp?productcode=3710_012t</producturl>
Read more

javascript - jQuery UI Splitter/Resizable for unlimited amount of columns -

using jqueryui splitter or resizable functions want create layout allows unlimited amount of columns added , columns need resizable. so fiddle: https://jsfiddle.net/f3glh3mw/ but in fiddle html contains out of nested sets instead of inline. limits possibilities above fiddle can have equal widths 2,4,8,16,32 etc columns. in between shows crooked can see in fiddle. when researching came on question: jquery ui , splitter if @ top answer shows structure like: <div class="wrap"> <div class="resizable resizable1"></div> <div class="resizable resizable2"></div> </div> full fiddle: http://jsfiddle.net/8qztj/86/ which structure want javascript hardcoded 2 resizable items. so here question: how modify last fiddle works amount of .resizable divs. or know of plugin can this. thanks helping! so far found plugin: http://www.bacubacu.com/colresizable/ which says , close functionality want. in
Read more

javascript - IE9 error '$'is not defined -

Image
<!--[if lte ie 9]><html class="lte9"><![endif]--><!--[if gt ie 9]><html><![endif]--> <!--[if !ie]><!--> <html> <!--<![endif]--> blah blah <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.1/jquery.min.js"></script> <script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/js/bootstrap.min.js"></script> <script src="{{ asset('js/mypage.js') }}" type="text/javascript"></script> </body> </html> when load page, ie9 brings error '$' not defined . how can solve error? +++ mypage.js $(function(){ //when load page, //ie9 tag not moving. $(window).load(function() { $('div.mask').hide(); }); // when click , willshow show. //for not ie 9 if (!$('html').hasclass('lte9')) { var = $('ul.about > li > span.activebtn');
Read more