Mobili versija | Apie | Visos naujienos | RSS | Kontaktai
 
Vartotojo vardas:
Slaptažodis:
Atsiminti
Login with a social network:

Jūsų požiūris

Aktyvios diskusijos

Ieškoti forume


Išsami paieška

 [ 74 pranešimai(ų) ]  Eiti į Ankstesnis  1, 2, 3
 
Naujos temos kūrimas Atsakyti į temą Pagrindinis diskusijų puslapis » Mokslas » Įdomusis mokslas
Žinutė Autorius
  Standartinė   Parašytas: 2016-12-31, 13:48 
     
rwc rašė:
Nežinau, kaip dar suprimityvinti uždavinį. Prie X pridedi 60 ir suapvalini iki 5mm, prie Y pridedi 100 ir suapvalini iki 5mm. Viskas telpa paprastame languoto sąsiuvinio lape 16x26cm.

[size = 10]Koordinatės mokykliniais langeliais:

[1] 0 25
[2] 3 28
[3] 3 30
[4] 4 14
[5] 4 27
[6] 4 29
[7] 4 30
[8] 5 25
[9] 5 30
[10] 5 31
[11] 7 4
[12] 7 14
[13] 7 22
[14] 7 27
[15] 7 29
[16] 7 30
[17] 8 8
[18] 8 25
[19] 8 34
[20] 10 11
[21] 10 19
[22] 10 36
[23] 11 15
[24] 11 42
[25] 12 18
[26] 12 20
[27] 12 24
[28] 12 25
[29] 12 34
[30] 13 18
[31] 13 42
[32] 13 43
[33] 14 8
[34] 14 10
[35] 14 12
[36] 16 29
[37] 17 23
[38] 17 36
[39] 17 50
[40] 18 7
[41] 18 17
[42] 18 45
[43] 19 2
[44] 19 51
[45] 20 14
[46] 21 35
[47] 22 7
[48] 22 18
[49] 23 14
[50] 23 15
[51] 23 15
[52] 23 19
[53] 23 20
[54] 24 10
[55] 24 14
[56] 25 18
[57] 26 5
[58] 28 11
[59] 29 8

Tokį arba padarai, arba baigi malti š..


[Upd.]Na kaip, dar tebeskaičiuoji? Ilgokai... Uždavinys gi net nereikalauja suskaičiuoti atstumo: pasakyk tik, kuria tvarka taškus sujungi, 5 minučių reikalas. Ir tiesą sakant, nesuprantu, kodėl tam neužtenka kad ir delno dydžio paveikslėlio – juk viso labo tik 59 taškai, mažiau nei 8x8 šaškių lentoj langelių.


50 ir 51 taskai sutampa. WTF ???

Siaip lapas 16 x 19 mazdaug mokykliniais langeliais, 6 tavo taskai netelpa. Bet telpa ant dvigubo. Vnz sitas tinka daugmaz, bet truksta siektiek chaotiskumo.

Ir gali nespeliot, nesiruosiu pasakot smulkmenu. Mano metodas nera labai jau paprastas, kaip kazkodel galvoji.
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2016-12-31, 15:47 
     
AAA000 suteikiu metu melagio ir pazaduko titula!
  • +1



Vartotojo avataras

Užsiregistravo: 2011-11-30, 19:32
Pranešimai: 2321
Miestas: Klaipėda
Reputacija: +99
   
 
Į viršų
  Standartinė   Parašytas: 2016-12-31, 17:44 
     
Aidas rašė:
AAA000 suteikiu metu melagio ir pazaduko titula!

Tave problemos kazkokios kankina? :D

-------------------
Perleidau rwc uzdavinuka per savo algoritma.
Taskus Nr50 ir Nr51 laikiau kaip viena taska, nes sutampa koordinates.
Taip pat yra nepakankamai chaotiskas tasku ismetymas: Realybej taip nebuna.
Yra net trys istriziniai sutapimai:
1. atstumai tarp tasku 25-21 ir 21-26 geometriskai simetriski ir susijungia vienam taske Nr21,
2. taip pat atstumai tarp tasku 34-20 ir 20-35 geometriskai simetriski ir susijungia vienam taske Nr20,
3. cia isvis nonsensas. dvigubos atkarpos 12-20-35 ir 35-23-12 geommetriskai simetriskos ir susijungia dviejuose taskuose Nr12 ir Nr35! WTF?
Mano algoritmas stringa ant tokiu vietu. Turi but chaotiska tasku aibe.
Aplamai per daug identisku atkarpu. Realybej taip nebuna, kad atstumai tarp miestu idealiai vienodi. Galejai geriau rwc parinkt aibe.
Atsakymas gavosi toks:
Taskai numeriais jungiasi taip:
1(pradzia)-8-5-6-9-14-18-13-27-26-21-25-23-12-4-20-17-11-33-43-57-59-58-55-[50:51]-56-53-52-48-41-45-49-54-47-40-34-35-30-37-36-28-15-16-29-46-38-31-42-44-39-32-24-22-19-10-7-3-2-1(pabaiga)
Galit nagrinet :D :D :D
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D


Paskutinį kartą redagavo AAA000 2016-12-31, 17:52. Iš viso redaguota 1 kartą.


Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2016-12-31, 17:51 
     
Jo, ir atmazam galo nebus. Tai atitinkamo dydžio popiergalio neranda, tai taškai per arti, tai „chaotiškumo trūksta“. Maivysis, kol elementarus uždavinys pats išsispręs. O jau kognityvinis disonansas, kad realų žemėlapį suskaidžius arkliniais sklypais po 30x30 km ar pan. du miestukai papuolė į vieną langelį – džiaugtųsi, kad uždavinio sąlyga leidžia vienu ėjimu abu aplankyti, ar ką, kad uždavinys pasidaro paprastesnis...

Dar, matai uždavinys nerealus, realybėje nebūna, išvis pribaigė... Kas gali būti realiau už tikros valstybės (Vokietijos, VDR) tikrų miestų, parinktų pagal gyventojų skaičių iš oficialaus registro, koordinates?
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2016-12-31, 17:56 
     
rwc rašė:
Jo, ir atmazam galo nebus. Tai atitinkamo dydžio popiergalio neranda, tai taškai per arti, tai „chaotiškumo trūksta“. Maivysis, kol elementarus uždavinys pats išsispręs. O jau kognityvinis disonansas, kad realų žemėlapį suskaidžius arkliniais sklypais po 30x30 km ar pan. du miestukai papuolė į vieną langelį – džiaugtųsi, kad uždavinio sąlyga leidžia vienu ėjimu abu aplankyti, ar ką, kad uždavinys pasidaro paprastesnis...

Tau gal ir dziaugsmas - kai supaprastina, ir tada tu jau pradedi kazka suvokt. O mano algoritmui netinka. Geriau kuo chaotiskiau. Paziuresim kaip tu atsakyma analizuosi :D :D :D Duok geresni varianta uz maniski - jei toks gudrus ir ten moki naudotis visokiom metodikom ir super programom su 0,01% paklaida :D. Cia spresta rankiniu budu geometriniais metodais.
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2016-12-31, 18:04 
     
AAA000 rašė:
rwc rašė:
Jo, ir atmazam galo nebus. Tai atitinkamo dydžio popiergalio neranda, tai taškai per arti, tai „chaotiškumo trūksta“. Maivysis, kol elementarus uždavinys pats išsispręs. O jau kognityvinis disonansas, kad realų žemėlapį suskaidžius arkliniais sklypais po 30x30 km ar pan. du miestukai papuolė į vieną langelį – džiaugtųsi, kad uždavinio sąlyga leidžia vienu ėjimu abu aplankyti, ar ką, kad uždavinys pasidaro paprastesnis...

Tau gal ir dziaugsmas - kai supaprastina, ir tada tu jau pradedi kazka suvokt. O mano algoritmui netinka. Geriau kuo chaotiskiau. Paziuresim kaip tu atsakyma analizuosi :D :D :D Duok geresni varianta uz maniski - jei toks gudrus ir ten moki naudotis visokiom metodikom ir super programom su 0,01% paklaida :D. Cia spresta rankiniu budu geometriniais metodais.


Tavo tas "grafinis algoritmas" tinkamas nebent tik optimaliam atstumui tarp bobu papu matuot ant playbojaus zurnalo...

PS. Sis forumas galetu naudoti priverstinius label'ius. Tai tokiem veikejam galetumet uzdeti raudona zyma "zinomas trolis" - butu aiskiau visiems.
  • 0




Užsiregistravo: 2016-10-02, 17:48
Pranešimai: 431
Reputacija: +540
   
 
Į viršų
  Standartinė   Parašytas: 2016-12-31, 23:35 
     
Tai imk pradinius duomenis, kas trukdė? Ten nėra tokio atvejo, kaip Vatikanas su Roma, Buda su Peštu, ar Vilijampolė su Aleksotu ir Žaliakalniu ant vienos upių santakos. Matai, langeliai per dideli pasidarė, taip jau gavosi, kad keturiuose gretimuose langeliuose reikia pažymėti tris miestus, ir atstumai tarp pasidarė jų lygūs langelio pločiui!

Ir maža problemytė, aš turiu beveik šeštadaliu trumpesnį kelią. Tarp kitko, atspėjai tik 24 iš 59 teisingų atkarpų, kuriomis reikia eiti!

Melagis melavo! Pažaduk, iki fejerverkų dar yra laiko! Ot įkelsiu abu brėžinius, tai tamstai bus sarmatos prieš visą internetą...

Kaip lemoną dalinsimės?
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 01:29 
     
rwc rašė:
Tai imk pradinius duomenis, kas trukdė? Ten nėra tokio atvejo, kaip Vatikanas su Roma, Buda su Peštu, ar Vilijampolė su Aleksotu ir Žaliakalniu ant vienos upių santakos. Matai, langeliai per dideli pasidarė, taip jau gavosi, kad keturiuose gretimuose langeliuose reikia pažymėti tris miestus, ir atstumai tarp pasidarė jų lygūs langelio pločiui!

Ir maža problemytė, aš turiu beveik šeštadaliu trumpesnį kelią. Tarp kitko, atspėjai tik 24 iš 59 teisingų atkarpų, kuriomis reikia eiti!

Melagis melavo! Pažaduk, iki fejerverkų dar yra laiko! Ot įkelsiu abu brėžinius, tai tamstai bus sarmatos prieš visą internetą...

Kaip lemoną dalinsimės?



Man įdomu, ar AAA000 įkeltų savo brėžinį (sprendimą) ar čia iš lempos surašė tuos skaičius?
  • 0


_________________
Aš už laisvą Lietuvą Rusijos sudėtyje!
I support Putin and green peasants!
Karbauskis rules again! I am with him too!



Užsiregistravo: 2010-02-08, 03:13
Pranešimai: 2790
Reputacija: +608
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 01:44 
     
Ne, sprendimas teisingas, tik daugumą ilgų kelių iš akies neteisingai pasirinko, subkontūrus vis ne iš to krašto apeidinėja ir lieka nepatogūs neprijungti miestai.

Aš kol kas nenoriu kelti teisingo sprendimo, gal dar bandys pagerint. Tokio didelio skirtumo (15,8623%), tiesą sakant, nesitikėjau – brėžinukas labai paprastas, dauguma paprastų euristikų jį iškart pagauna, o žinant, kad visi skaičiai suapvalinti iki „sąsiuvinio langelių“, tai ir be kompo nėra ką skaičiuoti.
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 02:02 
     
rwc rašė:
Ne, sprendimas teisingas, tik daugumą ilgų kelių iš akies neteisingai pasirinko, subkontūrus vis ne iš to krašto apeidinėja ir lieka nepatogūs neprijungti miestai.

Aš kol kas nenoriu kelti teisingo sprendimo.

Manai kad ten kazka speliojau? :D Toliau speliok. Nematavau isvis nei vieno atstumo, nors praverstu toks budas smulkesnei analizei.
Tiesiog tingejau didint mastelius ir iki galo optimizuot. Suprask toki dalyka, kai kruva tasku 5mm atstumu, o optimizacija geometriniu budu slankioja po 1mm, breziny debesis liniju ir ten nieko nebeimanoma normaliai iziuret.
Dar ta problema su simetrinem dalim. Man tokie atvejai duoda rezultatu issisakojima, ko pasekoj galiu nueit neteisinga kryptim, nes tiesiog imiau viena is dvieju laikydamas, kad identiskas optimizavimas :D Matyt kazkas isivele tarpiniam procese, kad sakai net sestadaliu skiriasi :D :D :D.
Dar neaisku su kuo tu ten rwc lygini. Jei tu taskus stumdei man iki langeliu, o lygini su pirminiu variantu - kai tasku aibe yra siektiek kitokia, tai dar neaisku kuris cia teisus :D As juk zinau tik savo metoda.
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 02:37 
     
Uoj uoj uoj, gudrutis. Blogam šokėjui milimetriniai langeliai pamaišė.

58 ėjimai šachmatų langeliais, ir tu suvaikščioji 33 langeliais daugiau nei reikia, čia jau virš bet kokių leistinų paklaidų. Ne nuo to kampo vaikščioti pradėjai, nuo dešinės būtų beveik išsisprendę tavo metodu. Pradėjęs nuo kairės į viršų, palikai keletą nepalankių langelių, ir paskui apeidinėjai visą žemėlapio vidurį perteklinėm ilgom linijom, kurios kitu atveju gražiai susivalgo imant ne pačius trumpiausius („optimaliausius“) kelius dešinėje.

Reikėjo „pastrateguoti“ kokius 5-6 ėjimus į priekį, bet matyt tiek paprasta geometrija neišneša.

Ir, beje, aš nieko specialiai nestumdžiau. Daviau tau duomenis net nepažiūrėjęs, kaip jie sprendžiasi (tik patį failą su koordinatėm atsidaręs). Paskui suapvalinau, kad tilptų į langelius – per tai nepamačiau, kad du taškai sukrito į vieną langelį (originale atstumas tarp jų ~7-8 punktus, abi koordinates dalijant iš 5 susiapvalino į vieną). Net nebuvau garantuotas, (a) ar ne per trivialus uždavinys, kad iš akies išsispręstų, ir (b) ar staigiai pats išspręsiu bent taip pat gerai (būtent šito uždavinio sprendimo gūglėj neaptikau – ir o tai būčiau gėdos apturėjęs, jei būtų tekę pačiam programuoti aplink kokį nenumatytą atvejį!).
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 04:34 
     
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 :D 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 :D
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 :D Tezinai tik tiek, kiek apie tai kazkas kazkur parase :D Pralinksminai. :D :D :D
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.
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 05:15 
     
Na, tai prašom: https://drive.google.com/open?id=0B5DMU ... kV6VHNrVnM
čia PDF'as: https://drive.google.com/open?id=0B5DMU ... GhhTEJMMUU
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-01-01, 05:49 
     
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
  • +1


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 06:30 
     
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 geriausią sprendimą per 0,2 sek. – sakiau tik, kad ras ne blogesnį nei tu pasiūlysi (o kažko gudraus ir nereikėjo, kad pagerintų 238: ji net neatsižvelgia, kad naudojama Euklido geometrija plokštumoje, ir nežino, kad negali būti trumpesnio kelio tarp dviejų tašku nei tiesė ir pan., todėl lygiai taip pat veiktų Minkovskio geometrijoje, Merkatoriaus koordinatėse, su Manhatano metrika, trimatėje erdvėje ir t.t., bet kokioje metrinėje erdvėje; ji net nebando pagerinti pirmo pasitaikiusio sprendinio keletu žingsnių į priekį – reikėtų bent 3; nebando sutvarkyti atskirų fragmentų; ir t.t.). Kliurkos tokios elementarios, jog net keista, kad algoritmas, visą sudėtingumą atspėjęs, lygiose vietose nubėgo ilgesniais keliais: matyt, kažkur būsiu klaidų privėlęs ;]

Pilnai tikiu, kad geometrinis metodas tokias kliurkas gali aptikti. Faktiškai, kiekvienas iteracinis algoritmas iškart aptiktų, kad porą 38-46 reikia „apsukti“ (mano euristika nėra iteracinė optimizacija: ji paremta vienu optimistiniu šūviu pagal topologinius parametrus, gretimų taškų grupavimą: https://ru.wikipedia.org/wiki/%D0%A2%D1 ... 0.B8.D0.B5 [cite: через триангуляцию Делоне приближённо решается евклидова[*] задача о коммивояжёре]; visas brėžinys suskaidomas trikampėmis sritimis, ir skaičiuojama, per kiek trikampių dvi viršūnės nutolusios; jei iškart neatspėja teisingai, toliau nieko taisyti nė nebando – pradžioj maniau, kad to reikės, bet ir taip pakankamai gerai skaičiavo, tad nedariau). Kitas dalykas, sutampantys taškai 50 ir 51 labai subalamutina mano euristiką, nes jai nėra skirtumo, ar tie taškai sutampa, ar yra nutolę per pusę brėžinio (jie vis tiek sudaro trikampio kraštinę): pakanka vieną iš jų pašalinti, ir nebelikus „fiktyvaus“ trikampio įsiterpusio tarp artimų taškų ta vieta išsisprendžia (aišku, nesunku suprogramuoti, kad tokius atvejus išprastintų – bet mano tikslas buvo iškepti kuo paprastesnį neblogai veikiantį algoritmą, kuris apdėtų tavo pasiūlytą sprendimą).

Ką gi, sveikinu! Naujas rekordas: 204,170431.


Atnaujinta Google Docs skaičiuoklė: https://docs.google.com/spreadsheets/d/ ... sp=sharing
LibreOffice nuotrauka PDF formatu: https://drive.google.com/open?id=0B5DMU ... 0RmWlF6Z0E
LibreOffice programa su skaičiuokle internete: https://www.rollapp.com/open/gdrive/ope ... 9686%22%7D
LibreOffice/OpenOffice skaičiuoklė parsisiuntimui: https://drive.google.com/open?id=0B5DMU ... lpnWDNwVmM
Excel skaičiuoklė parsisiuntimui (jei neveikia aukštesnė): https://drive.google.com/open?id=0B5DMU ... kJUR2djUGc

Nors imti dabar ir prasukti pilną perrinkimą... Gal tikrai reikėjo paieškoti sudėtingesnio žemėlapio, neimti pirmo pasitaikiusio aklai...

O kaip naudot... Pasirenki stulpelyje AAA000 kitą miesto numerį ir žiūri, kaip persipaišo grafikas (Google Docs versijoje rodo klaidas tame stulpelyje – taip ir turi būt, tingiu taisyt). Dist Stulpelio apačioje yra ilgių suma, ji irgi turi keistis. Google Docs versijoje neišeina kelių grafikų sukelt į vieną, tai pasukiok kairėn/dešinėn. Ai, dar Google Docs versijoje, jei nepanaudotas kuris miestas, tai jis pažymimas sąraše raudonu langeliu. O aš viską dariau su LibreOffice arba OpenOffice, į Google Docs perkėliau tik tam, kad būtų galima maigyti tiesiai iš naršyklės.


[*] – klaida wikipedijoje, turėtų būti „метрическая задача о коммивояжёре“, t.y., „в измеримом пространстве на множестве ребер“ – erdvė nebūtinai euklidinė; šitas algoritmas negali remtis jokiomis kitomis geometrinėmis savybėmis nei briaunos ilgis ir trikampio taisyklė, pvz., kampo smailumu. Todėl, gavus pradinį (labai greitą!) apytikslį sprendimą šiuo metodu, toliau yra prasmės pritaikyti kokį nors geometrinį iteracinį minimizavimo algoritmą – ką realiai tu ir padarei ;]

Visgi, bendruoju atveju jokia metodų kombinacija negarantuoja optimalaus sprendinio be pilnojo perrinkimo. Milijono dar teks palaukti, kol sugalvosi, kaip garantuoti visais atvejais.
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 12:16 
     
AAA000 rašė:
ir tada isitikintum, kad mano metodas tikslus 100%


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.
  • 0




Užsiregistravo: 2016-10-02, 17:48
Pranešimai: 431
Reputacija: +540
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 12:40 
     
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.
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 21:03 
     
Mano metode tokios "akivaizdzios" vietos iskart matosi. Kai parodziau - dabar jau ir pats pasidarei "gudrus". O ko iskart nematei? :D 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 :D Jis panasus i pvz mases centro paieskas, ir tikrai yra globalus :D :D :D 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 :D
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 21:21 
     
AAA000 rašė:
Mano metode tokios "akivaizdzios" vietos iskart matosi. Kai parodziau - dabar jau ir pats pasidarei "gudrus". O ko iskart nematei? :D 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 :D Jis panasus i pvz mases centro paieskas, ir tikrai yra globalus :D :D :D 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 :D



tai parodyk, kaip sprendi.
  • 0


_________________
Aš už laisvą Lietuvą Rusijos sudėtyje!
I support Putin and green peasants!
Karbauskis rules again! I am with him too!



Užsiregistravo: 2010-02-08, 03:13
Pranešimai: 2790
Reputacija: +608
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 21:45 
     
- rašė:
tai parodyk, kaip sprendi.

kiek uzmokesi? :D
----------------------
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... :D :D :D 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.
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-04, 22:14 
     
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į vieną metodą, o ne N skirtingų metodų kuriuos taikai kaip papuola, ir jei nė vienas neveikia, tada eini ieškoti naujo. Mano metodas greitas, duoda gerą sprendinį per baigtinį laiką, bet net nežada duoti geriausio. Galėčiau specialiai šiam žemėlapiui pritaikyti „sutvarkymą“ kitu metodu, kuris garantuoja optimalų sprendinį per eksponentinį laiką, bet ta pati strategija visiškai nebeveiks su kitu žemėlapiu.

Man keista, kad trianguliacijos metodas pasimovė tokiose paprastose vietose, kurios geometriniams algoritmams būtų saldainiukai – konstatuoju tai kaip trūkumą, kurio užlopymas reikšmingai bendru atveju nieko nepagerintų, ir tiek. Jeigu pastebėtas metodo klaidas pataisysiu rankomis – tai bus žaidimas ne pagal taisykles, nes aš neturiu griežtai suformuluoto metodo, kuris tokius pataisymus atliktų pats, be „operatoriaus“ įsikišimo (t.y. be „orakulo“).

Algoritmo/metodo teisingumas neturi priklausyti nuo duomenų, tame yra šito uždavinio (ir kitų matematinių/informacijos teorijos) esmė.

Įsivaizduok, kad turi užduotį: yra tūkstantis duomenų rinkinių. Tau reikia išsirinkti 10 rinkinių ir pagal juos sukurti universalų metodą, kuris išspręstų visus tūkstantį. Bandai su paprastais rinkinukais, iki 100 taškų, bet yra rinkinių ir su 1000, ir su 10 000.

Ir tai yra priežastis, kodėl nesiimu kombinuoti trianguliacijos su tiksliu metodu: yra be galo daug atvejų, kai trianguliacija atspėja labai blogą pradinę konfigūraciją (pvz., tavo 238 sprendimas yra toks „labai blogas“ – jis ne tik kad šiaip neoptimaliai paėmė kažkurį kampą, bet apskritai nuvažiavo ne į tą pusę, todėl tokią pradinę konfigūraciją paskui bandyti tvarkyti kaitaliojant viršūnes praktiškai beprasmiška).

Sutinku, kad „iš akies“ parinkti vien ar kitą metodą galima. Galima įvesti tam tikrus statistinius kriterijus, pagal kuriuos galima suformuluoti metodo parinkimo taisykles. Bet „iš akies“ savaime turi dydžio apribojimus. Kiek taškų dar nėra per daug, kad galėtum užtikrintai pasakyti, kuris metodas veiks, ir kuris – ne? O kaip, jei sukombinuosiu pačius duomenis: paimsiu rinkinį, kuriam tinka metodas A, brėžinio kampe prikabinsiu rinkinį, kuriam tinka B, tarp jų įpaišysiu rinkinį C ir taip toliau?

Tokio tipo uždaviniai turi dar vieną bjaurią savybę, kad jų sprendinių paieškos efektyvumas labai jautrus pradinėms sąlygoms. Pakanka skubotai sujungti du taškus, ir kol iki klaidingos briaunos prisikasi „iš kito galo“, jau bus beviltiška taisyti (verčiau tiesiog išmesti ir pradėti iš naujo). Todėl jei turi du metodus, kurie atskirai negarantuoja optimalaus sprendinio, tai bet kokia jų kombinacija tuo labiau negarantuoja (nes nežymi vieno metodo klaida gali būti tragiška kito metodo pradinei konfigūracijai).

Yra ir kitas faktas (būdingas būtent garantuotai optimaliems sprendimams, bet ne apytiksliams). Kiek dalinių metodų besudarytų kombinuotą, kombinuoto metodo efektyvumas niekada nebus geresnis nei blogiausio dalinio. Vienai ar kitai rinkinių klasei jų kombinacija gali veikti nuostabiai gerai, bet bus be galo daug rinkinių, kuomet sprendinį pasiekia tik pats lėčiausias iš jų.

Kadangi tu negali pasiūlyti vieno baigtinio garantuoto algoritmo, kuriame nebūtų spėliojimo „iš akies“, tai aš darau išvadą, kad tam tikrais atvejais vis tiek turėsi panaudoti kokį nors „bandymų ir klaidų“ metodą (kurio sudėtingumas, pagal apibrėžimą, yra eksponentinis), ergo – yra be galo daug brėžinių remsis būtent juo (todėl bus išsprendžiami tik eksponentiškai – t.y. pilnu perrinkimu), ergo bet koks pakankamai didelis brėžinys bus išsprendžiamas tik juo (išskyrus nykstamai mažą dalį atvejų; nykstamai – tai 1/(e laipsniu brėžinio dydis)).

Jau vien tavo frazė, kad yra „atsišakojantys“ algoritmai savaime reiškia, kad metodo visuma turi rekursinį pobūdį. Ir čia jau nebelabai įdomu, ar konkretus dalinis algoritmas teisingas. 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.
  • 0




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-05, 02:59 
     
rwc rašė:
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į vieną metodą, o ne N skirtingų metodų kuriuos taikai kaip papuola, ir jei nė vienas neveikia, tada eini ieškoti naujo. Mano metodas greitas, duoda gerą sprendinį per baigtinį laiką, bet net nežada duoti geriausio. Galėčiau specialiai šiam žemėlapiui pritaikyti „sutvarkymą“ kitu metodu, kuris garantuoja optimalų sprendinį per eksponentinį laiką, bet ta pati strategija visiškai nebeveiks su kitu žemėlapiu.

Man keista, kad trianguliacijos metodas pasimovė tokiose paprastose vietose, kurios geometriniams algoritmams būtų saldainiukai – konstatuoju tai kaip trūkumą, kurio užlopymas reikšmingai bendru atveju nieko nepagerintų, ir tiek. Jeigu pastebėtas metodo klaidas pataisysiu rankomis – tai bus žaidimas ne pagal taisykles, nes aš neturiu griežtai suformuluoto metodo, kuris tokius pataisymus atliktų pats, be „operatoriaus“ įsikišimo (t.y. be „orakulo“).

Algoritmo/metodo teisingumas neturi priklausyti nuo duomenų, tame yra šito uždavinio (ir kitų matematinių/informacijos teorijos) esmė.

Įsivaizduok, kad turi užduotį: yra tūkstantis duomenų rinkinių. Tau reikia išsirinkti 10 rinkinių ir pagal juos sukurti universalų metodą, kuris išspręstų visus tūkstantį. Bandai su paprastais rinkinukais, iki 100 taškų, bet yra rinkinių ir su 1000, ir su 10 000.

Ir tai yra priežastis, kodėl nesiimu kombinuoti trianguliacijos su tiksliu metodu: yra be galo daug atvejų, kai trianguliacija atspėja labai blogą pradinę konfigūraciją (pvz., tavo 238 sprendimas yra toks „labai blogas“ – jis ne tik kad šiaip neoptimaliai paėmė kažkurį kampą, bet apskritai nuvažiavo ne į tą pusę, todėl tokią pradinę konfigūraciją paskui bandyti tvarkyti kaitaliojant viršūnes praktiškai beprasmiška).

Sutinku, kad „iš akies“ parinkti vien ar kitą metodą galima. Galima įvesti tam tikrus statistinius kriterijus, pagal kuriuos galima suformuluoti metodo parinkimo taisykles. Bet „iš akies“ savaime turi dydžio apribojimus. Kiek taškų dar nėra per daug, kad galėtum užtikrintai pasakyti, kuris metodas veiks, ir kuris – ne? O kaip, jei sukombinuosiu pačius duomenis: paimsiu rinkinį, kuriam tinka metodas A, brėžinio kampe prikabinsiu rinkinį, kuriam tinka B, tarp jų įpaišysiu rinkinį C ir taip toliau?

Tokio tipo uždaviniai turi dar vieną bjaurią savybę, kad jų sprendinių paieškos efektyvumas labai jautrus pradinėms sąlygoms. Pakanka skubotai sujungti du taškus, ir kol iki klaidingos briaunos prisikasi „iš kito galo“, jau bus beviltiška taisyti (verčiau tiesiog išmesti ir pradėti iš naujo). Todėl jei turi du metodus, kurie atskirai negarantuoja optimalaus sprendinio, tai bet kokia jų kombinacija tuo labiau negarantuoja (nes nežymi vieno metodo klaida gali būti tragiška kito metodo pradinei konfigūracijai).

Yra ir kitas faktas (būdingas būtent garantuotai optimaliems sprendimams, bet ne apytiksliams). Kiek dalinių metodų besudarytų kombinuotą, kombinuoto metodo efektyvumas niekada nebus geresnis nei blogiausio dalinio. Vienai ar kitai rinkinių klasei jų kombinacija gali veikti nuostabiai gerai, bet bus be galo daug rinkinių, kuomet sprendinį pasiekia tik pats lėčiausias iš jų.

Kadangi tu negali pasiūlyti vieno baigtinio garantuoto algoritmo, kuriame nebūtų spėliojimo „iš akies“, tai aš darau išvadą, kad tam tikrais atvejais vis tiek turėsi panaudoti kokį nors „bandymų ir klaidų“ metodą (kurio sudėtingumas, pagal apibrėžimą, yra eksponentinis), ergo – yra be galo daug brėžinių remsis būtent juo (todėl bus išsprendžiami tik eksponentiškai – t.y. pilnu perrinkimu), ergo bet koks pakankamai didelis brėžinys bus išsprendžiamas tik juo (išskyrus nykstamai mažą dalį atvejų; nykstamai – tai 1/(e laipsniu brėžinio dydis)).

Jau vien tavo frazė, kad yra „atsišakojantys“ algoritmai savaime reiškia, kad metodo visuma turi rekursinį pobūdį. Ir čia jau nebelabai įdomu, ar konkretus dalinis algoritmas teisingas. 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? :D
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... :D :D :D
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-05, 07:00 
     
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 žinau, jog optimalų kelią galima rasti tik rekursine paieška, tai mane toks rezultatas tenkina. Kadangi turiu testų, kur mano metodas iš 1000 viršūnių parenka ištisus 100-200 fragmentus suboptimaliai (tačiau pralošia nedaug, skaičiuojant ilgį), tai akivaizdu, jog jo kombinuoti su kitu metodu nėra jokios prasmės. Tam, kad kitas metodas rastų, kaip mano sprendimą tokiu atveju pagerinti, reikia vos ne trečdalį mano sprendinio išardyti ir perspręsti. Kad nustatytum, kurią dalį reikia ardyti – reikia praktiškai išspręsti visą pradinį uždavinį. Tokia bėda yra praktiškai su visais euristiniais globalios paieškos algoritmais.

Jeigu nori greito algoritmo – pamiršk geometriją. Bandant jungti tašką prie taško užsiknisi, reikia ieškoti, kaip visą brėžinį sukapoti dalimis, ir čia prasideda problema: kur dėsi pirmą pjūvį? Pagal kokius kriterijus nuspręsi, kad būtent taip pjauti yra saugu? Kriterijus „iš akies“ netinka, nes su „normaliais“ duomenim iš akies nieko nepamatysi.

Mes žaidėm su ganėtinai paprastu atveju. Pats prašei 50 taškų, ir dar, kad būtų galima ranka susibraižyti. Mielai būčiau pasiūlęs 1000 arba 10 000 miestų uždavinį, o dar geriau – ne pilnąjį grafą euklidinėse koordinatėse. Pavyzdžiui, tarp miestų gali būti kelias, arba nebūti. Kelias nebūtinai tiesus. Nebūtinai dvipusis. Tai, ką mes sprendėm, yra uždavinys diskrečiosios matematikos studentams, įdomus labiau teoriškai. Tuo, kad galima parodyti, jog degeneruotu atveju (degenerate ~nepanašus į bendrąjį, netipiškas, išimtinis) euklidinis supaprastinimas neduoda naudos.

Pavyzdys: šachmatų lentoje užimta N atsitiktinių langelių. Rasti trumpiausią kelią per visus neužimtus langelius ir grįžti į pradinį. Problema ta, kad yra labai daug lygiaverčių sprendinių, ir dauguma algoritmų užsiknisa, ieškodami optimalaus. Gali parašyti sąlygą, kad draudžiama eiti per jau aplankytą langelį, bet tada gali sudėlioti kliūtis taip, kad nebūtų kitokio sprendinio. Toliau: gali lentoje pastatyti ilgą „tvorą“ su skylėmis; sprendimas susives į langelių lyginumo/nelyginumo skaičiavimą.

Kiek tokių atvejų numatysi atskiromis išimtimis? Visą knygą parašysi apie strategijas? Bet juk tai dar labiau apribotas uždavinio su miestais atvejis, jis pagal visus kriterijus turėtų būti paprastesnis!

Reikalavimas algoritmui vienintelis: per polinominį laiką rasti sprendinį bet kokiam miestų uždaviniui, nepriklausomai nuo miestų skaičiaus.

Eksperimentas gali būti vykdomas taip: tu turi sąsiuvinį, kuriame detaliai aprašai sprendimo instrukciją. Aš kitame kambaryje irgi turiu sąsiuvinį, kuriame surašau miestų koordinates. Atiduodame savo sąsiuvinius trečiam žmogui. Tu laimi, jei per fiksuotą laiką (tarkim, minučių skaičius lygus miestų skaičiaus kvadratui ar pan.) tas trečias žmogus pažodžiui laikydamasis tavo nurodymų randa trumpiausią kelią.

Didžiausia problema, kurią tau tektų išspręsti – tai, kad tu visiškai neįsivaizduoji, kokį žemėlapį aš nupiešiu. Mano problema kur kas paprastesnė: imituoti realias sąlygas. T.y., sugalvoti kiek įmanoma įvairesnių ribinių situacijų, kurios realybėje anksčiau ar vėliau pasitaikys. Sprendėjui draudžiama improvizuoti ir nukrypti nuo instrukcijų, o tu jam patarti negali.

Kodėl paskutinė sąlyga. Įsivaizduok, kad tavo metodą bandom pritaikyti mikroschemų testavimui. Reikia rasti tokį kelią, kuriuo einant būtų pamatuoti visi grandinės elementai – ir išanalizavus milijoną tranzistorių programa negi sustos paklausti tavęs, kur eiti toliau, nuo kurios vietos pradėti analizuoti likusius milijonus?

Arba kita situacija: tavo metodas taikomas Trafi.lt – žmogus mobilia programėle įveda pradinę ir galutinę stotelę, reikia rasti optimalų maršrutą. Tokių užklausų ateina po kelias dešimtis per minutę. Žmogus atsakinėti į visas negali, kaip ir negali priiminėti sprendimų kaskart, kai programa suabejoja.

Dabar, kodėl šachmatų lenta yra geras pavyzdys. Nes gretimi langeliai visada atrodo vienodai, ir tu negali nieko nuspręsti nežinodamas, kas už jų – dviejų, trijų, ... dešimties langelių atstumu. Iš kiekvieno langelio turi vienodus keturis kelius į gretimus langelis. Kaip nustatysi, ar galima laisvai eiti bet kuria kryptimi, ar turi pabandyti visas? Grįžtant prie klasikinio prekeivio uždavinio, tokia situacija gali pasitaikyti moderniame mieste, suskirstytame į stačiakampius kvartalus. Ir, įsivaizduok, kad prekeiviui reikia aptarnauti tiek šitą modernų stačiakampį mikrorajoną, tiek chaotiškos struktūros senamiestį, tiek užmiestį, kur kelių tinklas retas, o atstumai dideli. Ar vis dar veiks geometrinė heuristika? Ar vien matydamas taškų koordinačių sąrašą, tu gali užtikrintai pasakyti, kada reikia pakeisti strategiją? Kiek taškų likus aplankyti mieste, pradėsi planuoti išvažiavimą į užmiestį? O jeigu aš maršrutą specialiai sudėliojau taip, kad reikia aplankyti kelias dešimtis taškų mieste, bet jei nors ir patį pirmą aplankysi ne ta tvarka, kelias gausis ne optimalus – t.y., dar nepradėjus važiuoti mieste, tu jau turi planuoti išvažiavimą, N žingsnių į priekį? Be to, kai kuriuos taškus mieste gali aplankyti grįždamas. Be to, gali įvažiuoti ir išvažiuoti iš miesto kelis kartus, kaskart apvažiuodamas keletą taškų mieste.

Iš esmės, tu gali įrodyti atskirai strategiją užmiestyje, atskirai – senamiestyje, ir atskirai „šachmatų lentos“ mikrorajone, tačiau bet kokia improvizacija viename keičia uždavinio parametrus kitame. Vadinasi, jei turi dešimt potencialių strategijų mieste ir dešimt užmiestyje, tai tau reikia nagrinėti 100 strategijų su vienu išvažiavimu. O jeigu įvažiuoti ir išvažiuoti reikia kelis kartus? Kiekvieną kombinaciją įrodinėsi atskirai?

Ir jeigu dar nesupratai, šitaip prieiname prie NP-Hard klasės uždavinių esmės. Patikrinti sprendimą – t.y., įrodyti, kad jis optimalus, yra tas pats uždavinys, 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ą?
  • +1




Užsiregistravo: 2008-10-12, 05:22
Pranešimai: 6402
Miestas: ☀️☁️☂️☁️☀️
Reputacija: +403
   
 
Į viršų
  Standartinė   Parašytas: 2017-02-05, 13:34 
     
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 :D. 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 :D
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 :D :D :D
  • 0


_________________
Surinkai -10 tasku? Tavo ideologija paduoda dauniskumu... sekmes savo graudžiame, neapykantos ir pavydo persmelktame gyvenime.

Lyderiai-
Nr1. is immortallt - 99+ minusu :D :D :D
Nr2. is utf16 - 50+ minusu :D :D :D
Nr3. ipienius - 50+bbz minusu :D :D :D



Užsiregistravo: 2016-03-12, 10:09
Pranešimai: 3472
Reputacija: -76
   
 
Į viršų
Rodyti paskutinius pranešimus:
Rūšiuoti pagal
 


Naujos temos kūrimas Atsakyti į temą  [ 74 pranešimai(ų) ]  Eiti į Ankstesnis  1, 2, 3

Visos datos yra UTC + 2 valandos [ DST ]


Dabar prisijungę

Vartotojai naršantys šį forumą: Registruotų vartotojų nėra ir 3 svečių


Jūs negalite kurti naujų temų šiame forume
Jūs negalite atsakinėti į temas šiame forume
Jūs negalite redaguoti savo pranešimų šiame forume
Jūs negalite trinti savo pranešimų šiame forume
 

Ieškoti:
Pereiti į:
 
 

Reputation System ©'