Scribd Logo
Importer

Bienvenue sur Scribd !

  • 210 vues

    Complexité

    Transféré par

    Sami Krifa
    Le document décrit le problème de clique maximale et les différentes approches pour le résoudre, notamment les heuristiques, métaheuristiques et méthodes exactes.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Complexité

    Transféré par

    Sami Krifa
    210 vues9 pages
    Le document décrit le problème de clique maximale et les différentes approches pour le résoudre, notamment les heuristiques, métaheuristiques et méthodes exactes.

    Description originale:

    complexité

    Titre original

    Ro Complexité (1)

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Le document décrit le problème de clique maximale et les différentes approches pour le résoudre, notamment les heuristiques, métaheuristiques et méthodes exactes.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    210 vues9 pages

    Complexité

    Transféré par

    Sami Krifa
    Le document décrit le problème de clique maximale et les différentes approches pour le résoudre, notamment les heuristiques, métaheuristiques et méthodes exactes.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 9

    problème de

    Clique maximale
    Les membres :
    -Jaber Khalil
    -Meriam Gnichi
    -Fedi Lahbib

    Projet RO complexité
    Sommaire :
    1.Présentation du Probléme:

    a.Définition

    b.Formulation Mathématique

    c.Application réelles

    2.Définition des classes d’algorithmes :

    a.Heuristique

    b.Métaheuristique

    c.Exactes

    d.Approche
    1.Présentation du Probléme:
    a.Définition

    Le problème de clique maximum (MCP) est de trouver un sous-graphe complet de cardinalité


    maximale dans un graphe général.

    Une clique est maximale si elle n'est contenue dans aucune autre clique, une clique est
    maximale si sa cardinalité est le plus grand parmi toutes les cliques du graphe.

    Exemple de graphe possédant une 3-clique (en rouge)


    :
    b.Formulation mathématique

    Soit G = (V, E) un graphe avec l'ensemble de sommets V = {1,. . . , n} et jeu


    d'arêtes E.

    il existe une clique C de G est un sous-ensemble de V tel que tous les deux
    sommets de C sont adjacents, c'est-à-dire ∀u, v ∈ C, {u, v} ∈ E avec C de taille
    k tel que 1≤ k≤|V|
    c.Application réelles

    -bioinformatique et chimio-informatique

    -théorie du codage

    -économie

    -planification des examens

    -réseaux financiers

    -analyse de la transmission du signal

    -réseau social

    -une analyse réseaux sans fil et télécommunications


    2.Définition des classes d’algorithmes :
    a.Heuristique:

    Une heuristique est un terme donné à une classe d’algorithmes utilisées pour
    déterminer en temps réel une solution réalisable à un problème d’optimisation
    complexe. En optimisation combinatoire, théorie des graphes et théorie de la
    complexité, une heuristique est un algorithme qui fournit rapidement une solution
    réalisable, mais pas nécessairement optimale, pour un problème d'optimisation
    complexe
    b.Métaheuristique
    ● Une métaheuristique est une technique de
    résolution spécialisée à un problème. Elle ne
    garantit pas la qualité du point obtenu.
    ● Une métaheuristique est une heuristique
    générique qu’il faut adapter à chaque
    problème.
    ● Les métaheuristiques sont des stratégies qui
    permettent de guider la recherche d’une
    solution.
    ● Les métaheuristiques sont en général
    non-déterministes et ne donnent aucune optimum global (G) d’un problème d’optimisation
    les optima locaux (L).
    garantie d’optimalité.
    ● elles sont généralement des algorithmes
    stochastiques itératifs, qui progressent vers un
    optimum global.
    c.Exactes

    ● Dans Les méthodes exactes toutes les solutions de l’espace de recherche sont
    énumérées implicitement en utilisant des mécanismes qui détectent des échecs
    (calcul de bornes). Grâce à Ces méthodes on peut trouver des solutions optimales.
    Mais ces méthodes s’avèrent, malgré les progrès réalisés, plutôt inefficaces à
    mesure que la taille du problème devient importante.
    ● Les méthodes exactes ont permis de trouver des solutions optimales pour des
    problèmes de taille raisonnable et rencontrent généralement des difficultés face
    aux applications de taille importante.
    ● Dans cette classe des méthodes exactes, on peut trouver les algorithmes
    classiques suivants : La programmation dynamique, La programmation linéaire,
    Les méthodes de recherche arborescente (Branch & bound) .
    d.Approche

    Une méthode approchée (incomplètes) est une méthode d'optimisation qui a pour
    but de trouver une solution réalisable de la fonction objective en un temps
    raisonnable, mais sans garantie d'optimalité. L’avantage principal de ces méthodes
    est qu'elles peuvent s'appliquer à n'importe quelle classe de problèmes, faciles ou
    très difficiles .

    Vous aimerez peut-être aussi