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

Straipsnyje minima, kad bendras variantų, kuriuos reikia tikrinti skaičius yra n!/2. O aš ėmiau ir pagalvojau: reikia tikrinti tik tuos kelius, kurie nekerta savęs. Štai paprasta iliustracija kurią padariau: Akivaizdu: kad ir kokie keliai būtų vienoje ar kitoje pusėje, bendras trumpesnis kelias bus antrame variante, t.y. jei kelias nekerta savęs. (bent jau Švedijos žemėlapyje to tikrai nepastebėjau) Todėl manau kad jei kelias kerta pats save, tai tiesiog nėra optimalus kelias ir visus kelius, kurie kerta save reikia atmesti. Taigi iš viso kelių yra n!/2, o kiek yra kelių kurie nekerta savęs? Mano niekuo nepagrįstas spėjimas būtų ln(n!) variantų. Būtų malonu jei kas nors patvirtinų arba paneigtų mano spėjimą

to Giedriax: O jei susikertančių kelių ieškosime ne tarp 4 taškų, o tarkime tarp penkių ar dešimties? Tad susikertančių kelių paieškai reikės taikyti tą patį n!/2 perrinkimų skaičių. Tad nieko tai neoptimizuoja. Juolab, kad pats linijų susikirtimo patikrinimo veiksmas nėra paprastas. P.S. Rodos yra kita to paties pobūdžio probleminė užduotis. Kurios sąlyga lengviau suvokiama, neįpainiojanti geometrijos: Tarkime turime skaičių aibę: { 1, 2, 3, -4, 5, 6, -7, .... , -11 } Reikia patikrinti ar skaičių aibėje yra skaičių grupė, kurių suma tarkime yra lygi 0. Kaip tai padaryti neperrenkant visų įmanomų skaičių grupių?

As nesprendziu "vizualiai", as sprendziu tiksliai pagal tam tikras taisykles. Ir rezultatas 100% tikslus. Tiesiog sprest "matematiskai" siuo atveju netikslinga - nes skaitmenizuota matematika duoda tik apytiksli rezultata. Del uzrasymo ir uzapvalinimo paklaidu. Paklaida galima nustatyt kokia nori, iki priimtino lygio - bet rezultatas bus tokiu atveju nepakankamai tikslus, koks butu idealiu atveju. Mano algoritmas skaiciuoja idealu rezultato atveji. Cia del to, kad neimanoma tiksliai uzrasyt pvz 1/3 ar 1/7, ar kito panasaus atvejo skaitmeniniu budu. Bus kazkoks skaicius, tipo 0,333333332 ar 0,142857141 ; ir iskart duos paklaida programuojant mano metoda kompe. Nesu programeris - galbut imanoma uzprogramuoti ir tiksliai, bet tokie uzapvalinimai mano metoda darytu nepatikimu. As tikrinau kelis "apskaiciuotus" variantus. Vienakar buvo atvejis, kai mano rezultatas buvo geresnis ir rado siektiek trumpesni kelia - nors ten aiskino - kad parodytas geriausias "imanomas" Zinoma netikrinau "milijoniniu" atveju, apsiribojau kuklesniais Dabar del tu tavo samprotavimu , kad cia yra uzdavinys is supaprastinimo klases kai P galbut lygu NP. Cia yra tiesiog idealaus sprendimo ieskojimas apribotu budu, kai atrandamas kazkoks "oakulas" N. Va cia ir yra matematikos ribotumas. Mano algoritmas remiasi logika, o ne matematiku norais rast "orakula". Mano metodas uzrasius paprastai atrodytu mazdaug kaip PN=(P1+P2...PN)X, kur X<N. Kazkas tokio As sprendziu konkretu uzdavini, o ne issikelta kazkokia bendro pobudzio matematine fantazija, apie kuria tu cia rasineji. Tu tik pritempineji sita uzdavini i kazkokia bendra matematine problema, kuri idomi nebent matematikams su ribota logika, kai yra sugalvojamos matematines taisykles - kuriu rezultato matematiskai nebeimanoma suskaiciuot priimtinu praktiskai budu

Vat čia tai išminties perlas

Del optimalumo. Sauniai viska paaiskinai ir tikiu, kad tavo paaiskinimas yra tvirtas. Kitavertus, nesigilinant i matematines vingrybes, asmeniskai as pasakyma "optimaliausias" daugumoje atveju laikau "generic" logikos klaida. Jeigu rasantysis "optimaliausias" naudojo kaip sinonima "geriausias" be aprasytu salygu - tai tikriausiai pateisinama, nes abu variantai siuo atveju nieko nesako. "Geresnis kazkada kazkodel uz kitus". Tai sia prasme tinka ir "tobuliausias", "teisingiausias" etc. - visi nesako nieko konkretaus isskyrus tai, kad is keliu variantu vienas yra kazkuom kazkada pranasesnis, isskirtinis. Siuo atveju, kai nera duota salygu, tikriausiai galima suprasti, jog autorius turejo omenyje optimalesnis=artimesnis teoriskai optimaliam prie tam tikru salygu. Toks parasymas gal ir legatymus, bet man "neskanus" stiliaus prasme. Is serijos "Petriukas atbego paskutiniausias". Zodziu toks stilius labiau abstraktus ir daugiau "implainantis". Tai tikriausiai skonio reikalas, man albiau patinka tikslumas ir "ekplisityvumas". Kitais atvejais, kai pateikiamos salygos, as tai laikau vienareiksme logikos klaida. "Pagal kainos/spartos santyki optimaliausias yra X cpu". Nesamone. Optimalus. Kazkuris variantas yra optimalus kiti nera optimalus. Arba nei vienas nera optimalus, jeigu salygos per placios ir optimalus nera nei vienas is variantu. Apibendrinus, tikriausiai reiketu atsakyti i klausima: ar teisinga naudoti binarini santyki situacijoje, kai nera santykio/jis nezinomas/nedetalizuotas/neapibreztas ir norima nusakyti abstrakcia savybe. Nezinau, gal ir galima, bet man tai vistiek "neskanu"

ar koki nors žargono žodį. Kadangi Lietuvių kalboje yra pakankamai žodžių ir išsireiškimų, siūlyčiau naudoti juos. --------------------------- Jei skaičiui 5 priskirtume reikšmę 4, tai lygybė 2x2=5 būtu teisinga. Bet negalima skaičiui priskirti kitos reikšmės. Nemanau, kad liktum suprastas jei įvestum savo skaičių, pvz.: ö, ir sakytum, kad jis labiau nulis, nei tikras nulis.

Bent vienam daejo.

, kad „mažasis nulis“ o yra mažesnis už „didįjį nulį“ O. Gali pamatyti užrašą o<ε<O arba f1(x)=o(ln x), arba O(TIME)=n. Ir deja, taip: tokių užrašų nepakanka, nes dar naudojamos raidės omikron, omega ir (kažkodėl) theta, kaip ir begalybių yra Aleph0, Aleph1, ... AlephN+1. Kažkaip susišnekam, net susiginčijam kartais, kai pašnekovas lengvabūdiškai užrašo 0 arba ∞ nepatikslinęs, kurį apibrėžimą turi omeny.

As kai ne kalbininkas, tai paaiskink man toki dalyka. Rasai vartot "Petriukas atbego paskutinis", nes "paskutiniausias" skamba debiliskai. Bet uztat galima pasakyt, kad koks nors "Vasiukas atbego priespaskutinis". Arba imkim kita "Petriukas atbego leciausiai", o "Vasiukas atbego letai", arba "Vasiukas atbego leciau (nei kiti, bet ne leciausiai, kas rodo antras nuo galo)". Dabar imkim savoka "optimalus". Sakykim susitariam, kad optimalus butu kazkoks rezultatas trecdaliu letesnis nei Vasiuko, arba 2 trecdaliais greitesnis nei "Petriuko". Kazkoks tarpinis greitis. Ir man visai logiskai skambetu tokie pasakymai, kad "Petriukas atbego beveik optimaliai", o "Vasiukas parode optimaliausia rezultata". Ir man cia iskart aisku, kad optimalaus rezultato nebuvo isvis, ir aisku kuris atbego geriau nei kitas, ir kad optimalus greitis siuo atveju kazkur tarp Vasiuko ir Petriuko rezultatu ir arciau Vasiuko... Jei vartot, kad abu atbego neoptimaliai - skirtumo nematytum. Jei sakyt, kad "Vasiukas atbego optimaliai" - isvis meluotum. Plius sita savoka galima taikyt i abi puses, kai pvz su savoka "leciau" cia neissiverstum. Jei bandytum aiskint, kad vienas atbego greiciau, o kitas labiau leciau nei kitas greiciau - supainiotum. Tai dabar prasom man kaip neismananciam lietuviu kalbos kalbiniu subtilybiu ir niuansu, kokia "grynai kalbiskai lietuviska" savoka reikia vartot siuo atveju, ka as nusakiau vienu zodziu "optimaliausias", ir greiciausia padariau kazkokia super grubia kalbine klaida, ir pazeidziau kazkieno jautrias smegeneles lietuviskumo sudarkymu Nukrypom nuo matematikos temos

Esme yra tokia, kad vasiukas, petriukas ir kiti nieko optimalaus neparode, tik pabande pamalti maza smirdanti sudeli, jog buvo kitaip. O toliau savokos ne savokos, bet as teigiu stai ka: P=NP. xDDD Ir nesinervinkit, plebejai. Metu ar dveju begeyje bus irodyta, kad taip ir yra. Jeigu butu priesingai, kita kontora, isskyrus mano, jau butu visa intika padariusi per sikna ir visi dabartiniai mulkiai be bapkiu tupetumet. xDDD

T.y., jei su tokiomis euristikomis gali per, tarkim, mėnesį, išspręsti uždavinį su milijonu miestų, tai be jų bandydamas visus įmanomus kelius, išvaikščiotum viso labo tūkstantį ar kažkas tokio (išties skaičiai šauna aukštyn taip žvėriškai, kad sunkiai kažką paekstrapoliuosi: mažos smulkmenėlės pradeda daryti labai didelę įtaką skaičiavimo laikui).

Kalbos kultura nera mano sritis - kalbek kaip tu nori. Semantika - susitarimo reikalas, susigalvok reiksmes, kokios tau labiau patinka. Nori gilios matematines/filosofines diskusijos, kur viskas yra niekas ir niekas yra viskas - gali diskutuoti su rwc. As esu paprastas inzinierius, ir man pagal tam tikras salygas/kriterijus arba vienas is variantu yra optimalus, arba nera. Pasakymas optimalesnis/daugiau optimalus/maziau optimalus implaina, kad tai ne optimalu, ir kad tai "arciau/toliau optimalaus". Del manes galim vartot kad ir zodi "uraniumiskesnis" tokiu atveju - tas nieko nekeicia.

.

Del dalybos is nulio, cia yra ne matematine beda - o susitarimo, del taisykliu kaip skaiciuot beda. Nulis yra ne skaicius, o atskaitos riba. Kita tokia riba yra begalybe. Dalyba is nulio yra "ne negalima" - o nelogiskas veiksmas. Nes dalyba - veiksmas su tais paciai objektais - skaiciais. Dalint skaiciu is ribos - nelogiska. Ir tiek. Cia matematines skaiciavimo sistemos standarto klausimas. Romeniska sistema pvz nulio isvis neturejo - bet kazkaip tai sugebejo bent kazka suskaiciuot. Dar skaiciau apie kita matematine problema (nebeatsimenu pavadinimo - ten is 10 ar 15 neissprestu "aktualiausiu"), kur ten kyla matematikams sunkumai del to, kad neimanoma irodyt - butent intervale nuo 0 iki 1. Ten irgi zada savo matematinius "milijonus" uz sprendima - bet ta problema yra logine... Cia yra kartu ir sprendimas tos problemos - ir man priklausytu uzmoket, kad paaiskinau . Bet jis matai "nematematiskas" - problemos sprendimas.

Neturi. Negali net pademonstruoti, kad tavo parinktas/atspėtas sprendinys teisingas. Viskas labai paprasta: iš Gūglo parsisiunti kurį nors duomenų komplektą šitam uždaviniui (1000 koordinačių, sveikieji skaičiai nuo (x,y) 0 iki 999 999). Surašai, kuria tvarka sujungi, ir pažiūrim ar tavo sprendinys geresnis nei kitų sprendėjų, ar ne. Paprastumo dėlei, gali iš anksto susiskaičiuoti visą briaunų ilgių matricą, gi nedaug ten jų.

Galiu. Duok tasku aibe ant lapo, nu sakykim iki kokiu 50 (kad neuzsiknisciau neaisku kiek), ir isspresiu be problemu. Mano metodas braizybos pagalba - nes tai geometrinio pobudzio uzduotis. Ir as ja sugalvojau sprest butent geometriniu budu. Galesi paskui tikrintis savais "matematiniais" metodais, apie kuriuos as neismanau Man negaila

Prašom: http://people.sc.fsu.edu/~jburkardt/dat ... g59_xy.txt Apšilimui, 59 Vokietijos miestai, visos koordinatės sveikieji skaičiai nuo -200 iki 200. Paveiksliukas: http://people.sc.fsu.edu/~jburkardt/dat ... g59_xy.png .

------------ As gi rasiau jau - sprendziant su kazkokiais skaiciais programiniu budu iskart bus konvertavimo i brezini tarpusavio atstumu paklaidos - nes neimanoma absoliuciai tiksliai ismatuot atstumo tarp dvieju tasku tiksliu skaicium. Net jei ir "koordinates sveikieji skaiciai" - brezinys automatiskai bus netikslus - kazkurie taskai pasislinks kitu tasku atzvilgiu del suapvalinimu. Galiu issprest tik brezinini varianta. Tikslesnio brezinio negali duot? Taskai kaip kamuolys - o tarpai tarp tasku mazesni uz tasko dydi...

Kokios rezoliucijos atominį mikroskopą naudoji? Mano excelis palaiko tik iki A2 formato 1200 DPI. Ir dar verki dėl skaičiavimų paklaidų? Nagi nagi... O tu išspręsk bent su tokio didumo burbulais, jeigu ten per kokius tris ar keturis pikselius paklysi, tai esmės nepakeis.

Mano metode daug papildomo braizymo ir tikrinimo. O is delno dydzio lapelio nieko nesigaus normaliai padaryt. Kaip cia tau aiskiau paaiskint? Tasko centras svarbu, ir kad atstumas tarp tasku butu bent jau kokiu 10cm - tada jau galima dirbt. Dabar davei kazkokia fignia, kur taskai vos ne vienas ant kito uzlipe...