Srodne teme

14.04.2024. Re: Gde je Kejt? (samo pogrešni odgovori)
12.08.2002. Izrada VB koda ???
28.08.2002. loop i slanje mailova
07.10.2003. Track2 PAN algoritam
22.01.2004. Mala pomoch kod c ':'
08.08.2004. Pravljenje seriala
20.05.2004. Rekurzija u Flashu?

Navigacija

Brisanje liste

Lista poslednjih: 16, 32, 64, 128 poruka.

Algoritam za ovaj problem, kako da napravim loop

[es] :: Art of Programming :: Algoritam za ovaj problem, kako da napravim loop

Strane: 1 2

[ Pregleda: 8678 | Odgovora: 29 ] > FB > Twit

Autor

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Algoritam za ovaj problem, kako da napravim loop

^{26.03.2002. u 19:56 - pre 268 meseci}

Zamislite, da imamo kvadrat 0-1000 polja. Ima granice od [0,1000) v svaku smjer kvadrata . Znači, da je največa razlika, koju može da dosegnemo u tom kvadratu od točke (0,0) do (999.99999...,999.99999...).

U ovom kvadratu ima 52 točaka, koje imaju koordinate (x,y).
Nazovimo to tačker od A-Z i a-z.

A (525,187)
B (295,946)
C (364,787)
D (533,5)
E (203,862)
F (625,11)
G (824,675)
H (369,58)
I (308,785)
J (726,766)
K (155,22)
L (197,879)
M (881,599)
N (862,953)
O (328,391)
P (983,744)
Q (426,695)
R (478,583)
S (821,911)
T (79,60)
U (665,272)
V (191,773)
W (114,281)
X (800,567)
Y (222,693)
Z (846,961)
a (215,740)
b (353,769)
c (750,726)
d (908,909)
e (309,658)
f (867,649)
g (592,106)
h (16,637)
i (54,796)
j (449,649)
k (980,654)
l (594,819)
m (764,101)
n (921,307)
o (928,647)
p (738,196)
q (550,578)
r (478,489)
s (449,755)
t (189,415)
u (433,545)
v (967,478)
w (149,416)
x (144,117)
y (298,972)
z (854,144)

A što treba da učinim :
Treba nači najdulju liniju i "prehodati" sve tačke, tako da dođemo nazad na start point. Za start point možemo da uzmemo bilo koju tačku između gore nabrojanih tačaka.

Rezultat su tačke, stringovi tačaka u redu po kojem su "prehodane", tako da napravimo maksimalalnu distancu.
Treba da napravim više od 30684.463316758

Svi znamo, da je dužina između dvije tačke korjen razlike kvadrata koordinate tačke u x i y smijeru. Pitagora heh

A hack je u tome, što ne znam da napravim loop, sam znam da je to mukotrpni posao za procesor, jer sam sam u VB izprobao nekoliko algoritama, samo ne znam kako bi taj algoritam napravio u binarnom smislu, jedanput sam več to napravio, al sam zaboravio kako sam do toga došao.

Stvarno bi bilo dobro, da tko napravi ustrezan kod ili exe fajl. Najbolje bi bilo u VB.
Bilo bi dobro, da mi tko barem pomogne oko pitanja algoritma, jer je maksimalan put odvisan od sequence prehodanih tačaka.

A sada .....
Pozdrav Boris

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

Alter Ego
null
Pančevo

Član broj: 1880
Poruke: 453
*.panet.co.yu

Sajt: www.tridenet.com

Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{29.03.2002. u 14:47 - pre 268 meseci}

Ako sam te dobro razumeo, to što ti pokušavaš da rešiš je problem trgovačkog putnika. Jedina razlika je što tebi treba najduža putanja a u problemu TP se traži najkraća, međutim to ne menja ništa! Algoritmi za rešavanje ovog problema se dele u dve grupe:
1.Egzaktni
2.Heuristički

Inače, složenost je eksponencijalna, što znači da sa porastom broja tačaka(čvorova grafa) veoma brzo rastu zahtevi za rač. resursima. Najveći broj tačaka za koji je problem do sada rešen je negde oko 13500!

Što se tiče samog postupka rešavanja, to imaš u svakoj knjizi koja se bavi algoritmima, ili po časopisima, potraži po literaturi. Ako ne nađeš, javi pa ću da ti pošaljem neki od algoritama.

BTW, nisam najbolje shvatio, šta treba da napraviš 30684.463316758?

Zaista nema potrebe da izmišljaš rupu na saksiji, kad je to neko već uradio, zar ne?
� UNIX-u. Ako je VDK bibliote

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{02.04.2002. u 08:31 - pre 268 meseci}

30684.463316758 je največa dužina koju treba putnik da prehoda, a ja trebam da prehodam malo vise :)

A što se tiče algoritma, bilo bi dobro da mi pošalješ kako PM a može i po mail-u.

Hvala

Boris

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.dialup.mindspring.com

+18 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{02.04.2002. u 08:43 - pre 268 meseci}

Ako se dobro secam jednog od heuristickih algoritama, uradi sledece:

1) izaberi bilo koju tacku
2) nadji tacku koja je najudaljenija od te tacke, a na kojoj jos nisi bio
3) predji na novu tacku
4) idi na korak 2

Ovo ponavljaj dokle god ti ne nestane tacaka.

Naravno, ovo zavisi od izbora pocetne tacke, ali bi trebalo da otprilike radi ono sto tebi treba. Naravno, posto resavas (inverzni) problem trgovackog putnika, 'tacno' resenje bi zahtevalu suvise procesorkse snage, tako da treba da se zadovoljis nekom od heuristika.

Probaj ovo, i probaj da izaberes nekoliko pocetnih tacaka i da vidis kakvi su rezultati.

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{02.04.2002. u 13:11 - pre 268 meseci}

Taj algoritam sam več uradio i vidio, da su sve dužina manje od 30684.463316758, trebao bi algoritam, koji temelji na binarnom principu, tako da bih mogao skalkulirati sve kombinacije (oz. bar neke - znam, vječnost postupka i algoritma ).

Algoritam - bistvo je u binarnom zapisu loop-a sam jedanput več sastavio sam, ali sada ne znam kako mi je to uspjelo

P.S: Ne želim Heuristički pristup, ja bih radije jedan program da napravim u VB koji če biti exsaktni ( upotrebit če "sve" moguče kombinacije ) s opcijom save, da može i da startuje od jedne željene pozicije i tako nastavlja sa radom, jer sam znam koliko vremena i procesorske snage treba taj pristup !!!

Ajd još jedanput ču probati da riješim ovo :)

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

Reljam
Relja Markovic
San Francisco

Član broj: 531
Poruke: 1793
*.dialup.mindspring.com

+18 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{02.04.2002. u 18:08 - pre 268 meseci}

Hm, nije mi jasno - zar ovaj problem nije O(n!)? Ako jeste, sumnjam da ces moci da nadjes egzakti nacin, 52! nije malo. Medjutim napisi sta si uradio, zanima me.

Srecno!

Odgovor na temu

BobMarley
Vedran B
Bologna

Član broj: 148
Poruke: 1161
195.116.186.*

ICQ: 61882680

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{02.04.2002. u 20:56 - pre 268 meseci}

ok ovo nije isprobano vec samo teorija, ali uzmimo da ces najveci put napraviti ako radis kruzno Opisivanje prijasnje putanje (spirala prema vani).

podeli prostor u 4 jednaka kvadranta s obzirom na neku tacku, izaberi jedan od ta 4 i tu nađi tacku koja je najbliza pocetnoj zatim smao redom vrti isponova svaki kvadrant svaki put spajajuci prethodnu sa novom koja je dalje od prethodne (s obzirom na sredisnju - pocetnu).

:)

ne znam kako bi ovo ispalo, ali ideja je dobra ne ?

BobMarley (me) ...the legend

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{02.04.2002. u 22:56 - pre 268 meseci}

Ideja je jako dobra, moram priznati.

Mislim da je ideja sa spiralom dovoljno dobra, samo mislim, da bi namjestu spirale ( recimo slično kao kvadrat ).

ako bi uzeo samo jedan kvadrant, cijeli:
Ako uzmem za start point točku koja je najbliže sredini (500,500)
uvedem r i F variable

Primjer :
ako je start point (500,500)
r ide o 1 do 708 (max diagonala do rubne tačke našeg kvadrata)
a F ide od 0 do 2*PI*r
tako zaobiđem sve moguče točke, koje su na spirali ( ali ne znam, dal je to dovoljno dobro, jer bolje bi bilo ako bi točke bile na kvadratu !!!).

ako uzmem 4 kvadranta i u svakom od tih pravim tačke ( gornji primjer) koja duljina je od jednoga do drugoga para tačaka kvadranta veča. F je za sve kvadrante isti ( oz. barem sličan za sledečeg ), tu bih opet trebao da napravim koji algoritam, koji bi bio odvisan od pozicije (kuta).
Start point bi onda bio "centar" točka našeg cjelokupnog polja, sledeča točka bi bila u kvadrantu 1, sledeča u kvadrantu 2 i tako dalje ...

Probat ču sa programom pa ču ti reči.
Svakako hvala na toj teoriji !!!

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

BobMarley
Vedran B
Bologna

Član broj: 148
Poruke: 1161
195.116.186.*

ICQ: 61882680

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{03.04.2002. u 01:34 - pre 268 meseci}

hvala !
i nemoj slucajno da zaboravis javiti rezultate :)

BobMarley (me) ...the legend

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{03.04.2002. u 07:33 - pre 268 meseci}

Pa naravno, trenutno ima malih problema, ali rijesit cu to !!!

Boris

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{22.04.2002. u 13:49 - pre 267 meseci}

Citat:

BobMarley
hvala !
i nemoj slucajno da zaboravis javiti rezultate

Rezultati nisu tako dobri kao što sam mislio.
Na WEB-u sam našao par koristnih problema za ovaj primjer, ali mislim, da su vrjednosti minimuma / maximuma došle do skrajnih granica.

Što da kažem ...
Kad dobijem koju ideju više ...

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{07.05.2002. u 17:10 - pre 267 meseci}

Code:
<king>07:23am~/in/tsp_solve-1.3.7/tsp_solve be = 52 -p1 < ../TEST
-s1020781444 -m-1 52 -p1 be
1187.660726
Best Optimal Takes = 00:00:00.00C for 5543.399967
592 106
625 11
533 5
369 58
155 22
79 60
144 117
114 281
149 416
189 415
328 391
478 489
433 545
478 583
550 578
449 649
426 695
309 658
222 693
215 740
191 773
16 637
54 796
203 862
197 879
298 972
295 946
308 785
353 769
364 787
449 755
594 819
726 766
750 726
821 911
846 961
862 953
908 909
983 744
980 654
928 647
867 649
824 675
800 567
881 599
967 478
921 307
854 144
764 101
738 196
665 272
525 187
592 106
be 1 run 00:00:00.00C for 5543.399967
Completed

Evo to je max što sam mogao dobit, a dobit treba min 5107.3639119195

a imam još jeda extra info :

If you wish to research this problem a little more then it is basically the
travelling salesman problem, albeit on a topological torus this time

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

indy
Nikola Knežević
EPFL
Lausanne

Član broj: 3152
Poruke: 144
*.hemofarm.co.yu

Jabber: indy@elitesecurity.org

Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{07.05.2002. u 22:14 - pre 267 meseci}

Nedavno su nam pokazali dobru foricu, koja, opet daje dobre rezultate u problemu trgovackog putnika. (mada je heuristika).
LM, evo kako ide:
1. Napravi se bilo kakav Hamiltonov put
2. Odabere se 3 para spojenih tacaka
3. Uradi se prepovezivanje po parovima
4. Odabere se ono koje ponajvise odgovara, ili se prekida ako nema takvog
5. GOTO 2

Sta sam mislio o prepovezivanju:
Ako smo recimo odabrali tacke 1,2,3,4,5,6, i bile su spojene kao 1-2, 3-4 i 5-6.
Sada pravimo povezivanja (i naravno uklanjanja veza 1-2, 3-4 i 5-6)
1-3, 2-4 i 5-6
1-4, 2-5 i 3-6

I dalje shvatate sami. Ovo je jedna od bojih heuristika, koja daje veoma dobre rezultate.

:*a programmer types in code, compiles it, runs it, and waits for
it to crash. Programs that don't crash are presumed to be running
correctly." - UNIX Haters Handbook

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{08.05.2002. u 06:12 - pre 267 meseci}

Hm, nije tako dobra kao što misliš.

Evo što je moje najbolje :

Code:

-s1020801684 -m-1 52 -dWRAP -p1 -f../TEST be
693.732657
Best Optimal Takes = 00:00:00.00C for 5107.363914
100.568382 100.568385 592 106
92.195442 92.195445 625 11
172.351379 172.351385 533 5
111.521301 111.521298 369 58
26.172504 26.172505 298 972
124.579292 124.579292 295 946
18.027756 18.027756 203 862
149.040268 149.040263 197 879
84.970581 84.970583 155 22
86.452301 86.452299 79 60
166.721329 166.721324 144 117
139.463257 139.463257 114 281
40.012497 40.012498 149 416
141.056732 141.056726 189 415
179.175888 179.175891 328 391
71.840103 71.840100 478 489
58.898216 58.898217 433 545
72.173401 72.173402 478 583
123.458496 123.458495 550 578
51.429562 51.429563 449 649
64.257294 64.257295 426 695
90.824005 90.824006 449 755
21.095022 21.095023 364 787
47.759815 47.759816 353 769
127.003937 127.003937 308 785
93.776329 93.776330 309 658
47.518417 47.518417 222 693
40.804413 40.804412 215 740
138.917236 138.917242 191 773
88.005684 88.005682 54 796
181.245697 181.245690 983 744
63.655323 63.655322 908 909
17.888544 17.888544 862 953
55.901699 55.901699 846 961
244.934692 244.934685 821 911
142.242752 142.242750 594 819
46.647614 46.647615 726 766
89.872131 89.872131 750 726
50.249378 50.249378 824 675
105.891457 105.891454 867 649
87.091904 87.091905 800 567
67.178864 67.178866 881 599
52.469040 52.469038 928 647
39.812057 39.812058 980 654
166.379089 166.379085 16 637
177.079071 177.079078 967 478
176.232803 176.232801 921 307
99.744675 99.744674 854 144
98.493652 98.493655 764 101
105.380264 105.380264 738 196
163.783386 163.783394 665 272
105.118980 105.118980 525 187
592 106
be 1 run 00:00:00.00C for 5107.363914
Completed

Beat this .... a ja trebam da dobijem manje od 5107.3639119195

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{20.05.2002. u 14:38 - pre 266 meseci}

indy

Citat:

Nedavno su nam pokazali dobru foricu, koja, opet daje dobre rezultate u problemu trgovackog putnika. (mada je heuristika).
LM, evo kako ide:
1. Napravi se bilo kakav Hamiltonov put
2. Odabere se 3 para spojenih tacaka
3. Uradi se prepovezivanje po parovima
4. Odabere se ono koje ponajvise odgovara, ili se prekida ako nema takvog
5. GOTO 2

Sta sam mislio o prepovezivanju:
Ako smo recimo odabrali tacke 1,2,3,4,5,6, i bile su spojene kao 1-2, 3-4 i 5-6.
Sada pravimo povezivanja (i naravno uklanjanja veza 1-2, 3-4 i 5-6)
1-3, 2-4 i 5-6
1-4, 2-5 i 3-6

I dalje shvatate sami. Ovo je jedna od bojih heuristika, koja daje veoma dobre rezultate.

Hm, slaba heuristika, rezultati su jako slabi a i vrema dobivanja je jako slabo.

.. evo jednog izseka maila kojeg sam poslao čak 3 doktorom iz princeton-a i rice-a koje se bave sa TSP problemima.

Citat:

The best score for minimum : 5107.3639119195
The best score for maximum : 30684.463316758

Note:The accuracy of answers and calculation of paths in this question is limited by the accuracy of PHP float calculations and path length calculation for a path "ABCDE..." is on the basis of path_length= (A to B), path_length=path_length + (B to C), etc for the 52 mini-paths. This is then subject to SQL storage, and so the script result is final. If a seventh decimal place is lost here or there then tough luck! There is a tolerance on checking answers of 0.00001

--------------------------------------------------------------------------------

I have learned a lot from the books regarding TSP, i have also searched a lot of WEB pages, found some good applications to solve this problem.
I have tried to solved the problems with many approach ( spherical, topological torus, crosses ...) and what is my problem ?

I were unable to beat both limits my current best for min is 5107.363914 and for maximum : 30684.463305

My results don't bother me, what is bothering me is a fact that those answers might really the best global solution for that problem.
I have mail the constructor of that puzzle regarding the best possible solution for the upper puzzle, but he were unable to tell me what is the exact "best" solution for both problems (min & max), I have mailed some other friends but they were unable to beat my length.

So the question is were those lengths really the best possible combination for this puzzle ?
I'm really looking forward for your replies, or even the resoult for the best possible path to solve this puzzle ( proof).
I need some kind of proof that i'm not spending my time uselessly.
If those resoults are really the best global solutions for this puzzle I'll have to mail the constructor of that puzzle and ask him to
write new one.

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

unlimited

Član broj: 994
Poruke: 32
*.ptt.yu

Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{20.05.2002. u 19:22 - pre 266 meseci}

Nisam bas najbolje razumeo to sve sa kvadratima i duzinama. Ali da ponovim problem onako kako sam ga razumeo.

Date su 52 tacke, treba naci najduzu putanju koja spaja sve tacke (obici sve tacke) tako da se kroz svaku moze proci samo jednom stim da se moramo vratiti u pocetnu. Rezultat je duzina i redosled tacaka kroz koje se prolazilo.

Moguce resenje:

Najduza putanja se sastoji od zbira putanja izmedju pojedinih tacaka. Posto su ti date sve tacke mozes da napravis matricu A "rastojanja tacaka" 52x52 gde se na mestu A[x][y] nalazi duzina izmedju tacaka x i y.

Posto se najduza putanja sastoji od zbira putanja izmedju pojedinih tacka, najlakse resenje je proci matricu "rastojanja" po vrstama (ili kolonama), tako da dobijes pojedine sabirke, stim da iz svake vrste mozes da biras jedan element ali koji nije simetrican u odnosu na glavnu dijagonalu na prethodno izabrane elemente ([1,2] = ab == ba = [2,1] pa nema smisla). Prostije receno nemozes imati dva sabirka iz iste vrste ili kolone.

Ovo pretrazivanje je za pronalazenje najvece moguce duzine, i prolazi se kroz sve tacke tj. za sve moguce pocetne tacke, to moze da se smanji jer najduza putanja ne odredjuje jednoznacno putanju koja je odredjuje.

Recimo da je najduza putanja ako se ide preko a-b-c-d-a (gledano na cetiri tacke), neka je ukupan duzina jednako "duzina":

duzina = ab + bc + cd + da;

medjutima posto je ab==ba, bc==cb, cd==dc i da==ad, ako malo okrenemo orejentaciju dobijamo da je najduza putanja i ako se ide preko b-a-d-c-b,

duzina = ba + ad + dc + cb;

posto je matrica "rastojanja" simetricna u odnosu na glavnu dijagonalu i na glavnoj dijagonali su nule, moze se pretrazivati samo ispod ili iznad dijagonale, ali o tome nisam mnogo razmisljao, to ostavljam tebi, jedino sto se moze primetiti je da se nesme pojaviti da tri razlicita sabirka sadrze istu tacku (ne moze se pojaviti npr. ab cb db), jer bi to znacilo vracanje u jednu od tacaka (ovo vazi i za pretrazivanje cele matrice, dobar nacin da se preskoci neka iteracija).

Sto se tice pamcenja redosleda tacaka, njih mozes da generises nekako u zavisnosti od prolaska kroz matricu, jer za 52 tacke koliko mogu da procenim ima 52 razlicita redosleda koji daju istu duzinu. Recimo ako kreces od cd, redosled ti je c-d, ili d-c, dok je vec sledeci odredjen, sa prethodnom tackom.

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{20.05.2002. u 21:53 - pre 266 meseci}

Moram reči, da je tvoje razmišljanje veoma dobro.
Da uistinu tražim MINIMUM i MAXIMUM, no problem se otvara tako jer trebaš da veliko loopaš sa algoritmom, trebaš i gledati da iste parice koordinata ne uzmeš dvaput ili da ne uzmeš duljine iste koordinate, a ako malo bolje pogledaš ovaj algoritam, dobiješ da je u bistvu jako dobar, no programski tajming i rejting kod takog pristupa ( duljine parica ) je jako brz, no kad se kod eliminacije parica i same sequence tiče ovaj je problem minimalno cca 5 x slabiji ( brzina ) nego ako uzmeš svih 51!/2 kombinacija. Ako imaš vremena to bih programsko mogao i sam skužiti, no da vam stvar posimpliram, stvar konačnog rješenja ako je uopšte moguče dobiti najbolji rezultat ( največji problem je aproksimacija sql servera pri kalkulaciji ), tako da nismo ograničeni sa problemom kao problemom nego i sa konvergencijom rezultata.

Evo malo primjera rješenja preko java skripta, da u istinu vidite kakvi rezultati so primjerni :
http://www.painsley.org.uk/mathsmirror/java/travel/travel.htm
http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html

Ja mislim, da je taj problem problem križa ili topologičnog torus-a , a primjer za to je ovo :

Jao jao, opet sam dobio malo bolji rezultat za minimum, no opet premalo, da bih dobio dovoljno.
a kakvi su vaši rezultati za min/max ?

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

unlimited

Član broj: 994
Poruke: 32
*.ptt.yu

Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{21.05.2002. u 12:05 - pre 266 meseci}

Pogledao sam linkove koje si ostavio, i ono sto sam prvo vizuelno mogao zakljuciti, je da se najkraci put dobija ako se putevi izmedju pojedinih tacak ne seku, shodno tome logicno je da se najduzi put dobija ako se putevi sto vise seku (aku uzmemo cetiri tacke u temenima kvadrata to je ocigledno).

Ali da se vratim na problem koji si postavio, ako gledamo tvoj kvadrat 1000 x 1000 polja, (nadam se da sam dobro razumeo), ili jos bolje kordinatni sistem, ono sto se moze uociti da za razlicite tacke dobijas iste rezultate.

Opet jedan primer neka imas dve tacke u kvadradu sa poljima 4x4, recimo na mestima [1,4], [3,3]. Medjutim ako taj kvadrat rotiras za 90 stepeni dobijas tacke (ako sam dobro izracunao) [1,1] [2,3] izmedju kojih je duzina takodje ista.

Cilj ove price je da resenje ne treba vezivati za koordinate, nego za negi drugi parametar recimo povrsinu.

A sad cilj cele ove price. Posto se radi o zatvorenim putanjama (bilo da se radi o minimalnoj ili maksimalnoj putanji), zamislimo da imamo funkciju koja ce putanju da preslika na krug, takav da su odredjene duzine izmedju putanja tetive tog kruga, rezultat je sledeci, krug sa najmanjim precnikom odredjivao bi najkracu putanju, a krug sa najvecim precnikom najduzu putanju.

[Ovde je bila i prica o nekim parovima tacaka cije je rastojanje precnik tog kruga, ali nazalost posto to ne vazi, bar ne uvek morao sam da je izbrisem]

Sto se tice aproksimacija i konvergencija, kada broj tacaka tezi beskonacnosti, i taj put bi tezio obimu kruga, za konacan broj tacaka to bi opet moralo da se racuna.

Odgovor na temu

StratOS
Slovenija

Član broj: 2234
Poruke: 989
*.dsl.siol.net

+1 Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{21.05.2002. u 14:56 - pre 266 meseci}

Probaj sam malo da kalkuliraš, pa češ vidjeti, na papiru izgleda lako, a u onim linkovima kojih sam ti dao ima bar 50 načina kako to riješiti, ja sam se dugo zabavljao sa 6,7 primjera, a najbolje rezultat sam dobio trenutno sa križem (gledaj sliku gornjeg posta).

Problem je moguče riješiti ( ali neznaš, dal če ti dati bolje rezultat, pa zato i postoje i mnoge interpretacije ) i sa više predpostavki i aproksimacija, ako još malo razdjelim taj problem je moguče impretirati i po površini, kao što si ti rekao, i po ostalim parametrima kao što su radij, kutu među tačkama, putanji elipse ili sfere ...

Mene bolje zanima kako vam uspjeva da riješite/nastavite taj problem bolje i kakvi su vaši rezultati. Na kakav način ste do njih došli, zanimaju me i minimumi i maximumi.

Probajte malo, barem uzmite olovku u ruku i probajte napraviti maximalan poligon, koji se ne seče
evo primjera :

ili malo boljeg problema za kojeg je bila razpisana nagrada za 13,509 mjesta u USA

Pozdrav StratOS
"Multitasking - ability to f##k up several things at once."
"It works better if you plug it in."
"As a rule, software systems do not work well until they have been used, and have failed repeatedly, in real applications."
"The one who is digging the hole for the other to fall in is allready in it."

Odgovor na temu

unlimited

Član broj: 994
Poruke: 32
*.ptt.yu

Profil

Re: Algoritam za ovaj problem, kako da napravim loop

^{22.05.2002. u 05:17 - pre 266 meseci}

RESIO! Ili bar mislim da jesam ako se opet nisam negde zeznuo. Princip je da nadjes teziste sistema tacaka. Onda od tog tezista biras najdalju tacku za pocetnu, i od nje kreces, pa onda od nje najdalju i tako dalje, i dobijas najduzu putanju, slica stvar je i sa najkracom putanjom, biras najblizu od tezista za pocetnu, pa onda od nje najblizu itd. Sto se tice rezultata, posto sam generisao slucajne tacke oni su razliciti, ali se minimum krece uglavnom izmedju 3000 i 4000 hiljade, dok je maksimum negde oko 50000.

Odgovor na temu

[es] :: Art of Programming :: Algoritam za ovaj problem, kako da napravim loop

Strane: 1 2

[ Pregleda: 8678 | Odgovora: 29 ] > FB > Twit

Srodne teme

14.04.2024. Re: Gde je Kejt? (samo pogrešni odgovori)
12.08.2002. Izrada VB koda ???
28.08.2002. loop i slanje mailova
07.10.2003. Track2 PAN algoritam
22.01.2004. Mala pomoch kod c ':'
08.08.2004. Pravljenje seriala
20.05.2004. Rekurzija u Flashu?

Navigacija

Lista poslednjih: 16, 32, 64, 128 poruka.