Algos

Version imprimable

08/12/2005, 16h00
Premium

Algos

Bonjour,

je dois coder ces algos dans le cadre de mon projet.
Je sais bien que ces algos sont disponibles sur le web mais j'aurais besoin d'aide pour avoir un algo avec la meilleure complexité possible

Merci d'avance de votre aide
08/12/2005, 18h56
FrancisSourd

Re: Algo Warshall-Floyd/Prim/Kruskal/Bellman-Ford/Dijksta

Citation:

Envoyé par Man_Utd

j'aurais besoin d'aide pour avoir un algo avec la meilleure complexité possible

La question est trop vaste. Une réponse courte c'est: "lis les livres" puisqu'une réponse longue consisterait à écrire un véritable livre...

Les algos fournis dans les cours ou dans les bouquins ont déjà une bonne complexité (la meilleure connue en général): si ton code a la même complexité que le code sur le papier c'est déjà que ton projet est bien ficelé.

Il y a eu récemment une discussion sur les améliorations possibles de Dijkstra mais je ne sais pas si c'est ce que tu cherches...
http://www.developpez.net/forums/viewtopic.php?t=417123
08/12/2005, 21h58
BiLLKiLL

d'après mes cours, les complexités sont de :

Prim : O(mLogn) avec un Tas comme SD pour trouver rapidement l'arc de poids minimum appartenant au cocycle.
Kruskal : O(max(mLogn,m+ nlog n)) avec une SD Union Find
Dijkstra : O(mLogn) avec un Tas
FloydWarshall : O(n^3)
Je ne connais pas Bellman-Ford, je ne connais que Bellman tout court (O(mn) avec une liste FiFo mais de toute façon il en existe tellement de version 8O !)
09/12/2005, 10h17
FrancisSourd

Citation:

Envoyé par BiLLKiLL

Je ne connais pas Bellman-Ford, je ne connais que Bellman tout court (O(mn) avec une liste FiFo mais de toute façon il en existe tellement de version 8O !)

En général, l'algo de Ford est l'adaptation de l'algo de Bellman dans le cas où il n'y a pas de circuit dans le graphe. Grâce à cette propriété, on est assuré que l'optimum est trouvé dès la première itération de Bellman, ce qui fait un algo en O(m).
09/12/2005, 11h32
Premium

Re: Algo Warshall-Floyd/Prim/Kruskal/Bellman-Ford/Dijksta

Citation:

Envoyé par FrancisSourd

Citation:

Envoyé par Man_Utd

j'aurais besoin d'aide pour avoir un algo avec la meilleure complexité possible

La question est trop vaste. Une réponse courte c'est: "lis les livres" puisqu'une réponse longue consisterait à écrire un véritable livre...

Les algos fournis dans les cours ou dans les bouquins ont déjà une bonne complexité (la meilleure connue en général): si ton code a la même complexité que le code sur le papier c'est déjà que ton projet est bien ficelé.

Il y a eu récemment une discussion sur les améliorations possibles de Dijkstra mais je ne sais pas si c'est ce que tu cherches...
http://www.developpez.net/forums/viewtopic.php?t=417123

Je cherches juste des algos de ceux écrit dans le sujet qui soient le plus efficace possible pour mon projet de C.
Plus l'algo est rapide,plus la note obtenue sera élévée.
Si tu me dis que dans les livres,je trouverais mon bonheur,j'irais voir à la bibliothèque de ma fac voir ce que je trouve.
Est ce que tu aurais un livre d'algo à me conseiller qui traitent des algos que je recherches.
09/12/2005, 12h02
FrancisSourd

Re: Algo Warshall-Floyd/Prim/Kruskal/Bellman-Ford/Dijksta

Citation:

Envoyé par Man_Utd

Plus l'algo est rapide,plus la note obtenue sera élévée.

Il est violent ton prof d'algo :furax:

Citation:

Est ce que tu aurais un livre d'algo à me conseiller qui traitent des algos que je recherches.

Ce livre est très bien car très accès sur la programmation. Mais c'est du Delphi.
http://www.univ-valenciennes.fr/sp/sevaux/graphes/

Sur le web, je connais cette implantation en open source
http://www.math.uni-augsburg.de/opt/goblin.html
Mais je doute que la licence t'autorise à rendre ce code à ton prof en mettant ton nom;-) De toute manière, il se doutera de quelque chose!

Mais, pour avoir l'implantation la plus rapide, ce n'est plus forcément une question d'algorithmique et en tout cas pas (plus) une question de complexité. C'est le résultat d'un long travail de programmation et de tests comparant différentes implantations possibles et sélectionnant les meilleurs choix de programmation. Par exemple, selon la densité du graphe, il faudra utiliser une représentation du graphe par une matrice ou par une liste.
09/12/2005, 12h18
Premium

Re: Algo Warshall-Floyd/Prim/Kruskal/Bellman-Ford/Dijksta

Citation:

Envoyé par FrancisSourd

Citation:

Envoyé par Man_Utd

Plus l'algo est rapide,plus la note obtenue sera élévée.

Il est violent ton prof d'algo:furax:

Citation:

Est ce que tu aurais un livre d'algo à me conseiller qui traitent des algos que je recherches.

Ce livre est très bien car très accès sur la programmation. Mais c'est du Delphi.
http://www.univ-valenciennes.fr/sp/sevaux/graphes/

Sur le web, je connais cette implantation en open source
http://www.math.uni-augsburg.de/opt/goblin.html
Mais je doute que la licence t'autorise à rendre ce code à ton prof en mettant ton nom;-) De toute manière, il se doutera de quelque chose!

Mais, pour avoir l'implantation la plus rapide, ce n'est plus forcément une question d'algorithmique et en tout cas pas (plus) une question de complexité. C'est le résultat d'un long travail de programmation et de tests comparant différentes implantations possibles et sélectionnant les meilleurs choix de programmation. Par exemple, selon la densité du graphe, il faudra utiliser une représentation du graphe par une matrice ou par une liste.

CEci n'est pas un problème car je dois implémenter ces algos avec une matrice et un liste.
10/12/2005, 00h25
Sib

Pour ma part, notre prof d'algorithmique nous conseille vivement Introduction à l'Algorithmique de Thomas H. Cormen, qui est en quelque sorte sa bible..
Il l'utilise d'ailleurs pour faire son cours..

On y trouve des pseudo-algorithmes de tous les algorithmes que tu recherches..
Je pense donc que tu pourrais y trouver ton bonheur en ce qui concerne des algos efficaces ;)..

Bien sûr, il te reviendra la tâche de les implémenter en C !
14/12/2005, 15h43
Premium

Bonjour,

concernant les différents algos que je dois coder,je voudrais savoir quelle est la structure (matrice ou liste ) qui convient le mieux pour chacun des algos.
Si quelqu'un pouvait me l'indiquer,ce serait sympa.

Merci d'avance
14/12/2005, 21h01
Sib

Hop, petite liste (à toi de trouver les façons de les implémenter ;)) :

- Prim : Une file de priorité sous la forme d'un tas de Fibonacci
- Kruskal : Une structure de données d'ensembles disjoints (Union-Find structure)
- Dijkstra : Une file de priorité sous la forme d'un tas de Fibonacci

Pour les autres je ne sais pas, mais je suppose que Bellman-Ford utilise lui aussi une file de priorité, à cela près qu'elle doit aussi gérer les clés négatives..

De toute facon, tous ces algorithmes, ainsi que toutes les structures nécessaires à l'exécution de ces algorithmes de manière optimale sont expliqués dans le livre de Cormen (la bible de l'Algorithmique lol) :)

C'est une réponse un peut tardive, mes je viens de coder l'algoritme de warshall pour un besoin personnel...

Le voila :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{===============================================================================
  Convertion d'une valeur boolean en byte
===============================================================================}
Function BoolToByte(Valeur : Boolean) : Byte;
Begin
  If Valeur Then Result := 1
  Else Result := 0;
End;
{===============================================================================
  Convertion d'une valeur byte en boolean
===============================================================================}
Function ByteToBool(Valeur : Byte) : Boolean;
Begin
  If Valeur = 1 Then Result := True
  Else Result := False;
End;

Code:

1
2
3
4
5
6
7
8
9
  For K := 0 To Length(Tbl) - 1 Do
    For i := 0 To Length(Tbl) - 1 Do
      Begin
        If Tbl[I, K] Then
          For J := 0 To Length(Tbl) - 1 Do
            Begin
              Tbl[I, j] := ByteToBool(BoolToByte(Tbl[I, J]) Or BoolToByte(Tbl[K, J]));
            End;
      End;

A savoir que Tbl est un tableau dynamique de type : Array of Array Of Boolean.

J'èspere qu'il sera utile a quelqu'un :)