Forum » Programiranje » cene permutacij help please
cene permutacij help please
meszaj ::
Pozdrav vsem !
Imam eno nalogo za seminarsko, ki pa mi povzroca kar precej sivih las. Prosil bi za kaksen nasvet in pomoc lepo lepo lepoooooooo prosim. Branje pa stuff sem ze vgradil not. Zanima me predvsem kaksen bi bil ta pameten algoritem za permutacije. Meni vse skupaj disi po kaksnem usmerjenem grafu (problem trgovskega potnika??)
please help !
navodila so na tejle strani:
http://lalg.fri.uni-lj.si/~sliva/faks/i...
glejte pod: Algoritmi in podatkovne strukture 2 (vaje) , 1.seminar
tukaj pa moja skrajsana navodila:
Primer:
Imamo podano zaporedje A = { 3,4,5,7,8 } in relacijo R = { (3,4),(3,5),(4,5),(4,7),(4,8),(5,7),(5,8),(7,3),(7,8),(8,3)}
-V datoteki je podano le R = { (7,3), (8,3) } kar pomeni (7 je manjse od 3), (8 je manjse od 3)
-Poiscite permutacijo, ki ima za dano zaporedje A in relacijo R najmanjso ceno.
-Ce sta dva elementa v urejenem zaporedju v napacnem vrstnem redu (v konfliktu) glede na relacijo, prispevata ceno, ki je enaka razliki njunih indeksov na kvadrat, v urejenem zaporedju.
Podajam nekaj moznih resitev za zgornji primer:
1.) 5,4,3,7,8 cena=11; konflikti = ( 3-4, 3-5, 3-7, 3-8, 4-5)
2.) 4,7,3,5,8 cena=12; konflikti = ( 3-4, 3-8, 5-7)
3.) 4,3,5,7,8 cena=14; konflikti = ( 3-4, 3-7, 3-8)
Imam eno nalogo za seminarsko, ki pa mi povzroca kar precej sivih las. Prosil bi za kaksen nasvet in pomoc lepo lepo lepoooooooo prosim. Branje pa stuff sem ze vgradil not. Zanima me predvsem kaksen bi bil ta pameten algoritem za permutacije. Meni vse skupaj disi po kaksnem usmerjenem grafu (problem trgovskega potnika??)
please help !
navodila so na tejle strani:
http://lalg.fri.uni-lj.si/~sliva/faks/i...
glejte pod: Algoritmi in podatkovne strukture 2 (vaje) , 1.seminar
tukaj pa moja skrajsana navodila:
Primer:
Imamo podano zaporedje A = { 3,4,5,7,8 } in relacijo R = { (3,4),(3,5),(4,5),(4,7),(4,8),(5,7),(5,8),(7,3),(7,8),(8,3)}
-V datoteki je podano le R = { (7,3), (8,3) } kar pomeni (7 je manjse od 3), (8 je manjse od 3)
-Poiscite permutacijo, ki ima za dano zaporedje A in relacijo R najmanjso ceno.
-Ce sta dva elementa v urejenem zaporedju v napacnem vrstnem redu (v konfliktu) glede na relacijo, prispevata ceno, ki je enaka razliki njunih indeksov na kvadrat, v urejenem zaporedju.
Podajam nekaj moznih resitev za zgornji primer:
1.) 5,4,3,7,8 cena=11; konflikti = ( 3-4, 3-5, 3-7, 3-8, 4-5)
2.) 4,7,3,5,8 cena=12; konflikti = ( 3-4, 3-8, 5-7)
3.) 4,3,5,7,8 cena=14; konflikti = ( 3-4, 3-7, 3-8)
snow ::
Genetski algoritem nebi veljal?
Fitness pa daš število napačnih relacij.
Fitness pa daš število napačnih relacij.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
meszaj ::
z genetskimi algoritmi se se nisem ukvarjal, zato sem raje za kako drugo moznost.
se kaksna ideja?
se kaksna ideja?
Thomas ::
Napiši bruta forca program, ter ga ponudi Critticallu.
Simple.
Simple.
Man muss immer generalisieren - Carl Jacobi
Sci-Fi ::
Thomas:
Brute force pomeni pregled vseh permutacij. -> n!
Misliš da bi critticall to znal izboljšat?
Poleg tega program mora biti napiosan v Javi.
Pa potrebno je poznavanje delovanja algoritma pri zagovoru!!!!!
Sem že jaz razmišljal v to smer pa sem si premislil in sem sestavil svoj algo.
Izdam pa ga ne ker je od njega odvisna moja ocena!!!
Brute force pomeni pregled vseh permutacij. -> n!
Misliš da bi critticall to znal izboljšat?
Poleg tega program mora biti napiosan v Javi.
Pa potrebno je poznavanje delovanja algoritma pri zagovoru!!!!!
Sem že jaz razmišljal v to smer pa sem si premislil in sem sestavil svoj algo.
Izdam pa ga ne ker je od njega odvisna moja ocena!!!
Sci-Fi is the best way to dream
Sci-Fi ::
DMouse:
Sej bi pa ti ne vem povedat.
Moj proces pač dela določen čas in ne ve ali je dejansko prišel do optimalne rešitve.
Tk pač to je.
Sej na noben način ne morš vedet ali je rešitev ki jo da algoritem res minimalna, če ne preveriš vseh možnih rešitev.
Razen če znaš matematično dokazat, da je to res minimalna rešitev.
No a zanš?
To me res zanima. Če ti je to uspelo, pol svaka ti čast.
No tolko zaenkrat!
Sej bi pa ti ne vem povedat.
Moj proces pač dela določen čas in ne ve ali je dejansko prišel do optimalne rešitve.
Tk pač to je.
Sej na noben način ne morš vedet ali je rešitev ki jo da algoritem res minimalna, če ne preveriš vseh možnih rešitev.
Razen če znaš matematično dokazat, da je to res minimalna rešitev.
No a zanš?
To me res zanima. Če ti je to uspelo, pol svaka ti čast.
No tolko zaenkrat!
Sci-Fi is the best way to dream
DMouse ::
Hja, moj algoritem je zaenkrat samo v glavi, ampak ko bo sprogramiran, bo vedel kdaj je rešitev optimalna in bo takrat tudi nehal... i hope 
A se komu kaj sanja koliko bo tabela velika? Ker tisto o 250.000 elementih je men "mal" pretirano
, že 1000 elementov je smrt za vsak O(n^3) algoritem, za nekatere sem slišal, da jim algoritem poklekne pri malo več kot 100 elementih...
A se komu kaj sanja koliko bo tabela velika? Ker tisto o 250.000 elementih je men "mal" pretirano
, že 1000 elementov je smrt za vsak O(n^3) algoritem, za nekatere sem slišal, da jim algoritem poklekne pri malo več kot 100 elementih... Sci-Fi ::
fora je v tem, da tvoj algoritem ne bo imal dovolj časa da bi našel optimalno rešitev.
Zakaj?
Zato, ker imaš za enega od parametrov tudi čas izvajanja programa, in če tvoj algoritem v danem času na bo našel rešitve oz. dobrega približka rešitve in ne bo naredil outputa, potem tvoj program ne bo deloval in bo seminarska neuspešno opravljena.
Tako je nam rekel asistent. Zato si tudi ne moreš privoščiti iskanja optimalne rešite, ker enostavno ne boš imel dovolj časa.
Kar predstavljaj si da ti da 100 000 števil ti pa bi rad s svojim algoritmom poiskal optimalno zaporedje. Še po dveh letih ne bi bil fertk kaj šele v največ nekaj minutah kolikor bo verjetno tekel program.
Pa ne zdej mislit da bo res dal 100 000 števil.
Po mojem jih bo da celo manj od 1000. Ampak nikar me ne drži za besedo, kajti rekel je da ne pove ničesar o tem koliko števil bo dal!!
Pa čimprej spravi svoj algoritem iz glave v Javo ;), da ne bo prepozno
No toliko.
Zakaj?
Zato, ker imaš za enega od parametrov tudi čas izvajanja programa, in če tvoj algoritem v danem času na bo našel rešitve oz. dobrega približka rešitve in ne bo naredil outputa, potem tvoj program ne bo deloval in bo seminarska neuspešno opravljena.
Tako je nam rekel asistent. Zato si tudi ne moreš privoščiti iskanja optimalne rešite, ker enostavno ne boš imel dovolj časa.
Kar predstavljaj si da ti da 100 000 števil ti pa bi rad s svojim algoritmom poiskal optimalno zaporedje. Še po dveh letih ne bi bil fertk kaj šele v največ nekaj minutah kolikor bo verjetno tekel program.
Pa ne zdej mislit da bo res dal 100 000 števil.
Po mojem jih bo da celo manj od 1000. Ampak nikar me ne drži za besedo, kajti rekel je da ne pove ničesar o tem koliko števil bo dal!!
Pa čimprej spravi svoj algoritem iz glave v Javo ;), da ne bo prepozno
No toliko.
Sci-Fi is the best way to dream
Dusan_83 ::
A lahko kdo prosim pove, kako je naredil, da se mu program konca po n sekundah? Moznost je s threadi, vendar se mi ta resitev ne zdi najbolj elegantna, pa se doloceni problemi se pojavljajo.
Pa se nekaj: zakaj je uporabna tista time funkcija na Slivnikovi strani? Ker jaz je ne razumem najbolje...
Hvala za pomoc
Pa se nekaj: zakaj je uporabna tista time funkcija na Slivnikovi strani? Ker jaz je ne razumem najbolje...
Hvala za pomoc
Thomas ::
Zdej šele sem dal delat, čez noč. Če nisem naredu nobene napake pri osnovni bruta forca verziji, bomo zjutraj videli, kako je.
Man muss immer generalisieren - Carl Jacobi
Sci-Fi ::
Super!
No ko bo kej rezultatov, jih kr gor prlep.
Me zelo zanima kaj bo naredu s brutforce kodo.
Mi sploh ni jasno kako bi lahko izboljšal iskanje.
Ampak pustimo se presenetiti. Če je pohitril qSort, pol bo verjetn tud tuki kej našel.
Komaj čakam.
Pol bomo pa vidli kolk optimizaicja na roke še velja dandanes.
No ko bo kej rezultatov, jih kr gor prlep.
Me zelo zanima kaj bo naredu s brutforce kodo.
Mi sploh ni jasno kako bi lahko izboljšal iskanje.
Ampak pustimo se presenetiti. Če je pohitril qSort, pol bo verjetn tud tuki kej našel.
Komaj čakam.
Pol bomo pa vidli kolk optimizaicja na roke še velja dandanes.
Sci-Fi is the best way to dream
Thomas ::
No lej:
To je ena taka koda, ki dopušča samo dve izjemni števili od relacije. ex1 in ex2.
In 4 števila. Moram dat generalizirat še ...
// The algorithm has been enhanced For 98.492%
$DECLAREINT ex1 ex2 x1 tmp1 j tmp2
$DIMENSION tb[4] best[4] map[15]
$ENHANCING OFF
$RINVAR map[](0,1) ex1(0,3) ex2(0,3)
$RETVAR best[]
$SHOWVAR cmax ex1 ex2
// int best[4]; int ex1=0;int ex2=0;int x1=0;int tmp1=0;int j=0;int tmp2=0;
$BES
x1=1;
j=2;
tmp1=3;
if (ex1>=ex2) {
goto labelcritticall7;
}
if (ex2==x1) {
goto over;
}
if (tmp2==ex1) {
goto labelcritticall13;
}
tmp2=ex1|j;
if (tmp2==ex2) {
best[j]=tmp1;
best[x1]=x1;
best[tmp1]=j;
goto labelcritticall9;
}
over:;
best[x1]=x1;
best[j]=j;
while (j!=j) {
labelcritticall13:;
if (j==ex2) {
best[j]=x1;
best[x1]=ex2;
break;
}
labelcritticall7:;
best[tmp2]=x1;
best[tmp1]=j;
best[j]=tmp1;
goto labelcritticall9;
}
best[tmp1]=tmp1;
labelcritticall9:;
$EES
//$RINVAR map[](0,1) ex1(0,3) ex2(0,3)
$INVAR map[](1,1,1,1,1,0,0,0,0,1,1,0,1,1,1) ex1(3) ex2(2)
$INVAR map[](1,1,0,1,0,1,0,0,1,1,0,0,1,1,1) ex1(1) ex2(2)
$INVAR map[](1,0,1,1,0,0,0,0,0,0,1,0,0,1,0) ex1(2) ex2(2)
$INVAR map[](0,0,0,0,0,1,1,0,0,0,1,0,0,1,0) ex1(0) ex2(1)
$INVAR map[](0,0,1,0,0,0,0,1,1,1,0,0,1,1,1) ex1(3) ex2(1)
$INVAR map[](0,0,1,1,0,1,0,1,0,1,1,0,1,0,1) ex1(0) ex2(2)
$INVAR map[](0,0,0,1,0,0,1,1,0,1,0,1,0,1,0) ex1(1) ex2(3)
$INVAR map[](0,0,0,1,0,0,1,0,0,1,1,0,0,1,1) ex1(2) ex2(3)
$INVAR map[](1,1,0,0,1,1,1,1,1,1,0,1,1,1,1) ex1(1) ex2(0)
$INVAR map[](1,0,1,1,0,1,0,1,0,0,1,1,1,0,1) ex1(0) ex2(0)
$INVAR map[](1,1,0,0,0,0,1,1,1,1,1,1,0,0,1) ex1(0) ex2(1)
$INVAR map[](1,0,1,0,0,1,1,0,1,1,1,1,0,1,1) ex1(0) ex2(3)
$INVAR map[](0,1,0,1,0,1,0,0,1,0,1,1,0,1,1) ex1(2) ex2(0)
$INVAR map[](0,0,1,0,0,1,1,0,0,1,0,0,1,0,0) ex1(0) ex2(1)
$INVAR map[](1,0,1,0,1,1,1,1,1,0,0,1,1,0,0) ex1(3) ex2(3)
$INVAR map[](0,1,0,1,1,1,0,1,1,0,0,0,0,1,1) ex1(1) ex2(0)
$INVAR map[](0,1,0,1,1,1,1,1,0,1,0,0,0,0,0) ex1(3) ex2(0)
$INVAR map[](0,0,0,1,0,1,1,0,1,1,1,1,1,1,0) ex1(0) ex2(0)
$INVAR map[](1,1,0,0,1,0,0,0,1,0,1,1,0,0,0) ex1(0) ex2(0)
$INVAR map[](0,0,0,1,1,0,1,0,1,0,0,1,1,0,0) ex1(2) ex2(0)
To je ena taka koda, ki dopušča samo dve izjemni števili od relacije. ex1 in ex2.
In 4 števila. Moram dat generalizirat še ...
Man muss immer generalisieren - Carl Jacobi
Thomas ::
Hehe ... not true! Počak še mau, da zagonim čez noč bolj splošno verzijo. 
Man muss immer generalisieren - Carl Jacobi
meszaj ::
Jaz sem samo hotel vedet kako se naj navaden smrtnik loti zadeve-pa je tema zajadrala v tekmovanje genijev.
Naredil sem racunanje cene konfliktov in ugotovil, da zadeva laufa dosti prepocasi, da bi za vsako "pametno" permutacijo sel racunat konflikte.
Zato prosim za nasvet kako naj naredim program brez racunanja cene konfliktov-samo s pametnimi permutacijami?
Naredil sem racunanje cene konfliktov in ugotovil, da zadeva laufa dosti prepocasi, da bi za vsako "pametno" permutacijo sel racunat konflikte.
Zato prosim za nasvet kako naj naredim program brez racunanja cene konfliktov-samo s pametnimi permutacijami?
Thomas ::
Matr si sitn!
Ravno to hočem narest. Zreducirati brute force rešitev na optimum. Sem prepričan, da mi bo uspelo, samo nisem pa prepričan da prav kmalu (jutri, pojutrišnjem), ker mamo eno nujno delo.
BUT - če se ukvarjaš s takimi nalogami, ne bodi zoprn do tistih, ki bi radi prišli do rešitve. Okay?
Ravno to hočem narest. Zreducirati brute force rešitev na optimum. Sem prepričan, da mi bo uspelo, samo nisem pa prepričan da prav kmalu (jutri, pojutrišnjem), ker mamo eno nujno delo.
BUT - če se ukvarjaš s takimi nalogami, ne bodi zoprn do tistih, ki bi radi prišli do rešitve. Okay?
Man muss immer generalisieren - Carl Jacobi
minmax ::
fantje... če je slivnik rekel 250.000 potem bo dejansko dal vsaj en primer z 250.000 ...
drugače pa... sam predlagam simulirano ohlajanje in po možnosti kak 'forward differencing', da se zmanjša čas za evaluacijo primerkov...
drugače pa... sam predlagam simulirano ohlajanje in po možnosti kak 'forward differencing', da se zmanjša čas za evaluacijo primerkov...
Sergio ::
mmx: ni rekel da jih bo 250.000, to je dejansko tudi strogo zanikal :)
btw: zakaj ne bi imel konflikte v heapu, najvisji na vrhu, vzames najvisjega, premikas za ena levo/desno, pogledas bilanco. Ce je pozitivna, zavrnes resitev, vzames naslednjega iz heapa. Ce je negativna, sprejmes resitev, popravis heap, opa cupa, naredis stvar znova.
Kaj fali tej resitvi, DMouse, Sci-Fi? Zdi se mi, da pod zahtevnost O(m^2 * n), kjer je m stevilo konfliktov, n pa stevilo elementov, ne bos prisel. IMHO.
BTW, poraba pomnilnika tukaj NI problem. Jaz osebno, meszaj, sem uporabljal array ter ne vectorja, ki ga auto-inkrementiram, ce preseze kapaciteto.
Vec pa popoldne. Danes sem ravno iz CeBita (beri: 5 dni ne-programiranja seminarske, cas se izteka), bomo popoldne poskusili cim vec narest.
Kumbaya vsem FRI UNIjevcem. Slivnika bomo pa ze preziveli, no ;-)
btw: zakaj ne bi imel konflikte v heapu, najvisji na vrhu, vzames najvisjega, premikas za ena levo/desno, pogledas bilanco. Ce je pozitivna, zavrnes resitev, vzames naslednjega iz heapa. Ce je negativna, sprejmes resitev, popravis heap, opa cupa, naredis stvar znova.
Kaj fali tej resitvi, DMouse, Sci-Fi? Zdi se mi, da pod zahtevnost O(m^2 * n), kjer je m stevilo konfliktov, n pa stevilo elementov, ne bos prisel. IMHO.
BTW, poraba pomnilnika tukaj NI problem. Jaz osebno, meszaj, sem uporabljal array ter ne vectorja, ki ga auto-inkrementiram, ce preseze kapaciteto.
Vec pa popoldne. Danes sem ravno iz CeBita (beri: 5 dni ne-programiranja seminarske, cas se izteka), bomo popoldne poskusili cim vec narest.
Kumbaya vsem FRI UNIjevcem. Slivnika bomo pa ze preziveli, no ;-)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
DMouse ::
Nič ne fali, tut jest mam zelo podobne stvari v mislih, sam mal me zajebava samo programiranje tega... kako je blo na CeBitu?
Zgodovina sprememb…
- spremenil: DMouse ()
Thomas ::
tmp2=2;
x3=3;
ex1+=1;
if (ex1<=ex2) {
if (ex1==ex2) {
ex1=1;
best[ex1]=ex1;
ex1+=1;
best[tmp2]=ex1;
goto labelcritticall9;
}
if (ex2<x3) {
best[tmp2]=ex1;
best[ex1]=ex2;
ex1=x3;
goto labelcritticall1;
}
if (ex1==tmp2) {
best[tmp2]=ex2;
ex1=1;
best[ex1]=ex1;
goto labelcritticall9;
}
}
best[tmp2]=x3;
ex1=1;
best[one]=ex1;
labelcritticall9:;
ex1+=1;
labelcritticall1:;
best[x3]=ex1;
Hja no, tole je optimizirano za 1 "iregularnost v relaciji" za 4 elemente. Sploh ni več zanke. Kateri dve števili nista v < relaciji, označujeta ex1 in ex2, ki lahko zavzameta vsak par vrednosti, tako da je ex1 manjši.
Števila so označena samo z indeksi, ker njihova vrednost je irelevantna.
Generalizacija is underway.
Man muss immer generalisieren - Carl Jacobi
Sergio ::
Ena iregularnost v relaciji ima vedno minimalno rešitev, dočim sicer stvar ni niti delna urejenost. Food4Thought.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | matematika - pomočOddelek: Šola | 3689 (2744) | lebdim |
| » | Digitalna evolucija (strani: 1 2 3 4 … 26 27 28 29 )Oddelek: Znanost in tehnologija | 73525 (23694) | pietro |
| » | HTPC WIN7 + XBMC + siolTVOddelek: Pomoč in nasveti | 1980 (1804) | Primoz78 |
| » | Matematični problemOddelek: Šola | 1619 (1138) | BCSman |
| » | Funkcija z logičnimi operaterji.... (strani: 1 2 )Oddelek: Programiranje | 5159 (4505) | CaqKa |