Aktív témák

• #14 khalox őstag Spyx #13

  2004-10-22 17:39:40 #14

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  khalox

  őstag

  válasz Spyx #13 üzenetére

  Igaz, akkor branch&bound... (korlátozás és szétválasztás, vagy hogy a frászba hívják magyarul - lehet, hogy sehogyse hívják).
  
  [Szerkesztve]

• #12 khalox őstag Spyx #11

  2004-10-22 13:36:15 #12

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  khalox

  őstag

  válasz Spyx #11 üzenetére

  Ilyet keress, hogy 'mohó algoritmus', na az kell neked.

• #10 heihachi addikt Spyx #3

  2004-10-22 12:57:43 #10

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  heihachi

  addikt

  válasz Spyx #3 üzenetére

  Én ezt nem értem. Jó kis feladatnak tűnik, de nem értem.
  Van három érték:
  1 - futási idő
  2 - ????
  3 - hasznosság
  
  Az ok, hogy maximális legyen a hasznosság, de mennyi futási időnk van?

• #9 Miracle senior tag Spyx #8

  2004-10-22 01:17:46 #9

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  válasz Spyx #8 üzenetére

  ha nem ment fölösbe' akkor szívesen, örültem, hogy segíthettem :)
  szerk: és kíváncsi vagyok a te megoldásod eredményére, meg az algoritmusoda. Persze csak ha nem titkos.
  
  [Szerkesztve]

• #6 Miracle senior tag Spyx #5

  2004-10-22 00:19:17 #6

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Miracle

  senior tag

  válasz Spyx #5 üzenetére

  ez egy elég komoly játékelméleti probléma, nem foglalkoztam vele komolyan, csak olvastam valahol, és nem vagyok a dolgomban biztos, de úgy emlékszem, hogy az ilyen problémákra csak az összes eset végigpróbálgatása után lehet _tökéletes_ megoldást adni, de vannak megoldási stratégiák, amelyek nem adnak tökéletes megoldás, de az esetek nagyrészében jó megoldát adnak. sajnos nem emlékszem, hogy hol olvastam, de még egy problémára is emlékszem, ami ilyesmi volt, és a szerző 4 algoritmusra is adott olyan bemenetet, amivel nem a legjobb eredményt hozta ki. bár nem ugyan ez a probléma volt.
  szóval nekem lenne egy ötletem egy egy lehetséges algoritmusra, ami nem tudom, mennyire hatékony, Cben szerintem meg lehet oldani, és azt sem tudom, helyes-e, azaz mennyire ad jó megoldást, az a gyanúm, hogy megfelelő bemenetel meg leht sz*patni, de általános esetben szerintem nem olyan rossz eredményt ad:
  1: eltárolod a bemenetet egy szép nagy structokból álló tömbben, és kiszámítod a fajlagos haszon-arányát mindnek, (haszno/végrehajtási idő) rendezed
  2: fentről elindulsz lefelé, mindent úgy illesztesz be(az idő-tömbödbe, amiben nyilvántartod, hogy melyik időegységek foglaltak, és melyik task van ott), hogy éppen a határidejére érjen véget.
  3: ha amit be akarsz szúrni, és valahol ütközik, akkor agy rekurzív algoritmus megpróbál helyet csinálni neki, azaz
  ----ha a a végrehajtási idő jobb oldalán ütközik, akkor balra tolja, hogy beférjen,
  ----ha a végrehajtási idő a bal oldalán ütközik, akkor a már ott lévőt tolja balra, hogy ne ütközön,
  ----ha elfed egy másikat, akkor a másikat megpróbálja balra tolni
  ----ha egy már ott lévő teljesen elfedi, akkor az új elemet próbálod meg balra tolni
  ----ha több elemmel ütközik, akkor
  a: hagyod a francba
  b: megpróbálod balra tolni azokat, amik ütköznek, ha van közöttük
  időrés, ha nincs, akkor az új elemet próbálod
  meg balra tolni
  szerk: vége, ha végigment a fajlagosan rendezett bemeneten.
  szerk: a balra tolás az időben előbbre helyezést akarja jenenteni, vizuális típus vagyok, egyből elképzeltem.
  
  a különböző eltolásokat ugyan ez a beszúrófüggvény intézi, így ha a beillesztés miatti eltolás ütközést okoz, akkor értelem szerűn az először eltolt elemnek is megpróbál helyet csinálni a fent említett módon, kell viszont egy rekurzió-szint korlát, mondjuk hogy max 5ször hívhatja meg magát, ezt egyszerű beépíteni, és visszatérési értékben szépen benne lehet, hogy sikerült-e a beszúrás, és ha igen, akkor a tömb marad, ahogy van, ha nem, akkor a rekurzió minden szintje visszarendezi, amit eltologatot, és visszatér egy hamis értékkel.
  
  na ez egy kicsit bonyolult.
  eszembe jutott mégegy:
  egy parciálisan rekurzív függvény ami ha X időig rendezve vagyunk, akkor megnézi, mely taskok járnak le a legközelebb, és megpróbál z időnyit (vagy k tasknyit) előre feltölteni, ezen a z időn belül kipróbál minden lehetséges esetet, és a legjobbnak az _első_ elemét teszi bele a végeredménybe, majd megin megpróbál az utóbb betett task lejártától előrelátni.
  az utóbbit szerintem sokkal egyszerűbb lekódolni, de az előbbi megérzésem szerint jobb eredményt ad. bár sokkal nehezebb.
  persze lehet, hogy van tökéletes hatékony megoldóalgoritmus is, de azzal én nem szolgálhatok, ha nem sikerül olyat találni, akkor remélem segítettem valamit ezzel a két lehetőséggel.
  
  
  
  [Szerkesztve]

• #2 steveetm őstag Spyx #1

  2004-10-21 23:02:06 #2

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  steveetm

  őstag

  válasz Spyx #1 üzenetére

  Az előző topic erre miért is nem volt jó?
  
  Ha meg tudod valósítani akkor mi a gond?
  
  És a feladat se tiszta, mivan ha nem jut sorra az adott feladat amire be kell fejezni?
  
  Mit kell kiiratni? Az ok hogy amit végrehajtunk, de egy ütemező végrehajt mindent, csak ütemezi őket ugyebár. Nem inkább végrehajtás sorrendje akar ez lenni?
  
  A futási idő-t hogy kell értelmezni? Ha egyszer nekikezdesz a feladatnak az az idő egybe telik el, vagy csak egy ''ütem'' vonódik le?
  
  Üdv.: steveetm

Aktív témák