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
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:
Dost teorie, jak na to ?
- 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