Discussion :

[Mindiell]

Intéressant.
J'ai repris le code de Sylvain Togni en l'accélérant :

La plus grande boite est la 997,979,997 avec un volume de 973134811

Process returned 0 (0x0) execution time : 0.093 s
Press any key to continue.

La grosse différence étant, je pense que ma structure est faite ainsi :

Code :

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

1
2
3
4
5
6
7
struct Box
{
    unsigned int x;
    unsigned int y;
    unsigned int z;
    unsigned long volume;
};

Ce qui me permet de calculer le volume au fur et à mesure du chargement des boites. Ainsi le tri ne fera pas plusieurs calculs de volume à chaque comparaison.

Je me penche sur le problème du voyage

[Golgotha]

Merci Mindiell pour cette contribution.

Je te laisse découvrir le défi en cours.

Pour le moment seule deux participants on trouvés la solution pour ce défi qui demande beaucoup de réflexion.

Le défi actuel se terminera Dimanche soir, et le nouveau défi sera dévoilé lundi.

[JeitEmgie]

FYI

une solution open-source comme LKH trouve la solution en moins de 10 msec :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
time ./LKH golgoth.par 
PARAMETER_FILE = golgoth.par
PROBLEM_FILE = golgoth.tsp
Successes/Runs = 1/0 
Cost.min = 89187, Cost.avg = 89187.00, Cost.max = 89187
Gap.min = 0.000%, Gap.avg = 0.000%, Gap.max = 0.000%
Trials.min = 0, Trials.avg = 0.0, Trials.max = 0
Time.min = 0.0 sec., Time.avg = 0.0 sec., Time.max = 0.0 sec.
 
real	0m0.007s
user	0m0.004s
sys	0m0.002s

le résultat :

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
 
NAME : golgoth.89187.tour
COMMENT : Length = 89187
COMMENT : Found by LKH [Keld Helsgaun]
TYPE : TOUR
DIMENSION : 30
TOUR_SECTION
1
25
20
7
5
2
12
14
19
16
28
18
27
9
22
6
8
10
3
4
17
26
24
23
21
30
11
15
13
29
-1
EOF

Notez qu'elle fait les calculs intermédiaires en entier et non float, donc il faut encore recalculer la longueur exacte à la sortie…
et qu'elle numérote de 1 à N… et donc la solution est bien la même que celle précédemment trouvée…

[philben]

bonjour,

Probleme tsp symétrique (cycle hamiltonien) résolu en 31ms en VBA avec distances en double précision grâce à l'algorithme 2-Opt :

Temps (ms) : 31
0 Planete n°0
1 Planete n°24
2 Planete n°19
3 Planete n°6
4 Planete n°4
5 Planete n°1
6 Planete n°11
7 Planete n°13
8 Planete n°18
9 Planete n°15
10 Planete n°27
11 Planete n°17
12 Planete n°26
13 Planete n°8
14 Planete n°21
15 Planete n°5
16 Planete n°7
17 Planete n°9
18 Planete n°2
19 Planete n°3
20 Planete n°16
21 Planete n°25
22 Planete n°23
23 Planete n°22
24 Planete n°20
25 Planete n°29
26 Planete n°10
27 Planete n°14
28 Planete n°12
29 Planete n°28
Longueur totale : 89188,648014912

cordialement,

Philippe

[Bucketpc]

bonjour,

Probleme tsp symétrique (cycle hamiltonien) résolu en 31ms en VBA avec distances en double précision grâce à l'algorithme 2-Opt :



cordialement,

Philippe

Pourriez vous, expliquer le principe de l'algorithme 2-Opt en quelques mots ?

[philben]

Pourriez vous, expliquer le principe de l'algorithme 2-Opt en quelques mots ?

Il l'a mieux expliqué que je ne saurais le faire :
http://www.crdp.ac-grenoble.fr/imel/jlj/pvc/2opt.htm

Philippe

[Golgotha]

Bonjour,

Le défis n°2 est clôt, Merci aux participants !

Je vous laisse découvrir le défi n°3 sur mon blog.

http://blog.developpez.com/cs-blog/

Bon codage.

[philben]

bonjour,

bon ben je me lance pour le défi 3

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
 
Classe n°1:    983 
Classe n°2:    1401 
Classe n°3:    1909 
Classe n°4:    115 
Classe n°5:    566 
Classe n°6:    1 
Classe n°7:    1209 
Classe n°8:    1152 
Classe n°9:    647 
Classe n°10:   1947 
Classe n°11:   1947 
Classe n°12:   2770 
Classe n°13:   2960 
Classe n°14:   1600 
Classe n°15:   497 
Classe n°16:   111 
Classe n°17:   155 
Classe n°18:   0 
Classe n°19:   36 
Classe n°20:   626 
Temps : 702ms

Philippe

[Sylvain Togni]

Attention, dans le format du fichier le premier nombre est la hauteur et le deuxième la largeur, pas l'inverse !

[Golgotha]

Attention, dans le format du fichier le premier nombre est la hauteur et le deuxième la largeur, pas l'inverse !

Oui, j'avais mis la longueur, mais la hauteur c'est plus parlant. merci de la précision.

exemple :

5 8
....x...
.x..x...
xx.x..x.
..x.x...
.xx....x

La Hauteur est de 5, la largeur est de 8

[philben]

bonjour,

Attention, dans le format du fichier le premier nombre est la hauteur et le deuxième la largeur, pas l'inverse !

On a pas le droit d'orienter éventuellement la classe dans le sens de la largeur pour une grande contenance ? (c'est ce que j'ai fait )

Philippe

[Golgotha]

bonjour,



On a pas le droit d'orienter éventuellement la classe dans le sens de la largeur pour une grande contenance ? (c'est ce que j'ai fait )

Philippe

Les étudiants sont toujours face au nord (haut)

[Bucketpc]

Bonjour,

Pour le 3ème défis, je prévois toujours pas le piège à part essayer d'utiliser le maximum de chaises et tables dans chaque classe

Y a t il d'autres anomalies ?

[Golgotha]

Bonjour,

Pour le 3ème défis, je prévois toujours pas le piège à part essayer d'utiliser le maximum de chaises et tables dans chaque classe

Y a t il d'autres anomalies ?

Bonjour Bucketpc, que veux tu dire par là ?

[Bucketpc]

Je voudrais savoir s'il y a des astuces à utiliser. en d'autres termes, est ce qu'il suffit de juste de vérifier si les cases (i-1 j-1) (i-1, j+1), (i, j-1) (i, j+1) sont occupées par des étudiants ?

[philben]

bonjour

j'ai enfin entendu () que les élèves sont orientés au nord et je trouve finalement 626 élèves pour le problème n°20.

Qu'en pensez-vous ?

Philippe

[josmiley]

dommage qu'il n'y ait pas un thread par exercice, ça oblige à prendre le train au vol ...

ce code donne un resultat possible mais pas optimal; j'ai pas mieux pour l'instant. Trop dur.

Code :

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

1
2
3
4
5
6
7
x=open('defi_3.txt','r').readlines()
d=1
for c in range(int(x[0])):
	rangs = zip(*x[d+1:d+int(x[d].split()[0])+1])
	t = [r[0].count('.')for r in rangs]
	print 'classe',c,':',max(sum(t[::2]),sum(t[1::2]))
	d+=int(x[d].split()[0])+1

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
classe 0 : 9
classe 1 : 8
classe 2 : 26
classe 3 : 4
classe 4 : 7
classe 5 : 1
classe 6 : 16
classe 7 : 10
classe 8 : 14
classe 9 : 28
classe 10 : 26
classe 11 : 34
classe 12 : 40
classe 13 : 9
classe 14 : 16
classe 15 : 7
classe 16 : 39
classe 17 : 0
classe 18 : 32
classe 19 : 38

pour les boites à trier j'avais ça:

Code :

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

1
2
3
4
boxs = open('box.txt','r').read().strip(';').replace(';','),(')
boxs = eval('[('+boxs+')]')
boxs = sorted(boxs,key=lambda (x,y,z):x*y*z)
print boxs

[benDelphic]

on peut utiliser un programme linéaire pour résoudre le problème par rapport à chaque classe et ainsi bénéficier des places cassées pour empêcher les élèves de tricher et d'augmenter par la même occasion le nombre d'étudiants par classe
Xij =0 si un étudiant occupe la place i,j ;1 sinon . bij =0 si la place ne peut etre occupée (cassée) 1 sinon
à optimiser : la double somme de Xij ; sous les contraintes de type
bijXij+bi-1j-1Xi-1j-1+bij-1Xij-1+bi+1j+1Xi+1j+1+bij+1Xij+1=1 (faire attention aux bords)