Author Topic: Theorie des graphes  (Read 5541 times)

0 Members and 1 Guest are viewing this topic.

Offline maracuja

  • Base
    • View Profile
Theorie des graphes
« on: 21 January 2011 à 14:00:04 »
Salut,

Y aurait il des personnes qui pourraient faire un rappel sur la théorie des graphes, histoire de se rafraichir la mémoire.


Offline Patapom

  • Base
    • View Profile
    • www.patapom.com
  • Ancienneté: 1988
  • Groupe: Bomb!
  • Rôle: Coder
  • Ville: Lyon
Re : Theorie des graphes
« Reply #1 on: 21 January 2011 à 14:35:07 »
Je vais faire mon mesquin : http://en.wikipedia.org/wiki/Graph_theory ;D
.  Pom  .

Offline maracuja

  • Base
    • View Profile
Re : Theorie des graphes
« Reply #2 on: 21 January 2011 à 14:51:04 »
Effectivement, mais j'aurai choisi la page française. :D

Tu la joues mesquins, moi aussi :D : Quand tu codes un jeu, tu t'en sert forcément, par ex pour l'intelligence artificielle ou le traitement des images ? Craches le fromage :P (merde, c'est une pomme... alala :=))

Offline krabob

  • Base
    • Pouet.net
    • View Profile
    • www.m4nkind.com
  • Ancienneté: 1994
  • Groupe: Mankind
  • Rôle: code amiga / linux / OpenGL
  • Ville: Toulouse
Re : Theorie des graphes
« Reply #3 on: 21 January 2011 à 14:52:08 »
super un thread intéressant.
 ??? heu... heu ... ouai ya une histoire d'algo avec des piles ou un truc comme ça pour calculer le plus cours chemin d'un point A à un point B avec des poids pour les liens... oulà ça fait vieux dans ma tête.  :o

 ->
Algorithmes de résolution du problème classique de plus court chemin

 mouaip en fait j'avais du faire du Dijkstra dans mon vieux temps

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
« Last Edit: 21 January 2011 à 14:59:52 by krabob »
Votez comme ça Mélenchon ... ou Clément Wittman, ... ou Eva ! Oo

Offline maracuja

  • Base
    • View Profile
Re : Theorie des graphes
« Reply #4 on: 21 January 2011 à 14:56:25 »
Ce dont je me souviens, c'est qu'on a :
Un parcours en profondeur et en largeur. Le profondeur se déroule avec une pile et l'autre avec une file.
On peut calculer le plus court chemin d'un sommet vers tous les autres avec l'algo de Dijkstra si l'on a pas de circuit absorbant et que les valuations des arcs sont strictement positif. (mais ca semble assez lourd pour un jeu. Surtout si on doit le faire souvent avec un nombre de sommets assez important)
D'ailleurs si je comprends le baratin mathématique énoncé dans les pages citées par Krabob et Patapom : l'algo Dijsktra est un parcours en profondeur modifie. On doit parcourir en largeur et prendre l'arc de plus faible poids et itérer cela jusqu'a ce qu'on ne puisse plus parcourir car l'on aura tout visité sur le graphe ?
« Last Edit: 21 January 2011 à 15:01:06 by maracuja »

Offline Patapom

  • Base
    • View Profile
    • www.patapom.com
  • Ancienneté: 1988
  • Groupe: Bomb!
  • Rôle: Coder
  • Ville: Lyon
Re : Theorie des graphes
« Reply #5 on: 21 January 2011 à 15:01:42 »
Le seul truc que j'aie jamais codé pour de l'IA c'est A* ...
http://en.wikipedia.org/wiki/A*_search_algorithm
.  Pom  .

Offline maracuja

  • Base
    • View Profile
Re : Theorie des graphes
« Reply #6 on: 21 January 2011 à 15:03:24 »
Le seul truc que j'aie jamais codé pour de l'IA c'est A* ...
http://en.wikipedia.org/wiki/A*_search_algorithm

Ok c'est noté :=)
Meurchi :p

Offline maracuja

  • Base
    • View Profile
Re : Theorie des graphes
« Reply #7 on: 21 January 2011 à 15:04:36 »
super un thread intéressant.
 ??? heu... heu ... ouai ya une histoire d'algo avec des piles ou un truc comme ça pour calculer le plus cours chemin d'un point A à un point B avec des poids pour les liens... oulà ça fait vieux dans ma tête.  :o

 ->
Algorithmes de résolution du problème classique de plus court chemin

 mouaip en fait j'avais du faire du Dijkstra dans mon vieux temps

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

Merci Krabob :)

Offline LLB

  • Base
    • Pouet.net
    • Coup de coeur
    • View Profile
    • site perso
  • Ancienneté: 2000
  • Groupe: Ctrl-Alt-Test
  • Rôle: code
  • Ville: Munich
Re : Theorie des graphes
« Reply #8 on: 21 January 2011 à 15:05:08 »
Quote
l'algo Dijsktra est un parcours en profondeur modifie. On doit parcourir en largeur et prendre l'arc de plus faible poids et itérer cela jusqu'a ce qu'on ne puisse plus parcourir car l'on aura tout visité sur le graphe ?
C'est un parcours en largeur modifié. En fait, quand tous les poids sont égaux (ce qui arrive souvent pour les jeux), tu peux remplacer l'algo de Dijkstra par un parcours en largeur classique.

Offline maracuja

  • Base
    • View Profile
Re : Theorie des graphes
« Reply #9 on: 21 January 2011 à 15:08:10 »
Dans quel cas cela peut arriver ? Tu aurais un exemple concret pour illustrer le fait que tous les poids sont égaux ?

Offline LLB

  • Base
    • Pouet.net
    • Coup de coeur
    • View Profile
    • site perso
  • Ancienneté: 2000
  • Groupe: Ctrl-Alt-Test
  • Rôle: code
  • Ville: Munich
Re : Theorie des graphes
« Reply #10 on: 21 January 2011 à 15:12:03 »
Ça arrive souvent de représenter une map par un tableau 2D, chaque case a une valeur pour savoir si c'est un obstacle ou non. Tu cherches le plus court chemin pour déplacer ton unité.

Si pour aller d'une case à celle d'à côté, tu mets toujours le même temps, tu peux faire un parcours en largeur. Si tu ajoutes des trucs du genre "en montée ou pour traverser une rivière, on avance deux fois moins vite", alors tu as des poids différent et il vaut mieux utiliser Dijkstra.

Offline maracuja

  • Base
    • View Profile
Re : Theorie des graphes
« Reply #11 on: 21 January 2011 à 15:14:25 »
Ok :)

Offline LLB

  • Base
    • Pouet.net
    • Coup de coeur
    • View Profile
    • site perso
  • Ancienneté: 2000
  • Groupe: Ctrl-Alt-Test
  • Rôle: code
  • Ville: Munich
Re : Theorie des graphes
« Reply #12 on: 21 January 2011 à 15:30:19 »
Pour répondre à ta question de départ, la théorie des graphes est quelque chose d'assez large et générique. En pratique, on travaille souvent sur des graphes particuliers, ce qui simplifie beaucoup de choses. Beaucoup d'algos génériques sur les graphes que j'avais vus en cours ne m'ont jamais été utiles.

Par exemple, un arbre est un graphe particulier. Les algos sur les arbres peuvent donc t'intéresser (arbre binaire de recherche, quadtree...).
Comme dans mon autre exemple, un tableau 2D peut être vu comme un graphe. En traitement d'image, tu peux utiliser un algo de remplissage.
Ça m'est arrivé d'avoir un graphe de dépendance. Tu as une liste de tâches, certaines tâches dépendent d'autres tâches. Tu peux faire un tri topologique pour trouver dans quel ordre faire les choses (j'imagine que ça peut servir pour une IA).

Offline krabob

  • Base
    • Pouet.net
    • View Profile
    • www.m4nkind.com
  • Ancienneté: 1994
  • Groupe: Mankind
  • Rôle: code amiga / linux / OpenGL
  • Ville: Toulouse
Re : Theorie des graphes
« Reply #13 on: 21 January 2011 à 15:38:11 »
ptin ça pourrait trop servir à des effets de demo du genre par exemple, un générateur d'éclair !
Votez comme ça Mélenchon ... ou Clément Wittman, ... ou Eva ! Oo

Offline LLB

  • Base
    • Pouet.net
    • Coup de coeur
    • View Profile
    • site perso
  • Ancienneté: 2000
  • Groupe: Ctrl-Alt-Test
  • Rôle: code
  • Ville: Munich
Re : Theorie des graphes
« Reply #14 on: 21 January 2011 à 15:42:23 »
Pour générer des éclairs, je te suggère les L-systems (je ne sais pas s'il y a des meilleures approches, mais celle-là marche). Ça sert aussi à générer des arbres et d'autres formes arborescentes (il y en a plusieurs exemples dans Incubation).