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

rwc, ano metodas kitoks, nieko as ten nedelioju kaip tu cia aiskini per keleta ejimu i prieki ir pan. As siektiek skaiciau apie populiarius budus ar ten garsesnius algoritmus - maniskis kardinaliai kitoks. Pas mane vyksta valdoma pagal tam tikras taisykles keliu pakopu optimizacija iki galutinio rezultato. Kol nusistovi galutinis nebesikeiciantis variantas. Kai 60 tasku, tai gana ilgai uztrunka. O kai darai rankom labai mazu masteliu - gana sudetingai gaunasi. Galima nesunkiai praziuret ka nors. Nieko ten strateguot mano metode isvis nereikia. Nei vieta, nei nuo kurio tasko pradet nesvarbi. Isvis galima daryt net dalimis, o paskui jungt i kruva - vistiek optimizuosis. As tiesiog siektiek "apvirskinau" ir imeciau cia rezulta. Ir tai prasiknisau apie 3 val. Mokeciau programuot, automatizuociau ir uzsiimciau mano algoritmo strigimu tyrinejimu. Ir davesciau iki galo, kad galeciau greiciau pateikinet rezultatus tokiems skeptikams kaip tu O dabar tiesiog laiko svaistymas. Jei sitoj vietoj turi ideju - gali siulyt. Man neidomu kur tu ten tuos taskus traukei, ar kaip pats sprendei ir lyginai. Geriau paaiskink ka nors, kaip man greiciau butu galima braizyt kompo pagalba. Ta prasme kaip sukist koordinates, ir kaip uzbrezt linijas, kad tas darytusi ekrane. Gal yra tokiu programu, panasiu i paint, tik kad galetum irasinet koordinates, didint masteli kiek nori, (kad proceso paklaida bent jau galimetu stebet)? Sitai praverstu - ir tada isitikintum, kad mano metodas tikslus 100%. Juk cia istisai rasineji - kad cia visiems elementarus dalykai Mane aplamai labiau domino ar tu isvis suvoki kas cia vyksta tokiuose uzdaviniuose. Dabar supratau kad kazka girdejes apie metodus, galbut tave ten net kazkas apie tai mokino, bet principo matau visiskai nesupranti Tezinai tik tiek, kiek apie tai kazkas kazkur parase Pralinksminai. Mano metodas tikslus del to, kad lape atvaizduotas taskas niekada nepasislenka. O kai programa skaiciuoja (naujo optimizacinio tasko ivedimo koordinates mano atveju) - iskart atsiranda paklaidu - nes negali jo pavaizduot tarp dvieju pikseliu - vaizduoja ji artimiausio pikselio vietoje. Optimizuoti taskai taip issistumdo i sonus, o mano metodui svarbu, kad sekanciam etape jie turetu but tiksliose vietose. Braizant lape tokiu paklaidu nebuna - bet ten kiti minusai - masteliai ir pan. Mane domintu skaitmenizuotas variantas, as manau isdidinus masteli neribotai, galimetu isgaut net ir 100% tikslu rezultata. Bet reiktu patyrinet, kaip susijes procesas tarpusavy.

Na, tai prašom: https://drive.google.com/open?id=0B5DMU ... kV6VHNrVnM čia PDF'as: https://drive.google.com/open?id=0B5DMU ... GhhTEJMMUU

O kaip naudot programa? Uzvesk ant kelio. Kaip taskus idet? Nesupratau kaip ten veikia. Ir pamegink idet toki patikslinta marsruta: (perdirbau siektiek taviski, turetu but geresnis, nors cia irgi manau aiskiai ne galutinis - nes pagal mano metoda rodo maziausiai dar 4 vietas optimizuot, tik tingiu braizyt) taskai: pradzia:1-5-8-14-18-13-21-26-30-25-23-12-4-11-17-20-35-34-33-40-43-47-57-59-58-54-55-49-[sutampantis50:51]-56-53-52-48-45-41-37-27-28-36-46-38-42-44-39-32-31-24-22-29-19-16-15-9-10-7-3-6-2-galinis:1

Sorry, tik dabar pamačiau, kad vos man pasitraukus nuo kompo įdėjai pagerintą mano programos sprendimą. Jo, mano greita ir kvaila euristika pražioplino dvi vizualiai elementarias vietas, patingėjau tuomet „daprogramuot“, dabar irgi jau negrįšiu. Juk ir negarantavau, kad ji ras .

Tai nera svarbu. Tavo metodas budamas 100% tikslus, dar turi buti efektyviai apskaiciuojamas. Esme ta, kad jus zaidziat su "toy-example'ais". As irgi galiu pareiksti, kad man vieni juokai isskaidyti dvieju pirminiu skaiciu sandauga i dauginamuosius, kai tie skaiciai yra intervale iki 10. Problema tik ta, kad, pavyzdziui RSA naudoja 1024+ bit skaicius tam. Nesekiau visos diskusijos ir neanalizavau tavo metodo. Gal tavo metodas validus, ir gal praktiskai pritaikomas tam tikram data-set'e, bet jeigu didinant tasku skaiciu jo sudetingumas (O(n)) nera P klases, tai is esmes tu cia nieko neirodei. Ir tai tik tuo atveju, jeigu jis deterministinis.

AAA000 metodas yra geometrinis ir lokalus. Tuo viskas ir pasakyta. Žr. pirmą bandymą 17.01.01 05:15 PDF. Pavyzdžiui, Hilberto kreivę išsukti reikėtų vis tiek labai gilaus rekursinio trasavimo. Dėl to aš ir paėmiau Delauney trianguliaciją kaip efektyvią divide&conquer euristiką (bet ji susivėlė trivialiose vietose; viena iš jų – taip vadinamas „sidabrinis trikampis“ ties 50/51). Dvi akivaizdžias korekcijas AAA000 metodas surado, tik neaišku, kiek tam pagelbėjo vizuali intuicija. Banalus viršūnių sukeitinėjimas būtų pareikalavęs ne mažesnės nei 6 lygių rekursijos ties „sidabriniu trikampiu“ (žr. postą aukščiau). Beje, klasikiniams algoritmams 59 taškai nėra toks jau žaislinis datasetas.

Mano metode tokios "akivaizdzios" vietos iskart matosi. Kai parodziau - dabar jau ir pats pasidarei "gudrus". O ko iskart nematei? Sutinku, kad vizualiai jos gana akivaizdzios. Yra dar 4 tokios vietos, bet ten suvelta su tom lygiasonem-simetrinem figurom ir sudetinga patikrint. Del mano metodo "lokalumo" klysti Jis panasus i pvz mases centro paieskas, ir tikrai yra globalus Papildomas tasku kiekis neko ten is esmes nekeicia - tiesiog stumdo siektiek pati metoda. Jusu klaida, kad jus galvojat apie sita uzdavini, kad sprendimas yra kazkoks monolitinis algoritmas. O is tikro yra keliu algoritmu visuma, ir yra svarbesni algoritmai ir kaip cia geriau issireiskus - atsisakojantys - jei susidaro prielaidos. Ir viskas irodoma. Visi punktai

tai parodyk, kaip sprendi.

kiek uzmokesi? ---------------------- siaip reiks rwc nuorodas pastudijuot, kas ten per metodai. pirmas ispudis, kad nesuristas metodas su uzdaviniu - vadinas bus neirodomas. galimes ir koki sudetingesi tada pasprest ir palygint rezultata sakykim is kokiu 100 tasku. as tik zinau, kad kai virsija mazdaug 55 taskus - kompai nebesugeba suskaiciuot garantuoto 100% rezultato brutforce metodu... bet kiek suprantu galima rezultata patikrint netiesiogiai, ar jis idealus. bet ten irgi reikia irodyt - kad patikrinimo metodas neklystantis - nes kaip suprantu skaiciuoja irgi tik "teorini idealu" rezultata. tokio atvejo gali net nebut.

Ką reiškia, iškart nemačiau? Aš pateikiau tokį sprendimą, kurį man sugeneravo algoritmas. Juk niekur nesakiau, kad jis optimalus! Tame ir yra esmė, kad vertinu patį . Garantuoju, kad tu paprasčiausiai neturi įrodymo, jog metodas A vienoje šakoje nesugadina metodo B kitoje šakoje. Nes, jeigu turėtum – tuomet meluoji, jog tavo metodas nėra lokalus. Elementari logika, nereikia tam net mokslų būti baigus.

matai, tu nesuvoki esmes. algoritmai turi but irodomi. jei bent viena tarpine grandis neirodoma, arba abejotina - tada galioja tavo aiskinimai - kad rezultatas bus prastas ant tiek, kiek prasta tarpine grandis. bet jei imanoma irodyt kad visos tarpines grandys duoda 100% optimalu rezultata - kaip aiskinsi tada? as tau tiesiog bandau pasakyt, kad sabloniniai matematikai tokius uzdavinius nagrineja pagal supaprastinimo metoda tipo jei algoritmas netaikomas daliai uzdavinio - tai tokius sprendimus atmetam kaip klaidingus is principo... cia yra tiesiog matematinis siaurakaktiskumas - ir tiek...

Konkrečiam duomenų rinkiniui parašyti „metodą“ ir jį realizuoti programa paprasta: apskaičiuoji atsakymą ir parašai programą, kuri jį tiesiog atspausdina. Todėl aš ir nesiimu „optimizuoti“ apytikslio algoritmo papildomomis korekcijomis. Paėmiau Voronojaus diagramos skaičiavimą iš seno projekto, suprogramavau apibėgimą kiek galima labiau išoriniu kontūru, teikiant prioritetą dideliems trikampiams, ir tiek. Veikia? Veikia. Gerai veikia, labai greitai, su maža atmintimi. Duoda trumpesnį kelią nei paprastai sujungtų žmogus „iš akies“; pagal mano testus su klasikiniais duomenų rinkiniais (http://elib.zib.de/pub/mp-testdata/tsp/ ... index.html), 80-95% briaunų parenka teisingai, nuo idealaus kelio atsilieka vos pora procentų. Mano metodas daro supaprastinimus ir klaidas tam tikrose situacijose. Aš tai žinau. Atlikau eksperimentą ir dokumentavau rezultatą. Ir nesiruošiu eksperimento eigoje keisti metodo: t.y., tobulinti algoritmo, vos pamatęs, kad jis su tam tikru duomenų rinkiniu „nuvažiuoja į šoną“. Nes su kitokiu duomenų rinkiniu jis kitur „nuvažiuos“, negi vėl tobulinsiu? Kaip žinosiu, kad tobulindamas vienoje vietoje, nesugadinu kitoje? Yra vienintelis būdas: pakeitus metodą, eksperimentą kartoti nuo pradžių, su įvairiais duomenų rinkiniais (kadangi testavau su ~15 skirtingų rinkinių, tai įvedęs nors ir mažiausią korekciją, turiu vėl pertestuoti su visais, antraip nebūsiu įsitikinęs, kad mano metodas „nesugedo“). Kadangi , kaip ir sprendimo paieška (tik formuluojamas „iš kitos pusės“, bet skaičiavimų požiūriu 1:1). Analogiškai, įrodyti, kad kompleksinė heuristika duoda teisingą sprendimą, yra ne paprastesnis uždavinys. Labai jau tu atsainiai svaidaisi pareiškimais „įrodoma“, „100%“. Ir, beje, „dalimis įrodoma“ dar nereiškia, kad „kombinacija įrodoma“. Pvz.: Teorema 1: dalijant natūraliuosius skaičius (((A/B)/C)/D)/E vieną iš kito, neįmanoma gauti dalybos iš nulio. Teorema 2: atimant natūraliuosius skaičius vieną iš kito (((A-B)-C)-D)-E neįmanoma gauti dalybos iš nulio. Įrodyti: atimant ir dalijant natūraliuosius skaičius vieną iš kito, neįmanoma gauti dalybos iš nulio. Matai problemą?

as tau duosiu siokia tokia analogija. palygink sito uzdavinio sprendima sakykim su auganciu medziu. tavo sprendimo metodas - supjauni medi malkomis, ismatuoji ir sulipini sprendima . darau tokia isvada is to, kaip tu ten aprasineji, kad sprendi sita uzdavini. klaida yra tai - kad tu pjaustai pati medi. o tada nebegali irodyt - kad sprendinys geriausias imanomas. mano sprendimo budas yra kitoks. dabartiniam supaprastintam variante, kur sprendziau braizydamas - panasu sakykim i toki, kad jei medis isaugtu stulpo pavidalo, su keliom tiesiom sakom - gaunu 100% irodoma rezultata - nes su stulpo pavidalo medziu lengva dirbt paprastom priemonem ir lengva tikrint. bet uzdavinio sudetingumas tas - kad medziai neauga kaip stulpas, o sakojasi erdveje chaotiskai ir sunku tiksliai atvaizduot smulkmenas. tam man ir reikia kazkokiu programavimo priemoniu - kurias tu ivaldes, o as apie jas nixer neismanau . ir cia dar reiketu panagrinet sudetingesnius atvejus, bet manau mano algoritme imanoma aprasyt viska kas butina. tam mano algoritma reikia pildyt ataugom - bet nekeiciant esmes. ir tik tam - nes tu vat davei simetrinius atvejus ir pastrigo o tavo sprendimo atveju reikia isardyt viska ir pjaustyt kitokio ilgumo malkom ar dar ten isgalvot kazka keiciant pacia algoritmo esme... ir bandai man cia irodinet - kad musu sprendimai kazkuo identiski... jie is esmes kitokie. jei pridedi daugiau tasku is mano algoritmo sprendimo budo ziurint - cia tik nauja atauga, arba gretimas medis atsirado. o is tavo sprendimo budo ziurint - atsirado daugiau malku ir jos visos persimaise vienoje kruvoje. ir nebeimanoma suskaiciuot del per didelio kiekio... tu bandai sugalvot kazkoki dar labiau tobulesni malku supjaustymo buda - nes zinai ju labai daug (matematiniu pjaustymo budu), nors supranti kad tai beprasmiska... vat tas mane labiausiai ir linksmina