Matematické Fórum

pidzwick · 21. 03. 2012 15:09

Potreboval by som rychly alogoritmus pre takyto problem:

Mame mnozinu prvkov a kazdy prvok je ohodnoteny realnym cislom. Prvky sa navzajom mozu vylucovat. Potrebujem zistit mnozinu prvkov, v ktorej sa ziadna dvojica navzajom nevylucuje, pricom ta mnozina bude mat maximalnu sumu prvkov.

Priklad:

A 1.5
B 2
C 1.6
D 1.8
E 1.1

Dvojice, ktore sa vylucuju:
A B
C D
D E

Cize v tomto pripade by bola vysledna mnozina B C E so sumou = 4.7.

Problem je ten, ze potrebujem algoritmus, ktory najde tu mnozinu aj pri velkych vstupoch (max. cca 30 prvkov) a v realnom case (max. niekolko desiatok ms). V pripade nerealnosti takeho rychleho algorimtu dajte vediet.

Za kazdu pomoc vopred dakujem.

jindra · 21. 03. 2012 19:41

Můžeš specifikovat rychlost pomocí odhadu složitosti?

pidzwick · 22. 03. 2012 12:11

↑ jindra:
Prinajhorsom by to mohlo byt O(N^4).

Backtrackom to vychadza dost zle, lebo tam by sa museli prehladat takmer vsetky podmnoziny (moj pseudokod si velmi nevsimajte :D):

getMaxMnozina(celkova_mnozina) {
max_sum = 0;
max_mnozina = {};
rekurzivna_metoda({}, celkova_mnozina, 0);
return max_mnozina;
}

rekurzivna_metoda (aktualna_mnozina, mnozina_dalsich_prvkov, aktual_max)
if (mnozina_dalsich_prvkov JE PRAZDNA) {
if (aktual_max>max_sum) {
max_sum = aktual_max
max_mnozina = aktualna_mnozina
}
return
}
copy_mnozina_dalsich_prvkov = copy(mnozina_dalsich_pckov)

for (Prvok prvok: mnozina_dalsich_prvkov) {
copy_mnozina_dalsich_prvkov = copy_mnozina_dalsich_prvkov - prvok
copy2_mnozina_dalsich_prvkov = copy(copy_mnozina_dalsich_prvkov)
copy2_mnozina_dalsich_prvkov = copy2_mnozina_dalsich_ticpov - mnozina_prvkov_ktore_nemozu_byt_s_prvkom(prvok)
copy_aktualna_mnozina_prvkov = copy(aktualna_mnozina)
copy_aktualna_mnozina_prvkov = copy_aktualna_mnozina_prvkov + prvok
rekurzivna_metoda(copy_aktualna_mnozina_prvkov, copy2_mnozina_dalsich_prvkov, aktual_max+prvok.getHodnota())
}
}

Lumikodlak · 22. 03. 2012 21:11

To je zajimavy priklad :-) Podle me bude hodne zalezet na poctu dvojic (a na jejich usporadani), ne jenom na poctu prvku. Jsou nejaka pravidla pro pocet dvojic?
Kdyz se to rozdeli na skupiny dvojic, ktere se navzajem neovlivnuji, urcite se to o dost zrychli - napriklad tady vyersit zvlast pro A-B a zvlast pro C-D, D-E. Je jasne, ze pro tu skupinu A-B je maximum B, potom s A ani B neni treba dal pocitat, a resit jenom C, D, E. Tady to ma maly vliv, ale pri vetsi poctech by byl vliv velky.
Kdyz bude velky pocet dvojic v jedne skupine, tak to bude asi slozitejsi, neco by se podle me vymyslet dalo, ale nevim, jestli se to vejde do O(m^4), kde by m byl pocet dvojic, ale to kdyztak pozdeji, zatim dej vedet, jestli souhlasis s tim (a rozumis tomu), co jsem psal :-)

pidzwick · 23. 03. 2012 11:14

↑ Lumikodlak:

V skutocnosti je cca 110 prvkov (mozno bude casom viac). A z tych prvkov vlastne iba pre vybranu podmnozinu (vacsinou to bude 1-5 prvkov, ale je potrebne to mat poriesene aj pre vacsi pocet idealne max. 30) je potrebne najst podmnozinu s maximalnym suctom. Co som pozrel tak z tych 110 prvkov je cca 25% dvojic, ktore sa vylucuju z celkoveho poctu dvojic.

jindra · 23. 03. 2012 15:07

Lumikodlak napsal(a):
To je zajimavy priklad :-) Podle me bude hodne zalezet na poctu dvojic

Také myslím. Přemýšlel jsem nad tímto příkladem, a šel by řešit dynamickým programováním, rychlost by ale záležela hlavně na tom, jak rychle se dá zjistit jestli se další prvek nevylučuje. Ale nepřišel jsem na to jak to zařídit rychle.

Lumikodlak · 25. 03. 2012 00:42

Zkusil jsem to nejakym zpusobem naprogramovat C++, a myslim, ze to mozna funguje. Delal jsem to priblizne tak (Nic lepsiho jsem zatim nevymyslel, mohlo by to jit lepe. Overoval jsem spravnost jen pro jednoduche pripady) :

Nejdriv se vytvori matice podle toho, jak jsou ty dvojice, napriklad v prikladu, co jsi tu uvadel (na diagonale jednicky bez ohledu na to, jestli je prvek v nejake dvojici nebo ne). Jednicka na diagonale znamena, ze tam jakoby ten prvek muze byt, jednicka mimo diagonalu znamena, ze je s nejakym prvkem ve dvojici:

Code:

  A B C D E
A 1 1 0 0 0
B 1 1 0 0 0
C 0 0 1 1 0
D 0 0 1 1 1
E 0 0 0 1 1

Pak se postupuje po sloupcich, a snazis se kazdy sloupce nejak "vyresit". Takze zacnes na A, tam vidis, ze tam byt muze, ale je ve dvojici s B. Jsou dve moznosti (kupodivu :-) ) - bud tam A je, nebo neni. Pro kazdou z moznosti vynulujes oznaceni te dvojice, jako ze je vyresena a nemusis se dal starat, a jednou nechas A a vynulujes B, podruhe vynulujes A a nechas B. V prvnim pripade pak rekurzivne "vyresis" sloupec B s matici:

Code:

  A B C D E
A 1 0 0 0 0
B 0 0 0 0 0
C 0 0 1 1 0
D 0 0 1 1 1
E 0 0 0 1 1

a ve druhem pro:

Code:

  A B C D E
A 0 0 0 0 0
B 0 1 0 0 0
C 0 0 1 1 0
D 0 0 1 1 1
E 0 0 0 1 1

Sloupec B uz nema zadne dvojice, takze neni treba dal resit a akorat se vrati hodnota, a rozhodne se, ktera z moznosti mela vetsi soucet.
Dal budes postupovat na C, z nej budes rekurzivne resit D jednou pro:

Code:

  A B C D E
A 0 0 0 0 0
B 0 0 0 0 0
C 0 0 1 0 0
D 0 0 0 0 1
E 0 0 0 1 1

a jednou pro:

Code:

  A B C D E
A 0 0 0 0 0
B 0 0 0 0 0
C 0 0 0 0 0
D 0 0 0 1 1
E 0 0 0 1 1

Ale z D budes jeste dal rekurzivne resit pro E (v prvnim pripade to bude jednoduche, protoze tam D tam nemas tak tam E muzes nechat, ve druhem budou zas dve moznosti)

Spis jsem akorat nastinil princip, jsou tam jeste veci k doreseni, co jsem nepopsal (mimo jine to funguje jen pro kladne hodnoty, ale to je asi ok :-) ). Zatim dej kdyztak vedet, co si o tom myslis (myslite) :-) Kod v C++ kdyztak dodam, pro 30 prvku a 30 nahodnych dvojic to bezi asi 2ms, pro 30 prvku a 100 dvojic asi 50ms, urcite zalezi i na usporadani dvojic, v nekterych ne-nahodnych pripadech by to asi bylo horsi.

pidzwick · 28. 03. 2012 15:17

↑ Lumikodlak:
Pls ked mozes posli mi zdrojak, chcem sa na to blizsie pozriet.

Lumikodlak · 28. 03. 2012 22:37

Ok :-) psal jsem to, jak me napadlo, takze to neni moc propracovane. Pridal jsem tam jeste par komentaru, ale stejne nevim, jestli je to dobre citelne. Jsou tam zakomentovane ty 'new' a 'delete', protoze to tak bylo pomale, a napsal jsem to jinak. Celkove by to slo napsat lepe a tak, aby to bylo rychlejsi, ale do toho se mi zatim nechtelo :-)

Code:

#include "stdafx.h"

const int PocetPrvku = 30;
const int PocetDvojic = 100;
const int PocetTestu = 100;

typedef struct {
    int Dvojice[PocetPrvku];
    int Pritomen, Pocet, Index;
} Sloupec;

typedef struct {
    Sloupec Sloupce[PocetPrvku];
} Matice;

//    Inicializace (ted zbytecne, protoze se stejne nastavi nahodne hodnoty v testovacim cyklu)

float Prvky[PocetPrvku] = {
    1.5, 2, 1.6, 1.8, 1.1, 5.3, 7.3, 4.2, 5.3, 9.2,
    2.6, 7.3, 6.2, 7.3, 8.3, 7.2, 1.6, 3.7, 7.2, 1.6,
    3.6, 7.3, 2.8, 8.4, 2.7, 8.4, 5.7, 4.7, 3.7, 8.3
};

int Dvojice[PocetDvojic][2] = {{0, 1}, {2, 3}, {3, 4}, {5, 6}, {5, 7}, {5, 8}, {6, 9}, {7, 10}, {8, 10}};
Matice MaticeDvojic;
Matice DocasneMatice[64];

void VlozDvojici (int Dvojice[2]);
float ZpracujSloupec (Matice *MaticeDvojic, int Sloupec, int PosledniDocasna);

int _tmain(int argc, _TCHAR* argv[])
{
    float MeziSoucet;

    //     Cyklus pro opakovani testu

    for (int IndexTestu = 0; IndexTestu < PocetTestu; IndexTestu ++){    
        MeziSoucet = 0;
        
        // Nastaveni nahodnych hodnot
        
        for (int IndexPrvku = 0; IndexPrvku < PocetPrvku; IndexPrvku ++){
            Prvky [IndexPrvku] = (float)rand () / 32768.f;
        }
        for (int IndexDvojice = 0; IndexDvojice < PocetDvojic; IndexDvojice ++){
            Dvojice [IndexDvojice][0] = rand () % PocetPrvku;
            Dvojice [IndexDvojice][1] = rand () % PocetPrvku;
            if  (Dvojice [IndexDvojice][0] == Dvojice [IndexDvojice][1]){
                Dvojice [IndexDvojice][1] = (Dvojice [IndexDvojice][1] + 1) % PocetPrvku;
            }
        }
        memset (&MaticeDvojic, 0, sizeof(MaticeDvojic));
        for (int IndexSloupce = 0; IndexSloupce < PocetPrvku; IndexSloupce ++){
            MaticeDvojic . Sloupce [IndexSloupce] . Index = IndexSloupce;
            MaticeDvojic . Sloupce [IndexSloupce] . Dvojice [IndexSloupce] = 1;
            MaticeDvojic . Sloupce [IndexSloupce] . Pocet = 1;
        }

        //    Zpracovani

        for (int IndexDvojice = 0; IndexDvojice < PocetDvojic; IndexDvojice ++){
            VlozDvojici (Dvojice[IndexDvojice]);
        }

        for (int IndexSloupce = 0; IndexSloupce < PocetPrvku; IndexSloupce ++){
            MeziSoucet += ZpracujSloupec (&MaticeDvojic, IndexSloupce, 0);
        }
        printf ("Soucet : %f\n", MeziSoucet);
    }

    return 0;
}

//    Vlozi dvojici do matice

void VlozDvojici (int Dvojice[2]){
    if (Dvojice[0] < PocetPrvku && Dvojice[1] < PocetPrvku){
        if (!MaticeDvojic . Sloupce [Dvojice[0]] . Dvojice[Dvojice[1]]){
            MaticeDvojic . Sloupce [Dvojice[0]] . Dvojice[Dvojice[1]] = 1;
            MaticeDvojic . Sloupce [Dvojice[1]] . Dvojice[Dvojice[0]] = 1;
            MaticeDvojic . Sloupce [Dvojice[0]] . Pocet ++;
            MaticeDvojic . Sloupce [Dvojice[1]] . Pocet ++;
        }
    }
}

//    Procedura, ktera zpracovava sloupce, vola rekurzivne sama sebe

float ZpracujSloupec (Matice *MaticeDvojic, int Sloupec, int PosledniDocasna){
    int Sousedni[PocetPrvku];
    int PocetSousednich = 0;
    float MeziSoucet1, MeziSoucet2, Soucet;

    memset (Sousedni, 0, sizeof(Sousedni));

    //    Jestlize je sloupec prazdny anebo ma jen jednicku na diagonale, vratit se
    
    if (MaticeDvojic -> Sloupce [Sloupec] . Pocet == 0) return (0);
    if (MaticeDvojic -> Sloupce [Sloupec] . Pocet == 1){
        if (MaticeDvojic -> Sloupce [Sloupec] . Dvojice[Sloupec]){
            MaticeDvojic -> Sloupce [Sloupec] . Pritomen = 1;
            return Prvky[Sloupec];
        }
    }

    //    Vytvorit seznam prvku, s kteryma je ve dvojici a vynulovat oznaceni v matici
    
    for (int IndexDvojice = 0; IndexDvojice < PocetPrvku; IndexDvojice ++){
        if (Sloupec != IndexDvojice){
            if (MaticeDvojic -> Sloupce [Sloupec] . Dvojice [IndexDvojice] == 1){
                Sousedni[PocetSousednich] = IndexDvojice;
                PocetSousednich ++;
                MaticeDvojic -> Sloupce [Sloupec] . Dvojice [IndexDvojice] = 0;
                MaticeDvojic -> Sloupce [Sloupec] . Pocet --;
                MaticeDvojic -> Sloupce [IndexDvojice] . Dvojice [Sloupec] = 0;
                MaticeDvojic -> Sloupce [IndexDvojice] . Pocet --;
            }
        }
    }

    //    Zpracovat pripad, kde by prvek (sloupec) nebyl pritomny
    
//    Matice *DocasnaMatice1 = new (Matice);
    Matice *DocasnaMatice1 = DocasneMatice + PosledniDocasna;
    PosledniDocasna ++;
    memcpy (DocasnaMatice1, MaticeDvojic, sizeof(*DocasnaMatice1));
    if (DocasnaMatice1 -> Sloupce [Sloupec] . Dvojice [Sloupec]){                    //    Vynulovat prvek
        DocasnaMatice1 -> Sloupce [Sloupec] . Dvojice [Sloupec] = 0;
        DocasnaMatice1 -> Sloupce [Sloupec] . Pocet --;
    }
    MeziSoucet1 = 0;
    for (int IndexSouseda = 0; IndexSouseda < PocetSousednich; IndexSouseda ++){    //    Zpracovat vsechny sousedni
        MeziSoucet1 += ZpracujSloupec (DocasnaMatice1, Sousedni[IndexSouseda], PosledniDocasna);
    }
    for (int IndexSouseda = 0; IndexSouseda < PocetSousednich; IndexSouseda ++){    //    Vynulovat sousedni, aby se dal nezapocitavaly
        int Soused = Sousedni[IndexSouseda];
        DocasnaMatice1 -> Sloupce [Soused] . Dvojice [Soused] = 0;
        DocasnaMatice1 -> Sloupce [Soused] . Pocet --;
    }

    //    Zpracovat pripad, kde by prvek (sloupec) byl pritomny

//    Matice *DocasnaMatice2 = new (Matice);
    Matice *DocasnaMatice2 = DocasneMatice + PosledniDocasna;
    PosledniDocasna ++;
    memcpy (DocasnaMatice2, MaticeDvojic, sizeof(*DocasnaMatice1));
    if (DocasnaMatice2 -> Sloupce [Sloupec] . Dvojice [Sloupec]){        //    Uvazovat jen v pripade, ze prvek muze byt pritomny
        for (int IndexSouseda = 0; IndexSouseda < PocetSousednich; IndexSouseda ++){    //    Vynulovat vsechny sousedni
            int Soused = Sousedni[IndexSouseda];
            DocasnaMatice2 -> Sloupce [Soused] . Dvojice [Soused] = 0;
            DocasnaMatice2 -> Sloupce [Soused] . Pocet --;
        }
        MeziSoucet2 = Prvky[Sloupec];
        DocasnaMatice2 -> Sloupce [Sloupec] . Pritomen = 1;
        for (int IndexSouseda = 0; IndexSouseda < PocetSousednich; IndexSouseda ++){    //    Zpracovat vsechny sousedni
            MeziSoucet2 += ZpracujSloupec (DocasnaMatice2, Sousedni[IndexSouseda], PosledniDocasna);
        }
    }
    else{
        MeziSoucet2 = -FLT_MAX;
    }

    //    Pouzit moznost s vyssim souctem

    if (MeziSoucet1 > MeziSoucet2){
        memcpy (MaticeDvojic, DocasnaMatice1, sizeof(*MaticeDvojic));
        Soucet = MeziSoucet1;
    }
    else{
        memcpy (MaticeDvojic, DocasnaMatice2, sizeof(*MaticeDvojic));
        Soucet = MeziSoucet2;
    }

    PosledniDocasna --;
    PosledniDocasna --;
//    delete (DocasnaMatice1);
//    delete (DocasnaMatice2);
    return (Soucet);
}

V stdafx.h je tohle, ted nevim jestli to tam vsechno musi byt:

Code:

#include "targetver.h"

#include <stdio.h>
#include <tchar.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>

Kazdopadne si porad nejsem jisty, jestli to funguje spravne, overoval jsem to jen pro nektere ne moc slozite pripady. Kdybys tam necemu nerozumel, tak se klidne ptej :-) a mozna vysvetlim.

pidzwick · 30. 03. 2012 14:10

↑ Lumikodlak:
Dik, nakoniec som pouzil ten svoj algoritmus - zefektivnil som ho a teraz dost rychlo bezi.

Matematické Fórum

#1 21. 03. 2012 15:09

Algoritmus

#2 21. 03. 2012 19:41

Re: Algoritmus

#3 22. 03. 2012 12:11

Re: Algoritmus

#4 22. 03. 2012 21:11

Re: Algoritmus

#5 23. 03. 2012 11:14

Re: Algoritmus

#6 23. 03. 2012 15:07

Re: Algoritmus

Lumikodlak napsal(a):

#7 25. 03. 2012 00:42

Re: Algoritmus

Code:

Code:

Code:

Code:

Code:

#8 28. 03. 2012 15:17

Re: Algoritmus

#9 28. 03. 2012 22:37

Re: Algoritmus

Code:

Code:

#10 30. 03. 2012 14:10

Re: Algoritmus

Zápatí