Discussion :

[picodev]

je n'ai pas compris "file et backtracking, enfin tout dépend de ce que tu veux vraiment …"

une file pour garder les chemins, backtracking : une méthode pour parcourir ta matrice et trouver les chemins. C'est une idée de premier jet ne connaissant pas les détails de ce que tu cherches à obtenir.

pour tes questions:
1- Non un chemin peu ne pas commencer par la première colonne comme vous avez vu les nombres de la première colonne peuvent ne pas vérifier la condition donc on saute à la deuxième et bien sur on ne saute pas à chaque fois. Par exemple on a 14 colonne je vais prendre ~90% des colonnes c'est dire il saute ~2colonnes mais pas 3 colonnes ou plus. (c'est une autre complexité de mon idée que je l'introduirerai)

Tu entends par là qu'un chemin possède bien un élément par colonnes consécutives, donc sans trou = un chemin avec un élément en colonne i doit forcément avoir un élément dans la colonne i+1 si il y a un élément de la colonne i+2. Ou peut-on avoir un trou ?

2- Oui, elle sont triées. J'ai mis -1 pour qu'il stoppe et ne pas parcourir le reste de la colonne.

ça simplifie les choses

3- Je veux les chemins qui vérifie la condition à chaque fois et il couvre ( ou il passe) au moins par 90% des colonnes de la matrice. Si on trouve un chemin qui vérifie la condition à chaque fois de la colonne 1 à 6 donc je dois rejeté ce chamin puisqu'il ne couvre pas 90% des colonnes de la Matrice.

Là j'ai peur de comprendre qu'il faille accepter les chemins avec des trous

4- Je n'ai pas compris ici. je construis une matrice puis j'analyse cette matrice et je cherche en fonction de ma condition. Je trouve que les colonnes sont moins de l'autre idée.

Merci pour votre aide

Ça peut simplifier les choses si ta matrice est une matrice de structures plutôt que d'int.

[mido1951]

une file pour garder les chemins, backtracking : une méthode pour parcourir ta matrice et trouver les chemins. C'est une idée de premier jet ne connaissant pas les détails de ce que tu cherches à obtenir.

Tu entends par là qu'un chemin possède bien un élément par colonnes consécutives, donc sans trou = un chemin avec un élément en colonne i doit forcément avoir un élément dans la colonne i+1 si il y a un élément de la colonne i+2. Ou peut-on avoir un trou ?

ça simplifie les choses

Là j'ai peur de comprendre qu'il faille accepter les chemins avec des trous

Ça peut simplifier les choses si ta matrice est une matrice de structures plutôt que d'int.

Oui on peut avoir un trou ou deux. Je vais introduire l'idée des trou (Obligé).
Mais ici j'ai un petit problème parce que je dois vérifier les autres colonnes si je ne trouve pas la condition vérifié dans la première ou deuxième ou Neme colonne.
t'as vu mon dernier code? il a marché avec des données simple mais je dois introduire les autres complexités!!
pour la matrice de structure?!! je n'ai aps compris comment c'est simple? se sont des nombres.
Merci.

[picodev]

Bon l'idée de départ va être de définir un peu tes besoins, tous tes besoins, car produire quelque chose pour revenir en arrière et tout changer n'est pas productif du tout.

Il te faut quelque chose qui ressemble à :

Code :

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

1
2
3
4
5
6
7
8
void find_path(matrix_t m, visit_func_t visit)
{
  path_max_holes = m.width * 0.1;
  path_min_length = m.width - path_max_holes;
  first_col=0;
  path_list=path_list_new();
  backtrace_path(m, first_col, path_list, path_max_holes, path_min_length, visit);
}

avec

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
void backtrace( matrix_t m, int col, path_list_t path_list, int max_holes, int min_length, visit_func_t visit)
{
  if min_length>m.width-col return car il n'y a plus assez de colonnes
  if length(path_list)>=min_length visit(m, path_list);
 
  for(row=0; row<m.height && m[row][col]!=-1; ++row)
    if is_empty(path_list)
      push( (row,col) , path_list )
      backtrace(m, col+1, path_list, max_holes,min_length, visit)
      pop(path_ist)
    else if m[row][col].val=head(path_list)+3
      push( (row,col) , path_list )
      backtrace(m, col+1, path_list, max_holes,min_length, visit)
      pop(path_ist)
    else if max_holes!=0
      backtrace(m, col+1, path_list, max_holes-1,min_length, visit)
}

Enfin bon, c'est tapé à la volée, une idée à creuser

[mido1951]

Bon l'idée de départ va être de définir un peu tes besoins, tous tes besoins, car produire quelque chose pour revenir en arrière et tout changer n'est pas productif du tout.

Il te faut quelque chose qui ressemble à :

Code :

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

1
2
3
4
5
6
7
8
void find_path(matrix_t m, visit_func_t visit)
{
  path_max_holes = m.width * 0.1;
  path_min_length = m.width - path_max_holes;
  first_col=0;
  path_list=path_list_new();
  backtrace_path(m, first_col, path_list, path_max_holes, path_min_length, visit);
}

avec

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
void backtrace( matrix_t m, int col, path_list_t path_list, int max_holes, int min_length, visit_func_t visit)
{
  if min_length>m.width-col return car il n'y a plus assez de colonnes
  if length(path_list)>=min_length visit(m, path_list);
 
  for(row=0; row<m.height && m[row][col]!=-1; ++row)
    if is_empty(path_list)
      push( (row,col) , path_list )
      backtrace(m, col+1, path_list, max_holes,min_length, visit)
      pop(path_ist)
    else if m[row][col].val=head(path_list)+3
      push( (row,col) , path_list )
      backtrace(m, col+1, path_list, max_holes,min_length, visit)
      pop(path_ist)
    else if max_holes!=0
      backtrace(m, col+1, path_list, max_holes-1,min_length, visit)
}

Enfin bon, c'est tapé à la volée, une idée à creuser

merci pour le code. je vais essayer un peu de le dechiffrer parceque c'est un peu complexe à comprendre. Merci bcp.
j'ai une petite question: J'ai une machine un peu ancienne 32bit. j'utilise un découpage des sequence de taille k=3. Mais le problème quand j'augmente la taille k( k= 4 par exemple) ça marche pas. le programme se bloque. est-ce normal?
Merci

[picodev]

merci pour le code. je vais essayer un peu de le dechiffrer parceque c'est un peu complexe à comprendre. Merci bcp.
j'ai une petite question: J'ai une machine un peu ancienne 32bit. j'utilise un découpage des sequence de taille k=3. Mais le problème quand j'augmente la taille k( k= 4 par exemple) ça marche pas. le programme se bloque. est-ce normal?
Merci

Si le programme se bloque alors qu'il ne devrait pas alors c'est un bug …

[ternel]

D'un autre coté, tu parles d'un bug quand tu passes de 3 à 4, et il y a un gros 3 dans le code.
Pour moi, le problème, c'est d'avoir un nombre magique dans le code.