Jūs esate čia: Pradžia » Visos temos » Mokslas » Įdomusis mokslas |
Tai straipsnis iš rašinių ciklo. Peržiūrėti ciklo turinį
|
Šį uždavinį šimtai mokslininkų tebesprendžia daugiau nei 50 metų, sprendimo autoriui žadamos milijoninės premijos, tačiau sprendimo ne tik kad nėra, bet ir neaišku, ar jis išvis egzistuoja. Prisijunk prie technologijos.lt komandos! Laisvas grafikas, uždarbis, daug įdomių veiklų. Patirtis nebūtina, reikia tik entuziazmo. Sudomino? Užpildyk šią anketą!
O uždavinio sąlyga labai paprasta: rasti keliaujančiam pirkliui trumpiausią miestus jungiantį maršrutą, kuris prasideda ir baigiasi tame pačiame mieste. Dėl internetinės prekybos išnykus keliaujantiems pirkliams, atrodytų, uždavinys turėjo prarasti aktualumą (na, išskyrus pokemonų gaudytojus, kuriems svarbu surasti visus pokemonus savo mieste medžioklę pradedant ir užbaigiant savo namuose). Tačiau taip neįvyko. Keliaujančio pirklio uždavinys daug įdomesnis nei atrodo iš pirmo žvilgsnio. IstorijaKeliaujančio pirklio uždavinys, manoma, buvo sugalvotas – ar bent jau paskelbtas – XIX amžiuje. Mokslininkai jį tuomet suformulavo kaip trumpiausio Hamiltono ciklo radimo pilnai jungiame grafe uždavinį, o buitiškesnis „keliaujančio pirklio uždavinio“ pavadinimas atsirado tik po šimtmečio. Keliaujančio pirklio bėdos rimtesnio matematikų susidomėjimo sulaukė tik 1930 m. Atsiradus skaičiavimo mašinoms, šis uždavinys tapo dar svarbesnis: jam spręsti buvo kuriami įvairūs algoritmai, rengiami optimalių maršrutų sudarymo konkursai, uždavinio sprendinių pavaizdavimu susidomėjo ir skaitmeninio meno kūrėjai. Žymiausią ir daugiausiai matematikų dėmesio atkreipusį keliaujančio pirklio uždavinio konkursą 1962 m., reklamuodama televizijos serialą „Car 54“, paskelbė kompanija Procter & Gamble. Konkurso dalyviams reikėjo surasti trumpiausią maršrutą, kuriuo serialo herojai policininkai Toody ir Muldoon aplankytų 33 JAV miestus. Nugalėtojo laukė 10 tūkstančių dolerių, už kuriuos 7 dešimtmetyje JAV buvo galima nusipirkti namą. Prizu susigundė ir matematikai, tad galiausiai prizą teko padalinti daugybei „teisingo“ sprendinio autorių.
Tuomet atrodęs itin sudėtingas uždavinys, dabar lengvai išsprendžiamas. Pavyzdžiui, 2004 m. buvo rastas trumpiausias, ~72 tūkst. kilometrų ilgio, maršrutas, jungiantis 24978 Švedijos miestus. Uždavinio sudėtingumasTai kurgi visas uždavinio sudėtingumas? Miestų skaičius žinomas ir antrąkart lankytis tame pačiame mieste draudžiama, – vadinasi, galimų maršrutų skaičius ribotas ir tereikia juos visus patikrinti! Šioje vietoje visgi sustokime ir paskaičiuokime… Kadangi paskutinis maršruto miestas sutampa su pirmuoju, kiekvienam iš 33 miestų priskyrę po raidę, visą galimą maršrutą, kokia tvarka reikia aplankyti miestus, galime patogiai užrašyti tokia simbolių eilute: A Ā B C Č D E Ē F G Ģ
|
Visi šio ciklo įrašai:
|