fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Számítástechnika » Programozás » Milyen algoritmussal lehetne...

Milyen algoritmussal lehetne a leghatékonyabban megoldani a következő problémát?

Figyelt kérdés
Ha van nekem 500 darab számhármasom (pl: { {1: x=20, y=50, z=30 }, {2: x=80, y=40, z=20} ... {500: x= 44, y= 11, z= 99}} és én megadok egy számhármast (pl: {x= 210, y= 300, z=180}) akkor megtalálni azt a kombinációját (ismétléssel és anélkül is) az 500 számhármasomnak, amelyben a számok x y és z helyen álló számok összege a kívánt értékhez a legközelebbi? Tehát a fenti példában olyan számhármasokat keresk ahol az x-ek összege 210 az y-ok összege 300, a Z-k összege 180. Ha ilyen nincs akkor a legközelebbit megtalálni.

#kombináció #algoritmus
2023. jan. 19. 20:34
❮ 1 2 3 ❯
 11/25 anonim ***** válasza:
Legenerálás nyilván nem lesz gyors. Ez szükséges rossz. Majd, ezután lesz gyors az inputra, mert már a meglévő (az előfeldolgozás során létrejött) tudástárból tud dolgozni.
2023. jan. 19. 22:35
Hasznos számodra ez a válasz?
 12/25 anonim ***** válasza:

De, hogy ezeket a pontokat hol tárolod, hogy ne keljen megismételni, az már ízlés kérdése.


Tehát ezt 1x kell megcsinálni és máris nem igaz a köbös ordó. :) A tárigénye meg nagy lesz.


Vagy csinálsz kis tárigényűt hosszú futás idővel. Dönsd el.

2023. jan. 19. 22:41
Hasznos számodra ez a válasz?
 13/25 anonim ***** válasza:

Nem is jól, becsültem nem is ordó köbös lesz, ez sokkal rosszabb.

Mivel konkrét limit meg van adva 500 esetén ennyi összegzést kell csinálni, a binomial a binomiális együtthatókat jelenti:

binomial(500,5) + binomial(500,4) + binomial(500,3) + binomial(500,2) = 255 244 687 600 .

Még lehet hogy ennél is több, este van már ezt végig gondolni.

Viszont ebben stimmel hogy binomial(500,5) féle képpen lehet 500 objektumból 5-öt kiválasztani, binomial(500,4) féle képpen lehet 500 objektumból 4-et kiválasztani ... és így tovább.

2023. jan. 19. 22:53
Hasznos számodra ez a válasz?
 14/25 anonim ***** válasza:
Rossz értéket másoltam be a 255 244 687 600 csak a binomial(500,5), binomial(500,5) + binomial(500,4) + binomial(500,3) + binomial(500,2) = 257 838 551 975.
2023. jan. 19. 22:56
Hasznos számodra ez a válasz?
 15/25 anonim ***** válasza:

Igen erre én is gondoltam. Csak mondjál jobbat. Meg még tán ott van a párhuzamosítás.


De, ha ennyire benne vagy az ordóban, akkor találj polinom idejű algoritmust a SAT3 problémára. :)

2023. jan. 19. 22:58
Hasznos számodra ez a válasz?
 16/25 anonim ***** válasza:

A párhuzamosítás nem játszik, lényegében ugyanolyan lassú attól még. O(a) = O(a/c).

Van közelítő módszer, nem pont erre írja, de erre is kell lennie : [link]


Volt valami olyan közelítő algoritmus ami legrosszabb esetben is 2x rosszabb mint az optimális, de cserébe polinom idejű. Már rég volt az egyetemen, nem találom már melyik volt az.

2023. jan. 19. 23:32
Hasznos számodra ez a válasz?
 17/25 A kérdező kommentje:
Köszönöm a válaszokat, mentek a zöld pipák :) Igen sajnos ha előre legenerálom a lehetőségeket az borzasztóan sok kombináció, tehát ez már tárolásbeli kérdés. A másik pedig hogy lassú lesz. Esetleg valamilyen köztes megoldás még közbejöhet, hogy csak bizonyos mértékig tárolom el a kombinációkat, hogy az algoritmus futást megtámogassam.
2023. jan. 20. 08:59
 18/25 anonim ***** válasza:

#17

Ha tényleg max 500 lehet, akkor nincs értelme optimalizálgatni 2023-ban, mert gyorsan kiszámolja még egy gyenge gép is.


Ha fontos lenne mégis valamit kitalálni, akkor este szívesen segítek munka után, mert nagyon érdekes problémának találom:) meg van egy matek bsc-m proginfó mellett, szóval csak kitalálunk valamit majd:D és tényleg nagy pacsi, mert legalábbis számomra ez egy nagyon érdekes probléma, amit nem tűnik triviálisnak optimalizálni.

2023. jan. 20. 11:24
Hasznos számodra ez a válasz?
 19/25 A kérdező kommentje:
Köszönöm, szívesen veszem. A jelenlegi megközelítés itt az, hogy random kiválasztok egyet az 500-ból, ismételgetem addig amíg még nem lépi át a paraméterben megadott limitet, aztán keresek egy olyan másik számhármast, ami még nem lépi át a limitet és azzal is megismétlem. És így tovább amíg még van olyan számhármasom ami felhasználható. Sajnos így nagyon pontatlan eredményeket ad az algoritmus, még akkor is ha többször ráfuttatom hogy optimálisabbat találjon.
2023. jan. 20. 13:38
 20/25 anonim ***** válasza:

"Ha tényleg max 500 lehet, akkor nincs értelme optimalizálgatni 2023-ban, mert gyorsan kiszámolja még egy gyenge gép is."


Mint ahogy tegnap írtam látszik, hogy százmilliárdos nagyságrendű a műveletigénye. Ténylegesen valamilyen konstansfaktorosszor több lesz. Ez konkrétan órákba is telhet. Bár nem tudom mit értesz az alatt, hogy mi az a gyors, mivel nem egy egzakt fogalom hogy gyors.


"Ha fontos lenne mégis valamit kitalálni, akkor este szívesen segítek munka után, mert nagyon érdekes problémának találom:) meg van egy matek bsc-m proginfó mellett"[...]


Te ezek szerint akkor jobban benne vagy mint én, mert én már régen tanultam és nem foglalkoztam aztán vele.


[...]"a számok x y és z helyen álló számok összege a kívánt értékhez a legközelebbi?"

Érdekes módon ezt senki nem jegyezte meg : Milyen metrika szerint? Azaz milyen távolságfüggvény szerint? 3 dimenziós térben értelmezett Euklideszi távolság szerint? Vagy ( abs(x) , abs(y) , abs(z) ) számhármas lexikografikus rendezési relációja szerint? Vagy ... ?

2023. jan. 20. 16:46
Hasznos számodra ez a válasz?
❮ 1 2 3 ❯

További kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »




Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!