Sayohat qilayotgan sotuvchining izidan - In Pursuit of the Traveling Salesman

Sayohat qilayotgan sotuvchini ta'qib qilishda: Matematika hisoblash chegaralarida bu kitob sotuvchi muammosi, tomonidan Uilyam J. Kuk, tomonidan 2012 yilda nashr etilgan Prinston universiteti matbuoti, 2014 yilda qog'ozli qayta nashr etilgan.[1] Asosiy kutubxonalar ro'yxati qo'mitasi Amerika matematik assotsiatsiyasi uni bakalavriat matematikasi kutubxonalariga kiritishni taklif qildi.[2]

Mavzular

The sotuvchi muammosi samolyotda yoki mavhumroq matematik bo'shliqlarda, ballar to'plamining eng qisqa tsikli turini topishni so'raydi. Qattiq-qattiq, qabul qiladigan algoritmlar polinom vaqti uning optimal echimini topishi kafolatlanishi ehtimoldan yiroq;[3] boshqa tomondan a qo'pol kuch bilan qidirish hammasidan almashtirishlar har doim muammoni aniq hal qilar edi, ammo eng kichik muammolardan tashqari hamma uchun yaroqli bo'lishi juda uzoq vaqt talab etadi.[4] Ushbu juda tez va juda sekin ishlaydigan vaqtlar o'rtasida o'rtacha yo'lni bosib o'tish va kattaroq misollarning aniq echimini topadigan amaliy tizimni ishlab chiqish qiyin savollarni tug'diradi. algoritm muhandisligi,[5][3] bu "kombinatorial optimallashtirishning ko'plab kontseptsiyalari va texnikasi" ning rivojlanishiga sabab bo'ldi.[3]

Kitobning kirish qismida 50-yillarning o'rtalarida qo'l bilan hal qilingan 49 punktli masalalardan tortib, muammo bo'yicha hisoblash chegaralari o'rganilgan. Jorj Dantzig, D. R. Fulkerson va Selmer M. Jonson 85.900 ball bilan muammoni 2006 yilda optimal tarzda hal qilingan Concorde TSP Solver, bu Kukning rivojlanishiga yordam berdi. Keyingi boblarda muammoning dastlabki tarixi va shu bilan bog'liq muammolar, shu jumladan Leonhard Eyler ustida ishlash Kenigsbergning etti ko'prigi, Uilyam Rovan Xemilton "s Icosian o'yini,[6] va Julia Robinson birinchi bo'lib 1949 yilda muammoni nomlash.[7] Boshqa bir bobda muammoning real dasturlari tasvirlangan,[6] "genomlar ketma-ketligi va kompyuter protsessorlarini loyihalashdan tortib sayyoralar uchun musiqa va ovni tartibga solishga qadar".[8] Sharhlovchi Brayan Xeys kitobning "eng jozibali vahiysi" ni ushbu haqiqiy dasturlardan biri haqiqiy sayohat uchun marshrutni rejalashtirish bo'lganligi deb ta'kidlaydi. sotuvchilar 20-asrning boshlarida.[4]

To'rt-etti boblar, "kitobning yadrosi", muammoni hal qilish usullarini muhokama qiladi evristika va metaevristika, chiziqli dasturlash gevşemesi va tekislik usullari, ga qadar filial va bog'langan ushbu metodlarni birlashtirgan va Konkord tomonidan qo'llaniladigan usul. Keyingi ikki bobda, shuningdek, kompyuter dasturlarini bajarish bo'yicha texnik materiallar va Hisoblash murakkabligi nazariyasi muammoning.[6][9]

Qolgan boblar odamlarga yo'naltirilgan bo'lib, odamlar va hayvonlarning muammolarini hal qilish strategiyasini va TSP echimlarini san'at asarlariga kiritishni o'z ichiga oladi. Julian Letbridge, Robert Bosch va boshqalar.[6][10] Qisqa yakuniy xulosalar bobida kelajakdagi mumkin bo'lgan yo'nalishlar, shu jumladan, bu borada rivojlanish imkoniyatlari ko'rsatilgan P va NP muammosi.[6][11]

Tomoshabinlar

Kitob mutaxassis bo'lmagan auditoriya uchun mo'ljallangan, texnik tafsilotlardan qochgan[3][5][12] va "tushunarli uslubda" yozilgan.[13] Unda ko'plab tarixiy asarlar, misollar, qo'llanmalar va hikoyaning asosiy ishtirokchilarining biografik ma'lumotlari va fotosuratlari mavjud bo'lib, uni matematik asosga ega bo'lmagan o'quvchilarga taqdim etish mumkin.[10][12]

Garchi Sayohat qilayotgan sotuvchining izidan Darslik emas, sharhlovchi Kristofer Tompson chiziqli dasturlash va masalaning qo'llanilishidagi ba'zi materiallarni "sinfda foydalanish uchun juda mos keladi", deb ta'kidlaydi, xususan uning bir nechta sohalarni bog'lash usuli. raqamli tahlil, grafik nazariyasi, algoritm dizayn, mantiq va statistika.[14]

Sharhlovchi Sten Vagon "kombinatorial algoritmlarga qiziqqan har qanday o'quvchi ushbu kitobda katta ahamiyatga ega bo'ladi" deb yozadi.[5] Jan Karel Lenstra va Devid Shmoys "Yozish qulay va qiziqarli; taqdimot juda yaxshi. Biz uni o'qishdan juda zavqlandik" deb yozing.[3] Va sharhlovchi Xaris Aziz "Kitob har qanday kishiga matematik qiziqish va g'oyalarni rivojlantirishga qiziqish bilan tavsiya etiladi" degan xulosaga keladi.[10]

Tegishli ishlar

Kukning Concorde bilan ishlashining batafsil tafsilotlarini, muammo va shunga o'xshash mavzular bo'yicha jiddiyroq tadqiqotchilar uchun mos bo'lgan, Kukning avvalgi kitobida topishingiz mumkin. Devid Applegate, Robert E. Biksi va Vatslav Chvatal, Sayohatchining sayohatchisi muammosi: hisoblash tadqiqotlari (2007).[2][4][10]Sayohatchining sotuvchisi muammosiga oid boshqa kitoblar, shuningdek, texnik jihatdan Sayohat qilayotgan sotuvchining izidan, o'z ichiga oladi Sayohat qiluvchi sotuvchi muammosi: Kombinatorial optimallashtirish bo'yicha ekskursiya (Lawler, Lenstra, Rinnooy Kan va Shmoys tomonidan, 1985) va Sayohat qiluvchi sotuvchi muammosi va uning o'zgarishi (Gutin va Punnen tomonidan, 2006).[10]

Adabiyotlar

  1. ^ Zbl  1301.00021
  2. ^ a b Gittleman, Art (2012 yil fevral), "Sharh Sayohat qilayotgan sotuvchining izidan", MAA sharhlari, Amerika matematik assotsiatsiyasi
  3. ^ a b v d e Lenstra, Yan Karel; Shmoys, Devid (2016), "Sharh Sayohat qilayotgan sotuvchining izidan", Amerika Matematik Jamiyati to'g'risida bildirishnomalar, 63 (6): 635–638, doi:10.1090 / noti1397, JANOB  3495222
  4. ^ a b v Xeys, Brayan (2012 yil may-iyun), "Matematik yo'l sayohatlari (sharh Sayohat qilayotgan sotuvchining izidan)", Amerikalik olim, 100 (3): 252–254, JSTOR  23223051
  5. ^ a b v Vagon, Sten (2012), "Sharh Sayohat qilayotgan sotuvchining izidan", Amerika matematik oyligi, 119 (9): 808–811, doi:10.4169 / amer.math.monthly.119.09.808, JSTOR  10.4169 / amer.math.monthly.119.09.808, JANOB  3013985
  6. ^ a b v d e Verner, Frank (2012), "Sharh Sayohat qilayotgan sotuvchining izidan", Matematik sharhlar, JANOB  2866515
  7. ^ Schuessler, Jennifer (2012 yil 15 mart), "Villi Loman, qayerdasiz? (Sharh Sayohat qilayotgan sotuvchining izidan)", The New York Times
  8. ^ Benker, Xans, "Sharh Sayohat qilayotgan sotuvchining izidan", zbMATH, Zbl  1236.00007
  9. ^ Baldacci, Roberto (2013 yil iyul - avgust), "Sharh Sayohat qilayotgan sotuvchining izidan", Interfeyslar, 43 (4): 391, JSTOR  23481217
  10. ^ a b v d e Aziz, Xaris (2012 yil avgust), "Sharh Sayohat qilayotgan sotuvchining izidan", ACM SIGACT yangiliklari, 43 (3): 51, doi:10.1145/2421096.2421108
  11. ^ Makgonigal, Frensis (2012 yil yanvar), "Sharh Sayohat qilayotgan sotuvchining izidan", IMA kitob sharhlari, Matematika instituti va uning qo'llanilishi
  12. ^ a b Tirado Dominuez, Gregorio (2012 yil noyabr), "Sharh Sayohat qilayotgan sotuvchining izidan", EMS sharhlari, Evropa matematik jamiyati
  13. ^ Shefer, Robert (2012 yil yanvar), "Sharh Sayohat qilayotgan sotuvchining izidan", Nyu-York jurnali
  14. ^ Tompson, Kristofer (2012 yil fevral), "Sharh Sayohat qilayotgan sotuvchining izidan", Yaqinlashish, Amerika matematik assotsiatsiyasi, doi:10.4169 / loci003821

Qo'shimcha o'qish