Lasīju te pēdējā laikā klasiku, un nopietni populārzinātniski darbi tika pamesti novārtā. Skaidra lieta, ka ilgi tas tā nevarēja vilkties. Nolēmu pievērsties ceļojošā tirgotāja problēmai (TSP). Par šo problēmu biju domājis jau no bērna kājas pat nezinot, ka gudri vīri tam ir veltījuši daudzus gadus. Ideja ir pavisam vienkārša. Piemēram, tu gribi apceļot visus bijušos Latvijas PSR rajonu centrus, tādi ir veseli piecdesmit deviņi. Tā kā laika tev nav daudz, tad tu vēlies viņus apskatīt veicot pēc iespējas mazāku ceļu gabalu. Tātad viss, kas jāizdara, ir jāatrod īsākais ceļš, lai apmeklētu visus rajonu centrus un atgrieztos starta punktā.

Grāmata ir veltīta tieši šādām problēmām, kā atrast īsāko ceļu starp n punktiem. Viens paņēmiens ir pavisam vienkāršs – ņemam un apskatām visus iespējamos ceļus, sasummējam kopgarumu un beigās izvēlamies īsāko. Nav slikts variants, ja šādu punktu ir, teiksim, 5. Tas mums liktu apskatīt nieka 120 ceļus un dienas laikā mums būtu skaidrs, kur kā braukt. Tomēr 59 ir daudz nopietnāks izaicinājums! Te būtu jāapskata veseli 1.38683119 × 10^80 ceļi. Tas ir diezgan ievērojams daudzums, un kļūst skaidrs, ka ar vienkāršu ceļu pārlasi nekāda aršana nebūs.

Šajā grāmatā autors ir apkopojis populārākos algoritmus, kas ļauj TSP problēmu atrisināt efektīvāk, lai gan negarantē optimālo rezultātu. Te ir gan lineārā algebra, gan dažādi viltīgi paņēmieni, kas palīdz problēmu atrisināt to darot pa daļām. Ir pat paņēmieni, kurus gan es vairāk sauktu par izmisuma soļiem, testēt cik labi pērtiķis spēj uzlasīt izmētātu barību, vai testējot cilvēka spējas atrast optimālu risinājumu, savienojot ar zīmuli punktiņus. Cilvēks kopumā ir diezgan spējīgs TSP problēmu risinātājs, parasts cilvēks iekļaujas ceļā, kas vidēji par optimālo maršrutu ir tikai ~25% lielāks.

Galvenais uzdevums joprojām ir, atrast algoritmu, kas spētu atrast optimālo ceļu ātrāk nekā pilnīga pārlase, vai arī pierādīt, ka šāds universāls algoritms neeksistē. Vēl varētu rasties jautājums par šīs problēmas praktisko pielietojumu tautsaimniecībā. Pirmais un būtiskākais ir loģistikas ceļu sakārtošana, optimālais ceļš palīdz atrast lētāko kravus sūtīšanas, piegādes maršrutu. Otra populāra lieta ir iespiedplašu ražošana, tas palīdz samazināt izmaksas līdz pat trīsdesmit procentiem.

Ja nu kādam ir uznākusi luste dot savu ieguldījumu šīs problēmas risinājumā var iesākumā apskatīt šo rīku. Tas savulaik ir devis diezgan lielu ieguldījumu TSP problēmu risināšanā un Latvijas PSR rajonu centru problēmu atkodīs visai viegli. Ja paveiksies, tad, iespējams, pierādīsi, ka N=NP, jeb tautas vārdiem runājot, pierādīsi, ka jebkuru problēmu, kuras atrisinājuma pareizību var ātri pārbaudīt ar datoru, var arī ātri atrisināt ar to. Clay Matemātikas institūts par šī apgalvojuma pierādījumu ir gatavi maksāt veselu miljonu dolārus.

Grāmatas sākums, kur rakstīts par problēmas vēsturi un agrīnajām risināšanas metodēm, lasījās tīri labi. Tomēr, tiekot līdz nodaļām, kur manas matemātikas zināšanas vairs nebija tik labas, lasīšana kļuva grūtāka un varētu pat teikt neinteresantāka. Nē, algoritmi mani vienmēr ir aizrāvuši, tomēr te ar matemātiku jābūt ļoti lielos draugos, pamatus jau it kā saproti, bet par pilnīgu izpratni gan es nevarētu runāt. Ja nepatīk matemātika, tad interesanti būs lasīt kādas četras grāmatas nodaļas. Kopumā lieku 8 no 10 ballēm.