AuK/Greedy-Algorithmen SS10/Java-Programm

Wiki-Quelltext dieser Seite.

<language>Java</language>
<code id="4be93e7d6c1bf">/* Wichtig: in der Form {A,B,C,D,E,F,G}*/
        int []StadtA        ={0,4,9,10000,10,6,10000};
        int []StadtB        ={4,0,3,10000,10000,10000,5};
        int []StadtC        ={9,3,0,8,10000,10000,6};
        int []StadtD        ={10000,10000,8,0,3,9,3};
        int []StadtE        ={10,10000,10000,3,10000,10000,0};
        int []StadtF        ={6,10000,10000,9,10000,0,7};
        int []StadtG        ={10000,5,6,3,10000,7,0};
        int []auswahl       =new int[7];

        int tempPfad                =0;
        int lauf                    =1;
        int zähler                  =0;
        int set                     =1;
        int k                       =0;
        int letztesElement          =0;
        int tempElement             =0;
        int neuerWert               =0;
        int []letzteStadt           =new int [20];
        ArrayList<Integer> Pfad=new ArrayList();
        Pfad.add(0);
 /*beginn der Prozedur*/

while(lauf==1){



 switch(zähler){
     case 0:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtA[i];
            };break;
     case 1:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtB[i];
            };break;
     case 2:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtC[i];
            };break;
     case 3:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtD[i];
            };break;
     case 4:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtE[i];
            };break;
     case 5:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtF[i];
            };break;
     case 6:for(int i=1;i<auswahl.length;i++){
                auswahl[i]=StadtG[i];
            };break;
 }

             //Greedy_Algorithmus
//==============================================================================
            for(int i=0;i<auswahl.length;i++){
            //Prüfung ob die jeweilige Stadt breits besucht wurde(nur einmal pro Stadt)
              for(int j=0; j<letzteStadt.length;j++){
                 if(letzteStadt[j]==i){
                     set=0;
                 }
              }
            //einfügen des Pfades in tempPfad sollte obige Bedingung erfüllt sein
              if(tempPfad>=auswahl[i] && auswahl[i]!=0 || tempPfad==0){
                 if(set==1){
                 tempPfad=auswahl[i];
                 zähler=i;
                 }
              }
              //zurücksetzten der Variable set für den nächsten Durchlauf
              set=1;
            }

            //hinzufügen der besuchten Stadt
 //=============================================================================
            //benötigt man zur Pfadmodifizierung
             letztesElement=letztesElement+tempPfad;
             Pfad.add(letztesElement);
            //Pfad wir, falls nötig, modifiziert um die kürzeste Strecke zu suchen
             for(int i=1; i<Pfad.size();i++){
                 if(Pfad.get(i)+auswahl[letzteStadt[i]]<tempElement && k>=1 && auswahl[letzteStadt[i]]!=0){
                      neuerWert=Pfad.get(i)+auswahl[letzteStadt[i]];
                         for(int j=i;j<=Pfad.size();j++){
                             Pfad.remove(Pfad.size()-1);
                         }             
                     Pfad.add(neuerWert);
                     Pfad.add(neuerWert+tempPfad);
                 }
             }
                        
                        letzteStadt[k+1]=zähler;
                      
                        tempElement=tempElement+tempPfad;
                        k++;
                        //System.out.println("auswahl :"+tempElement);
                        tempPfad=0;
                        
//Prüfung ob Stadt breits erreicht wurde
//==============================================================================
            for(int i=0;i<letzteStadt.length;i++){
                if(letzteStadt[i]==3){
                System.out.println(Pfad);
                  lauf=0;
                }
            }

        }
</code>