Kombinatorikos algoritmai: nedvišalė personalo užduotis

Turime lakūnų uždavinį, tai nėra tik lakūnų uždavinys, šis uždavinys yra kaip stereotipinis tokio tipo uždavinių sprendimo modelis. galime paminėti tokio pat tipo uždavinius: kambario kaimynų grupavimas į kambarius, ir kiti, kuriuose naudojamas nedvišalio grupavimo principas. Uždaviniui išspręsti naudosime grafų algoritmus. Kodėl? Todėl, kad tai yra patogiausias šio tipo uždavinių sprendimo metodas. Taigi, šiame darbe parodysime, kaip suporuosime lakūnus, kalbančius įvairiomis kalbomis ir mokančius skraidyti tam tikrais lėktuvais. Paprastumo dėlei neįtrauksime į uždavinį kokio nors pasirengimo rodiklio.
Per antrąjį pasaulinį karą, Karališkosios Didžiosios Britanijos Oro Pajėgos (KDBOP) turėjo daug pilotų iš skirtingų valstybių, kurie kalbėjo skirtingomis kalbomis ir mokėjo skraidyti įvairiais lėktuvais. KDBOP turėjo vienam lėktuvui priskirti du pilotus, kurie būtų suderinamomis kalbomis (tarkim, kad suderinama kalba yra ta pati kalba.) ir mokantys skraidyti tais pačiais lėktuvais. KDBOP norėjo, kad būtų kuo daugiau skraidomų lėktuvų, kadangi kare paprastai lėktuvų yra daug, o mokančių jais skraidyti mažai, tai iškilo toks klausimas, kaip suporuoti kuo daugiau pilotų, galinčių skraidyti tais pačiais lėktuvais.
Kad suformuluotume šią problemą, kaip atitinkamą uždavinį, mes apibrėžiame grafą G = (N, A), čia N – mazgų skaičius, o A – briaunų skaičius. Grafo mazgai atstovauja pilotus ir sujungiame mazgus lanku, jei atstovaujami pilotai yra „suderinami“. Visa tai daroma automatiškai c++ parašytoje programoje. Visa tai atliekama, remiantis nedvišalio poravimo algoritmu, (angl. „Nonbipartite Perssonel Assignment“).
Uždavinys įgauna sudėtingumo tuomet, kada reikia išnagrinėti žiedo problemą:
1. Paveikslėlis
Pirmame paveikslėlyje matome dvi gėles (angl. Flower), sudarytas iš subgrafo kurio komponentai yra: žiedas ir kotas (angl. Stem).
Žiedas (angl. Blossom) – tai yra nelyginį mazgų skaičių turintis alternatyvusis ciklas, kuris prasideda ir baigiasi tam tikrame galiniame koto taške w, ir neturi kito bendro su kotu mazgo. Pavadinkime šį mazgą „žiedo baze“.
Mūsų sprendžiamame uždavinyje susiduriame tik su žiedo problema.
Pagrindinis šio uždavinio sprendimo algoritmas yra toks:
Paaiškinimas:
1. Algoritmas pradeda darbą.
2. Sprendiniui M suteikiamas tuščios aibės statusas.
3. Kiekvienam mazgui p, priklausančiam aibei N,...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!