Discussion :

[naou18]

Bonjour,

J'ai besoin de votre aide.
Je travail sur le probléme du voyageur du commerce -- PVC.
Pour le moment je dois géner aleatoirement une solution (c a d d'un chemin ) et afficher de son coût.
La solution qui m'ai venu à l'esprit c'est de créer deux tableaux, le 1er contient des élements successive, par exemple le tableau du départ [1,2,3,4,5,6] qui représent un chemin d'un certain coût, étant donné que l'élement 1-->représente la ville 1, ainsi de suite .

Le deuxiéme tableau dois contient d'autre chemin possible avec les mêmes villes, qui sont génerer d'une manière aléatoire.
par exemple tableau d'arrivé après l'appele à la méthode aléatoire [3,2,1,6,5,4].
Voila la signature de ma méthode.

Code :

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

1
2
3
4
5
6
7
8
9
public static Chemin aleatoire(int n) {
		int[] t = new int[n];
		int[] tab = new int[n];
		for (int i = 0; i < n; i++) {
			t[i] = (i + 1);
// la je dois remplire le tableau tab avec des valeurs aléatoires comme dans l'exemple.
 
	return new Chemin(tab, chemin(tab, matr));
		}

Qu'est ce que je dois faire pour avoir ce tableau avec les mêmes villes, mais d'une manière aléatoire.
Merci d'avance.

[mouddene]

Bonjour,
je ne comprends pas très bien , je ne sais si tu veux savoir comment générer des arcs aleatoires entre tes villes ou autre chose, car le problème du voyageur reste assez complexe, une meilleure solution soit les solvers ou un langage fonctionnel comme prolog par exemple !

[naou18]

Je veux uniquement savoir comment remplir le tableau avec les éléments que j'ai d'une manière aléatoire.
Pour l'implémentation c'est en langage Java.
Je sais que je dois utiliser Math.Random(), mais je ne sais pas comment, car le tableau ne dois contenir que les éléments du tableau du départ.

[kolodz]

Je te conseil la méthode sort avec un "Comparator" aléatoire.

Je te propose une implémentation :

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
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
 
public class Test implements  Comparator<Integer> {
	private int baseSeed;
 
	public Test(int baseSeed) {
		this.baseSeed = baseSeed;
	}
 
	/**
         * @param args
         */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Test test = new Test(4451);
		Integer[] myArray = new Integer[1000];
		for (int i = 0; i < myArray.length; i++) {
			myArray[i] = new Integer(i);
		}
		Arrays.sort(myArray, test);
		for (Integer integer : myArray) {
			System.out.print(":"+integer);
		}
 
	}
 
	@Override
	public int compare(Integer arg0, Integer arg1) {
		Random rand = new Random(baseSeed+arg0.intValue()+arg1.intValue());
		int toReturn = rand.nextInt(3)-1;
		return toReturn;
	}
 
}

C'est du pseudo-aléatoire, tout est déterminé par la clé que tu donne au début.
Si un puriste passe dans le coin, il te dira que ce n'est pas géniale comme procédé. Mais cela fait son office.

Cordialement,
Patrick Kolodziejczyk.

[naou18]

Merci pour votre conseil.
Mais je préfère ma méthode, sauf que je ne sais pas comment y arrivé.

[kolodz]

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
/**
         * @param args
         */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] test = new int[10];
		Random randomer = new Random();
		for (int i = 0; i < test.length; i++) {
			int value = 1+randomer.nextInt(10);
			while (tableContains(test, value)) {
 
				value = 1+randomer.nextInt(10);
			}
			test[i]= value;
		}
		for (int i = 0; i < test.length; i++) {
			System.out.print(":"+test[i]);
		}
	}
 
	private static boolean tableContains(int[] table, int value) {
		for (int i = 0; i < table.length; i++) {
			if(table[i]==value){
				return true;
			}
		}
		return false;
	}