Avoir un tableau de nombres aléatoires pour le PVC

Version imprimable

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:

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.

07/12/2012, 01h04
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 !
07/12/2012, 01h10
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.

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

Je te propose une implémentation :

Code:

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.

07/12/2012, 04h03
naou18

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

Code:

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;
	}

07/12/2012, 11h15
naou18

Merci pour votre réponse.
Est ce que je peux avoir une explication du code que vous avez écrie sachant que vous n'avez pas utilisé mon tableau de départ?
Une autre chose quelle est la différence entre Math.random() * n par exemple et la classe Random que tu a utilisé?

Pour la différence entre Math et Random :
http://docs.oracle.com/javase/7/docs...lang/Math.html

http://docs.oracle.com/javase/7/docs...il/Random.html

Pour le code :

Code:

1
2
3
4
5
6
7
8
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);
// Basiquement l'index +1 de manière systématique : Apport d'information de la valeur faible
	return new Chemin(tab, chemin(tab, matr));
		}

Code:

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
/**
         * @param args
         */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//Initialisation 
		int[] test = new int[10];
		Random randomer = new Random();
		for (int i = 0; i < test.length; i++) {
			// on ajoute 1 au random pour ne pas correspondre à la valeur 0
			// Car 0 est la valeur d'initalisation et donc déjà dans le tableau
			// On peut remplacer cela par une initialisation du tableau à -1 par exemple
			int value = 1+randomer.nextInt(10);
			// On prend un valeur au hasard dans la plage voulu
			while (tableContains(test, value)) {
 				//Si elle est déjà dans le tableau on en cherche une autre
				// Jusqu'à en avoir une qui n'est pas dans le tableau
				// D'où le +1 pour n pas avoir 0 qui est déjà dans le tableau
				value = 1+randomer.nextInt(10);
			}
			test[i]= value;
		}
		On affiche le tableau pour voir quelque chose dans la console
		for (int i = 0; i < test.length; i++) {
			System.out.print(":"+test[i]);
		}
	}
 
	/*
	 * Methode perso pour vérifier si une valeur se trouve dans notre tableau
	*/
	private static boolean tableContains(int[] table, int value) {
		for (int i = 0; i < table.length; i++) {
			if(table[i]==value){
				return true;
			}
		}
		return false;
	}

Une autre approche qui m'est venue à l'esprit, pour le fun (quoique potentiellement plus efficace ?) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int n = 21; int[] tab = new int[n];; Arrays.fill(tab, 0); int tenFactor = String.valueOf(n).length(); int r; boolean done; for (; n > 0; n--) { done = false; while(!done) { r = (int)(Math.random() * Math.pow(10, tenFactor)); if(r < tab.length && tab[r] == 0) { tab[r] = n; done = true; } } }
L'idée étant d'utiliser les premiers chiffres après la virgule du double généré par random(), d'où la multiplication par une puissance de 10 via tenFactor ainsi que de ne pas reparcourir le tableau pour tester si une valeur existe déjà mais de se baser plutôt sur l'index.

07/12/2012, 14h56
professeur shadoko

java.util.Collections.shuffle?

Très bonne idée :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
		Integer[] test = new Integer[10];
		for (int i = 0; i < test.length; i++) {
			test[i]=new Integer(i);
		}
		List<Integer> listDate = new ArrayList<Integer>(Arrays.asList(test));
		Collections.shuffle(listDate);
		System.out.println(listDate);
 
		test = (Integer[]) listDate.toArray(new Integer[10]);
 
		for (int i = 0; i < test.length; i++) {
			System.out.print(test[i]);
		}

http://docs.oracle.com/javase/7/docs...util.Random%29

Citation:

Envoyé par professeur shadoko

java.util.Collections.shuffle?

Je la trouvais pas dans util.Arrays celle-là, et pour cause :D

Le problème est intéressant, pour info :) :
pas besoin de créer une liste temporaire supplémentaire :

Code:

Collections.shuffle(Arrays.asList(test));

D'autant plus que dans le JDK 6, le code source de Collections.shuffle() qui utilise swap() converti la liste en tableau pour swaper les index puis reconverti le tableau en liste...
Bref pour les perfs, ce qui peut s'avérer important lors de la résolution de "problèmes" (genre backtracking ou autre), ceci semble l'une des meilleures soluces, ce que fait Collections.shuffle() mais sans les conversions/copies (temps divisé par 10 pour n = 999999) :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int n = 999999; int[] arr = new int[n]; // Remplissage du tableau for (int i = 0; i < arr.length; i++) { arr[i] = i + 1; } // Shuffle for (int i = arr.length; i > 1; i--) { int old = arr[i - 1]; int index = (int) (Math.random() * i); // swap arr[i - 1] = arr[index]; arr[index] = old; }
(Je me demande aussi si l'une ou l'autre des méthodes proposées offre une meilleure équiprobabilité)

Voila j'ai trouvé ce que je cherche :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
// remplir un tableau avec les nombres 1 2 3 . . . n
int[] numbers = new int[n];
for (int i = 0; i < numbers.length; i++)
numbers[i] = i + 1;
// tirer n nombres et les mettre dans un second tableau
int[] result = new int[n];
for (int i = 0; i < result.length; i++)
{
// créer un indice aléatoire entre 0 et n - 1
int r = (int)(Math.random() * n);
// choisir l’élément à cet emplacement aléatoire
result[i] = numbers[r];
// déplacer le dernier élément vers l’emplacement aléatoire
// c'est la qu'il y a un peu de difficulté à comprendre 
numbers[r] = numbers[n - 1];
n--;
}

Merci de votre aide précieux.
Cependant je ne sais pas si c'est pratique côté performance.
Quelqu'un à une idée?

08/12/2012, 01h40
kolodz

Ton algo est du type o(n). (Bien pensé au passage)
On peut difficilement faire mieux.

Cordialement,
Patrick Kolodziejczyk.

Salut,

Tout d'abord, on ne doit pas accepter des doublons.

J'étais sur le point de te proposer la méthode suivante quand j'ai constaté que tu en avais trouvé une du même type. Je te la passe quand même:

Code:

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
 
      public static int[] nombresAlea2(int[] tabDepart)
      {
      /** valeurs min et max des nombres aléatoires sont en fait les 6 numéros (0 a 5)
        * des éléments à extraire aléatoirement du tableau de départ (dans notre cas 0 à 5)
        */
         int min = 0;
         int max = tabDepart.length -1;
 
         String lesNombresAlea = "";
 
         int nbreVal = ((max - min) +1);
      /** sera la taille du tableau résultat( en fait, la même taille que celle du tableau départ).
        */
 
         int[] resultat = new int[nbreVal];
 
         for (int i1 = 0; i1 <nbreVal; i1++)
         {
         //LES NOMBRES ALÉATOIRES TROUVÉS SONT LES INDICES D'ACCÈS AUX ÉLÉMENTS DU TABLEAU tabDepart[]
            Random r = new Random();
            int aI = min + r.nextInt(nbreVal); //le nombre trouvé
            if(lesNombresAlea.indexOf(Integer.toString(aI)) > -1) // c'est un doublon
            {
               System.out.println("Le nombre trouvé " + aI + " est un doublon qu'on ignore !!!");
               i1--;
            }
            else
               lesNombresAlea+= aI + " ";
         }
         lesNombresAlea = lesNombresAlea.trim();
         System.out.println("Les nombres aléatoires 2: " + lesNombresAlea);
         String[] result = lesNombresAlea.split(" +");
         //for(String res : result) System.out.println(res);
 
         for(int i = 0; i <nbreVal;i++)
         {
            resultat[i] = tabDepart[Integer.parseInt(result[i])];
            System.out.println("resultat[i] = " + resultat[i]);
         }
         return resultat; // tabDepart = {1,2,3,4,5,6}
      }

Appel de la méthode:

Code:

1
2
3
4
5
6
7
8
9
 
            int[] tabDepart = {1,2,3,4,5,6};
 
            mini = 0;
            maxi = tabDepart.length -1;
            System.out.println("maxi = " + maxi);
 
         	//Appel de la méthode
            int[] tabResult = nombresAlea2(tabDepart);

Cordialement,

Dan