Discussion :

[otspot]

Bonjour

Imaginons qu'on a un plateau de cases a explorer, qu'on a le droit d'aller dans les 4directions et qu'on a pas le droit "d'avancer" sur des cases par ou on est deja passé, mais par contre on a le droit de revenir sur nos pas (ce qui impliquerais "reculer" sur des cases par ou on est deja passé. Comment explorer tout le plateau avec le minimum de deplacements.

J'ai pensé a la courbe de peano, mais le point de depart, est toujours un coin, alors que pour moi le point de depart c'est le milieu.

J'ai aussi pensé a exploré toutes les positions, avec une conditions d'evaluation, mais ca prendrai bcp de temps, et je me demandais s'il nyavait pas une variante, pour partir du milieu.

Dsl, si je n'ai pas été très clair, et merci par avance

[Zavonen]

Partant du mieu et divisant le rectangle en quatre quarts, tu peux parcourir chaque quart d'un coin à un autre en appliquant l'algo que tu connais.

[pseudocode]

Le minimum de deplacement est egal au nombre de cases du tableau. Impossible de faire moins.

Donc une bonne vieille spirale est une solution optimale.

[Zavonen]

Donc une bonne vieille spirale est une solution optimale.

Sauf que dans le cas d'un rectangle, tu te fais coincer après avoir rejoint le bord. Il te reste deux parties isolées à parcourir (incompatible avec la contrainte de ne pas repasser par les même points).

[otspot]

Zavonen, je trouve que ton idée est très bonne, même si ne crois pas que ca soit la méthode la plus optimale. Je vais essayer de programmer tout ca et je vous tiendrez au courant.

Et sinon pour la spirale, c'est la première idée, qui m'est venu à l'esprit, mais après y avoir pensé, je ne crois pas qu'elle soit bonne.

Merci

[pseudocode]

Sauf que dans le cas d'un rectangle, tu te fais coincer après avoir rejoint le bord. Il te reste deux parties isolées à parcourir (incompatible avec la contrainte de ne pas repasser par les même points).

!

Dans mon pauvre cerveau plateau=carré. Faut que j'arrete le Wyx.

[otspot]

Je viens de vérifier la méthode, et il ya plusieurs cas, ou elle marche pas, il suffit de prendre un tableau de 5*5.

Donc, si vous avez d'autres idées

Merci

[pseudocode]

Je viens de vérifier la méthode, et il ya plusieurs cas, ou elle marche pas, il suffit de prendre un tableau de 5*5.

Donc, si vous avez d'autres idées

Merci

Ton plateau est-il toujours un carré ou peut-il être rectangle ?
Est-il toujours de taille impaire (longueur, largeur) ?
S'il est de taille paire, comment définir le point de départ (le milieu) ?

[Zavonen]

même si ne crois pas que ca soit la méthode la plus optimale.

Si tu passes par tous les points une fois et une seule, tous tes chemins ont la même longueur. En quoi l'un d'entre eux peut-il être 'optimal'?

[Zavonen]

Le chemin 'diagonal' (exemple: (0,0) (0,1) (1,0) (2,0) (1,1) (0,2) (0,3) (2,1) etc... te permet d'aller d'un coin de rectangle à n'importe quel autre, quitte à parcourir un côté directement AVANT de commencer.
Tu peux donc, partant de n'importe quel point intérieur parcourir l'ensemble en appliquant 4 fois ce principe.
C'est facile à programmer si on remarque que sur un segment de diagonale la somme des coordonnées reste constante, et que quand on passe d'un segment au suivant cette somme est diminuée ou augmentée d'une unité, selon qu'on monte ou qu'on descend.

[otspot]

D'avance merci pour ton aide.

Je n'ai pas bien compris ta dernière explication, la seule chose que je peux deja dire, c'est qu'on a pas le droit d'aller en diagonale.

La solution optimale, pour moi, c'est la solution qui me ferai explorer toutes les cases du plateau, avec le minimum de déplacements, c'est tout. Après s'il yen a plusieurs, j'en prendrai une au pif

Pour le plateau, le nombres de colonnes et égale au nombres de lignes, mais il peut être pair. Et dans ce cas la, le milieu c'est l'une des 4cases, qui entourent le noeud central.

[Zavonen]

La solution optimale, pour moi, c'est la solution qui me ferai explorer toutes les cases du plateau, avec le minimum de déplacements,

Tu auras toujours le même nombre de déplacements=le nombre de cases

c'est qu'on a pas le droit d'aller en diagonale.

Dans ce cas il faut oublier ça (dommage...)

[otspot]

Je commence vraiment a me dire, que je ferai mieux de faire une fonction recursive pour explorer tout l'arbre, je ne sais pas si c'est jouable. Le nombre de combinaisons doit être enorme mais si je limite le plateau a 10 colonnes....?

[Zavonen]

Partons d'un point quelconque à l'intérieur de ton carré.
De là, tu peux partir dans quatre directions NSEO, et puis tu as des parités de lignes et de colonnes au dessus et en dessous, à gauche et à droite.
J'affirme qu'il est possible de barbouiller un des 4 rectangles par des va et vient en ne se faisant pas bloquer dans un coin à la fin.
J'affirme qu'il est possible de barbouiller ensuite le rectangle adjacent à celui déjà parcouru, mais on ne peut savoir où on va finir.
Si on est près d'un bord c'est gagné. Il n'y a plus qu'à colorier un grand rectangle par des va et vient.
Le cas le plus ennuyeux c'est quand on revient à côté du point de départ.
Voici la stratégie pour finir:
Se décaler d'une case.
Aller vers un bord en longeant la partie déjà parcourue.
Revenir vers le point de départ par des balayages en sens inverse
Quand c'est fini il n'y a plus qu'un rectangle à couvrir
Si on est près du bord c'est gagné.
Le cas ennuyeux c'est quand, une fois de plus, on termine près de notre nouveau point de départ.
S'écarter alors d'une case dans la zone non coloriée, aller vers le premier grand rectangle colorié, le longer pour regagner le bord, comme précédemment.
Revenir du bord vers le centre par des balayages en sens inverse.
A la fin, quel que soit l'endroit où on arrive il n'y a plus qu'un segment à parcourir dans un sens ou un autre.
Je ne suis pas sûr d'avoir été bien clair.
Essaye de suivre mes indications avec un crayon.

[pseudocode]

@Zavonen: ca marche avec un rectangle de 9x7 ?

[Zavonen]

@Zavonen: ca marche avec un rectangle de 9x7 ?

No, Sir !

[pseudocode]

je crois me souvenir qu'il y a une limitation pour les courbes "fermées" de remplissage d'espace. C'est trop loin pour que je me souvienne mais je pense que le pavage 9x7 n'a pas de solution par courbe fermée.

[Zavonen]

Voilà un petit 'en-cas' . Je voulais l'utiliser pour démontrer l'inexistence de solutions dans le cas 7*9, mais ça rame vraiment trop !

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
# -*- coding: iso-8859-1 -*-
import copy
 
# nombre de lignes
n=5
#nombre de colonnes
m=5
#nombre de solutions
nbsol=0
 
#les voisins d'une case L=[x,y]
def voisins (L):
    R=[]
    x=L[0]
    y=L[1]
    x1=x-1
    x2=x+1
    y1=y-1
    y2=y+1
    if  x1>=0:
        R.append([x1,y])
    if x2<n :
        R.append([x2,y])
    if y1>=0 :
        R.append([x,y1])
    if y2<m:
        R.append([x,y2])
    return R
 
#affiche les solutions commençant par le chemin L (liste de cases)
def printsolutions (L):
    global nbsol
    Dernier=L[-1]
    VD=voisins(Dernier)
    if len(L)==n*m-1:
        Premier=L[0]
        for v in VD:
            if not(v in L):
                R=copy.deepcopy(L)
                R.append(v)
                print R
                nbsol=nbsol+1
    else:
        for v in VD:
            if not (v in L):
                Q=copy.deepcopy(L)
                Q.append(v)
                printsolutions(Q)
 
 
def main():
     printsolutions([[n/2,m/2]])
     print nbsol
 
if __name__ == '__main__':
    main()

[pseudocode]

Voilà un petit 'en-cas' . Je voulais l'utiliser pour démontrer l'inexistence de solutions dans le cas 7*9, mais ça rame vraiment trop !

et avec 3x5 ? ( )

Code :

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

1
2
3
 
C:\Python25>python.exe src\DVP445076.py
0

[Zavonen]

Ah ben voui, j'ai même pas pensé à essayer ça.
Pour les rectangles, en général, la cause est entendue, c'est Niet !
Mais pour les carrés ?