Vita:Mohó algoritmus

Ez a szócikk témája miatt az Informatikai műhely érdeklődési körébe tartozik.
Bátran kapcsolódj be a szerkesztésébe! Bővítendő Ez a szócikk bővítendő besorolást kapott a kidolgozottsági skálán. Nagyon fontos Ez a szócikk nagyon fontos besorolást kapott a műhely fontossági skáláján. Értékelő szerkesztő: Zafir (vita), értékelés dátuma: 2012. július 16.

Informatikai szócikkek

Wikipédia:Cikkértékelési műhely/Index

Elnevezés

Nem értek egyet a mohó algoritmus fordítással. A mohóság, és a kapzsiság a dolgok megszerzésének gyors és nem korlátozott formáját jelenti. A greedy algoritmusban nem erről van szó, hanem fukarságról. Az aprópénzek számának minimalizálása az eredmény, ahogy ezt nyilván más is láthatja, vagyis szűkmarkúságról, fukarságról. – Genezistan ^vita 2010. június 22., 10:44 (CEST)

Itt nem a célról van szó (tehát hogy a legkevesebb pénzérme legyen), hanem a módszerről, hogy az algoritmus úgy dolgozik, hogy mindig az aktuális pillanatban legjobbnak tűnő lehetőséget választja. Tehát ha a legkevesebb pénzérmét akarjuk kiválasztani, akkor ő mohó módszerrel mindig a legnagyobb érméből fog választani, ameddig csak tud, mert az tűnik a legjobb ötletnek. Egyébként a szakirodalom is "mohó algoritmusnak" nevezi (pl. a forrásként is szereplő "Introduction to Algorithms" könyv magyar fordítása is). – Hunyadym ^Vita 2010. július 2., 23:17 (CEST)

Attól, hogy a szakirodalomban hogyan van fordítva, még nem biztos, hogy jónak is nevezhető az eredmény. Függ attól, honnan nézed a kérdést. A "legjobbnak" tűnő lehetőség függvény, a legnagyobbak választása minimalizálja a darabszámot, megfordítva, a legkisebbek választása maximálja a darabszámot. Mivel itt az összeg, a visszajáró pénz ugyanaz, az értkben nem lehet maximálni, csak önhülyítéssel, csak a darabszá lehet a célfüggvény. Ez egyébként így vana sort algoritmusoknál is - először felezel, azután megint, stb. ahogy te is tudod. Például: Bejárati ajtó egy előtérben, rajta felirat: befelé nyílik. Kifelé nyílik. Attól függően, hogy kintről (az utcáról) akarsz bemenni az ajtón, vagy bentről akarsz kimenni az utcára, a felirat lehet megtévesztő is. Le is rajzolhatod, a probléma a chunking (tagolás) problémája, hol húzzuk meg egy esemény határait. Az elnevezések pedig ritkán tartoznak a logika körébe, gondolom ebben egyetértünk. Genezistan ^vita 2010. július 5., 09:24 (CEST)

Ezt mohó algoritmusnak hívják, függetlenül attól, egyetért-e ezzel mindenki vagy sem. Szvsz egyébként jól van fordítva. ♥♥♥ Gubb the Skaarj Slayer ✍ 2010. július 5., 09:45 (CEST)

Azt, hogy mit minek hívnak, azon valóban nem lehet vitatkozni. Azt, hogy valamit tükörfordítással fordítanak vagy sem - lehet vitatkozni, de csak olyanokkal, akik egy szó jelentését alaposabban megfontolják, és hajlandóak neveket adni, esetenként némi logika alapján. Se szeri se száma az agyatlan fordításnak, vagy csak az angol szóátvételnek. Mindenki olyan virtuális világban (szómágiában) él, amilyen neki tetszik, legfeljebb azt fogja találni, hogy káosz van a fejében a szavak és a jelölt valóság közti viszony tekintetében. Genezistan ^vita 2010. július 5., 10:01 (CEST)

A mohó algoritmust nem csak a pénzérmék elosztásához használják, használható például a legrövidebb út megkereséséhez is (Dijkstra-algoritmus), minimális feszítőfák előállításához. Pl. ez utóbbit úgy lehet előállítani, ha mindig a legkisebb élet választjuk ki, ami mellett a fa fa marad. Azaz itt nem arról van szó, hogy fukarok vagyunk az élekkel, hanem arról, hogy szépen sorban mindig mohó módon azt az élet választjuk ki, ami a legjobbnak tűnik az adott pillanatban. – Hunyadym ^Vita 2010. július 5., 10:46 (CEST)

A legjobb mitől mohó? – Genezistan ^vita 2010. július 5., 15:18 (CEST)

Nem a legjobbsága miatt mohó, hanem azért, mert mindig a helyi, lokális optimumot, tehát az adott pillanatban a legjobbnak tűnő megoldást választja. Tehát nem gondolkodik előre, hanem csak az aktuális helyzetet figyeli. (Amikor ott van az asztalon előtted egy süti és egy tál hús, akkor először a sütit eszed meg, mert az finomabb, de nem gondolsz bele, hogy utána már nem fogod tudni megenni a húst, és így éhes maradsz a végére. Elég béna példa, de remélem, érted a lényeget.) – Hunyadym ^Vita 2010. július 5., 15:47 (CEST)

A mohó módszer nem mindig használható, pl. a hátizsák-problémánál. Van pl. egy 50 kg kapacitású hátizsákunk, abba kell belerakni dolgokat, és minden dolognak van egy értéke és egy súlya. A feladat, hogy a lehető legnagyobb értékű dolgokat elvigyük. Ha mohó módon csináljuk, akkor mindig azt rakjuk bele, amelyiknek a legnagyobb az érték/súly hányadosa. (Mert az tűnik a leghasznosabbnak.) Ez viszont nem lesz jó, pl. ha a következő tárgyak vannak: 10 kg 60 Ft; 20 kg 100 Ft; 30 kg 120 Ft. Ekkor az érték/súly hányadosok a következők: 6 Ft/kg; 5 Ft/kg; 4 Ft/kg. Így a mohó algoritmus belerakná az első kettőt, így 30 kg és 160 Ft lenne az eredmény (a harmadik már nem fér bele a zsákba), de ennél jobb a két utolsó elhelyezése (220 Ft). (A feladat egyébként dinamikus programozással oldható meg a legegyszerűbben.) Tehát a "mohó" szó nem a végeredményre, hanem a módszerre utal. – Hunyadym ^Vita 2010. július 5., 10:46 (CEST)

A dinamikus programozás más tészta, mert ott két irányból keresed az optimumot. Genezistan ^vita 2010. július 5., 15:18 (CEST)

A dinamikus programozás tudtommal az, amikor részfeladatokra osztod a problémát, és azok eredményét tárolod, és az alapján döntesz. – Hunyadym ^Vita 2010. július 5., 15:47 (CEST)

A travelling salesman probléma inkább hasonlít, csak ellenkező előjelű? Az hogy valaki a helyi optimumot választja a globális optimum helyett, vagyis meg akar takarítani lépéseket az úton, úgy hogy mindig a legkisebb lépést tegye meg, azzal csak szaporítja lépései számát, de nem vezet a legrövidebb úthoz. Genezistan ^vita 2010. július 5., 15:18 (CEST)

Az utazóügynök-probléma nem oldható meg mohó módszerrel, de még dinamikus programozással sem, tehát mohó módszerrel nem fog helyes megoldásra jutni. – Hunyadym ^Vita 2010. július 5., 15:47 (CEST)

Szerintem itt egyszerű darabolási kérdésről van szó - egy szorzatról. Mindegy, hogy 100 forintot 10 db 10-esre vagy 2 db 50-re váltok, attól száz forint marad. Ha a módszer neve ezután a "gazdaságos", optimalizáló, és ezért a legjobb, akkor legyen. De akkor minden igyekezetünk, amelyben energiát, időt, pénzt, munkát, stb. akarunk megtakarítani, egyben mohó is, ami ugye nonszensz. De ez a rövidtávú gazdaságosság (mohóság) csak abban segít, hogy hamarabb fogyjanak el az egyébként véges erőforrások, amelyek között nagyság (mennyiség) szerint válogatsz. Genezistan ^vita 2010. július 5., 15:18 (CEST)

Ha meg nem nézzüók a pénzérmék névértékét, csak a méretét (ami arányos az értékével), akkor az észlelésünknek vagyunk kitéve, amely hamarbb veszi észre a nagyobb alakzatot, és azokról tartja lényegesnek először beszámolni, amiben nincs mohóság, csak fiziológia. Genezistan ^vita 2010. július 5., 15:18 (CEST)

Nem erről van szó, nem azért választjuk a nagyobb pénzérmét, mert azt hamarabb vesszük észre, hanem mert úgy kevesebb érmét kell felhasználni. A mohóság, vagy ahogy nevezed, "rövidtávú gazdaságosság" eredményes lesz ebben az esetben, mert így lesz a legkevesebb a pénzérme. – Hunyadym ^Vita 2010. július 5., 15:47 (CEST)

Ez a téma igazán nem érdemel meg ennyi munkát és szép külalakot, de köszönet érte. A magam részéről már mindent elmondtam, csak azt a poént tartogattam, hogy a greedy, az nem is mohó, hanem kapzsi, vagyis nem azt jelzi, hogy gyorsan hajtódik végre az algoritmus, hanem ahogy te írtad, mindig a legnagyobb falatot választva. Ez pedig a nagy étvágyra, az éhségre utal, nem pedig a dolgok sebes eltüntetésére. Egyébként pedig a magyar kifejezésnek magyarul kell jól hangzania. Nem tudom, hohy a fenti magyarázat nélkül valaki, aki először olvassa ezt a szókapcsolatot, hogyan tudna rátalálni (az angol eredeti nélkül) a kifejezés értelmére. Van mohó ember, de nem létezőnek, elképzelhetelennek, vagy képzavarnak tűnik egy algoritmust mohósággal jellemezni, főleg, hogy az algoritmust emberek írják, és az magától nem mutat emberi tulajdonságokat, ahogy a felhők, a tűz vagy az atom sem. De az is biztos, ha már vaalki egyszer leírta, az emberek hozzászoknak, és nem érdemes ennek megváltoztatásába energiát ölni. Az antropomorf és animisztikus gondolkodás újabb mélypontja - egy lexikonban. Genezistan ^vita 2010. július 5., 19:12 (CEST)