Úloha z Algoritmov a dátových štruktúr II

Je to už nejaká tá chvíľa, čo som sa ozval. Ťažko povedať, prečo. Možno preto, že som nemal veľmi o čom písať. Alebo preto, že aj keď som konečne mal o čom, nemal som kedy. Alebo možno kvôli niečomu úplne inému. V každom prípade dnes mám o čom aj kedy. 🙂

 

Pred pár týždňami (pravdu povediac sú to už skoro dva mesiace) sme dostali na ADS II úlohu. Vyriešenie tejto úlohy bol jeden z požiadaviek na udelenie zápočtu a asi si viete celkom dobre predstaviť, že ani na prvý pohľad nepôsobila nijak jednoducho.

 

Zadanie bolo v celku jednoduché – na prednáške sme prebrali algoritmy na hľadanie tokov v sieťach (Dinicov a Golbergov algoritmus). Tiež sme sa dozvedeli, že toky v sieťach sa dajú jednoducho previesť na problém hľadania maximálneho párovania v bipartitnom grafe. A úloha znela (nečakane 😉 ) implementovať nejaký algoritmus na hľadanie maximálneho párovania.

 

A to ešte stále nebolo všetko. Vypracované programy vyhodnocoval automatický systém na desiatich zadaniach s narastajúcou zložitosťou. A výpočet mal prebehnúť v stanovenom časovom limite. To by zase až tak nevadilo, keby limit nebol nastavený tak tesne. A za funkčné sa považovalo také riešenie, ktoré správne a v stanovenom čase spočítalo aspoň 9 z 10 zadaní.

 

Úloha to bola naozaj zložitá a aj napriek tomu, že poznámky z Dinicovho algoritmu som mal relatívne presné, nepodarilo sa mi ho implementovať bez pomoci. Nakoniec som musel požiadať o konzultáciu nášho cvičiaceho. Po tejto konzultácii (ktorá bola mimochodom naozaj prínosná) som už nemal veľké problémy a o dva dni už som mal v ruke riešenie, ktoré vracalo správny výsledok.

 

Problém bol v tom, že môj program potreboval na výpočet obrovské množstvo času (na najzložitejšie zadanie potreboval až 33 sekúnd). A tak sa začala fáza optimalizácie. A to tiež nie je také jednoduché, ako sa zdá. Po ďalšom dni sa mi nakoniec podarilo čas potrebný na posledné zadanie skresať až na 3,2 sekundy, čo bol naozaj skvelý výsledok. Po nejakom čase strávenom optimalizáciu výpisu výsledku môžem povedať, že som úlohu splnil a vyhodnocovací systém mi udelil 90 zo 100 možných bodov (tento systém beží na pomalšom počítači a tak posledné zadanie neprešlo v časovom limite).

 

A keď už som strávil toľko času s jedným algoritmom, rozhodol som sa, že ho zverejním. Pre záujemcov, ako aj pre tých, ktorí možno študujú rovnakú školu ako ja a možno dostanú rovnakú (alebo podobnú) úlohu v budúcnosti.

 

Najprv ale celkové zadanie úlohy:

Na parketě se sešli tanečníci a tanečnice. Každý je ovšem ochoten tancovat pouze s některými účastníky opačného pohlaví. Navrhněte tanečníkům co nejvíc párů, které vyhovyjí jejich požadavkům. Každý smí být pochopitelně nanejvýš v jednom páru.

Popis vstupu: Na standardním vstupu dostanete neorientovaný bipartitní graf. Na první řádce standardního vstupu je N ≤ 100000 – počet vrcholů bipartitního grafu. Následuje N řádek. Na i-tém z nich jsou sousedi vrcholu i ve formátu počet_sousedů soused_1 soused_2 … Vrcholy jsou číslovány od 1 do N a každý graf obsahuje nejvýš 200000 hran. Graf je neorientovaný, tedy je-li vrchol u sousedem vrcholu v, tak i vrchol v je sousedem vrcholu u.

Popis výstupu: Na standardní výstup vypište nalezené maximální párování. Na první řádek standardního výstupu vypište velikost párování. Na následujících řádkách popište libovolné korektní párování této velikosti, vždy jedna mezerou oddělená dvojice čísel (vrcholů) na řádku.

 

A tu je samotný zdrojový kód riešenia. Kvôli lepšej prehľadnosti som sa rozhodol uviesť tu neokomentovanú verziu. Okomentovanú verziu si môžete stiahnuť spolu s vzorovými vstupmi a výstupmi pod týmto kódom. Aby bolo jasné, kód je v jazyku C#, použitá verzia .NET Framework je 2.0 (funguje aj na 3.5). Kód je preložiteľný pod Visual Studiom 2005 a vyšším aj GMCS.

 

using System;
using System.Collections.Generic;
using System.Text;

namespace MaxMatchFinal
{
    class Program
    {
        static Vertex[] partA;
        static Vertex[] vertices;
        static List<Vertex> MatchedAVertices = new List<Vertex>();
        static List<Vertex> UnmatchedAVertices = new List<Vertex>();

        static Queue<Vertex> BFSCue = new Queue<Vertex>();
        static Queue<Vertex> BFSCueBackup = new Queue<Vertex>();

        static void Main(string[] args)
        {
            int N = Int32.Parse(Console.ReadLine());
            vertices = new Vertex[N + 1];
            partA = new Vertex[N + 1];

            Initialize(N);

            int faza = 1;
            int d = BFS(faza);
            while (d != -1)
            {
                for (int i = 0; i < UnmatchedAVertices.Count; i++)
                {
                    if (DFS(UnmatchedAVertices[i], d))
                    {
                        MatchedAVertices.Add(UnmatchedAVertices[i]);
                        UnmatchedAVertices.RemoveAt(i);
                        i--;
                    }
                }
                faza++;
                d = BFS(faza);
            }

            Print();

            Console.ReadLine();
        }

        static void Print()
        {
            StringBuilder sb = new StringBuilder();
            sb.AppendLine(MatchedAVertices.Count.ToString());
            foreach (Vertex v in MatchedAVertices)
            {
                sb.Append(v.Index);
                sb.Append(' ');
                sb.Append(v.Pair);
                sb.Append('\n');
            }
            Console.Write(sb.ToString());
        }

        static void Initialize(int count)
        {
            int index = 1;

            while (index <= count)
            {
                Vertex v = new Vertex(index);
                v.Distance = -1;
                int ncount = CodEx.Reader.Console().Int();
                for (int j = 0; j < ncount; j++)
                {
                    v.Neighbours.Add(CodEx.Reader.Console().Int());
                }
                vertices[index] = v;
                index++;
            }

            Queue<int> vertexcue;

            foreach (Vertex ve in vertices)
            {
                if (ve != null && !ve.IsPartitySet)
                {
                    vertexcue = new Queue<int>();

                    vertexcue.Enqueue(ve.Index);
                    ve.IsPartityA = true;
                    ve.FazaInit++;

                    while (vertexcue.Count > 0)
                    {
                        Vertex u = vertices[vertexcue.Dequeue()];

                        if (u.IsPartityA)
                        {
                            partA[u.Index] = u;
                        }

                        foreach (int h in u.Neighbours)
                        {
                            if (vertices[h].FazaInit < 1)
                            {
                                vertexcue.Enqueue(h);
                                vertices[h].IsPartityA = !u.IsPartityA;
                                vertices[h].FazaInit++;
                            }
                        }
                    }
                }
            }

            foreach (Vertex v in partA)
            {
                if (v != null)
                    UnmatchedAVertices.Add(v);
            }
        }

        static int BFS(int F)
        {
            int shortest = -1;

            bool partity = false;
            bool foundinpartity = false;

            foreach (Vertex a in UnmatchedAVertices)
            {
                BFSCue.Enqueue(a);
                a.FazaBFS = F;
                a.Distance = 0;
            }

            while (BFSCue.Count > 0)
            {
                Vertex v = BFSCue.Dequeue();
                int d = v.Distance;

                if (v.FazaBFS == F)
                {
                    partity = v.IsPartityA;

                    if (!v.IsPartityA)
                    {
                        if (v.IsInPair)
                        {
                            BFSCueBackup.Enqueue(vertices[v.Pair]);
                            vertices[v.Pair].FazaBFS = F;
                            vertices[v.Pair].Distance = d + 1;
                        }
                        else if (!foundinpartity)
                        {
                            foundinpartity = true;
                            shortest = d;
                        }
                    }
                    else
                    {
                        foreach (int i in v.Neighbours)
                        {
                            if (vertices[i].FazaBFS < F)
                            {
                                BFSCue.Enqueue(vertices[i]);
                                vertices[i].FazaBFS = F;
                                vertices[i].Distance = d + 1;
                            }
                        }
                    }
                }

                if (!foundinpartity && (BFSCue.Count == 0 || (BFSCue.Peek().IsPartityA && partity == false)))
                {
                    foundinpartity = false;
                    partity = !partity;
                    BFSCue = BFSCueBackup;
                    BFSCueBackup = new Queue<Vertex>();
                }
            }
            return shortest;
        }

        static bool DFS(Vertex v, int max)
        {
            if (v.Distance == max - 1)
            {
                bool result = false;

                foreach (int i in v.Neighbours)
                {
                    Vertex N = vertices[i];

                    if (!N.IsInPair)
                    {
                        N.Pair = v.Index;
                        v.Pair = i;
                        result = true;
                        break;
                    }
                }
                v.Distance = -1;
                return result;
            }
            else
            {
                bool result = false;

                foreach (int i in v.Neighbours)
                {
                    Vertex s = vertices[i];

                    if (s.Distance == v.Distance + 1)
                    {
                        s.Distance = -1;

                        if (DFS(vertices[s.Pair], max))
                        {
                            v.Pair = s.Index;
                            s.Pair = v.Index;
                            result = true;
                            break;
                        }
                        else
                        {
                            result = false;
                        }
                    }
                }
                return result;
            }
        }

        class Vertex
        {
            List<Int32> iNeighbours = new List<int>();

            public List<Int32> Neighbours
            {
                get { return iNeighbours; }
            }

            Int32 iPair;

            public Int32 Pair
            {
                get { return iPair; }
                set
                {
                    iPair = value;
                    iIsPair = true;
                }
            }

            Int32 iDistance;

            public Int32 Distance
            {
                get { return iDistance; }
                set { iDistance = value; }
            }

            Boolean iPartA;

            public Boolean IsPartityA
            {
                get { return iPartA; }
                set
                {
                    iPartA = value;
                    iPartSet = true;
                }
            }

            private int ii;

            public int Index
            {
                get { return ii; }
                set { ii = value; }
            }

            Boolean iPartSet;

            public Boolean IsPartitySet
            {
                get { return iPartSet; }
            }

            Boolean iIsPair;

            public Boolean IsInPair
            {
                get { return iIsPair; }
            }

            Int32 iPhase;

            public Int32 IPhaseBFS
            {
                get { return iPhase; }
                set { iPhase = value; }
            }

            public Int32 FazaBFS
            {
                get { return iPhase; }
                set { iPhase = value; }
            }

            Int32 iPhaseInit;

            public Int32 FazaInit
            {
                get { return iPhaseInit; }
                set { iPhaseInit = value; }
            }

            public Vertex(int i)
            {
                ii = i;
                iPhase = 0;
                iPhaseInit = 0;
            }
        }
    }
}

Drobná poznámka: metóda Initialize využíva namespace Codex, ktorý je stavaný na mieru nášmu vyhodnocovaciem systému CodEx. Namiesto neho bude potrebné zistiť aktuálne číslo ručne (možno s použitím int.Parse() alebo niečoho podobného).

 

Stiahnuť si môžete okomentovanú verziu spolu s vzorovými vstupmi a výstupmi (časová náročnosť rastie spolu s poradovým číslom zadania).

 

Uznávam, že tento program na prvý pohľad nevyzerá veľmi zložito a v skutočnosti ani nie je. Zložité bolo hlavne pochopiť, ako Dinicov algoritmus funguje. Programovanie potom išlo viac menej hladko. Druhá zložitá vec bola opltimalizácia kódu na rýchlosť výpočtu.

 

Dúfam, že môj kód niekomu príde vhod. A keď nie, aspoň si teraz môžete predstaviť, aké úlohy sa riešia na Algoritmoch a dátových štruktúrach II. 🙂

Reklamy

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s