Sujet Précédent Sujet Suivant

[PHP] recherche d'un chemin dans une BD

Fermé
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008 - 12 janv. 2006 à 16:06
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008 - 18 janv. 2006 à 11:55
Bonjour, j'ai un problème pour réaliser une fonction qui me permette de rechercher un chemin dans ma base de données.
Par exemple prennons une table qui contient 3 champs (par exemple), dans le 1er champs se trouve un ID, dans le 2nd un nom,de ville par exemple, et dans le 3éme un autre nom de ville, une ligne correspond à ville 1 est relier à ville2.

ex du contennu de la table :

| ID | nom 1 | nom 2 |
| 1 | AAA | BBB |
| 2 | CCC | AAA |
| 3 | BBB | DDD |
| 4 | AAA | YYY |
| 5 | EEE | YYY |
| 6 | DDD | EEE |

Si l'utilisateur demande par exemple les chemins pour relier AAA à YYY, le progrmme devra donner comme reponse :
1 - AAA | BBB
1 - BBB | DDD
1 - DDD | EEE
1 - EEE | YYY
2 - AAA | YYY

Je n'ai aucun pb pour afficher ce genre de réponse.
Pour engendrer cette réponse je parcours la table à la recherche de la ville de depart, ensuite si je la trouve je mets le nom dans un tableau à 2 dimensions(chaque ligne correspond à un chemin possible entre 2 villes), et je reparts de la 2éme ville(devient la nouvelle ville de depart), ainsi de suite jusqu'à temps de trouver le nom de la ville finale.
Mon problème est que le programme s'arrète si jamais il rentre (dans l'exemple) dans la 2éme ligne, il affichera :
1 - AAA | CCC
Je ne trouve pas comment faire pour revenir en arrière et repartir par un autre chemin
A voir également:

11 réponses

Réponse 1 / 11
crabs Messages postés 908 Date d'inscription lundi 18 avril 2005 Statut Membre Dernière intervention 3 août 2008 507
12 janv. 2006 à 17:45
Salut,
Recherches du coté des algoritmes de parcours de graphe :
'parcours graphe chemin' dans Google.
A+, crabs
0
Réponse 2 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
13 janv. 2006 à 11:52
Je pense avoir trouver quelque chose d'interessant, mais je n'ai jamais réalisé un arbre ayant un nombre de fils varriable, le seul que j'ai fait était un arbre n'ayant que 2 fils au maximum, alors je ne vois pa trop comment le programmer ! Un ptit coup de main svp ;-)
(merci à toi crabs !)
0
Réponse 3 / 11
crabs Messages postés 908 Date d'inscription lundi 18 avril 2005 Statut Membre Dernière intervention 3 août 2008 507
13 janv. 2006 à 13:14
Salut,

Pour les arbres binaires, dans la cellule correspondant à ton noeud il y a la
référence au fils de gauche et celui de droite.
Pour les arbres pouvant avoir 0 à n fils, tu remplaces ces deux variables par
un tableau de fils et le nombre de fils.
Evidement en PHP, la notion de cellule n'existe qu'au travers des tableaux
associatifs, mais tu peux mettre un tableau comme variable d'un tableau.
Exemple d'affectation : 
// Initialisation
noeud['AAA']['fils'] = array( 'BBB' ) ;
// Ajout
noeud['AAA']['fils'][] = 'YYY' ;

A+, crabs
0
Réponse 4 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
13 janv. 2006 à 16:50
<?php
$result = mysql_query("SELECT * FROM nom_table");

import_request_variables("P","recu_");
for($x=0;$x <20;$x++)
{
for($y=0;$y <20;$y++)
{
$passepar[$x][$y] = "";
}
}
$fin=false;
$new_depart=$recu_depart;
//Pour verrifier si on n'est pas déjà passé
function rech_deja_passe($a,$b,$x,$y)
{
$present=false;
for($i=0;(($i<$y)&&!$present);$i++)
{
if($b[$x][$i]==$a)
{
$present=true;
return $present;
}
}
return $present;
}
$x=1;
$y=$k=0;
$sauv=true;
$ID=array();
$z=0;
for($j=0;$j<mysql_num_rows($result);$j++)
{
mysql_data_seek($result,$j);
$champs=mysql_fetch_array($result);
if(($champs[1]==$new_depart)&&($champs[6]==0)&&(!rech_deja_passe($champs[3],$passepar,0,$z))&&($new_depart!=$recu_arrive))
{
if($sauv)
{
$sauvegarde=$j;
$sauv=false;
}
if((!rech_deja_passe($champs[3],$passepar,0,$z))&&($j!=(mysql_num_rows($result)-1)))
{
if(!rech_deja_passe($champs[3],$passepar,$x,$y))
{
echo "<tr align=\"center\">";
echo'<td>'.$champs[0].'</td><td>'.$champs[1].'</td><td>'.$champs[2].'</td><td>'.$champs[3].'</td><td>'.$champs[4].'</td><td>'.$champs[5].'</td><td>'.$champs[6].'</td><td> '.$champs[7].'</td><td> '.$champs[8].'</td><td> '.$champs[9].'</td>';
echo"</tr>";
$passepar[$x][$y]=$new_depart;
$y++;
$z=$passepar[$x][$y];
echo' passepar['.$x.']['.$y.'], valeur: '.$z.' <br>';
if($champs[3]==$recu_arrive)
{
$passepar[0][$z++]=$champs[1];
$passepar[$x][$y]=$champs[3];
$new_depart=$recu_depart;
$x++;
$y=0;
$j=$sauvegarde;
$sauv=true;
}
else
{
$new_depart=$champs[3];
$j=0;
}
}
}
else
{
//ne rentre jamais dans cette boucle ne c pas pourquoi
if($j==(mysql_num_rows($result)-1))
{
echo 'hello1';
$new_depart=$passepar[0][$z-1];
$x++;
$y=0;
$j=0;
}
}
}
else
{
if(($champs[3]==$new_depart)&&($champs[6]==0)&&(!rech_deja_passe($champs[1],$passepar,0,$z))&&($new_depart!=$recu_arrive))
{
if($sauv)
{
$sauvegarde=$j;
$sauv=false;
}
if((!rech_deja_passe($champs[1],$passepar,0,$z))&&($j!=(mysql_num_rows($result)-1)))
{
if(!rech_deja_passe($champs[1],$passepar,$x,$y))
{
echo "<tr align=\"center\">";
echo'<td>'.$champs[0].'</td><td>'.$champs[1].'</td><td>'.$champs[2].'</td><td>'.$champs[3].'</td><td>'.$champs[4].'</td><td>'.$champs[5].'</td><td>'.$champs[6].'</td><td> '.$champs[7].'</td><td> '.$champs[8].'</td><td> '.$champs[9].'</td>';
echo"</tr>";
$passepar[$x][$y]=$new_depart;
$y++;
$z=$passepar[$x][$y];
echo' passepar['.$x.']['.$y.'], valeur: '.$z.' <br>';
if($new_depart==$recu_arrive)
{
$passepar[$x][$y]=$new_depart;
$new_depart=$recu_depart;
$x++;
$y=0;
$j=$sauvegarde;
$sauv=true;
}
else
{
$passepar[0][$z]=$new_depart;
$new_depart=$champs[1];
$z++;
$j=0;
}
}
}
else
{
//ne rentre jamais dans cette boucle ne c pas pourquoi
if($j==(mysql_num_rows($result)-1))
{
echo 'hello2';
$new_depart=$passepar[0][$z-1];
$x++;
$y=0;
$j=0;
}
}
}
}
if($j==(mysql_num_rows($result)-1))
{
echo 'hello1';
if (!trouve)
{
$new_depart=$passepar[0][$z-1];
$x++;
$y=0;
$j=0;
}
}
}

mysql_close();
?>
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 11
crabs Messages postés 908 Date d'inscription lundi 18 avril 2005 Statut Membre Dernière intervention 3 août 2008 507
15 janv. 2006 à 17:01
Salut,
Perso je ferais ça en 2 passes :
1) lecture de la BD avec remplissager des structures (puis liberation des ressources mysql)
2) le traitement
Peux-tu donner la référence à l'algo que tu as décidé d'utiliser
A+, crabs
0
Réponse 6 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
15 janv. 2006 à 20:11
Que veux-tu dire par "référence à l'algo"?
Que je te donne l'algo que j'ai écrit? Si tu me demande la référence du code sur lequel j'ai copié, il n'y en a aucune car je l'ai fait au fur et à mesure ;-)
Effectivement je me suis aussi résoud à le faire en 2 phases.
Par contre j'ai un petit pb pour afficher ce qu'il y a dans le tableau à 2 dimension j'ai essayer de l'afficher directement et en passant par une variable mais losque je l'affiche c'est comme s'il n'y avait rien dedans!
0
Réponse 7 / 11
crabs Messages postés 908 Date d'inscription lundi 18 avril 2005 Statut Membre Dernière intervention 3 août 2008 507
15 janv. 2006 à 20:49
Salut,
Si c'est à des fins de debug, utilises la fonction print_r().
Sinon regarde du coté de la sturture de controle foreach().

A+, crabs.
0
Réponse 8 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
16 janv. 2006 à 14:40
j'ai revu le programme en le separant en plusieur étapes je ne recupère que la parti la plus interessante de la table et je place le resultat dans une autre table, du coup je ne travail plus que sur une trentaine de ligne au lieu de 300. Je separ ensuite dans 2 fonction le fait d'avoir un chemin direct et indirect
0
Réponse 9 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
17 janv. 2006 à 10:35
je te remercie pour le print_r(), il m'a permi de voir que mon tableau était vide "de temps en temps", ce que je n'arrive pas à comprendre, suivant où je place cette fonction il m'affiche le tableau avec ou sans valeur, pourtant je pensais que le fait de déclarer le tableau dans la partie principale du programe (en dehors des fonctions) me permetais d'y accéder tout le tps !
0
crabs Messages postés 908 Date d'inscription lundi 18 avril 2005 Statut Membre Dernière intervention 3 août 2008 507
17 janv. 2006 à 21:10
Salut,
Il faut déclarer alors la porté de la variable grace au mot clé global. Ex: 
$une_var_gloable = 0 ;
function f( $x )
  {
  global $une_var_gloable ;
  $une_var_gloable += $x ;
  }

A+, crabs
0
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
18 janv. 2006 à 10:23
merci j'avais essayé d'utiliser les variables global mais je les utilisais mal
0
Réponse 10 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
17 janv. 2006 à 11:07
pour continuer dans ma 1ére idée, je vai essayer array_push () pour utiliser une pile,et unset() pour supprimer l'élément blocant , qui sera le dernnier element de la pile.
Par contre j'aimerai ensuite copier toutes les piles obtenues dans un tableau à 2 dimension, j'ai trouvé la fonction array_chunk () mais le pb c'est que les listes vont avoir des tailles variable dc je ne sais pas quelle fonction utiliser pour sa.
0
Réponse 11 / 11
diafwl1 Messages postés 52 Date d'inscription mercredi 27 avril 2005 Statut Membre Dernière intervention 5 août 2008
18 janv. 2006 à 11:55
J'ai separé en 2 fonction la recherche la 1ère recherche les chemins direct et la 2nd les indirect (ne fonctionne pas toujours et s'arrète après avoir trouV un resultat (je doit enlever trop de chemin de recherche après chaque passage) 

function chemin_direct($dep,$arr)
		{
			global $nb_new_row;
			global $new_result;
			global $result_chemin;
			global $prohib;
			global $x;
			$direct=false;
			$chemin=array();
			for($i=0;(($i<$nb_new_row)&&!$direct);$i++)
			{
				mysql_data_seek($new_result,$i);
				$ch=mysql_fetch_array($new_result);
				if(($ch[1]==$dep)&&(!in_array($ch[0],$prohib)))
				{
					if($ch[2]==$arr)
					{
						array_push($chemin,$ch[1],$ch[2]);
						array_push($result_chemin,$chemin);
						$prohib[$x++]=$ch[0];
						$chemin=array();
						$direct=true;
					}
				}
				else
				if(($ch[2]==$dep)&&(!in_array($ch[0],$prohib)))
				{
					if($ch[1]==$arr)
					{
						array_push($chemin,$ch[2],$ch[1]);
						array_push($result_chemin,$chemin);
						$prohib[$x++]=$ch[0];
						$chemin=array();
						$direct=true;
					}
				}
			}
			return $direct;
		}


		function chemin_indirect($dep,$arr)
		{
			global $new_result;
			global $nb_new_row;
			global $prohib;
			global $x;
			global $result_chemin;
			$new_depart=$dep;
			$new_arrive=$arr;
			$chemin=array();
			$indirect=false;
			for($i=0;(($i<$nb_new_row)&&!$indirect);$i++)
			{
				mysql_data_seek($new_result,$i);
				$champs=mysql_fetch_array($new_result);
				if(($champs[1]==$new_depart)&&(!in_array($champs[0],$prohib)))
				{
					if($champs[2]==$new_arrive)
					{
						array_push($chemin,$champs[1],$champs[2]);
						array_push($result_chemin,$chemin);
						$prohib[$x++]=$champs[0];
						$indirect=true;
					}
					else
					{
						if(rech_suite($champs[2]))
						{
							array_push($chemin,$champs[1]);
							$new_depart=$champs[2];
							//$prohib[$x++]=$champs[0];
						}
						else
						{
							if(!rech_suite($champs[1]))
							{	
								if (count($chemin)!=0)
								{
									$new_depart=$chemin[count($chemin)-1];
									unset($chemin[count($chemin)-1]);
								}
								else
									break;
								$prohib[$x++]=$champs[0];
							}
						}
						$i=-1;
						//$nb_passage++;
					}
				}
				else	
				if(($champs[2]==$new_depart)&&(!in_array($champs[0],$prohib)))
				{
					if($champs[1]==$new_arrive)
					{
						array_push($chemin,$champs[2],$champs[1]);
						array_push($result_chemin,$chemin);
						$prohib[$x++]=$champs[0];
						$indirect=true;
					}
					else
					{
						if(rech_suite($champs[1]))
						{
							array_push($chemin,$champs[2]);
							$new_depart=$champs[1];
							$prohib[$x++]=$champs[0];
						}
						else
						{
							if(!rech_suite($champs[2]))
							{	
								if (count($chemin)!=0)
								{
									$new_depart=$chemin[count($chemin)-1];
									unset($chemin[count($chemin)-1]);
								}
								else
									break;
								$prohib[$x++]=$champs[0];
							}
						}
						$i=-1;
						//$nb_passage++;
					}
				}
			}
			return $indirect;
		}
		
		function rech_suite($a)
		{
			global $new_result;
			global $nb_new_row;
			global $prohib;
			$trouve=false;
			for($j=0;(($j<$nb_new_row)&& !$trouve);$j++)
			{
				mysql_data_seek($new_result,$j);
				$ch=mysql_fetch_array($new_result);
				if((($a==$ch[1])||($a==$ch[2]))&&(!in_array($ch[0],$prohib)))
					$trouve=true;
			}
			return $trouve;
		}
0

Discussions similaires

Chemin Logo du site de la Cité de l'espace
Keiios -
blux -

11 réponses
comment lire des bd gratuitement en ligne sur internet ?
theodu13480 -
Ereka -

2 réponses
Comment télécharger des BD en pdf
kawax -
bentafat -

4 réponses
recherche à partir de la barre d'adresse
Sylviane -
Lulin -

11 réponses
lire ou télécharger le magasin WITCH MAG
qualinka -
mangoan -

9 réponses