Mantkārīgie algoritmi – Greedy algorithms

Šajā rakstā jūs uzzināsiet, kā ieviest šo paradigmu, lai atrisinātu sarežģītas problēmas, izmantojot “Mantkārīgus algoritmus”.

Ir filozofisks princips, ko sauc par Okama “bārdas nazis”. Tajā teikts: “Vienkāršākām teorijām, ja tās atbilst empīriskiem novērojumiem, salīdzinājumā ar sarežģītākām, ir dodama priekšroka.” Šis problēmu risināšanas princips apgalvo, ka vienkāršība ir labāka par sarežģītību.

Mūsu gadījumā mantkārīgais algoritms ir vienkāršs risinājums. Šī ir alternatīva pieeja dinamiskai programmēšanai, jo šīs pieejas mērķis ir piedāvāt tūlītēju uzdevuma risinājumu un dod priekšroku vietējai optimizācijai, nevis holistiskākai globālai pieejai. Iesaistoties ar problēmu, kas sadalīta segmentos, izmantojot dinamiskās programmēšanas pieeju, tiktu atrasts globāli optimāls risinājums, lai katra apakšproblēma tiktu atrisināta un izvēlēta ,un ieviesta labākā apakškopa.

Mantkārīga pieeja aplūkotu risinājumu sarakstu un ieviestu lokālu optimizāciju. Parasti tiek izvēlēta pašreizējā visizdevīgākā iespēja.

Lai to padarītu skaidrāku, ņemsim CPU piemēru, kuram ir veicamo uzdevumu saraksts.

Dinamiskās programmēšanas pieejas izmantošana nozīmētu darbību apakškopas atlasi, ko varētu pabeigt noteiktā laikā, un veikt šos uzdevumus. Izmantojot mugursomas analoģiju, tas nozīmētu, ka ir jānosaka, kuru priekšmetu apakškopu iesaiņot, lai palielinātu vērtību maisa piepildīšanas procesā. Mantkārīga algoritma pieeja tam vienmēr būtu izvēlēties vērtīgāko priekšmetu un ievietot to somā, nedomājot par to, kādus citus priekšmetus tas izslēgtu no procesa. Tādējādi mūsu CPU piemērā mantkārīga pieeja nozīmētu, ka vispirms jāizvēlas īsākā programma, pēc tam nākamā īsākā programma un tā tālāk. Lai gan tas var nenovest pie globāli optimizēta risinājuma, tas samazinās pieskaitāmās izmaksas, aprēķinot visefektīvāko vienumu apakškopu. Lai labāk saprastu, kā šīs divas pieejas atšķiras, apskatīsim īsākā ceļa problēmu.

Attēlā parādīta karte ar deviņiem dažādiem mezgliem — A, B, C, D, E, F, G, H un S. Katrs mezgls ir savienots ar citu mezglu ar svērtu ceļu. Šis svars atspoguļo izmaksas, kas rastos, izvēloties šo ceļu.

Tādējādi mūsu CPU piemērā mantkārīga pieeja nozīmētu, ka vispirms jāizvēlas īsākā programma, pēc tam nākamā īsākā programma un tā tālāk. Lai gan tas var nenovest pie globāli optimizēta risinājuma, tas samazinās pieskaitāmās izmaksas, aprēķinot visefektīvāko vienumu apakškopu. Tagad jums ir jādodas ceļā no E uz F pēc iespējas izveidojot visefektīvāko maršrutu. Dinamiskā programmēšanas pieeja ietvertu tabulas izveidi un katra potenciālā mezgla aprēķināšanu no E. No turienes tā ieviestu nākamo mezglu kopu un aprēķinātu uzkrātās izmaksas. Šāda pieeja neapšaubāmi nonāktu pie visefektīvākā risinājuma.

Izmantojot iegaumēšanu pēc sākotnējo aprēķinu veikšanas, tie tiktu saglabāti, un turpmākie braucieni gūtu labumu no ātrāka aprēķinātā laika. Tā ir augšupēja globāla pieeja problēmai. Mantkārīga pieeja atšķirtos savā metodoloģijā. Tā vietā, lai mēģinātu atrast optimālu savienoto maršrutu apakškopu, tas sāktos mezglā E un apskatītu katru pieejamo savienojumu. Tādējādi tajā būtu atlasīti svari, proti, 5, 3, 2, 4 un 12, kas atbilst mezglam C, B, D, G un H.

Zemākā vērtība šajā masīvā ir 2, kas atbilst mezglam D. mantkārīgs princips, tas veiktu šo atlasi un virzītos uz nākamo mezglu. Pieņemot, ka datu struktūra bija virzīts grafiks, tas tiktu parādīts ar vēl trim mezgliem A, F un G, kuru vērtības ir attiecīgi 7, 5 un 6. Tā kā F ir galīgā atrašanās vieta, tas izvēlētos F un laimīgi nonāktu galamērķī, sakrājot kopējo sodu 7 par brauciena laiku no E uz D un pēc tam uz F, kura svars ir 2 + 5. Vizuāli var redzēt ka šī ir visefektīvākā pieeja, un tā radās, neveidojot izsmeļošu kombināciju tabulu un neaprēķinot visus maršrutus. Tomēr, ja mezglam starp G un F būtu sods 2, tas būtu izvēlējies mazāk optimālu risinājumu. Tas ir kompromiss, izvēloties mantkārīgu, nevis dinamisku pieeju. Lai gan mantkārīga algoritma pieskaitāmās izmaksas ir zemas un risinājuma kodēšana ir diezgan vienkārša, tas ne vienmēr garantēs labākās iespējas atgriešanu.

Tagad jums ir labāka izpratne par mantkārīgā algoritma pieeju. Turklāt jūs redzējāt, kā tas ir salīdzināms ar dinamisko risinājumu, un tādējādi padziļinājāt jūsu izpratni par šīs alternatīvās pieejas stiprajām un vājajām pusēm. Nākamreiz, kad plānojat maršrutu Google Maps, apsveriet piedāvāto maršrutu izvēli un padomājiet par to, kā šīs saknes varētu būt aprēķinātas.