Forum d'entraide PHPFrance

Bonjour,

question un peu particulière à propos d'un problème auquel je me heurte depuis quelques jours...

Objet de la question : connaître avec php le chemin le plus court dans un graphe orienté.

J'ai dans une base de données MySQL, des points pour lesquels j'ai défini 2 champs : "libelle" et "destination" et qui au final peuvent être schématisés par le graphe suivant :

libelle | destination
------------------------
A | B
A | C
C | D
C | E
C | F
D | F



Mais que ces points soient tirés d'une bdd ou d'un tableau en php, celà n' a pas d'importance, c'est surtout la suite qui me pose un problème!

Le but est que d'après ce tableau de points, un algorithme arrive à sortir le chemin le plus court, ce qui correspondrait dans mon exemple au chemin A -> C -> F (considérant que je cherche le chemin le plus court entre A & F).

Je pense que cet algorithme est celui de l'algorithme de Dijkstra ( http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ), mais SANS les valeurs (les poids), car pour moi tous les poids valent "1", mais je n'arrive pas à implémenter ce code en php avec les boucles et tout...

Quelqu'un aurait-il un début de piste svp?

Merci!

Bonsoir,

Lorsque j'étais à l'université, mon professeur avait pris deux exemple pour illustrer les algorithme exponentiel qui demandent des ordinateur si puissant qu'il n'ont pas encore été inventé.

ces deux exemples étaient:

1) Le choix du meilleur itineraire pour un voyageur de commerce
2) L'établissement du planning des classe d'un collège

Un algorithme peut être trouvé mais il donnera la première possibilité (ou la Xème en cas d'itération) mais jamais la meilleure.

J'espère me tromper pour vous mais il me semble que vous devrez "bricoler"

Charles

Merci de votre réponse Charly 74.

Concernant cet algorithme que j'essaie de transposer en php, il existe déjà et on retrouve des foisons de codes sur le net en C, C++ etc... mais pas en php...

Le voyageur de commerce est un algo qui parcours un graphe de façon exhaustive. tous les sommets seront visités alors que celui de Dijkstra ne parcourra que les sommets nécessaires.

Cet algo est largement faisable aujourd'hui sans des ordinateurs de type "bêtes de courses".

C'est cette transposition que j'essaie de faire en php... mais rien sur le net n'y fait allusion... tout est en C.

Tu peux traiter le problème facilement.

Soit un tableau regroupant la liste des sommets desquels A est le prédécesseur :
$tab = array('B' => 1, 'E' => 1, etc…);

Pour chaque sommet appartenant à $tab, on prend son successeur et on l'ajoute au tableau s'il n'y est pas, en incrémentant le compteur, si par exemple on a B->D et B->E, on aura :
$tab = array('B' => 1, 'D' => 2, 'E' => 1, etc…);

On s'arrête dès que l'on a trouvé F.

Cela s'implémente très facilement : C'est beaucoup plus simple d'utiliser un tel algorithme que de partir dans des solutions certes générales et efficaces, mais très lourdes à implémenter. Si tu veux récupérer le chemin et pas seulement la valeur, tu peux stocker des informations supplémentaires dans ton tableau, voire mieux, utiliser de l'objet. Par contre, si tu veux le faire pour tous les chemins, tu vas être obligé de revenir à un algo plus classique, mais dans ce cas je te conseillerais plutôt du Roy-Warshall, c'est pas trop compliqué et ça fait à peut près tout…

Merci de ta réponse Sékiltoyai

le problème que je vois est que je ne connais pas par avance le nombre de sommets desquels A est le prédécesseur...

En effet, le graphe que j'ai mis est très simplifié et je pourrais avoir par exemple à chercher, sur un ensemble de 100 sommets et en prenant le 25ème comme origine et le 85ème comme arrivée le chemin le plus court entre les deux. Or, dans ce cas, je ne saurai jamais quels sont (en volume et en quantitatif) le nombre de prédecesseurs du 85ème...

D'autre part, il y a une notion très importante qu'il faut prendre en compte, c'est les SENS des flèches. Je mettais dans mon 1er post que le graphe est orienté mais l'exemple que je donne n'est peut-être pas bon car on ne voit pas un "retour en arrière".

Aussi, il se peut qu'on ait à un moment ou un autre un groupe de sommets qui fasse un boucle... et là, il faudra sortir de la boucle...



C'est un exercice difficile, très difficile pour moi car je tente de me lancer là-dedans avec une expérience qui frise malheureusement zéro dans ce domaine et je n'ai pas en mains toutes les "logiques" nécessaires pour sortir, si ce n'est qu'un "pseudo code"... c'est pour dire! Mais c'est passionnant et c'est pour moi un sacré challenge... et j'y arriverai!

PS : dans la mesure où c'est un graphe non pondéré, je ne veux pas récupérer la valeur (je ne peux pas); pour moi tous les arcs valent "1". Le chemin le plus court entre deux points que je pourrai choisir, devra être celui qui utilise le moins d'arcs possibles.

le problème que je vois est que je ne connais pas par avance le nombre de sommets desquels A est le prédécesseur...

En effet, le graphe que j'ai mis est très simplifié et je pourrais avoir par exemple à chercher, sur un ensemble de 100 sommets et en prenant le 25ème comme origine et le 85ème comme arrivée le chemin le plus court entre les deux. Or, dans ce cas, je ne saurai jamais quels sont (en volume et en quantitatif) le nombre de prédecesseurs du 85ème...

Ma solution demande à ce que tu aies récupéré l'ensemble de la table. Dans la mesure où cela pourraît être important en transit de données, je te suggère d'utiliser des procédures stockées et de faire exécuter le travail directement par le serveur SQL…

D'autre part, il y a une notion très importante qu'il faut prendre en compte, c'est les SENS des flèches. Je mettais dans mon 1er post que le graphe est orienté mais l'exemple que je donne n'est peut-être pas bon car on ne voit pas un "retour en arrière".

Aussi, il se peut qu'on ait à un moment ou un autre un groupe de sommets qui fasse un boucle... et là, il faudra sortir de la boucle...

Ne t'en fait pas, j'y ai pensé, mon algorithme s'arrête automatiquement d'explorer un chemin s'il est dans une boucle, puisque s'il revient à un sommet déjà défini, il l'ignore. Si une boucle part de E, une fois que l'analyse reviendra en E, elle s'arrêtera d'explorer ce chemin puisque E est déjà dans le tableau des résultats.

PS : dans la mesure où c'est un graphe non pondéré, je ne veux pas récupérer la valeur (je ne peux pas); pour moi tous les arcs valent "1". Le chemin le plus court entre deux points que je pourrai choisir, devra être celui qui utilise le moins d'arcs possibles.

Disons que je ne partais pas du principe d'un graphe pondéré, c'est vrai qu'en y réfléchissant, vu que la valeur n'est pas utilisée, tu peux la remplacer par un tableau définissant le chemin. Par exemple :

array(
    'B' => array('A', 'B'), // On a un chemin direct entre A et B
    'C' => array('A', 'C'),
    'D' => array('A', 'B', 'D'),
    'E' => array('A', 'B', 'D', 'E') // Le chemin A->E passe par B et D
);

L'implémentation est assez immédiate, il faudra juste, en fonction de tes obligations, optimiser la communication php <-> mysql soit en faisant tout faire par mysql, soit en faisant tout faire par php, soit en rusant avec une solution qui récupérerait le minimum de données mais en un minimum de fois…

1) Le choix du meilleur itineraire pour un voyageur de commerce
[...]
Un algorithme peut être trouvé mais il donnera la première possibilité (ou la Xème en cas d'itération) mais jamais la meilleure.

C'est faux. Le voyageur de commerce est l'exemple courant permettant d'illustrer les algorithmes génétiques.

À partir de quelques points seulement, tester toutes les solutions possibles prendrait effectivement des millions d'années, c'est pour cela qu'on utilise cet algo pour rapidement arriver à une solution optimale.

Voici un exemple de mise en oeuvre où l'on voit très bien le fonctionnement de la recherche : http://magnin.plil.net/anciensite/cours ... ageur.html

J'espère me tromper pour vous mais il me semble que vous devrez "bricoler"

Pas forcément, il y a des dizaines d'algorithmes permettant de résoudre des problèmes complexes, il suffit parfois de chercher.