» »

Problem škatel

Problem škatel

1
2
»

snow ::

Če je lahko v eni škatli samo ena škatla potem je EA ful ful lažji. :)

Mogoče za trening ko mi bo dolgčas. :\
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

mia- ::

aha, ce morjo bit ene v drugi, potem je to to kar sem mislil..
in graf vsebovanosti "dobro" opise stvar

no tomas povej primer , pri katerem graf in najdalsa pot ne bi bila prava resitev

Thomas ::

Graf vsebovanosti je lahko večkrat pretrgan. Več takih grafov vsebovanosti je v splošnem rešitev.

Rabiš dodatno informacijo, kje se kakšen začne in kje neha. To so rešitve in niso vse optimalne in v splošnem jih je več taboljših.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

mia- ::

pot se zacne pri tisti tocki, v katero ne gre nobena puscica(skatla)
.. takih tock(skatel) je lahko vec

ce je graf pretrgan, pomeni da nobena skatla iz enega dela, ne pase v nobeno skatlo iz drugega dela, in obratno..
ker pakiramo samo 1x, ostale pustimo, je spet dovolj, da gledamo najdalso pot v raztrganem grafu

(ce bi pakirali veckrat, bi morali gledati vse mozne neodvisne poti, ki pokrijejo cimvecji del grafa) a vendar mislim da to ni misljeno v navodilu

snow ::

Skatle:
0:3 5 4
1:10 4 10
2:9 75 77
3:24 84 30
4:766 397 714
5:2315 9568 1202
6:434 398 4107
7:2842 566 2200
8:8254 9438 591
9:7 6 4

Resitev:
2/10
0->9 1->2 2->4 3->6 4->7 6->5 7->8 9->3 (notranja skatla->zunanja skatla)

Mislim da resitev stima. Ce najde kdo boljso resitev ali ugotovi da je resitev napacna naj pove nenadoma. :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

snow ::

Tole je bil en najbolj simpl evolucijski algoritem: populacija 200, tournament selekcija, tournament size 4, verjetnost mutacije 2% in le en tip mutacije = zamenjava zunanje škatlice. encoding: array števil, ki so predstavljale zunanje škatlice.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Bravo snow, bravo. Tko se dela.
Man muss immer generalisieren - Carl Jacobi

svit ::

Snow: zdaj pa še ponovi za 500 škatel :)... Pa povej kako si dobil tiste dodatne argumente (verjetnost mutacije 2%) in zakaj so taki. Sam sicer mislim, da ne bom uporabil EA, ker nimam dovolj izkušenj iz tega. Edino če mi razložiš bolj podrobno ta postopek. Sicer so mi jasne glavne zamisli EA, vendar v programiranju tega nisem še poskusil. Prav tako me zanima čas, ki si ga porabil za to nalogo.
Ni ideje

snow ::

Porabil sem nekje uro.
Če hočem zadevo naštimat na 500 škatel spremenim eno cifro.


2% hmm nevem. Tako sem nastavil začetno. Ti gruntaj in se igraj. :)
Pa lahko probuješ različne velikosti populacij - naštimaš v main funkciji ko narediš instanco.
Pa štimaš lahko tournament size (zdej je na 4... no cifra tam je 3 ker vedno vzame enega.. se pravi +1)
Lahko bi tud kak crossover si pogruntal :) Lahko ti dam ideje če hočeš.

//evolucijsko zlaganje skatlic - by snow
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>

struct SSkatla{
    int x;
    int y;
    int z;
    SSkatla(int, int, int);
};

SSkatla::SSkatla(int ix, int iy, int iz)
{
    x = ix;
    y = iy;
    z = iz;
}

struct SGenome{
    std::vector<int> zunanja;
    int fitness;
    SGenome(int);
};

SGenome::SGenome(int s)
{
    for(int i=0;i<s;i++)
    {
        zunanja.push_back(-1);
    }
}

class CGASkatle{
    std::vector<SSkatla> skatle;
    std::vector<SGenome> population;
    std::vector<SGenome> selected;
    int Fitness(SGenome&);
    
    int SkatliPasejo(SSkatla, SSkatla);
    
    int populationsize;
    int skatelsize;
    
    int bestfitness;
    int bestindex;
    
    int prevbest;
    
    public:
    CGASkatle(int, int);
    void Evaluation();
    void Selection();
    void Mutation();

};

CGASkatle::CGASkatle(int p, int s)
{
    srand(static_cast<unsigned int>(time(0)));
        
    populationsize=p;
    skatelsize=s;
    
    bestfitness=s;
    bestindex=0;
    
    prevbest=s;
    
    for(int i=0;i<populationsize;i++)
    {
        population.push_back(SGenome(skatelsize));
        selected.push_back(SGenome(skatelsize));
    }
    
    //zmisli si nekaj random velikih skatlic :)
    int max=1000;
    for(int j=0;j<skatelsize;j++)
    {
        max=static_cast<int>(pow(10,1+rand()%4));
        skatle.push_back(SSkatla(1+rand()%max,1+rand()%max,1+rand()%max));
        std::cout<<j<<":"<<skatle[j].x<<" "<<skatle[j].y<<" "<<skatle[j].z<<" "<<std::endl;
    }
}

int CGASkatle::SkatliPasejo(SSkatla zunaj, SSkatla notri)
{
    if(zunaj.x>notri.x && zunaj.y>notri.y && zunaj.z>notri.z){return 1;}
    if(zunaj.x>notri.x && zunaj.y>notri.z && zunaj.z>notri.y){return 1;}
    if(zunaj.x>notri.y && zunaj.y>notri.x && zunaj.z>notri.z){return 1;}
    if(zunaj.x>notri.y && zunaj.y>notri.z && zunaj.z>notri.x){return 1;}
    if(zunaj.x>notri.z && zunaj.y>notri.x && zunaj.z>notri.y){return 1;}
    if(zunaj.x>notri.z && zunaj.y>notri.y && zunaj.z>notri.x){return 1;}
    
    return 0;
}

//prešteje vidne škatle (odšteje škatle v škatlah od vseh)
int CGASkatle::Fitness(SGenome& res)
{
    int f=skatelsize;
    
    for(int c=0;c<skatelsize;c++)
    {
        if(res.zunanja[c]!=-1)
        {
            f--;
        }
    }
    
    return f;
}

//našima fitness vsem in si zapomni najboljšega
void CGASkatle::Evaluation()
{
    for(int i=0;i<populationsize;i++)
    {
        population[i].fitness=Fitness(population[i]);
        if(population[i].fitness<bestfitness)
        {
            bestfitness=population[i].fitness;
            bestindex=i;
        }
    }
    
    if(prevbest!=bestfitness)
    {
        prevbest=bestfitness;
        std::cout<<std::endl<<bestfitness<<"/"<<skatelsize<<std::endl;
        /*
        for(int j=0;j<skatelsize;j++)
        {
            if(population[bestindex].zunanja[j]!=-1)
            {
                std::cout<<j<<"->"<<population[bestindex].zunanja[j]<<" ";
            }
        }
        */
    }
}

//tournament selekcija... tournament size 4.
void CGASkatle::Selection()
{
    for(int i=0;i<populationsize;i++)
    {
        int bidx=rand()%populationsize;
        int bf=population[bidx].fitness;
        int tsize=3;
        while(tsize--)
        {
            int opp=rand()%populationsize;
            if(population[opp].fitness<bf)
            {
                bf=population[opp].fitness;
                bidx=opp;
            }
        }
        selected[i]=population[bidx];
    }
    population.swap(selected);
}

void CGASkatle::Mutation()
{
    for(int p=0;p<populationsize;p++)
    {
        for(int s=0;s<skatelsize;s++)
        {
            //verjetnost mutacije je 20/1000
            if(rand()%1000<=20)
            {
                int v=rand()%skatelsize;
                if(SkatliPasejo(skatle[v],skatle[s]))
                {
                    for(int d=0;d<skatelsize;d++)
                    {
                        if(population[p].zunanja[d]==v)
                        {
                            population[p].zunanja[d]=-1;
                        }
                    }
                    population[p].zunanja[s]=v;
                }
            }
        }
    }    
}

int main()
{    
    // (populationsize, skatel)
    CGASkatle solver(200,500);
    while(1)
    {
        solver.Selection();
        solver.Mutation();
        solver.Evaluation();
    }

    return 0;
}


:D
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

snow ::

Kompajlal z mingw (gcc) integriranim v Dev C++.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

svit ::

To je danes poslal profesor na vprašanje ali so lahko dve vzporedni škatli v eni škatli:

"To je težja različica naloge. Načeloma bi lahko v neko škatlo 'vzporedno' shranili več škatel. Zopet se lahko sam odločite, katero nalogo boste reševal."


Snow: hvala. Mogoče bom uporabil.
Ni ideje

mia- ::

moj algoritem bi v psevdokodi izgledal

A = generirajMatrikoVsebovanosti(podatki);
NajdalšaPot = najdalšapot(A);

izluščiti potem pravo rešitev ni težko. Potrebno je povedati da algoritem najdalše poti najdemo v teoriji grafov. Fajn je tkole problem prevest na teorijo, kjer že obstaja polno orodij. Ravno to je point vseh teorij.
Torej vse kar je za narest je zgenerirat matriko - dvojna for zanka. Sicer je v danem primeru dotičina matrika antisimetrična(za usmerjene grafe), in je dovlj izračunati zgornjo/spodnjo polovico.

snow ::

Napiši program, pa si zmislimo 500 škatel pa gremo testirat.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

mia- ::

jah program napisat je tko, da rabiš čas.
sicer pa to delajo računalničarji ,
matematiki sam psevokodo teramo:) nam je povsem zadostno.


Sicer pa , ko bom imel čas morda lahko napišem.. Sam bo v Javi:)
Še da ponovim kako sem razumel nalogo, predno se spravim karkoli.
Pakiramo eno škatlo v drugo (ne smeta it 2 vzporedno v eno)
in pakiramo samo enkrat. Kar pomeni, da preostale škatle pustimo vsako zase in jih ne poskusamo se dodatno pakirat? svit?

Vesoljc ::

od kje si pa te omejitve dobil?

Naloga
Danih je n (500) škatlic znanih velikosti ( ai, bi, ci), i = 1,..., n.
Sestavi program, ki bo določil, kako naj zložimo škatlice ene v druge, tako da bo na koncu ostalo vidnih čim manj škatlic.
Namig: pomagaj si z grafom vsebovanosti škatlic.
Abnormal behavior of abnormal brain makes me normal...

snow ::

Jaz sem razumel in sprogramiral takole(ker je bilo rečeno da ne moremo dat več škatel vzporedno v eno):
Ena škatla lahko gre samo v eno... ampak ta lahko ima znotraj še kakšno.

1 -> 2
2 -> 3
3 -> 4 ...

Ne gre pa recimo:
1 -> 3
2 -> 3


mia-
kaj si ti mislil s tistim pakiramo samo enkrat?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

mia- ::

**Naša naloga je postaviti škatle ene v drugo tako, da bo vidnih čim manj škatlic. Število škatel, katerim se ne bi uspelo uvrstiti v množici mora biti minimalno**

Jaz sem razumel takole:torej število škatel, katerim se nebi uspelo uvrstiti v množici (v pakiranje?) more biti minimalno..
torej kao pakiramo enkrat, ostale škatle ki so preostale, jih pač pustimo kukr so, sam more jih bit minimalno?

Primer:
mamo 5 škatel in recimo da
1-> 2 ->3 to potem izgleda od zunaj kot ena škatla (kot trojka)
Preostaneta 4 in 5, a vendar tudi če 4 ->5 jih pustimo vsako posebej?
Kao to so te škatle, k se niso uspele uvrstit v pakiranje 1->2->3,
torej v našem primeru je sta te škatli 2.
Lahko bi pakirali tudi večrat, recimo 4->5 (poleg 1-2-3) in potem imeli od zunaj le 2 škatle?

snow ::

> Lahko bi pakirali tudi večrat, recimo 4->5 (poleg 1-2-3) in potem imeli od zunaj le 2 škatle?

Po moje je lahko pakiranj več.
Se pravi iz škatel 1,2,3,4,5 lahko naredimo (kot si rekel): 1->2->3 in 4->5 kar nam da rezultat: 2

Tako imam tudi sam narejen moj program.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

snow ::

mia- a tvoja rešitev z matriko vsebovanosti deluje za oba problema?

To mi je všeč pri EA.. se da dokaj hitro poštimat za kakšne variante.
Tudi za ono težjo varianto če bi lahko v eno škatlo dal več škatel vzporedno. Ampak tam ne vem kako bi preverjal ali dve škatli pašejo v eno? A za to obstajajo kakšne točne rešitve?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

mia- ::

nop, ne dela za oba, samo za lažjega:)

ne poznam ea , sam vidm pa da je kr kul glede fleksibilnosti.

da bi moj program delal za večkratna pakiranja bi si mogu mau pogledat če se da preuredit, al pa pogledat v teorijo grafov če so še kšna orodja

svit ::

Mislim, da moraš potem preostale škatle prav tako pospraviti. Se pravi da imaš več urejevalnih postopkov.
Ni ideje

snow ::

Kot je on moj primer zgoraj z 10 škatlami?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Jim ne potegne tale EA, a snow?
Man muss immer generalisieren - Carl Jacobi

snow ::

Thomas - praktično bi rekel da je tole čist en 'hello world EA'. Pa pač ni... Hm. :]

Svit kaj si pa kaj ti naredil? kero verzijo delaš?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Zgodovina sprememb…

  • spremenilo: snow ()

svit ::

Snow: malo več potrpljenja. Delal bom tvojo verzijo. In če se mi bo dalo še drugo verzijo.
Ni ideje
1
2
»


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[c++] naloge

Oddelek: Programiranje
475586 (4126) technolog
»

Kaj sploh je programiranje? (strani: 1 2 )

Oddelek: Programiranje
5410276 (8277) imagodei
»

RMA za WD disk

Oddelek: Strojna oprema
164118 (3773) ender
»

Colour (3,14.......) noise

Oddelek: Znanost in tehnologija
122299 (1905) Thomas
»

Škatlar Zmago na POPu

Oddelek: Znanost in tehnologija
272404 (1677) ThePlayer

Več podobnih tem