Jau 50 metų neįveikiamas keliaujančio pirklio uždavinys: išspręsite - milijoninės premijos garantuotos

Smagiai persiskaite

Labai paprastas sprendimas, kaip issprest ir rast rumpiausia marsruta. Nematau cia jokio sudetingumo. Algoritmas butu per tris uzdavinio supaparastinimo etapus iki elementaraus varianto, kuri kompas suskaiciuotu per sekundes. Galiu pasufleruot - sis uzdavinys tiesiogiai susijes su kitu uzdaviniu - optimaliausiu sujungimu tarp daug tasku kelio radimo. Apie uzdavini teko skaityt matematikos idomybiu knygoje pries keleta metu - dar tada sugalvojau sprendima. Negi iki siol niekas nesumaste? Duomenis suvedinet ilgiau uztruktu, negu suskaiciuot. Geriau rasykit smulkia instrukcija, kaip gaut ta premija, nes labai miglotai siulo. Man visiskai neaisku kur cia kreiptis, nemanau kad cia isvis aktuali matematine problema...

Pasirodo Lietuvoje turime neatrasta talenta

: Tai kad čia yra „optimaliausiu sujungimu tarp daug tasku kelio radimo“ uždavinys. Labai kietas pasiūlymas: NP-Hard klasės (eksponentinio sudėtingumo) kombinatorinį uždavinį spręsti suvedant jį į save patį... Problema ta, kad šio uždavinio neįmanoma išspręsti dalimis, nes optimalus atskirų Oilerio ciklų sujungimas pats savaime yra eksponentinio sudėtingumo uždavinys. T.y. gali būti, kad į optimalų komivojažieriaus maršrutą įtraukus naują viršūnę, naujasis maršrutas su senuoju neturės nė vienos bendros briaunos.

Nesupranti tu sito uzdavinio visiskai. Tame ir reikalas, kad jis nera eksponentinis, tik taip yra galvojama. Jei itrauki nauja marsruta - tiesiog isideda papildoma grandis jau esanciam marsrute. Sprendimo algoritme sudetine dalis yra butent ne perskaiciavimas visu naujai atsirandanciu marsrutu, o naujos grandies vietos paieska. Ir tada nereikia tikrint su visom grandim - tereikia isiterpt. Skaiciavimo progresija netampa geometrine. As net erdvej galiu paskaiciuot optimaliausia marsruta, nors cia tepraso tik plokstumoj. Ta prasme duok man koordinates kokiu nors milijardo zvaigziu erdveje ir duosiu sprendima optimaliausio marsruto keliaujanciam pirkliui. As nezinau del ko cia neissprendzia - nemoka salygu aprasyt greiciausia... As tiesiog zinau kaip teisingai apribot skaiciavimu kieki, ir tiek. Ir irodyta kad mano apribojimo metodas duoda geriausia galima varianta (kitu irodyta, net sitai man nebutina daryt ). Dar ten straipsny siektiek netiesa raso. Raso kad galima paskaiciuot koks bus bendras ilgis optimaliausio marsruto. Is tikro tas ilgis greiciausiai nesutaps lygiai per vieno marsruto ilgi. Nors kai nepateikta metodika - tai tiksliai negaliu pasakyt. Gal ir sutaps. Arba nesutaps per viena. Ta prasme sitas teiginys neirodytas, o straipsny teigia, kad tai isankstine taisykle

Oi ne taip paprasta... Pavyzdžiui, teiginį Akivaizdu: jei turi optimalų maršrutą be Jonavos ir nori rasti optimalų maršrutą su Jonava, neužtenka rasti du miestus, tarp kurių reikia "įsiterpti". Būtina tikrinti su ne vienu prieš tai rastu maršrutu, kas ir yra dinaminio programavimo algoritmas.

Kur as tau sakiau, kad reikia isiterpt konkreciai tarp "dvieju miestu"? Cia tavo prielaida, kuri neteisinga. Tu labai pazodziui supratai viska. Kai ismeti jonava, issimeta viena jungtis. Ir iskart keiciasi dar dvi jungtys. Tada tikrini. tada dar galbut keiciasi dvi jungtys. Vel tikrini. O ne eksponentinis procesas vyksta. As turiu algoritma, "kaip reikia isiterpt", ir kurias vietas reikia patikrint. Ir nuo kurios vietos tikrint nebebutina. Nieko nerasiau, kad sena grandine nepasikeis, o pasikeis tik "vietos tarp artimiausiu miestu" - kaip tu cia traktuoji pripaises. Papildomos jungtys gali atsirast bet kurioj vietoj. Reikalas butent tame, kad as zinau kaip tiksliai matematiskai ieskot. O ne pamatyt is akies kazka... Matau bandai suprast mano metoda, nes siektiek aprasiau principa

Bet aišku, tu to matematiškai neaprašysi, ir net nebandysi to paskelbti - baisu milijoną gaut?

Gal būtu galima pataisyti, nes labai jau akį rėžia.

, optimaliausias, minimaliausias, tobuliausias, teigiamiausias ir visos kitos nesąmonės. Matematiškai optimalus nebūtinai reiškia geriausias, greičiausias, efektyviausias – supranti? Laisvame tekste tarp daugybės tobulų ir daugybės netobulų gali būti keli tobulesni už kitus ir keli pagal atskirus kriterijus tobuliausi. Taip ir optimaliausi. Paryškintose frazėse „optimaliausias“ ir yra „optimalus“→„minimizuojantis briaunų verčių sumą“, todėl superlatyvo priesaga perteklinė/parazitinė. Mažytė stiliaus klaida, nieko tragiško.

. Tai nėra didelė klaida, bet vis tiek klaida, kuri labai krenta į akis. Laisvame tekste gali nors ir kas antras žodis būti rusiškas, tačiau norėtųsi, kad straipsniuose klaidų būtu kuo mažiau.

As pasiruoses parodyt sprendimo buda bet kam, kas parodys man uz ta sprendima mokama milijona Tu ji matei? Ar tik sitam straipsny perskaitei, kad "kazkas lygtai siulo". Arba gal nori sutarpininkaut uz 10% Kokios bedos tave kankina? Dar klausimas butent tau - kaip atrodo "matematiskai aprasytas" sprendimas? Gal gali placiau pakomentuot? As siulau veikianti uzduoties sprendima. Ar jis kazkam atrodys "matematiskai aprasytas", ar "ne" - man giliai p*fig.

http://www.claymath.org/millennium-prob ... ium-prizes Še. Bet pirma turėtum griežtai įrodyti, jog tavo sprendimas veikia. Jei nori, galiu sutarpininkaut - į bendraautorius įtrauksi, papublikuosiu peer-reviewed žurnale, po poros metų turėsi babkes. Bet tik 50 % (bendraautoriai dalijasi po lygiai).

Patikrinau savo budu sita varianta su Jonava. Algoritmas padare tik 7 iterpimus ir ismete galini rezultata

Cia kiti uzdaviniai kiek suprantu, nera tam sarase keliaujancio pirklio uzduoties. Anglu as per prastai kertu, kad ten suprasciau niuansus...

N=NP. populiariai - keliaujančio pirklio uždavinys.

briaunos (t.y., kelio atkarpos, kuria reikėtų eiti abiem atvejais). Jeigu tu „gerinsi“ vieną kelią, tai niekaip nepasieksi kito, prieš tai nesugadinęs visų N-1 originalių briaunų „blogėjimo“ kryptimi. Ir faktiškai kol to nepadarysi iki galo (t.y., kryptingai beblogindamas iki pat pabaigos), tol neturėsi jokio požymio, kad eini teisinga linkme, o ne šiaip šaudai atsitiktinai. Kitas variantas. Tarkime, kad grafą sudaro dvi nutolusios viršūnių aibės, tarp kurių yra viršūnių spiečius, sudarantis N-matį taisyklingąjį daugiakampį arba N-matį kubą – pavyzdžiui, dvigubą tetraedrą. Apeiti N-mačio kubo gretimas briaunas yra, jei neklystu, yra (N-1)! būdų. Kaitaliok tas viršūnes kaip tiktai nori, jokio pagerėjimo ar pablogėjimo tarpusavyje nebus, bet yra apribojimas, kad priklausomai nuo pradinės viršūnės, ne visos gali būti galinės (ir dar visokių kitokių aplinkybių, kurios turi prasmę kubo išorėje, bet dėl simetrijos ir pan. yra bereikšmės kubo viduje). Tai reiškia, kad atstumą tarp dviejų viršūnių gali lemti neribotas skaičius tarpinių viršūnių, tarp kurių gali būti neribotas skaičius kelių, kurių visų ilgis vienodas! Ir visi to kelio gabaliukai atskirai yra visiškai vienodi! Ir visi gabaliukai po dvi briaunas vienodi! Ir visi gabaliukai po 3... Bet, priklausomai nuo to, pro kurią hiperkubo viršūnę įeisi, ir pro kurią išeisi į aplinkines viršūnes, skiriasi viso grafo (įskaitant ir kubą) maršruto ilgis! Tai nori pasakyti, kad su kiekvienu skirtingu bandymu sujungti priešingas puses, tavo algoritmas spręs hiperkubo apėjimą? Ar nebūtų paprastas toks eksperimentas: duodu tau 1 000 000 000 viršūnių koordinates (kurias jungiantis trumpiausias kelias man žinomas), o tu per kalendorinius metus apskaičiuok sprendimą, geresnį nei tas, kurį turiu aš.

gramatikos, jei mums būtinų minimalių konstruktų buitinė kalba neturi. Gana vien to, kad be mums patogių LR(1) mes apskritai dar laužome smegeninę bandydami suvokti tas jūsų OSV-SVO-VOS-... dviprasmybes.

Tingiu labai gilintis ka cia prirasei, bet mano budas gali skaiciuot nuo bet kurios vietos, o ne kaip tu isivaizduoji, kad skaido problema i smulkesnes arba daro kazkokias isimtis, analizuojant kazkokias nors virsunes pakrasciuose ir pan. Su mano budu gali plest kaip nori ir kiek nori is bet kurios tasku vietos. Siaip yra vienas variantas, del kurio ir pats abejoju, kad butu tik vienas imanomas geriausias atsakymas - jei kazkur tarpiniam skaiciavime rastu simetriska sprendima. Praktikoj kai taskai ismetyta chaotiskai - taip neturetu nutikt Bet simetrijos atveju pagal mane turetu but keli identiski geriausi sprendimai. As cia senai labai sugalvojes ta metoda, nesu nagrinejes smulkiau problematiskesniu atveju. Taip kad sitoj vietoj galbut ir neklysti. Bet manau imanoma padaryt kad ir tokius atvejus "suvirskintu". Galim isbandyt jei nori Man tik idomu kaip tu man "paduosi" duomenis, kai as sita metoda taikau lape popieriaus ir nemoku programint breziniu kompe Siaip tasku programavimas breziniuose dar ir koordinatines paklaidas duoda, o mano metodas yra tikslus analogiskai. Jei bus paklaidos - nezinau kas ten gausis...

Tame ir yra problema, kad sprendi vizualiai. Kitaip tariant, naudoji nedeterministinį algoritmą su orakulu – savo vaizduote. Pabandyk matematiškai užrašyti savo orakulą! Užrašyk taškus koordinatėmis ir nepiešk. Skaičiuodamas, žymėkis kiekvieną dviejų skaičių lyginimą. Ieškodamas panašių skaičių, lenk pirštus, į kiek skaičių pasižiūri, kol randi reikiamą. Labai greitai pamatysi, kad veiksmų skaičius auga eksponentiškai! Tuo labiau, pamatysi, jog tavo „orakulas“ naudoją euristiką, kuri tinka toli gražu ne visais atvejais. Susirašyk kiekvieną veiksmą ir po to papildyk duomenis tokiais, kad tuos veiksmus Didžiausias iki šiol optimaliai išspręstas komivojažieriaus uždavinys yra keliasdešimt milijonų miestų. Įprastais algoritmais su įprastais kompais, skaičiuojant paromis, optimalūs sprendiniai randami max. kelių šimtų miestų uždaviniams. Didžiausi uždaviniai, kuriems kada nors buvo ieškomi sprendiniai, sudaro apie kelis šimtus milijonų miestų. Apie tuos sprendinius žinoma, kad jie nėra labai blogi (t.y., jie nėra blogesni už optimalius daugiau nei viena tūkstantąja procento dalimi ar kažkas tokio), bet nėra žinoma, ar egzistuoja geresni sprendiniai.