Mi az a kapzsi algoritmus?
Lehet, hogy sok algoritmikus tervezési technikáról hallott, miközben néhány cikket szitál. Néhány közülük:
- Nyers erő
- Oszd meg és uralkodj
- Kapzsi programozás
- Dinamikus programozás, hogy csak néhányat említsünk. Ebben a cikkben megtudhatja, mi a kapzsi algoritmus, és hogyan használhatja ezt a technikát sok olyan programozási probléma megoldására, amelyek egyébként nem tűnnek triviálisnak.
Képzelje el, hogy túrázni indul, és célja a lehető legmagasabb csúcs elérése. A térkép már meg van, mielőtt elkezdené, de a térképen több ezer lehetséges út látható. Túl lusta vagy, és egyszerűen nincs időd mindegyiket értékelni. Csavarja be a térképet! Egyszerű stratégiával kezdett túrázni - legyen mohó és rövidlátó. Csak haladjon olyan utakon, amelyek a legnagyobb mértékben emelkednek. Ez jó stratégiának tűnik a túrázás terén. De vajon mindig a legjobb?
Miután az utazás véget ért, és az egész tested fáj és fáradt, először megnézed a túrázási térképet. Istenem! Van egy sáros folyó, amin át kellett volna mennem, ahelyett, hogy folyamatosan felfelé sétáltam volna. Ez azt jelenti, hogy a kapzsi algoritmus a legjobb azonnali választást választja, és soha nem gondolja felül a döntéseit. A megoldás optimalizálása szempontjából ez egyszerűen azt jelenti, hogy a kapzsi megoldás megpróbálja megtalálni a helyi optimális megoldásokat - amelyek sokfélék lehetnek -, és elmaradhat egy globális optimális megoldástól.
Formális meghatározás
Tegyük fel, hogy van egy célfüggvénye, amelyet optimalizálni (maximalizálni vagy minimalizálni kell) egy adott ponton. A kapzsi algoritmus minden lépésnél kapzsi döntéseket hoz, hogy biztosítsa a célfüggvény optimalizálását. A Kapzsi algoritmusnak csak egy lövése van az optimális megoldás kiszámításához, így soha nem megy vissza és nem változtatja meg a döntést.
A kapzsi algoritmusoknak vannak előnyei és hátrányai:
- Nagyon könnyű kapzsi algoritmust (vagy akár több kapzsi algoritmust) előállítani egy problémára. A kapzsi algoritmusok futtatási idejének elemzése általában sokkal könnyebb lesz, mint más technikák (például a Divide and Conquer) esetében. A Divide and Conquer technika esetében nem világos, hogy a technika gyors vagy lassú-e. Ez azért van, mert a rekurzió minden szintjén a méret kisebb és az alproblémák száma növekszik.
- A nehéz rész az, hogy a kapzsi algoritmusokért sokkal többet kell dolgoznia a helyesség kérdéseinek megértésében. Még a helyes algoritmus mellett is nehéz bizonyítani, miért helyes. A kapzsi algoritmus helyességének bizonyítása inkább művészet, mint tudomány. Sok kreativitással jár. Általában egy algoritmus előállítása triviálisnak tűnhet, de annak bizonyítása, hogy valóban helyes, egészen más probléma.
Intervallumütemezési probléma
Merüljünk el egy érdekes problémában, amellyel szinte bármely iparágban vagy az élet bármely területén találkozhat. A probléma néhány esete a következő:
- N előadássorozatot kap egy napra az egyetemen. Egy adott előadás ütemezése olyan formában van (s idő, f idő), ahol s idő az adott előadás kezdési idejét, és hasonlóan az f idő jelenti a befejezés időpontját. Adva egy N előadási ütemtervet, ki kell választanunk a nap folyamán tartandó előadások maximális sorozatát úgy, hogy egyik előadás ne fedje át egymást, azaz ha az Li és Lj előadás szerepel a kiválasztásunkban, akkor > = i befejezési ideje vagy fordítva .
- A barátod tábori tanácsadóként dolgozik, és ő felel a táborlakók tevékenységeinek megszervezéséért. Az egyik terve a következő mini-triatlon gyakorlat: minden versenyzőnek 20 kört meg kell úsznia a medencéből, majd 10 mérföldet kell kerékpároznia, majd 3 mérföldet kell futnia.
- A tervek szerint a versenyzőket szakaszosan küldik ki a következő szabály alapján: a versenyzőknek egyenként kell használniuk a medencét. Más szavakkal, az első versenyző úszik a 20 kört, kiszáll és biciklizni kezd.
- Amint ez az első személy kijön a medencéből, egy második versenyző megkezdi a 20 kör úszását; amint kint van és elkezd biciklizni, egy harmadik versenyző úszni kezd stb.
- Minden versenyzőnek van egy tervezett úszási ideje, egy tervezett kerékpáros ideje és egy tervezett futási ideje. A barátod el akarja dönteni a triatlon menetrendjét: egy sorrendet a versenyzők rajtjának sorrendjéhez.
- Tegyük fel, hogy az ütemterv teljesítési ideje az a legkorábbi időpont, amikor az összes versenyző a triatlon mindhárom szakaszával végez, feltéve, hogy az időjelzések pontosak. Mi a legjobb megrendelés az emberek kiküldésére, ha valaki azt akarja, hogy az egész verseny minél hamarabb lezáruljon? Pontosabban, adjon meg egy hatékony algoritmust, amely olyan ütemtervet állít elő, amelynek teljesítési ideje a lehető legkisebb
Az előadás ütemezésének problémája
Nézzük meg a probléma megoldásának különféle megközelítéseit.
Először a legkorábbi kezdési idő, azaz válassza ki azt az intervallumot, amely a legkorábbi kezdési idővel rendelkezik. Vessen egy pillantást a következő példára, amely megtöri ezt a megoldást. Ez a megoldás kudarcot vallott, mert lehet, hogy nagyon korán kezdődik egy intervallum, de ez nagyon hosszú. Ez azt jelenti, hogy a következő stratégiát kipróbálhatnánk, ahol először kisebb időközönként nézzük meg.
Először a legkisebb intervallum, azaz végül az előadásokat az intervallumuk sorrendjében választja ki, ami nem más, mint az övék finish time - start time. Ez a megoldás megint nem helyes. Nézze meg a következő esetet.
Jól látható, hogy a legrövidebb intervallumú előadás a középső, de ez itt nem az optimális megoldás. Nézzünk meg egy másik megoldást erre a problémára, és nyerjünk betekintést ebbe a megoldásba.
Először a legkevésbé ütköző időköz, azaz olyan időközöket kell megnéznie, amelyek a legkevesebb konfliktust okozják. Ismét van egy példa, ahol ez a megközelítés nem talál optimális megoldást.
A diagram azt mutatja, hogy a legkevésbé zavaró intervallum a közepén található, mindössze 2 konfliktussal. Ezután csak a legvégén választhatjuk ki a két intervallumot, egyenként 3 konfliktussal. De az optimális megoldás a 4 intervallum kiválasztása a legfelső szinten.
A legkorábbi befejezési idő először . Ez az a megközelítés, amely mindig a legoptimálisabb megoldást nyújtja számunkra erre a problémára. Nagyon sok betekintést nyertünk a korábbi megközelítésekből, és végül rátaláltunk erre a megközelítésre. Az intervallumokat a befejezési idejük növekvő sorrendje szerint rendezzük, majd a kezdetektől kezdjük kiválasztani az intervallumokat. A nagyobb áttekinthetőség érdekében nézze meg a következő álkódot.
function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end Mikor használjuk a Kapzsi algoritmusokat
A kapzsi algoritmusok segíthetnek megoldások megtalálásában sok, látszólag nehéz problémára. Az egyetlen probléma velük az, hogy elképzelhető, hogy a megfelelő megoldással áll elő, de nem biztos, hogy ellenőrizni tudja a helyes megoldást. Az összes kapzsi probléma közös tulajdonsága, hogy egy helyi optima végül globális minimumokhoz vezethet anélkül, hogy átgondolná a már megfontolt választási halmazot.
A kapzsi algoritmusok sokféle probléma megoldásában segítenek, például: