400 Bad Request

Bad Request

Your browser sent a request that this server could not understand.

Příklad programu na DFS - Depth-first search

Příklad programu na DFS - Depth-first search

Příspěvekod Ariczek » 21 říjen 2011 11:33:10

Jak už topic napovídá, jedná se o algoritmus prohledávání do hloubky, v tomto případě s prořezáváním.
http://en.wikipedia.org/wiki/Depth-first_search

Na jakém problému si to ukážeme ?
Použijí zadání jedné semestrálky ze školy:

Úloha MTG: minimální tloušťka grafu
Zadáním přesným bych vás tu unudil... takže vlastními slovy :D
Takže mějme graf - tam jsou tlustý tečky, a čárky co je spojujou - uzly a hrany:)

př. Vstupní soubor:
Kód: Vybrat vše
5
01111
10100
11000
10001
10010


první řádka udává že máme 5 uzlů. Každá další řádka říká s kým má uzel hrany ? např. řádka 4: 10001 - říká, že uzel 4 má hranu s uzlem 1 a s uzlem 5.

A o co se vlastně budeme snažit ?

očíslujeme si uzly od 1...n. takto takto očíslované si je seřadíme za sebe do řady. Mezi kazdou dvojici uzlu spocitame, kolik hran tam prochazi. Nejvetsi takove cislo nazveme tloustka grafu. A ted hledame takove ocislovani uzlu, aby tato tloustka byla minimalni. Viz prilozeny obrazek:
zadani.png
zadani.png (28.12 KiB) Zobrazeno 9099 krát


Dost teorie, jak na to ? :D

Kód: Vybrat vše
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

void help(char** arg) {
   cout << "Spatne pouziti, nutno zadat parametry: " << endl
      << "Spravne pouziti: " << arg[0] << " G " << endl
      << "G - soubor reprezentujici neorietovany souvisly graf o n uzlech a stupni nejvyse k, kde" << endl
      << "n - prirozene cislo predstavujici pocet uzlu grafu" << endl
      << "k - prirozene cislo radu jednotek predstavujici maximalni stupen uzlu grafu" << endl;
}

struct hrana{
   int a;
   int b;
   void vypis() {
      cout << a << " " << b << endl;
   }
};

// funkce slouzi pro nacteni hran ze vstupniho souboru predaneho jako parametr
int nacti(vector<hrana>& hrany, const char* jmeno_souboru) {   // vraci pocet uzlu
   ifstream is;
   is.open(jmeno_souboru,ios_base::binary);
   char* num = new char[10];
   is.getline(num,9); // jedna se o cislo - pocet uzlu grafu.
   int pocetUzlu = atoi(num); // cislo n
   delete num;
   for (int i = 0; i < pocetUzlu; i++) { // cyklus pres vsechny uzly grafu - pro kazdy je jedna radka ve vstupnim souboru
      int current = pocetUzlu+i;   // nove nactene uzly cisluji od n - do 2n-1
      char* help = new char[pocetUzlu*2+10]; // vytvori dostatecne velky char* - neni jiste zda radky jsou 0101 ci 0 1 0 1
      is.getline(help, pocetUzlu*2+2);   // nacti radku
      if ((int)strlen(help) < pocetUzlu + 2) {   // syntaxe souboru 0101
         for (int j = i; j < pocetUzlu; j++) {   // matice incidence je u neorientovaneho grafu symetricka - tedy staci ji projit polovina
            if (help[j] == '1') {
               hrana h;   // souradnice a je vzdy mensi nez b
               h.a = pocetUzlu + i;
               h.b = pocetUzlu + j;
               hrany.push_back(h);
            }
         }
      } else {   // syntaxe souboru 0 1 0 1
         for(int j = 2*i; j < pocetUzlu*2; j+=2) {
            if (help[j] == '1') {
               hrana h;   // souradnice a je vzdy mensi nez b
               h.a = pocetUzlu + i;
               h.b = pocetUzlu + j;
               hrany.push_back(h);
            }
         }
      }
      delete help;
   }
   return pocetUzlu;
}

struct potomek {
   vector<hrana> hrany;
   int pocetNahrazenych;
   int sirkaDoBodu;
};

vector<potomek> vygenerujPotomky(potomek p, int pocetUzlu) {
   vector<potomek> ret;
   if (p.pocetNahrazenych == pocetUzlu) {   // pokud uz jsme nahradili vsechny uzly negeneruj nic, nejsou potomci
      return ret;
   }
   for (int i = 0; i < pocetUzlu; i++ ) {
      bool changed = false;
      vector<hrana> kopie = p.hrany;
      for (int j = 0; j < (int) kopie.size(); j++) {
         if (kopie[j].a == pocetUzlu+i) {   // v tuto chvili prestava platit ze a < b
            kopie[j].a = p.pocetNahrazenych;
            changed = true;
         }
         if (kopie[j].b == pocetUzlu+i) {
            kopie[j].b = p.pocetNahrazenych;
            changed = true;
         }
         if (kopie[j].a > kopie[j].b) {   // tady opet zajistim a < b
            int pomoc = kopie[j].b;
            kopie[j].b = kopie[j].a;
            kopie[j].a = pomoc;
         }
      }

      if (changed) {   // vytvoren potomek
         potomek temp;
         temp.hrany = kopie;
         temp.pocetNahrazenych = p.pocetNahrazenych+1;

         int meziSoucet = 0;
         for (int j = 0; j< (int) kopie.size(); j++) {
            if (kopie[j].a <= p.pocetNahrazenych && kopie[j].b > p.pocetNahrazenych)
               meziSoucet++;
         }
         if (p.sirkaDoBodu < meziSoucet) {
            temp.sirkaDoBodu = meziSoucet;
         } else {
            temp.sirkaDoBodu = p.sirkaDoBodu;
         }
         ret.push_back(temp);
      }

   }
   return ret;
}

int main(int argc, char* argv[]) {
   if (argc != 2) {
      help(argv);
      return 1;
   }
        time_t t_start, t_end;
        t_start = time(NULL);
   char* jmeno_souboru = argv[1];
   vector<hrana> hrany;
   int pocetUzlu = nacti(hrany,jmeno_souboru);   // nacteni hran ze souboru do hrany
   /*for (int i = 0; i < (int) hrany.size(); i++) {
      hrany[i].vypis();
   }*/

   stack<potomek> zasobnik;
   potomek first;
   first.hrany = hrany;
   first.pocetNahrazenych = 0;
   first.sirkaDoBodu = 0;
   zasobnik.push(first);

   bool nalezenoReseni = false;   // promenne ovladajici orezavani
   int nalezenaSirka = 0;

   vector<hrana> best;
   int counter = 0;

   while (!zasobnik.empty()) {
      
      //cout << zasobnik.size() << endl;
      potomek pomoc = zasobnik.top();   // vem nejhlubsiho potomka
      zasobnik.pop();
      //cout << pomoc.sirkaDoBodu << endl;
      if (nalezenoReseni && nalezenaSirka < pomoc.sirkaDoBodu) {
         continue;      // oriznuti
      }
      if (pomoc.pocetNahrazenych == pocetUzlu) {   // mame k expanzi jiz uplnou permutaci
         if (nalezenoReseni == false) {
            nalezenaSirka = pomoc.sirkaDoBodu;
            nalezenoReseni = true;
            best = pomoc.hrany;
         cout << counter << endl;
         counter = 0;
            cout << "? " << nalezenaSirka << endl;
            /*for (int i = 0; i < (int) best.size(); i++) {
               best[i].vypis();
            }*/
            continue;
         } else if (nalezenaSirka > pomoc.sirkaDoBodu){
            nalezenaSirka = pomoc.sirkaDoBodu;
            best = pomoc.hrany;
         cout << counter << endl;
         counter = 0;
            cout << "# " << nalezenaSirka << endl ;
            /*for (int i = 0; i < (int) best.size(); i++) {
               best[i].vypis();
            }*/
            continue;
         }
      } else {
         vector<potomek> ret = vygenerujPotomky(pomoc,pocetUzlu);
         if (ret.size() > 0) {
            for (int i = 0; i < (int) ret.size(); i++) {
               potomek helpy = ret[i];
               if (nalezenoReseni && nalezenaSirka < helpy.sirkaDoBodu) {
                  counter++;
                  continue;   // oriznuti - prave pridavany stav ma vetsi sirku nez jiz nejlepsi nalezeny
               } else {   // nejsem v poslednim uzlu, a nebylo jeste nalezeno reseni
                  zasobnik.push(helpy);
                  //cout << ".";
               }
            }
         }
      }
   }
   cout << counter << "X" << endl << nalezenaSirka << endl;
   for (int i = 0; i < (int) best.size(); i++) {
      best[i].vypis();
   }
t_end = time(NULL);
cout << "Doba behu: " << (int) t_end - t_start << endl;
   return 0;
}

Myslim si, že kód je relativně všeříkající, jen doplním že ořezávám právě podle té šířky.
Pokud by byl zájem, mohu do toho zatáhnout ještě paralelní programování, a ukázat jak se to dá efektivně řešit pomocí MPI.
Ariczek
Ariczek
 
Příspěvky: 51
Registrován: 21 říjen 2011 10:54:52

Re: Příklad programu na DFS - Depth-first search

Příspěvekod Wlezley » 21 říjen 2011 23:10:25

Jen dodám, že na české wiki je o tom taky pár informací. http://cs.wikipedia.org/wiki/Prohled%C3 ... do_hloubky

Je to zajímavý, nikdy jsem nic podobného neviděl ani neřešil. Možná by se to dalo využít například k analýze sociálních sítí.

Dobrá práce Ariczek :thumbup1:
Uživatelský avatar
Wlezley
 
Příspěvky: 316
Registrován: 24 září 2011 22:54:46
Bydliště: Plzeň
Projekt: Wlezley EU


Zpět na C/C++

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 2 návštevníků


cron