Witam!
Moim celem jest zmutowanie posiadanego drzewa w taki sposób. Posiadam drzewo t, buduje drzewo t2; znajduję losowe miejsce w drzewie t (nie może nim być root tego drzewa); idę do rodzica wylosowanego node'a; usuwam losowo albo prawe dziecko albo lewe dziecko, wylosowanego node'a (oraz całe poddrzewo idąc od usuniętego dziecka); pod usunięte dziecko podstawiam root drzewa t2; otrzymuje zmutowane drzewo t. Problem w mojej implementacji polega, na tym, że metoda, która robi mutację raz działa poprawnie, a raz nie. Częściej poprawnie, ale jednak nie za każdym razem,a bardzo rzadko trafi się crash (drzewa, która są poddawane tej operacji na pewno są poprawne).
Przykładowy prefixowy output:
Drzewo t : / + x + x - sin x x
Drzewo t2: x
Drzewo t po mutacji: / x czyli nie powstało nawet poprawne drzewo wyrażeń .
Analizowałem już różne scenariusze na kartce, ale nie potrafię zrozumieć jak mogło powstać / x
Wywołanie main'a testujące funkcje mutującą :
int main()
{
Tree t;
t.init();
for (int i = 0; i < 100; i++) {
cout << endl << "Drzewo orginal: ";
t.printTree();
t.doTheMutation(); //to samo, co ponizsza metoda Tree::mutation
cout << endl << "Drzewo orginal po mutacji: ";
t.printTree();
}
return 0;
}
Używam poniższej metody do mutacji:
Pod parametr przy wywołaniu podstawiam root drzewa, które ma być mutowane
void Tree::mutation(Node* &node)
{
if (!(getHeight() <= 1))
{
Tree tempTree;
for (int i = 0; i < 30; i++) // ????
tempTree.randomPrefix();
tempTree.init(); // buduje losowe drzewo
bool mutated = false;
Node* temp = node;
// ide w lewo albo w prawo od korzenia
if (rand() % 10 <= 4)
{
temp = temp->left;
}
else
{
temp = temp->right;
}
if (temp != 0) {
while (temp->left != 0 && temp->right != 0 && !mutated)
{
if (rand() % 10 <= 4)
{
//tu zrob mutacje
temp = temp->parent;
if (rand() % 10 <= 4)
{
delete temp->left;
temp->left = 0;
}
else
{
delete temp->right;
temp->right = 0;
}
if (temp->right == 0)
{
temp->right = tempTree.root;
(tempTree.root)->parent = temp;
}
else
{
temp->left = tempTree.root;
(tempTree.root)->parent = temp;
}
mutated = true;
}
else
{
//szukaj dalej
if (rand() % 10 <= 4)
{
temp = temp->left;
}
else
{
temp = temp->right;
}
}
}
//zrob mutacje na lisciu, jesli wczesniej nie bylo mutacji
if (!mutated)
{
temp = temp->parent;
if (rand() % 10 <= 4)
{
delete temp->left;
temp->left = 0;
}
else
{
delete temp->right;
temp->right = 0;
}
if (temp->right == 0)
{
temp->right = tempTree.root;
(tempTree.root)->parent = temp;
}
else
{
temp->left = tempTree.root;
(tempTree.root)->parent = temp;
}
}
}
}
}
Mam jeszcze dodatkowe pytanie, nie związane bezpośrednio z mutowaniem drzewa. Gdy losuję wyrażenie prefixowe do zbudowania drzewa tempTree, tak jak w powyższej metodzie muszę zrobić bezsensownego fora, bez którego za każdym razem tempTree będzie identyczny jak drzewo, które chce zmutować. Dodatkowo przy takim wywołaniu:
for (int i = 0; i < 100; i++) {
cout << endl << "Drzewo orginal: ";
t.printTree();
t.doTheMutation(); // wywołanie powyzszej metody inną nazwą
cout << endl << "Drzewo orginal po mutacji: ";
t.printTree();
}
drzewo tempTree budowane wewnątrz t.doTheMutation(); dopiero po kilku iteracjach pętli for zmienia się, gdzie każde wywołanie t.doTheMutation() robi :
Tree tempTree;
for (int i = 0; i < 30; i++) // ????
tempTree.randomPrefix();
tempTree.init(); // buduje losowe drzewo
Więc drzewa, tempTree, powinny być prawie zawsze inne z każdą iteracją for'a, a tak nie jest. Dopiero po np. 10 iteracjach tempTree zmienia się w inne drzewo.
Budowanie losowego drzewa na pewno działa dobrze, ponieważ takie wywołanie :
Tree t1,t2,t3;
t1.init();
t2.init();
t3.init();
Tworzy prawie zawsze różne drzewa.
Linijka srand(time(0)); jest w konstruktorze klasy Tree. To jest mój główny podejrzany w sprawie identyczny losowań, ale nie widzę powodu, żeby to była przyczyna "mało losowych" drzew.
Funkcja init, która buduje losowe drzewo:
void Tree::init() {
buildTree(randomPrefix()); // buduje drzewo ze stringa w parametrze, gdzie randomPrefix()
//zwraca randomowe wyrażenie prefixowe w stringu np. "+ x y"
doTheMath(); // liczy wartosc funkcji f(x,y) zapisanej w drzewie przy danym x,y.
}
C++