Not logged in. · Lost password · Register

Page:  1  2  next 
AverageGuy
Member since Dec 2015
68 posts
Subject: [Altklausur - SS15] 5 - DAG
Hallo,

im Folgenden handelt es sich um die Teilaufgabe a).
Ich würde diese Aufgabe mit einem Breitensuche-Algorithmus bearbeiten.

"Für die Tiefensuche bräuchte man einen Markierschritt, der bei dieser Aufgabe nicht realisierbar wäre."
- Liege ich mit dieser Aussage richtig?

Ist mein Ansatz richtig oder laufe ich Richtung Wand?
This post was edited on 2016-03-11, 18:13 by AverageGuy.
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
557 posts
+1 AverageGuy
Ich vermute, Aufgabe 5 (Seite 8, https://www2.cs.fau.de/teaching/WS2015/AuD/organisation/ol…) ist eigentlich gemeint.

Allgemein zu Tiefensuche in DAGs: Warum markiert man Knoten? Ist das bei einem gerichteten azyklischen Graph überhaupt ein Problem?

Konkret zu der Aufgabe: Hier suchst du doch eigentlich nichts, sondern sollst nur so lange den Graph ablaufen (welche Kanten du nimmst, sagt dir die übergebene HashMap) und zurückgeben, ob du damit bei TRUE oder FALSE landest.
AverageGuy
Member since Dec 2015
68 posts
Vielen Dank für den Tipp. Ich habe auch den Titel geändert.
Ich habe hoffentlich alles richtig verstanden und eine Lösung gefunden:
        String thisString = this.v;
        if(this == TRUE){
            return true;
        }else if(this == FALSE){
            return false;
        }
       
        if(tv.contains(thisString)){
            tv.remove(thisString);
            return this.trueC.eval(tv);
        }else if(tv.contains("!" + thisString)){
            tv.remove(thisString);
            return this.falseC.eval(tv);
        }else{
            return false;
        }

"Testcase" laut Angabe (einfach in main einfügen):
        BDD a = new BDD();                        a.v = "a";
        a.trueC = new BDD();                      a.trueC.v = "c";
        a.trueC.falseC = TRUE;
        BDD b = new BDD();                        b.v = "b";
        a.falseC = new BDD();                     a.falseC.v = "c";
        b.trueC = FALSE;
        b.falseC = TRUE;
        a.trueC.trueC = b;
        a.falseC.falseC = b;
        a.falseC.trueC = FALSE;
       
   
        HashSet<String> test = new HashSet<String>();
        test.add("!a");
        test.add("!b");
        test.add("c");

        System.out.println("ERGEBNIS:    " + a.eval(test));

Falls der Code richtig sein sollte, darf er gerne als Musterlösung bei den Altklausuren gepostet werden.
AverageGuy
Member since Dec 2015
68 posts
Hast du auch noch einen Tipp für die b).
Ich habe folgendes:
        if(p.contains(this)){
            return true;
        }
        p.add(this);
       
        if(this.trueC != null){
            return this.trueC.isDAG(p);
        }
       
        if(this.falseC != null){
            return this.falseC.isDAG(p);
        }
       
        return false;

Das funktioniert natürlich nicht, weil ich erst das falseC aufrufe, wenn trueC schon durchgelaufen ist.
Normalerweise würde ich das ja in einer Schleife schreiben, nur leider weiß ich nicht wie ich das mit den Nachfolgern löse,
da diese hier trueC und falseC sind und nicht in einem Array o.ä.
Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
Ich würde ggf. "==" durch equals ersetzen, in denen du nicht etwas auf null prüfst. Wobei hier sollte "==" und equals keine Unterschiede liefern.
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
557 posts
In reply to post #4
Quote by AverageGuy:
tv.remove(thisString);

Warum möchtest du Elemente aus dem übergebenen HashSet löschen? Die Variablenbelegung ändert sich doch nicht. Außerdem schließt die Aufgabenstellung nicht aus, dass sie selbe Variable von unterschiedlichen Knoten ausgewertet wird.

Quote by AverageGuy:
tv.contains("!" + thisString))

Warum ein Ausrufezeichen vorne an den String anhängen?

Quote by Aufgabenstellung:
Dabei sei die Variable mit Namen this.v genau dann true, wenn sie im HashSet tv vorkommt.

"!v" ist keine Variable.

Quote by AverageGuy:
Hast du auch noch einen Tipp für die b).
Ich habe folgendes:
        if(p.contains(this)){
            return true;
        }
        p.add(this);
       
        if(this.trueC != null){
            return this.trueC.isDAG(p);
        }
       
        if(this.falseC != null){
            return this.falseC.isDAG(p);
        }
       
        return false;

Das funktioniert natürlich nicht, weil ich erst das falseC aufrufe, wenn trueC schon durchgelaufen ist.
Normalerweise würde ich das ja in einer Schleife schreiben, nur leider weiß ich nicht wie ich das mit den Nachfolgern löse,
da diese hier trueC und falseC sind und nicht in einem Array o.ä.

Sieht doch nicht schlecht aus, nur sind soweit ich das auf die Schnelle sehe true und false konsequent vertauscht. Zum ersten if: Wenn du den Knoten im aktuellen Durchlauf schon mal gesehen hast, hast du doch einen Zyklus gefunden und es ist kein DAG.

Wenn es dir hilft, dass es ein Array ist, dann bau dir doch eins mit new BDD[] {this.trueC, this.falseC}. Wie würdest du es damit lösen? Danach kannst du dir überlegen wie du dieses Array wieder los wirst.
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
557 posts
In reply to post #5
Quote by Ezekiel15:
Ich würde ggf. "==" durch equals ersetzen, in denen du nicht etwas auf null prüfst. Wobei hier sollte "==" und equals keine Unterschiede liefern.

Warum? Hier wird kein equals implementiert, damit verhält es sich genau wie ==. Und die dass TRUE und FALSE als static final deklariert sind, ist doch ein starker Hinweis dafür, dass es jeweils sowieso nur ein Objekt davon gibt.
ic97usop
ehemals Chayyam
Member since Sep 2015
369 posts
Die Implementierung von AverageGuy hat meines Erachtens noch einen weiteren Fehler. Wenn der trueChild mal nicht null ist, wird sofort etwas zurückgegeben. Der falseChild-Zweig wird damit gar nicht erst durchlaufen. Ist also erst im falseChild-Zweig ein Kreis vorhanden, so wird dieser nicht detektiert. Den Codeabschnitt
  1. if(this.trueC != null){
  2.         return this.trueC.isDAG(p);
  3. }
sollte man daher imo. durch
  1. if(this.trueC != null && !this.trueC.isDAG(p)){
  2.         return false;
  3. }
ersetzen.
Eine ruhige, sachliche und freundliche Arbeitsweise ist der Schlüssel zum Erfolg.
AverageGuy
Member since Dec 2015
68 posts
@izibi
Teilaufgabe a): habe ich anscheinend falsch verstanden. Ich bin von dieser Art der Variablenbelegung ausgegangen: z.B. {"a", "!b", "c"}.

Teilaufgabe b): Besser als das bekomme ich es nicht hin. Ich glaube ich bin an den Grenzen meiner Fähigkeiten angelangt...
Ich weiß einfach nicht, wie ich es schaffe, dass ich nicht nur die trueC's durchlaufe.
Ich habe den Tiefensuche-Code eigentlich 1:1 aus den Folien genommen und auf mein Problem angewandt: Ohne Erfolg wie du siehst.
        if(p.contains(this)){
            return false;
        }
        p.add(this);
       
       
        BDD[] run = new BDD[]{this.trueC, this.falseC};
        for(BDD child : run){   
            if(child == null){
                continue;
            }
           
            if(!p.contains(child)){
                return child.isDAG(p);
            }else{
                return false;
            }
        }
       
        return true;
Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
Ich bin mit der Aufgabe / Aufgabenstellung auch nicht glücklich, mein Ansatz zur a):
(nur eine Skizze)

  1.     boolean eval(HashSet<String> tv) {
  2.         if (tv.isEmpty()) {
  3.             return true;
  4.         } else {
  5.             if (tv.contains(this.v)) {
  6.                 tv.remove(this.v);
  7.                 return this.eval(tv);
  8.             } else {
  9.                 boolean t1 = false;
  10.                 boolean t2 = false;
  11.                 if (trueC != null) {
  12.                     t1 = trueC.eval(tv);
  13.                 }
  14.                 if (falseC != null) {
  15.                     t2 = falseC.eval(tv);
  16.                 }
  17.                 return t1 || t2;
  18.             }
  19.         }
  20.     }
This post was edited on 2016-03-12, 19:10 by Ezekiel15.
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
557 posts
In reply to post #9
Quote by AverageGuy:
Teilaufgabe b): Besser als das bekomme ich es nicht hin. Ich glaube ich bin an den Grenzen meiner Fähigkeiten angelangt...
Ich weiß einfach nicht, wie ich es schaffe, dass ich nicht nur die trueC's durchlaufe.
Ich habe den Tiefensuche-Code eigentlich 1:1 aus den Folien genommen und auf mein Problem angewandt: Ohne Erfolg wie du siehst.

Wann ist der Teilgraph, der vom aktuellen Knoten ausgeht, denn azyklisch? Zum einen darfst du den aktuellen Knoten nicht schon mal besucht haben (das passt in deinem Code), zum anderen darf weder das true-Kind, noch das false-Kind Zyklen enthalten, oder anders ausgedrückt: beide Kinder müssen selbst DAGs sein. Also eigentlich, willst du da etwas wie return trueC.isDAG() && falseC.isDAG();, nur dass es auch null sein könnte.

Wenn du grob bei deinem Code mit der Schleife bleiben willst oder den Code später so umschreiben willst, dass für jedes Kind ein if da steht: du willst nur returnen, wenn dein Kind kein DAG ist, dann weißt du sicher, dass der komplette Graph kein DAG ist. Sonst willst du noch das andere Kind überprüfen.

(Im wesentlichen steht der Code dafür ja sowieso schon im Post von ic97usop.)

Quote by AverageGuy:
            if(!p.contains(child)){
                return child.isDAG(p);
            }else{
                return false;
            }

Dieses if ist redundant, das fragt genau ab, was child.isDAG(p) dann gleich als erstes nochmal prüft.
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
557 posts
In reply to post #10
Quote by Ezekiel15:
  1. tv.isEmpty()
[…]
  1. tv.remove(this.v);

Das sieht nach einem Versuch aus, rekursiv auf dem übergebenen HashSet zu arbeiten. Das ist aber doch die Variablenbelegung, die über die komplette Auswertung konstant bleibt. Es darf daraus nichts entfernt werden. Das hier (Code ungetestet und nur schnell hingeschrieben) ist ein gültiger BDD (niemand sagt, dass eine Variable nicht doppelt ausgewertet werden darf):

  1. BDD a = new BDD(), b = new BDD();
  2. a.v = "x";
  3. a.trueC = b;
  4. a.falseC = b;
  5. b.v = "x";
  6. b.trueC = BDD.TRUE;
  7. b.falseC = BDD.FALSE;

Also ein Knoten, der x auswertet und unabhängig von dessen Wert in einen zweiten Knoten übergeht, der nochmal x auswertet und dann in TRUE oder FALSE geht. Wenn a.eval(tv) nun ein tv.remove("x"); macht, verfälscht das das Ergebnis.

Bei Aufgabe a) soll Rekursion nur auf dem BDD betrieben werden und die einzige Methode, die man vom übergebenen HashSet braucht, ist contains.
ic97usop
ehemals Chayyam
Member since Sep 2015
369 posts
Da ich mich beim Lernen auf DSP auch mal ablenken will, habe ich mich auch mal an der Aufgabe versucht.

  1. import java.util.*;
  2.  
  3. public class BDD {
  4.    
  5.     static final BDD TRUE = new BDD();
  6.     static final BDD FALSE = new BDD();
  7.     BDD trueC, falseC;
  8.     String v;
  9.    
  10.     /*************************************************************
  11.      * Task 5.a: Function to evaluate a boolean expression       *
  12.      * @param tv: given expression                               *
  13.      * @return true iff the given graph satisfies the expression *
  14.      *************************************************************/
  15.     boolean eval(HashSet<String> tv){
  16.         /** Sanity check that the hashset is not null. **/
  17.         if(tv == null){
  18.             return false;
  19.         }
  20.         /** Base cases **/
  21.         if(this.equals(TRUE)){
  22.             return true;
  23.         }
  24.         if(this.equals(FALSE)){
  25.             return false;
  26.         }
  27.         /**********************************************
  28.          * Recursion cases.                           *
  29.          * Please note that some sanity checks might  *
  30.          * be removed due to assumptions of the task. *
  31.          **********************************************/
  32.         if(!tv.contains(v) && this.falseC != null && this.falseC.eval(tv)){
  33.             return true;
  34.         }
  35.         if(!tv.contains('!' + v) && this.trueC != null && this.trueC.eval(tv)){
  36.             return true;
  37.         }
  38.         return false;
  39.     }
  40.    
  41.     /*********************************************
  42.      * Task 5.b: A recursive function to check   *
  43.      * whether the given graph is a DAG          *
  44.      * @return true iff the given graph is a DAG *
  45.      *********************************************/
  46.     boolean isDAG(){
  47.         return isDAG(new HashSet<BDD>());
  48.     }
  49.    
  50.     /************************************************
  51.      * Helping function for task 5.b                *
  52.      * @param p set of visited nodes                *
  53.      * @return false iff the graph contains a cycle *
  54.      ************************************************/
  55.     boolean isDAG(HashSet<BDD> p){
  56.         /** Just a sanity check since this function is not private. **/
  57.         if(p == null){
  58.             return false;
  59.         }
  60.         /** Base cases. **/
  61.         if(this.equals(TRUE) || this.equals(FALSE)){
  62.             return true;
  63.         }
  64.         if(p.contains(this)){
  65.             return false;
  66.         }
  67.         /** Mark the current element as visited. **/
  68.         p.add(this);
  69.         /** Recursion cases. **/
  70.         if(this.trueC != null && !this.trueC.isDAG(p)){
  71.             return false;
  72.         }
  73.         if(this.falseC != null && !this.falseC.isDAG(p)){
  74.             return false;
  75.         }
  76.         /************************************************
  77.          * Now mark the current element as unvisited    *
  78.          * to ensure that we still can revisit it later *
  79.          * from a different tree branch.                *
  80.          ************************************************/
  81.         p.remove(this);
  82.         return true;
  83.     }
  84.    
  85.     /** Tests for task 5.a **/
  86.     public static void testEval1(){
  87.         BDD a = new BDD();
  88.         a.v = "a";
  89.         BDD b = new BDD();
  90.         b.v = "b";
  91.         BDD c1 = new BDD();
  92.         c1.v = "c";
  93.         BDD c2 = new BDD();
  94.         c2.v = "c";
  95.         a.trueC = c1;
  96.         a.falseC = c2;
  97.         c1.trueC = b;
  98.         c1.falseC = TRUE;
  99.         c2.trueC = FALSE;
  100.         c2.falseC = b;
  101.         b.trueC = FALSE;
  102.         b.falseC = TRUE;
  103.         HashSet<String> tv = new HashSet<String>();
  104.         tv.add("a");
  105.         tv.add("!b");
  106.         tv.add("c");
  107.         assert a.eval(tv) : "Error at eval test 1";
  108.         System.out.println("Eval test 1: OK");
  109.     }
  110.    
  111.     public static void testEval2(){
  112.         BDD a = new BDD();
  113.         a.v = "x";
  114.         BDD b = new BDD();
  115.         b.v = "x";
  116.         a.trueC = b;
  117.         a.falseC = b;
  118.         b.trueC = TRUE;
  119.         b.falseC = FALSE;
  120.         HashSet<String> tv = new HashSet<String>();
  121.         tv.add("!x");
  122.         assert !a.eval(tv) : "Error at eval test 2";
  123.         System.out.println("Eval test 2: OK");
  124.     }
  125.    
  126.     /** Tests for task 5.b **/
  127.     public static void testDAG1(){
  128.         BDD a = new BDD();
  129.         a.v = "a";
  130.         BDD b = new BDD();
  131.         b.v = "b";
  132.         BDD c1 = new BDD();
  133.         c1.v = "c";
  134.         BDD c2 = new BDD();
  135.         c2.v = "c";
  136.         a.trueC = c1;
  137.         a.falseC = c2;
  138.         c1.trueC = b;
  139.         c1.falseC = TRUE;
  140.         c2.trueC = FALSE;
  141.         c2.falseC = b;
  142.         b.trueC = FALSE;
  143.         b.falseC = TRUE;
  144.         assert a.isDAG() : "Error at DAG test 1.";
  145.         System.out.println("DAG test 1: OK");
  146.     }
  147.    
  148.     public static void testDAG2(){
  149.         BDD a = new BDD();
  150.         a.v = "a";
  151.         a.trueC = a;
  152.         a.falseC = FALSE;
  153.         assert !a.isDAG() : "Error at DAG test 2.";
  154.         System.out.println("DAG test 2: OK");
  155.     }
  156.    
  157.     /***************************************
  158.      * Main function for testing purposes. *
  159.      * Do not forget to enable assertions. *
  160.      * @param args not needed here         *
  161.      ***************************************/
  162.     public static void main(String[] args){
  163.         testEval1();
  164.         testEval2();
  165.         testDAG1();
  166.         testDAG2();
  167.     }
  168.  
  169. }
Eine ruhige, sachliche und freundliche Arbeitsweise ist der Schlüssel zum Erfolg.
This post was edited 2 times, last on 2016-03-13, 12:05 by ic97usop.
Ezekiel15
Ezekiel15
Member since Oct 2015
182 posts
@ic97usop, damit läuft du nur dann weiter, wenn in tv eine Variable der Form "v" oder "!"+v auftaucht, aber nicht bis zu einem Endknoten hier TRUE oder FALSE gekommen bist, die du auf jeden Fall erreichen musst. 
Dein Code ist fast richtig und die Aufgabe ist eig. simpler: if(tv.contains(this.v)) nehme die true Kante, sonst nehme die andere Kante. (natürlich nur, insofern eine Kante existiert), rekursion
Ist bspw. dein HashSet leer würdest du sicher immer die false Kante nehmen.
This post was edited 3 times, last on 2016-03-13, 12:17 by Ezekiel15.
ic97usop
ehemals Chayyam
Member since Sep 2015
369 posts
Quote by Ezekiel15:
@ic97usop, damit läuft du nur dann weiter, wenn in tv eine Variable der Form "v" oder "!"+v auftaucht, aber nicht bis zu einem Endknoten hier TRUE oder FALSE gekommen bist, die du auf jeden Fall erreichen musst. 
Dein Code ist fast richtig und die simpler: if(tv.contains(v)) nehme die true Kante, sonst nehme die andere Kante. (natürlich nur, insofern eine Kante existiert)
Ist bspw. dein HashSet leer würdest du sicher immer die false Kante nehmen.

Ich habe meinen Code etwas geändert. Allerdings muss man imo. beide Zweige abprüfen, wenn weder v noch !v in tv enthalten sind.

Wenn tv.contains(v) => nimm nur trueC
Wenn tv.contains(!v) => nimm nur falseC
Sonst => nimm beides

Ist die Hashset außerdem leer, verstehe ich aus der Aufgabenstellung nicht, ob die Bedingung "wahr" oder "falsch" ist. Ich habe das für den Fall "wahr" implementiert.
Eine ruhige, sachliche und freundliche Arbeitsweise ist der Schlüssel zum Erfolg.
This post was edited on 2016-03-13, 12:09 by ic97usop.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen