Skočiť na obsah


Fotografia
* * * - - 1 Hlasov

Problém obchodný cestujúci

matematika

  • Prosím prihláste sa ak chcete odpovedať
Téma má 40 príspevkov

#26 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 17. September 2018 - 21:22:47

To akze mam ti pospajat rucne body a ty skontrolujes s najlepsou drahou? Este raz to je metoda pre ludi a myslim ze dobra a efektivna kedze clovek nie je stroj, na algortimy sa zide partak urcite co ma chut nieco naprogramovat ked je v tom zbehly, ja by som si musel oprasovat stare vedomosti naucene len z netu. Postup je troska iny, musim dobre pochopit jestvujuce algoritmy, pretoze u algoritmov to bude ine kedze je viac moznosti, jednou je napr. ghladat uplny algoritmus ktory bude elminovat zbytocne vetvy, ktore proste nemozu byt dobre. Potom sa da hladat turbu algoritmus ze najde rychlo nejake lokalne minimum ale v nejakej vetve ktora sa javi ako najperpektivnejsia, prinos je hlavne rychlosti dali by sa riesit dostatocne velke mnozstva bodov, teda aj viac ako tisice. Ked mas takyto problem s obrovským poctom bodov tak to nemas taketo ze par miest na velkej ploche rozutekanych. Ja dufam ze sa aj tono zapoji a ked sa vymysli nieco zaujimave nemusime to vesat nanet zadarmo, az taky dobrak nie som ze venujem tomu kopu casu a potom to dopadne este tak, ze sa ma niekto opyta a na co to vlastne je:)

 

takze spolupraca na takychto veciach sa vzdy hodi.


vygeneruj nahodne na nejakej ploche  do 1000 bodov a ja ti to ukazem, ale to co chces vlastne je pracne, navyse to ide o dokazovanie ze metoda pre ludi je dobra, mozeme skusit ale s tym sa naciaram 1000 spojnic

Priložený súbor(y)


  • 0

#27 Darkman

Darkman

    Winzárten

  • FS Members
  • PipPipPipPipPipPipPip
  • 4583 príspevkov
  • 9 tém

Príspevok bol napísaný: 18. September 2018 - 19:48:36

To akze mam ti pospajat rucne body a ty skontrolujes s najlepsou drahou? Este raz to je metoda pre ludi a myslim ze dobra a efektivna kedze clovek nie je stroj,

Ja ti neviem, ked tvorim nejaky algoritmus, tak vzdy chcem vediet jeho vykonnost. Mysliet si, ze je dobry, mi nestaci. Aj ked je len pre ludi, a je jasne, ze nebude 100% optimalny, by mna, ako autora, zaujimalo nakolko sa prbilizuje inym implementaciam.

vygeneruj nahodne na nejakej ploche  do 1000 bodov a ja ti to ukazem, ale to co chces vlastne je pracne, navyse to ide o dokazovanie ze metoda pre ludi je dobra, mozeme skusit ale s tym sa naciaram 1000 spojnic

Ak si ten algoritmus schopny formalne definovat, tak skutocne nie je problem ho zapisat do kodu a pozriet, ako sa mu vedie. A vobec tych bodov nemusi byt 1000, staci 10, nerovnomerne distribuovanych na ploche. To by nemal byt problem nakreslit na stvorcekovy papier, pospajat a odmerat/vypocitat.
  • 0

#28 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 18. September 2018 - 21:34:11

Mas ho formalne definovany a nie len formalne, mas ho na via ako 10 bodov, mas prikaldy mozes skusat, pretoze pre ludi nie je zaiden :) ale si srandista ze 10 bodov myslim ze touto vetou si to zabil. A ja fakt nemam cas na plytke debaty.

Algoritmus je do max 3 iteracii u 10 bodov na jednu, ak najdes nejaky lepsi algoritmus na tri iteracie, a to nehovorim, ze staci si to zratat sam ked mas o tom pochybnosti ako sa to chova pri viac bodoch random rozhodenych prave to mas obrazok v predoslom prispevku, urcite to nie je optimalne je to na jednu iteraciu, a ze sa to nebude az tak lisit s dokonalou drahou mozes preverit sam na tych jednoduchsich, u symetrickych co mam v prikladoch je to dokonala trasa akurat je tam jeden zlozitejsi a ten si mozes prepocitat sam, mne netreba vsetko pracne ratat vidim ze to je blizko optima, co je skvale na do troch iteracii.


  • 0

#29 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 19. September 2018 - 09:35:48

Pridal som nejake dalsie zlozitejsie asymetricke obrazky do clanku, popri kave. CO je podstatne je to, ze sa dju samozrejme zratat drahy a porovnat to by musel mat clovek program. TAk ako mozeme vediet, ze je to blizke optimalnej drahy bez narocneho ratania, to je celkom zaujimave ako hadanka, ktora ma samozrejme riesenie.

Priložený súbor(y)


  • 0

#30 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 6356 príspevkov
  • 1 tém

Príspevok bol napísaný: 19. September 2018 - 10:24:39

map002g.png

 

 

Tak ukaz ako sa ti podari klasicky problem , hlavne mesta v USA


  • 0

#31 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 19. September 2018 - 10:28:38

to je zopar bodov, nic viac je tam len obvodova technika a par pincipov nekrizit, mat z jedneho uzla dve spojnice, minimalne drahy medzi uzlami pouzit a to co mas nakreslene tomu zodpoveda


  • 0

#32 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 6356 príspevkov
  • 1 tém

Príspevok bol napísaný: 19. September 2018 - 10:33:11

ved ano, ale  dost trvalo kym to ludia v 18 storoci nasli,    tak ukaz ako funguje tvoj algoritmus a mas zaroven spravny vysledok.  


  • 0

#33 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 19. September 2018 - 10:38:42

tyso ty si hadam rozumny clovek tak si precitaj ten diel treti alebo vsetky najdes v nom postupy ako to robit, ja necurujem dodrziam to co som popisal a tak by som aj tu darhu co si dal nakreslil. lebo ked dodrzis co som napisal sa k tomu dopracujes a pomerne rychlo. vidis hore kde je mozno aj 200 uzlov, to som urobil okamzite samozrejme sa to da optimalizovat pri troche casu, pc by to urobil tak rychlo este aj soptimalizaciou ze by si to mal do sekundy podla tych pravidiel. Samozrejme netvrdim ze neexistuje v narocnom probleme vela bodov nejaka nestandartna ecsta ktora ma este nizsie minimum, to nie je v ludskych silach robit bez systemu.

 

Pre zaujimavost slovensko vzdusnou ciarou.

Priložený súbor(y)


  • 0

#34 Darkman

Darkman

    Winzárten

  • FS Members
  • PipPipPipPipPipPipPip
  • 4583 príspevkov
  • 9 tém

Príspevok bol napísaný: 19. September 2018 - 12:08:21

Mas ho formalne definovany a nie len formalne, mas ho na via ako 10 bodov, mas prikaldy mozes skusat, pretoze pre ludi nie je zaiden :) ale si srandista ze 10 bodov myslim ze touto vetou si to zabil. A ja fakt nemam cas na plytke debaty.

Pytat sa na uspesnost algoritmu, ktory ty povazujes za optimalny, skutocne nie je plytka debata. Ako si vobec dosiel na tvrdenie, ze je optimalny, ked si ani samotnu cestu nezmeria.

Momentalne som vo Varsave, ale ked pridem, tak asi nakodim apku, ktora ti vygeneruje urcity pocet bodov, ktore ti nasledne dovoli pospajat, a zaroven ti ale vypocita cestu pomcou simulovaneho zihania. Takze porovnat vysledky uz vobec nebude pracne ;)


  • 0

#35 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 19. September 2018 - 12:28:43

Afrika - obvodova technika


Plytke je ze povazujes 10 bodov za nejaku dostatocnu vzorku udajom pre porovnavanie efektivnosti, pri tom pocte ani nepouzijes cik cak, vidis sam na mapach afriky, USA su len naznaky pouzitia cik - caku. Na to ako viem ze je optimalny bez toho aby som poznal celkovu dlzku, odpovedam to je moje tajomstvo, skor urobim tu cestu ako spocitam 100 bodov.

Priložený súbor(y)

  • Priložený súbor  afrika.jpg   204.04K   0 Počet stiahnutí

  • 0

#36 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 19. September 2018 - 13:31:26

Ale ja pisem ze zatial mam efektivnypostup pre ludi, o tom nepochybujem, vobec neviem ako by to bolo naucit to pocitac, ci by nebol kod prilis zlozity na rozdiel od dostupnych algoritmov. Algoritmus pre pocitac bude nieco asi nieco ine to musim premysliet a hlavne sa musim zoznamit s algoritmami ktore su a ako funguju detailne. Kebyze ma existovat dobra aplikacia musi body abstrahovat z lubovolneho obrazka, previest ich na suradnice poratat dlzky medzi nimi atd. Az nasledne moze spustit nejaky algoritmus a teraz zavisi ci uplny ci neuplny, tato metoda sa prave ujme pri obrovskom pocte bodov kde nie je mozne urobit uplny algoritmus z dovodu limitov vypoctoveho vykonu pc. Mate metodu, mna nikto neplati za napady, ani za vyucbu ako co robit ..


  • 0

#37 game

game

    phantom fsp

  • Management
  • 30203 príspevkov
  • 310 tém

Príspevok bol napísaný: 23. September 2018 - 18:25:27

tak mi napadlo, keď som nevedela v noci spať, že tento problém by mohol byť zaujímavejší, alebo bol, obchodní cestujúci existovali už aj v časoch, ke´d auto nebola samozrejmosť:  keby ten obchodný cestujúci musel počítať so spojmi... napadlo mi to z jednej detektívky dámy Agathy Christie, kde v jednom z príbehov vystupuje obchodný cestujúci, ktorý cestuje vlakmi :)

už padám :ahooj:


  • 0

#38 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 24. September 2018 - 18:33:12

Skor by bolo na mieste ci ti clanky nieco dali, pretoze kazdy jeden niekedy potrebuje navstivit x miest po sebe a potom sa vratit domov. 


  • 0

#39 game

game

    phantom fsp

  • Management
  • 30203 príspevkov
  • 310 tém

Príspevok bol napísaný: 24. September 2018 - 19:46:58

ale isteže, nepoužila by som k tomu matematiku, nie som matematik, ale v podstate sú to veci, ktoré sa využívajú... jedna príhoda spred nesmierne mnoho rokov:

bola som malé decko, v tých časoch v rodine ešte bol zvyk robiť hodne veľké svadby, autá nemal každý mládenec, a v meste bolo zvykom prísť pekne k rodine a pozývať na svadbu osobne - predstaviť nevestu, oznámiť, že sa idú brať a osobne pozvať...

pán a dáma, ktorí k nám vtedy zaklopali, on bol veterinár, ona mladá právnička, a zobrali to pekne z gruntu: neskôr som sa dozvedela, že si popísali ulice, zavolali tetu, ktorá poznala každého, vyčlenili na to jednu sobotu poobede a jednu nedeľu poobede a peši pochodili všetkých v celom mestečku pekne podľa podobného plánu... odvtedy sme podobné plány využili už veľakrát, v menšom merítku samozrejme... v skutočnosti je to jediné rozumné riešenie, keď dobrý človek musí pochodiť hodne, účelne a za čo najkratšiu dobu  : )

 

tie vaše články sú vskutku fajn, a páči sa mi aj diskus... ale čo môj chudák bez auta? teda Agathin chudák : )


  • 0

#40 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 24. September 2018 - 20:26:16

tak je fajn, aspon to nie je debata daj algoritmus a dovidenia :) urcite je to zaujimave tema, matamatika nanajvys pre zakladnu skolu, nic zlozite. nesmierna vyhoda je to ze sa to da robit aj pre naozaj vela bodov a da sa vybudovat aj k tomu algoritmus. Ludia si dnes zvykaju na cudne veci chvalia uplne kraviny, ale to co ma nejaku cenu tak to si ani nevsimnu.


  • 0

#41 robopol

robopol

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5211 príspevkov
  • 12 tém

Príspevok bol napísaný: 25. September 2018 - 14:42:21

pripravujem vylepsenie metod a pokus najst dokonaly algoritmus, z urcitych vylepseni jestvujucich poznatkov, ak ma niekto zaujem ten co vie programovat pomoc sa zide. Pokial sa to podari malo by to byt lepsie ako to co existuje na trhu a to urcite.


  • 0





Podobné témy pre kľúčové slovo: matematika