Aktív témák

• #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]

Aktív témák