Discussion :

[Tash23]

Bonjour !

Voilà: j'aimerais générer toutes les possibilitées de n nombre en faisant des calculs à chaque fois que je génère une possibilté et en fonction du résultats je vois si je continu la génération de possiblitées ou non.

Exemple: J'ai 25 villes à visiter mais je ne peux pas rouler plus de 5h/jours donc si toutes les routes de 4 villes dépassent déjà les 5h ca me sert à rien de générer toutes les routes possible plus longues.

J'ai ce code qui génère tout avec une fonction récursive et j'ai essayer d'ajouter une autre fonction (voilà) pour essayer de voir si je peux stopper la fonction récursive mais ca marche pas:

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
void voila (int con, vector <int> buffer)
{
	con++;
	if (con ==8)
	{
		for (int i=0; i < buffer.size(); i++)
		{
			buffer [i] = 3;
		}
	}
	return;
}
 
void bbf(vector<int> chchaine, int taille_chchaine, vector<int> bububuffer, int lonlongueur, int inind, int compt)
{
	if(inind>=lonlongueur)
	{
		for (int it =0; it < bububuffer.size(); it++)
		{
			cout << bububuffer[it];
		}
		cout << endl;
		return;
	}
 
	for(int ii=0; ii<taille_chchaine; ii++)
	{
		bububuffer[inind] = chchaine[ii];
		bbf(chchaine,taille_chchaine,bububuffer,lonlongueur,inind+1, compt);
	}
	voila (compt, bububuffer);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
	vector<int> tatable (3,0);//-----------------------------------------
	for (int i=0; i< tatable.size(); i++)
	{
		tatable[i] = i+1;	//vector dont il utilise les chiffres : 1, 2, 3, ...
	}
 
	int taille_tatable = tatable.size();
	int bubuffer = (int) calloc( taille_tatable+1, sizeof(int));
	vector <int> buuuuffer (taille_tatable,0); 
	int compt =0;
 
	for(int i=1; i<=taille_tatable; i++)
	{
		bbf(tatable,taille_tatable,buuuuffer,i,0,compt);
	}
	system("pause");
	return 0;
}

Sinon je voulais aussi me servir de la fonction permutation mais j'arrive pas non plus à "l'arreter en cours de route"..

peut être qu'il faudrait faire sans récursivité mais je n'arrive pas à faire l'algo pour ca..

help me please

Ps: l'ordre compte

[Bousk]

Bonjour,

ton problème me fait beaucoup penser au "voyageur de commerce" et "plus court chemin".
Renseignes-toi sur ces sujets / algos, ça devrait t'apporter de précieuses informations.

[Tash23]

Bonjour,

Oui oui je sais bien mais j'ai un probleme particulier avec un très grand nombre de contraintes et j'aurais juste besoin d'aide pour trouver un moyen d'arreter le listing des routes possible au moment ou je veux. Ou alors un prog qui listerait les routes possibles par pallier (1 pallier = ensemble de route d'une certaine longueur) ou je pourrais m'arreter au pallier voulu mais j'arrive pas à en faire un qui prendrait toutes les clients a visiter en compte à chaque fois..

genre: pour 3 clients:
pallier 1 : 001, 002, 003
pallier 2 : 012, 013, 021, 023, 031, 032
pallier 3 : 123, 132, ...

[white_tentacle]

En général, quand on veut se limiter à une certaine profondeur d’appels lors d’appels récursifs, on passe cette profondeur en paramètre et on la décrémente à chaque appel récursif. Quelque chose comme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
int explorer(param1, param2, int maxdepth)
{
  if(maxdepth == 1)
     return truc;
  else
   {
     // traitement
        explorer(...., maxdepth -*1)
    }
}

[jblecanard]

Salut !

Je vais passer rapidement sur les nombreuses erreurs que j'ai rencontrées:
- La fonction voila qui ne sert à rien (enlève là, le résultat est le même), car tu passes tous ses arguments par copie.
- Le calloc (en C++, on utilise new), converti dans un type invalide int alors que ce devrait être un int*.
- Les noms de variables atroces (pourquoi ?).

Je suppose que tu es débutante et ces remarques ne résolvent pas ton problème. La proposition de white_tentacle est classique mais peut ne pas fonctionner pour toi car la condition d'arrêt n'est pas nécessairement une profondeur limite, ce qui semble être ton cas. En revanche, si sa proposition est adaptée à ton problème, n'hésite pas, c'est le plus simple.

Une autre solution ici pourrait être de vectoriser ton algo, c'est à dire le transformer en algorithme non récursif. C'est facile dans ton cas car tu n'utilises pas le résultat de ton appel récursif pour la suite du calcul.

L'idée générale est qu'au lieu de faire un appel récursif, tu stockes les données nécessaires pour l'appel à la fin d'une liste, afin d'effectuer cet appel plus tard. Puis une boucle parcourt la liste et fait le calcul sur tout son contenu tant qu'il en reste. Ainsi, ton algo n'est plus récursif et tu peux t'arrêter pile quand tu veux.

Voici une implémentation de ton algo en C++11 qui te montre comment faire (il va falloir te débrouiller un peu si tu ne peux pas utiliser C++11):

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
#include <iostream>
#include <vector>
#include <tuple>
#include <list>
 
using namespace std;
using record_t = std::tuple< std::vector<int>, std::vector<int>, int, int, int>;
 
void bbf(list<record_t>& to_process) {
  // Extract data
  std::vector<int> chchaine, bububuffer;
  int lonlongueur, inind, compt;
  tie(chchaine, bububuffer, lonlongueur, inind, compt) = to_process.front();
 
  // Do process
  if (inind>=lonlongueur) {
    for (int i : bububuffer) cout << i;
    cout << endl;
    return;
  }
 
  for (size_t ii=0; ii < chchaine.size(); ++ii) {
    bububuffer[inind] = chchaine[ii];
    to_process.emplace_back(record_t(chchaine, bububuffer,lonlongueur,inind+1, compt));
    //bbf(chchaine,bububuffer,lonlongueur,inind+1, compt);
  }
}
 
int main(int argc, char* argv[])
{
  vector<int> tatable (3,0);
  for (size_t i=0; i < tatable.size(); ++i) tatable[i] = static_cast<int>(i+1);
 
  int taille_tatable = tatable.size();
  vector <int> buffer (taille_tatable,0);
  int compt =0;
 
  list<record_t> record_to_process;
 
  for(size_t i=1; i<=taille_tatable; ++i) {
    record_to_process.emplace_back(record_t(tatable, buffer, i, 0, compt));
  }
 
  while (record_to_process.size()) {
    bbf(record_to_process);
    record_to_process.pop_front();
    if (false) break;  // Remplacer false par ta condition d'arrêt
  }
 
  return 0;
}

Il sort exactement le même résultat que celui que tu donnes en exemple.