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

Laravel mail error `Swift_TransportException in StreamBuffer.php line 269: Connection could not be established with host smtp.gmail.com [ #0]` -

i developing website contact-us page guest users can send me email using gmail . anytime try send mail using contact-us form, error swift_transportexception in streambuffer.php line 269: connection not established host smtp.gmail.com [ #0] this mail.php return [ 'driver' => env('mail_driver', 'smtp'), 'host' => env('mail_host', 'smtp.gmail.com'), 'port' => 587, 'from' => ['address' => '', 'name' => ''], 'encryption' => env('mail_encryption', 'tls'), 'username' => env('mail_username'), 'password' => env(mail_password), 'sendmail' => '/usr/sbin/sendmail -bs', 'pretend' => env('mail_pretend', false), ]; this .env mail_driver=smtp mail_host=smtp.gmail.com mail_port=587 mail_username=afecjaped@gmail.com mail_password=********...
Read more

c# SetCompatibleTextRenderingDefault must be called before the first -

i tried search exception couldn't find solution on case i'am using code below invoke .net application : assembly assem = assembly.load(data); methodinfo method = assem.entrypoint; var o = activator.createinstance(method.declaringtype); method.invoke(o, null); the application invoked has form , in entrypoint of application : [stathread] static void main() { application.enablevisualstyles(); application.setcompatibletextrenderingdefault(false); //exception application.run(new form1()); } setcompatibletextrenderingdefault must called before first iwin32window object created in application. edit : assembly = assembly.load(data); methodinfo method = a.gettype().getmethod("start"); var o = activator.createinstance(method.declaringtype); method.invoke(o, null); you should create new method skips initialization...
Read more