From 418470ffc8f62fef965d4bedae776202af992afa Mon Sep 17 00:00:00 2001
From: dirk <dirk@voyager.(none)>
Date: Wed, 25 Apr 2007 10:56:38 +0200
Subject: [PATCH] ADA* added try java -Xmx100M schiebe adastern

---
 schiebe.java | 297 +++++++++++++++++------------------------------------------
 1 file changed, 84 insertions(+), 213 deletions(-)

diff --git a/schiebe.java b/schiebe.java
index a5b47cf..e64f7f7 100644
--- a/schiebe.java
+++ b/schiebe.java
@@ -145,8 +145,8 @@ class schiebe {
         
         //System.out.println(argv.length);
         if( argv.length > 0) {
-            if( argv[0].equals("tiefensucheexp") ) {
-                tiefensucheexp();
+            if( argv[0].equals("adastern") ) {
+                adastern();
             } else if( argv[0].equals("asternsimpel") ) {
                 asternsimpel();
             } else if (argv[0].equals("dfs") ) {
@@ -325,226 +325,97 @@ class schiebe {
         }
     }
     
-    
-    //deprecated!!!
-    private static void tiefensucheexp() {
-        int beste_tiefe = 32786;
-        int max_tiefe   = 0;
-
-        Knoten ka=null, kb=null, kc=null, kd=null, ke=null,
-               kf=null, kg=null, kh=null, ki=null, kj=null,
-               kk=null, kl=null, km=null, kn=null, ko=null,
-               kp=null, kq=null, kr=null;
-
-        LinkedList<Knoten> knotenListeA = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeB = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeC = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeD = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeE = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeF = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeG = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeH = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeI = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeJ = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeK = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeL = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeM = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeN = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeO = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeP = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeQ = new LinkedList<Knoten>();
-        LinkedList<Knoten> knotenListeR = new LinkedList<Knoten>();
-
-
-        knotenListeA = trs.expandKnoten(start);
-        System.out.println(knotenListeA.size());
-        for (int a=0; a<knotenListeA.size(); a++)
+    private static void adastern ()
+    {
+        int maxTiefe = 15;
+        int maxTiefeNeu;
+        while (maxTiefe > 0)
         {
-            ka= knotenListeA.get(a);
-            if (ka.is(ziel)) 
-                System.out.println("GEFUNDEN A");
-            knotenListeB = trs.expandKnoten(ka);
-
-            for (int b=0; b<knotenListeB.size(); b++)
+            System.out.println("Starte asternluft mit maxTiefe "+ maxTiefe);
+            maxTiefeNeu = asternluft2(maxTiefe);
+            if (maxTiefeNeu < maxTiefe) maxTiefe = maxTiefeNeu;
+            else maxTiefe=0;
+        }
+    }
+    
+    private static int asternluft2(int maxTiefe) {
+        // Alle Knoten der Tiefe 7 entwickeln
+	LinkedList<Knoten> schichtListe= new LinkedList<Knoten>();
+        LinkedList<Knoten> pfad;
+        schichtListe.add(Knoten.getStart());
+        Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
+        LinkedList<Knoten> expandListe= null;
+        boolean tiefe8=false;
+        while (!tiefe8) {
+            Knoten k = schichtListe.poll();
+            expandListe = trs.expandKnoten(k);
+            pfad = testZiel(expandListe,true);
+            if (pfad.size()> 0 && pfad.size()-1 < maxTiefe) return pfad.size()-1;
+            if (expandListe.getFirst().get_tiefe()<8) 
             {
-                kb=knotenListeB.get(b);
-                if (kb.is(ziel)) 
-                    System.out.println("GEFUNDEN B");
-                knotenListeC = trs.expandKnoten(kb);
-
-                for (int c=0; c<knotenListeC.size(); c++)
+                //Knoten löschen die zu weit entfernt sind
+                LinkedList<Knoten> expand2Liste = (LinkedList<Knoten>)expandListe.clone();
+                for (Knoten t:expand2Liste)
                 {
-                    kc=knotenListeC.get(c);
-                    if (kc.is(ziel)) 
-                        System.out.println("GEFUNDEN C");
-                    knotenListeD = trs.expandKnoten(kc);
-
-                    for (int d=0; d<knotenListeD.size(); d++)
+                    if (t.get_heuristik() > maxTiefe) 
                     {
-                        kd=knotenListeD.get(d);
-                        if (kd.is(ziel))
-                            System.out.println("GEFUNDEN D");
-                        knotenListeE = trs.expandKnoten(kd);
-
-                        for (int e=0; 
-                                e<knotenListeE.size(); e++)
-                        {
-                            ke=knotenListeE.get(e);
-                            if (ke.is(ziel))
-                                System.out.println("GEFUNDEN E");
-                            knotenListeF = trs.expandKnoten(ke);
-
-                            for (int f=0; 
-                                    f<knotenListeF.size(); f++)
-                            {
-
-                                kf=knotenListeF.get(f);
-                                if (kf.is(ziel))
-                                    System.out.println("GEFUNDEN F");
-                                knotenListeG = trs.expandKnoten(kf);
-
-                                for (int g=0; 
-                                        g<knotenListeG.size(); g++)
-                                {
-
-                                    kg=knotenListeG.get(g);
-                                    if (kg.is(ziel))
-                                        System.out.println("GEFUNDEN G");
-
-                                    knotenListeH = trs.expandKnoten(kg);
-
-                                    for (int 
-                                            h=0; h<knotenListeH.size(); h++)
-                                    {
-
-                                        kh=knotenListeH.get(h);
-
-                                        if (kh.is(ziel))
-                                            System.out.println("GEFUNDEN H");
-
-                                        knotenListeI = trs.expandKnoten(kh);
-
-                                        for 
-                                            (int i=0; h<knotenListeH.size(); h++)
-                                            {
-                                                ki=knotenListeI.get(i);
-                                                if (ki.is(ziel))
-                                                    System.out.println("GEFUNDEN I");
-                                                knotenListeJ = trs.expandKnoten(ki);
-
-                                                for (int j=0; 
-                                                        j<knotenListeJ.size(); j++)
-                                                {
-                                                    kj=knotenListeJ.get(j);
-                                                    if (kj.is(ziel))
-                                                        System.out.println("GEFUNDEN J");
-                                                    knotenListeK = trs.expandKnoten(kj);
-
-                                                    for (int k=0; 
-                                                            k<knotenListeK.size(); k++)
-                                                    {
-
-                                                        kk=knotenListeK.get(k);
-                                                        if (kk.is(ziel))
-                                                            System.out.println("GEFUNDEN K");
-                                                        knotenListeL = 
-                                                            trs.expandKnoten(kk);
-
-                                                        for (int l=0; 
-                                                                l<knotenListeL.size(); l++)
-                                                        {
-
-                                                            kl=knotenListeL.get(l);
-                                                            if (kl.is(ziel))
-                                                                System.out.println("GEFUNDEN L");
-                                                            knotenListeM = 
-                                                                trs.expandKnoten(kl);
-
-                                                            for (int m=0; 
-                                                                    m<knotenListeM.size(); m++)
-                                                            {
-
-                                                                km=knotenListeM.get(m);
-                                                                if (km.is(ziel))
-                                                                    System.out.println("GEFUNDEN M");
-                                                                knotenListeN 
-                                                                    = trs.expandKnoten(km);
-
-                                                                for (int n=0; 
-                                                                        n<knotenListeN.size(); n++)
-                                                                {
-
-                                                                    kn=knotenListeN.get(n);
-                                                                    if (kn.is(ziel))
-                                                                        System.out.println("GEFUNDEN N");
-
-                                                                    knotenListeO = trs.expandKnoten(kn);
-
-                                                                    for (int o=0; o<knotenListeO.size(); o++)
-                                                                    {
-
-                                                                        ko=knotenListeO.get(o);
-                                                                        if (ko.is(ziel))
-                                                                            System.out.println("GEFUNDEN O");
-
-                                                                        knotenListeP = trs.expandKnoten(ko);
-
-                                                                        for 
-                                                                            (int p=0; p<knotenListeP.size(); p++)
-                                                                            {
-
-                                                                                kp=knotenListeP.get(p);
-
-                                                                                if (kp.is(ziel))
-                                                                                    System.out.println("GEFUNDEN P");
-
-                                                                                knotenListeQ = trs.expandKnoten(kp);
-
-
-                                                                                for (int q=0; q<knotenListeQ.size(); q++)
-                                                                                {
-
-                                                                                    kq=knotenListeQ.get(q);
-
-                                                                                    if (kq.is(ziel))
-                                                                                        System.out.println("GEFUNDEN Q");
-
-                                                                                    knotenListeR = trs.expandKnoten(kq);
-
-
-                                                                                    for (int r=0; r<knotenListeR.size(); r++)
-
-                                                                                    {
-
-                                                                                        kr=knotenListeR.get(r);
-
-                                                                                        if (kr.is(ziel))
-                                                                                            System.out.println("GEFUNDEN R");
-
-                                                                                        // knotenListeS = trs.expandKnoten(kr); 
-                                                                                    }
-                                                                                }
-                                                                            }
-
-                                                                    }
-
-                                                                }
-                                                            }
-                                                        }
-                                                    }
-                                                }
-                                            }
-                                    }
-                                }
-                            }
-                        }
+                        expandListe.remove(t);
                     }
                 }
+                schichtListe.addAll(expandListe);
             }
+            else tiefe8 = true;
+            //auf keinen Fall sortieren, Breitensuche und Luftheuristik beißen sich
+	    //Collections.sort(schichtListe);
         }
-
-        ////////////////// ENDE TIEFENSUCHE
+        
+        // nun enthällt schichtListe alle Knoten der Tiefe 7
+        // und wir beginnen mit A* LuftlinienHeuristik
+        Runtime rt = Runtime.getRuntime();
+        System.out.println("Schicht 7 vollständig entwickelt mit "+schichtListe.size()+" Knoten");
+        System.out.println(rt.totalMemory()+" von "+rt.maxMemory()+" belegt");
+        
+        //zunächst schichtListe nach LuftlinienHeuristik sortieren
+        Knoten.setHeuristikTyp(Knoten.HEURISTIK_LUFT);
+        for (Knoten k: schichtListe){
+            k.computeHeuristik();
+        }
+        Collections.sort(schichtListe);
+        
+        //nun für jeden Knoten der Schicht 7 jeweils A* ausführen
+        int fortschritt=0;
+        for (Knoten k : schichtListe) {
+            if ((float)schichtListe.indexOf(k)/(float)schichtListe.size()*100 >= fortschritt)
+            {
+                if (fortschritt%10 == 0) System.out.print("*");
+                else System.out.print(".");
+                fortschritt++;
+            }
+            LinkedList<Knoten> knotenListe = new LinkedList<Knoten>();
+            knotenListe.addAll(trs.expandKnoten(k));
+            Knoten l = null;
+            while (knotenListe.size()>0 && knotenListe.getFirst().get_tiefe()<15 ){
+                l = knotenListe.poll();
+                expandListe = trs.expandKnoten(l);
+                pfad = testZiel(expandListe,true);
+                if (pfad.size()> 0 && pfad.size()-1 < maxTiefe) return pfad.size()-1;
+                //knoten löschen die zu weit vom ziel entfernt sind
+                LinkedList<Knoten> expand2Liste = (LinkedList<Knoten>)expandListe.clone();
+                for (Knoten t:expand2Liste)
+                {
+                    if (t.get_heuristik() > maxTiefe) 
+                    {
+                        expandListe.remove(t);
+                    }
+                }
+                knotenListe.addAll(expandListe);
+                Collections.sort(knotenListe);
+            }
+        }
+        return 0;
     }
 
+    
+
 }
 
-- 
2.11.4.GIT