Wann ist f_1(x) schneller als f_2(x).
-
Hallo, ich habe ein riesiges Problem, nun ich besuche ein Fach das 2 Semester über mir ist. Nun ich habe eine aufgabe bekommen. Jetzt bin ich in ein punkt angekommen in der aufgabe das ich nicht bewältigen kann.
Nun die aufgabe ist folgender maße, finde eine Lösung in ein spiel.
Nun ich habe zur Auswahl 2 heuristische Funktionen c_1(n) und c_2(n).Wobei wenn ich die zeiten vergleiche für jedent punkt n folgendes gilt c_1(n) < c_2(n)
In kurzen Sätze habe ich zwei algoritmen zur Auswahl Minimax und a-b cut.
Für Minimax. Habe die zeit folgender maßen berechnet.F_x(n) = G_x(n) + H_x(n). x=1,2.
Wobei G(n) die zeit die ich brauche um ein such Baum zu bilden und gleich mit g*(b^n) ist. b^n sind alle knoten in ein n –großen Baum wobei jeder knoten b Kinder hat, und g ist die zeit die ich brauche um die Kinder zu bilden. Und die heuristische Funktionen H(n) die der algorithmus braucht habe ich volgendes gleichung herausgefunden H(n) = c_x(n) = (t_x)*(b^n) ist, fur x = 1,2 gilt c_1(n) < c_2(n) ist. Nun bilde ich volgende Funktionen.
F_1(x) = (g + t_1)*b^x.
Und
F_2(x) = (g+ t_2)*b^x.
Wobei g,b,t_1,t_2,x in |N sind. Dazu ist g,b,t_1,t_2 konstanten in beiden Funktionen sind, also sie verändern sich nicht wenn x sich verändert. Und es gilt das c_1(n) < c_2(n) also auch folgendes fur t_x t_1 < t_2.
---------------------------------------------PROBLEM-----------------------------------------------
Nun mein problemm ist folgendes. Ich werde ungefähr folgendes gefragt. für die Funktion mit der zeit t_1 (also F_1) gilt das mein Baum eine tiefe von d hat. Und für die Funktion mit der zeit t_2 (also F_2) hat mein such Baum eine tiefe von d-1.. Unter welche Bedingung ist c_1(n) kleiner als c_2(n).d ist eine zufällige zahl also d = 1,2,3,4,…,n… ist.
Meine Funktionen schauen also so aus.
//nicht vergesen t1 < t2
F_1(x) = (g + t_1)*b^x.Und
F_2(x) = (g + t_2)*b^(x-1).
Mit schneller meine ich das meine heuristische such algotitmus schneller eine Lösung findet.
Meine Antwort ist folgender weise, 100% ist meine Vermutung falsch. Asiptotisch(???) gilt für die Funktionen
F_1(x) = b^x
F_2(x) = b^(x-1)
Aber die beiden Funktionen beschneiden sich nirgendwo also ist F_1 immer schneller da sie ja b mal schneller ist als F_2 aber ich bin mir nicht sicher. Sie konnten sich ja irgnetwo schneiden dann ist F_2 schneller für x < als schneide punkt.
Bitte. Bitte, bitte Helft mir . Habe keinen Idee ob das richtich ist und die aufgabe geht noch weiter (für a-b cut), mein Termin ist Dienstag bitte, bitte HILFE.
-
Versuche mal deine Frage etwas zu strukturieren und das Wesentliche in konsistenter Notation zu schreiben. Mir ist nicht klar was genau die Aufgabe ist und um was es sich handelt. Idealerweise schreibe eine Aussage in mathematischer Notation hin, die es zu beweisen gilt.
Notfalls poste die Aufgabe wie sie auf dem Übungsblatt steht.
Du fragst: "Unter welche Bedingung ist c_1(n) kleiner als c_2(n)"
Oben schreibst du: "...jedent punkt n folgendes gilt c_1(n) < c_2(n)"" für die Funktion mit der zeit t_1"
Was ist eine Funktion mit einer Zeit?"F_1(x) = (g + t_1)*b^x.
F_2(x) = (g + t_2)*b^(x-1).
...
F_1(x) = b^x
F_2(x) = b^(x-1)"Ja was denn nun? Wenn du das asymptotische Verhalten untersuchen willst ist z.B. die O-Notation sinnvoll.
u.s.w.
Also bitte nochmal.
-
Egal, ich hab die aufgabe mitlerweile shon raus(YU HU). danke aber an alle die sich beschefticht haben.