Probleme java heap space

**arno15** · 27/11/2007, 18h30

Bonjour à tous

je développe en ce moment un petit programme censé calculé une solution au problème du voyageur de commerce (Trading Salesman Problem).
Pour ce faire , ma classe prend en entrée une Arraylist contenant les villes , elle calcule ensuite toutes les permutations possible qu'elle placent dans une autre ArrayList (...

) et cherche ensuite celle dont la longueur est la plus courte.

Pour un jeu de 9 villes tous se passe bien, mais dès qu'on passe la barre des 9 villes j'obtiens le message d'erreur suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.ArrayList.<init>(ArrayList.java:136)
        at tsp.Arraylist.<init>(Arraylist.java:25)
        at tsp.Permutations.<init>(Permutations.java:30)
        at tsp.OptimalTspCourse.<init>(OptimalTspCourse.java:29)
        at tsp.Main.main(Main.java:133)

Bien sur je connais plus ou moins la raison de ce problème... ( pour 10 villes il y a 10! soit environ 3 500 000 possibilités, ce qui fait un très gros tableau ).
Mais si quelq'un a une idée pour pouvoir optimiser un peu le code et être capable de calculer le parcours pour un peu plus de villes ca serait bien, il faudrait que je réussisse à le faire tourner pour 15villes.

Je vous mets mes classes pour que vous puissiez regarder. les plus importantes sont les Classes Permutations et OptimalTspCourse

Classe ville et TSPville :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
package tsp;
 
/**
*Cette classe définit une ville par des coordonnées dans un plan et un nom.
*
*@since 18/11/07
*@version 1.0 11/07
* @author LEFEBVRE
*/
public class ville {
 
 
	private int x;
	private int y;
	private String name;
 
   /** Creates a new instance of ville */
	public ville()
	{
		x = 0;
		y = 0;
		name = "automaticname";	
	}
 
	public ville(int xc , int yc )
	{
		x = xc;
		y = yc;
		name = "automaticname";
	}
 
	public ville(int xc , int yc , String nom)
	{
		x = xc;
		y = yc;
		name = nom;		
	}
 
	public int getX()
	{
		return x;
	}
 
	public int getY()
	{
		return y;
	} 
 
	public String getName()
	{
		return name;
	}
 
	public void display()
	{
		System.out.println("Absicce : "+x);
		System.out.println("ordonnée : "+y);
		System.out.println("Nom : "+name);
	}
 
	public void setX(int xc)
	{
		x = xc;
	}
 
	public void setY(int yc)
	{
		y = yc;
	}
 
	public void setName(String nom)
	{
		name = nom;
	}
 
	public void setCoord(int xc , int yc)
	{
		setX(xc);
		setY(yc);
	}
        public void setAll(int xc, int yc, String nom)
        {
            setX(xc);
            setY(yc);
            setName(nom);
        }
 
}
 
package tsp;
 
/**
*Cette classe définit une ville par des coordonnées dans un plan et un nom.
*elle possède également un indicateur de parcours afin d'indiquer si on est déja passer par cette ville
*
*@since 18/11/07
*@version 1.0 11/07
*@author LEFEBVRE Arnaud  
*/
public class TSPville {
 
 
        private ville city;
	private boolean prc;
 
    /** Creates a new instance of TSPville */       
	public TSPville()
	{
		city = new ville();
		prc = false;	
	}
 
	public TSPville(int xc , int yc )
	{
		city = new ville(xc,yc);
		prc = false;
	}
 
	public TSPville(int xc , int yc , String nom)
	{
		city = new ville(xc,yc,nom);
		prc = false;	
	}
 
        public TSPville(int xc, int yc ,String nom, boolean b)
        {
		city = new ville(xc,yc,nom);
		prc = b;            
        }
 
        public TSPville(TSPville v)
        {
            city = new ville(v.getX(),v.getY(),v.getName());
            prc = v.getPrc();
        }
 
	public int getX()
	{
		return city.getX();
	}
 
	public int getY()
	{
		return city.getY();
	} 
 
	public String getName()
	{
		return city.getName();
	}
 
	public boolean getPrc()
	{
		return prc;
	}
 
	public void display()
	{
		System.out.println("Absicce : "+getX());
		System.out.println("ordonnée : "+getY());
		System.out.println("Nom : "+getName());
	}
 
	public void setX(int xc)
	{
		city.setX(xc);
	}
 
	public void setY(int yc)
	{
		city.setY(yc);
	}
 
	public void setName(String nom)
	{
		city.setName(nom);
	}
 
	public void setCoord(int xc , int yc)
	{
		city.setX(xc);
		city.setY(yc);
	}
 
	public void setPrc(boolean b)
	{
		prc = b;
	}
 
        public void setAll(int xc, int yc, String nom)
        {
		city.setX(xc);
		city.setY(yc);
                city.setName(nom);
        }
 
        public TSPville clone()
        {
            return new TSPville(getX(),getY(),getName(),prc);
        }
 
        public boolean equals(Object o)
        {
             if (!(o instanceof TSPville))
             return false;
             else 
             {
                 boolean result=true;
                 TSPville v = (TSPville) o;
                 if (! (v.getX() == this.getX()))
                 {
                     result = false;
                 }
                 else if (!(v.getY() == this.getY()))
                 {
                     result = false;
                 }
                 else if   (!(this.getName().equalsIgnoreCase(v.getName())))
                 {
                     result  = false;
                 }
                 else if  (! (this.prc == v.getPrc() ) )
                 {
                     result = false;
                 }
                 return result;
             }
        }
 
        public String toString()
        {
            return (getName()+"("+getX()+","+getY()+")"+"ST:"+getPrc());
        }
 
}

Classe Arraylist (surcharge de ArrayList pour l'opération de clonage) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package tsp;
import java.util.*;
/**
 *
 * @author LEFEBVRE
 */
public class Arraylist extends ArrayList{
 
    /** Creates a new instance of Arraylist */
    public Arraylist() {
        super();
    }
 
    public Arraylist(Arraylist p)
    {
        super(p);
    }
 
    public Arraylist clone()
    {
        Arraylist result = new Arraylist();
        Iterator i = this.iterator();
        while (i.hasNext())
        {
            TSPville v = (TSPville) i.next();
            result.add(v.clone());
        }
        return result;
    }
 
    public void displayville()
    {
        Iterator i = this.iterator();
        while (i.hasNext())
        {
            Object o = i.next();
            if (o instanceof TSPville)
            {
                TSPville v = (TSPville) o;
                System.out.println(v);
            }
            else if (o instanceof Arraylist)
            {
                Arraylist l = (Arraylist) o;
                System.out.println(l);
            }
        }
    }
}

Classe permutation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package tsp;
 
/**
 *
 * @author LEFEBVRE
 */
public class Permutations {
 
    private Arraylist origine;
    private Arraylist permutations;
 
    /** Creates a new instance of Permutations */
    public Permutations(Arraylist p) 
    {
        origine = new Arraylist(p);
        permutations = new Arraylist();
        int nb = fact(p.size());
        System.out.print("CALCUL DES PERMUTATIONS EN COURS :  \\ : 0%");
        for (int i = 0 ; i < nb ; i++)
        {
            Arraylist per = new Arraylist(origine);
            Permutation(i,per);
            permutations.add(per);
            if (i%5==0)
            working(i,nb);
 
        }
    }
 
    private int fact(int k)
    {
        int result =  1;
        for(int i = 0; i < k ; i++)
        {
            result = result * (k-i);
        }
        return java.lang.Math.abs(result);
    }
 
    private Arraylist Permutation (int k)
    {
        Arraylist result = new Arraylist(origine);
        int fact = 1;
        for (int i = 2 ;  i < origine.size() ; i++)
        {
            fact = fact*(i-1);
            int pos = i - ( (k/fact) % i ) - 1;
            swap(pos,i,result);
        }
        return result;
    }
 
    private void Permutation (int k,Arraylist r)
    {
        //Arraylist result = new Arraylist(origine);
        int fact = 1;
        for (int i = 2 ;  i < origine.size() ; i++)
        {
            fact = fact*(i-1);
            int pos = i - ( (k/fact) % i ) - 1;
            swap(pos,i,r);            
        }
        //return result;
    }
 
    private void swap(int i, int j,Arraylist A)
    {
        Object oi = A.get(i);
        Object oj = A.get(j);
        A.set(j,oi);
        A.set(i,oj);        
    }
 
    public void display()
    {
        permutations.displayville();
        System.out.println(""+permutations.size()+" permutations trouvées au total.");
    }
 
    public Arraylist getPermutations()
    {
        return permutations;
    }
 
    public Arraylist getPermutation(int index)
    {
        return (Arraylist) permutations.get(index);
    }
 
    public int getNbPermutations()
    {
        return permutations.size();
    }
    public void working(int i,int end)
    {
        String [] load = {"-","\\" ,"|" ,"/" };
        int k = (i*100)/end;
        if (k <10)
            System.out.print("\b\b\b\b\b\b");
        else
            System.out.print("\b\b\b\b\b\b\b");
        System.out.print(""+load[i%4]+" : "+k+"%");
    }
}

Classe getOptimalTSPCourse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package tsp;
import java.util.*;
 
/**
 *
 * @author LEFEBVRE
 */
public class OptimalTspCourse {
 
    private Arraylist origine;
    private Arraylist best;
    Permutations pt;
    //private Arraylist permutation;
 
    /** Creates a new instance of OptimalTspCourse */
    public OptimalTspCourse(Arraylist p) 
    {
        origine = new Arraylist(p);
        best = new Arraylist();
        pt = new Permutations(origine);
        //permutation = new Arraylist()
    }
 
    public double FindOptimalTSPCourse()
    {
        Arraylist BEST = new Arraylist(pt.getPermutation(0));
        double result = function.calcLongTSP(BEST);
        for(int i = 1; i < pt.getNbPermutations() ; i++)
        {
            Arraylist t = new Arraylist(pt.getPermutation(i));
            double x = function.calcLongTSP(t);
            if (x<result)
            {
                result = x;
                BEST.clear();
                BEST.add(t);
            }
        }
        best.clear();
        best.add(BEST);
        return result;
    }
 
    public void displayBest()
    {
        System.out.println(best);
        /*Iterator i = best.iterator();
        while(i.hasNext())
        {
            Object o = i.next();
            if (o instanceof TSPville)
            {
                TSPville v = (TSPville) o;
                System.out.println(v);
            }
        }*/
    }
}

Classe des fonctions communes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package tsp;
import java.util.*;
/**
 *
 * @author LEFEBVRE
 */
public class function {
 
    /** Creates a new instance of function */
    public function() {
    }
 
     public static double sqr(double x)
     {
            return (x*x);
     }
 
     public static double Distance(TSPville v1, TSPville v2)
     {
            double XX = sqr( v2.getX() - v1.getX() );
            double YY = sqr( v2.getY() - v1.getY() );
            return java.lang.Math.sqrt( XX+YY );
     }
 
     public static double Distance(int i, int j,Arraylist tovisit)
    {
            TSPville v1 = new TSPville( (TSPville) tovisit.get(i));
            TSPville v2 = new TSPville( (TSPville) tovisit.get(j));
            double XX = sqr( v2.getX() - v1.getX() );
            double YY = sqr( v2.getY() - v1.getY() );   
            return java.lang.Math.sqrt( XX+YY );            
     }
 
 
 
     public static double calcLongTSP(Arraylist parcours)
     {
         double result = 0;
         //String op = ""+result;
         Iterator i = parcours.iterator();
         TSPville first;
         TSPville last = new TSPville();
         if (! parcours.isEmpty())
         {
             first = (TSPville) i.next();
             last = first.clone(); 
 
         while (i.hasNext())
         {
             TSPville v = (TSPville) i.next();
             result = result + function.Distance(last,v);
             //op = op + " + "+function.Distance(last,v);
             last = v.clone();
         }
         result = result + function.Distance(last,first);
         }
         //System.out.println(op);
         //writelog(op);
         return result;
     }   
}

et enfin le main :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package tsp;
import java.util.*;
/**
 *
 * @author LEFEBVRE
 */
public class Main {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) 
    {
                Arraylist t = new Arraylist();
                TSPville v1 = new TSPville(0,0,"V1");
                TSPville v2 = new TSPville(0,5,"V2");
                TSPville v3 = new TSPville(5,0,"V3");
                TSPville v4 = new TSPville(10,0,"V4");
                TSPville v5 = new TSPville(0,10,"V5");
                TSPville v6 = new TSPville(5,5,"V6");
                TSPville v7 = new TSPville(5,10,"V7");
                TSPville v8 = new TSPville(10,5,"V8");
                TSPville v9 = new TSPville(10,10,"V9");
                TSPville v10 = new TSPville(0,15,"V10");
                t.add(v1);
                t.add(v2);
                t.add(v3);
                t.add(v4);
                t.add(v5);
                t.add(v6);
                t.add(v7);
                t.add(v8);
                t.add(v9);
                t.add(v10);
                OptimalTspCourse tc = new OptimalTspCourse(t);
                System.out.println("Distance du meilleur parcours : "+tc.FindOptimalTSPCourse());
                tc.displayBest();

Voila j'espère que vous pourrez m'aider, et merci d'avance

**BugFactory** · 27/11/2007, 18h38

Le problème n'est pas le code, mais l'algorithme. Le problème du voyageur de commerce est assez célèbre pour ça. Vous n'y arriverez jamais avec une recherche exhaustive.

Bon courage.

**arno15** · 27/11/2007, 18h46

je sais que ce genre de probleme ne pourra etre résolu avec un tel algorithme, mais dans le cadre d'un projet je dois proposer un algorithme optimal (celui que j'ai posté), des algorithmes d'approximation ainsi que des heuristiques.
je dois également pouvoir mesurer la distance entre les solutions de chacun des algorithmes, c'est pourquoi je dois absolument utiliser cette algorithme ...

**BugFactory** · 27/11/2007, 19h08

Envoyé par arno15

mais dans le cadre d'un projet je dois proposer un algorithme optimal (celui que j'ai posté)...

Une minute, l'algorithme que vous avez posté, c'est bien la recherche exhaustive? Parce que si c'est le cas c'est très loin d'être un algorithme optimal.

**arno15** · 27/11/2007, 22h37

et bien, c'est un algorithme qui vérifie chacune des possibilités, une par une, dans leur totalité,

Il y a plusieurs optimisations auquel j'ai pensé, comme par exemple diviser par 2 le nombre 2 possibilité en éliminant l'inverse des parcours, où encore ne plus vérifier la longueur d'un parcours quand celle ci à déja dépassé la plus petite déja trouvé, mais je ne suis pas convaincu de leur éfficacité...

je me suis aussi demandé si je n'avais pas fait un mauvais choix au niveau de la "collection" ArrayList...

En tout cas, je cherche

PS : c'est un projet de fac que je rend

Voila, merci pour votre aide

**ToTo13** · 28/11/2007, 09h52

Bonjour,

si vous faites un peu de recherche sur le problème du voyageur de commerce, vous vous appercevrez que la recherche exhaustive est quasiment impossible...
Dans tous les ce problème est plutôt pour le forum "algorithmes".

On est obligé d'utiliser des heuristiques ou méta heuristiques telles que le recuit simulé ou maintenant la méthode tabou.

Toutefois, si vous vous obstinez sur une recherche exhaustive (peut être ne connaissez vous que cette méthode) il y a différentes possibilités pour améliorer la recherche :
- Commencer à chaque étape par trier les voisins par ordre croissant au sens de la distance.
- C'est vrai que c'est très coûteux au début, mais en général, dans la solution optimale on va souvent vers le voisin le plus prôche... Mais cela permettra de rapidement supprimer de nombreuses branches de votre arbre de recherche.
- Sur le même raisonnement, après avoir trié els voisins par ordre croissant, on peut se permettre de ne parcourrir à chaque étape que la moitié de l'arbre.

Probleme java heap space

Langage Java

Discussions similaires

Partager

Partager