[PHP] recherche d'un chemin dans une BD

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention -
diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention - 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

Afficher la suite

A voir également:

[PHP] recherche d'un chemin dans une BD
Recherche automatique des chaînes ne fonctionne pas - Guide
Comment faire une recherche à partir d'une photo - Guide
Je recherche une chanson - Guide
Rechercher ou entrer l'adresse mm - recherche google - Guide
Fréquence tnt recherche manuelle - Forum Téléviseurs

11 réponses

Réponse 1 / 11

crabs Messages postés 908 Date d'inscription Statut Membre Dernière intervention 507

Salut,
Recherches du coté des algoritmes de parcours de graphe :
'parcours graphe chemin' dans Google.
A+, crabs

Réponse 2 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

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 !)

Réponse 3 / 11

crabs Messages postés 908 Date d'inscription Statut Membre Dernière intervention 507

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

Réponse 4 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

<?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();
?>

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 Statut Membre Dernière intervention 507

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

Réponse 6 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

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!

Réponse 7 / 11

crabs Messages postés 908 Date d'inscription Statut Membre Dernière intervention 507

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.

Réponse 8 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

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

Réponse 9 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

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 !

crabs Messages postés 908 Date d'inscription Statut Membre Dernière intervention 507

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

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

merci j'avais essayé d'utiliser les variables global mais je les utilisais mal

Réponse 10 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

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.

Réponse 11 / 11

diafwl1 Messages postés 52 Date d'inscription Statut Membre Dernière intervention

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;
		}

Discussions similaires

comment lire des bd gratuitement en ligne sur internet ?

Chemin Logo du site de la Cité de l'espace

Lire des bd en ligne

Comment télécharger des BD en pdf

recherche à partir de la barre d'adresse

Votre réponse

Discussions similaires