University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Refoufi,A |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Les algorithmes approchés pour le probléme de voyageur de commerce Type de document : texte imprimé Auteurs : Bensedira,Houria, Auteur ; Refoufi,A, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (42 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : TSP (PVC)
heuristique
PPV (Plus Proche Voisin)
2-OptIndex. décimale : 004 - Informatique Résumé :
Résumé
Un voyageur veut visiter certain nombre de villes, débutant et finissant son parcours dans la même ville en visitant chacune des villes une et une seule fois. Ce problème est connu sous le nom du problème de voyageur de commerce (PVC).
Le problème de voyageur de commerce (TSP) est un problème classique d’optimisation combinatoire NP-complet. Des heuristiques ont été proposées permettant de trouver des solutions presque optimales, on distingue trois classes d’heuristiques : de construction, d’amélioration et métaheuristiques. D’après l’étude sur le PVC, nous proposons une hybridation de deux méthodes, nous avons choisi parmi les heuristiques de construction l’algorithme de plus proche voisin (PPV), et parmi les heuristiques d’amélioration on a l’euristique 2-OptNote de contenu : Sommaire
Introduction générale…………….………………………………………………………………….1
Chapitre 1………………………………………………………………………………………………3
1. Introduction..................................................................................................................3
2. Définition de base..........................................................................................................3
2.1. classe P .................................................................................................................4
2.2. Problème de classe NP :..............................................................................................................4
2.2.1. Classe NP-complet : .............................................................................................................4
2.3. Classe NP-difficiles : .............................................................................................4
2.4. Notions sur les graphes :..............................................................................................5
a. Un graphe .................................................................................................................5
b. Graphe complet......................................................................................................................5
c. Cycle hamiltonien...............................................................................................................5
d. Un graphe pondéré ............................................................................................................5
2.5. Notion de complexité algorithmique : ...................................................................................6
3. Problème de voyageur de commerce :..........................................................................................7
3.1. Définition : .......................................................................................................7
a. Domaines d’applications : .....................................................................................................8
b. Exemple : ................................................................................................................................8
4. Méthodes de résolution du TSP :................................................................................................10
4.1. Les algorithmes exacts :............................................................................................................10
4.1.1. Méthodes des plans sécants (Cutting plane) :..................................................................10
4.1.2. Algorithme Branch & Bound (séparation-évaluation) ...................................................11
4.1.2.1 Branch and Bound pour le problème de TSP : .........................................................12
5. Conclusion ....................................................................................................................................12
Chapitre 2…………………………………………………………………………………….13
1. Introduction .......................................................................................................................... 13
2. C’est quoi les heuristiques : .................................................................................................. 13
3. Les algorithmes d’approximation du TSP : .......................................................................... 13
3.1 Heuristiques de construction : ............................................................................................. 14
3.1.1 L’euristique de plus proche voisin (Nearest Neighbor) : .............................................. 14
3.1.2 L’euristique de Greedy : ............................................................................................... 14
3.1.3 Heuristique de Christofides : ................................................................................. 15
a. Principe : .................................................................................................................... 15
3.2 Les heuristiques d’amélioration : ........................................................................................ 18
3.2.1 Algorithme de recherche local ...................................................................................... 18
a. 2-opt heuristique : ...................................................................................................... 18
b. 3-opt heuristique : ...................................................................................................... 18
c. k-Opt : ........................................................................................................................ 19
3.3 Les métaheuristiques :......................................................................................................... 20
3.3.1 Algorithme génétique : .............................................................................................. 20
a. Principe : .................................................................................................................... 21
b. L’algorithme génétique pour TSP : ........................................................................... 21
3.3.2 Recherche de tabou : ................................................................................................. 21
3.3.3 L’euristique de colonie de fourmis : .......................................................................... 22
a. Principe : .................................................................................................................... 23
4. Conclusion ............................................................................................................................. 24
Chapitre 3……………………………………………………………………………………..25
1. Introduction...................................................................................................................................25
2. Conception de TSP: ......................................................................................................................25
2.1. Description de TSP : .............................................................................................................25
2.2. Description de notre approche : ..........................................................................................26
2.2.1. Description d’heuristique de plus proche voisin :......................................................26
2.2.2. Description d’heuristique 2-Opt :................................................................................28
2.2.3. L’heuristique 3-opt : .....................................................................................................30
2.2.4. Diagramme de classe : ..................................................................................................30
2.2.5. La complexité des algorithmes :...................................................................................32
3. Implementation .............................................................................................................................33
3.1. Outils de développement ..................................................................................................33
Java .......................................................................................................................33
NetBeans ......................................................................................................................34
3.2. Description du prototype réalisé : ...................................................................................34
4. Conclusion ...............................................................................................................41
Conclusion générale………………………………………………………………………….42Côte titre : MAI/0259 Les algorithmes approchés pour le probléme de voyageur de commerce [texte imprimé] / Bensedira,Houria, Auteur ; Refoufi,A, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (42 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : TSP (PVC)
heuristique
PPV (Plus Proche Voisin)
2-OptIndex. décimale : 004 - Informatique Résumé :
Résumé
Un voyageur veut visiter certain nombre de villes, débutant et finissant son parcours dans la même ville en visitant chacune des villes une et une seule fois. Ce problème est connu sous le nom du problème de voyageur de commerce (PVC).
Le problème de voyageur de commerce (TSP) est un problème classique d’optimisation combinatoire NP-complet. Des heuristiques ont été proposées permettant de trouver des solutions presque optimales, on distingue trois classes d’heuristiques : de construction, d’amélioration et métaheuristiques. D’après l’étude sur le PVC, nous proposons une hybridation de deux méthodes, nous avons choisi parmi les heuristiques de construction l’algorithme de plus proche voisin (PPV), et parmi les heuristiques d’amélioration on a l’euristique 2-OptNote de contenu : Sommaire
Introduction générale…………….………………………………………………………………….1
Chapitre 1………………………………………………………………………………………………3
1. Introduction..................................................................................................................3
2. Définition de base..........................................................................................................3
2.1. classe P .................................................................................................................4
2.2. Problème de classe NP :..............................................................................................................4
2.2.1. Classe NP-complet : .............................................................................................................4
2.3. Classe NP-difficiles : .............................................................................................4
2.4. Notions sur les graphes :..............................................................................................5
a. Un graphe .................................................................................................................5
b. Graphe complet......................................................................................................................5
c. Cycle hamiltonien...............................................................................................................5
d. Un graphe pondéré ............................................................................................................5
2.5. Notion de complexité algorithmique : ...................................................................................6
3. Problème de voyageur de commerce :..........................................................................................7
3.1. Définition : .......................................................................................................7
a. Domaines d’applications : .....................................................................................................8
b. Exemple : ................................................................................................................................8
4. Méthodes de résolution du TSP :................................................................................................10
4.1. Les algorithmes exacts :............................................................................................................10
4.1.1. Méthodes des plans sécants (Cutting plane) :..................................................................10
4.1.2. Algorithme Branch & Bound (séparation-évaluation) ...................................................11
4.1.2.1 Branch and Bound pour le problème de TSP : .........................................................12
5. Conclusion ....................................................................................................................................12
Chapitre 2…………………………………………………………………………………….13
1. Introduction .......................................................................................................................... 13
2. C’est quoi les heuristiques : .................................................................................................. 13
3. Les algorithmes d’approximation du TSP : .......................................................................... 13
3.1 Heuristiques de construction : ............................................................................................. 14
3.1.1 L’euristique de plus proche voisin (Nearest Neighbor) : .............................................. 14
3.1.2 L’euristique de Greedy : ............................................................................................... 14
3.1.3 Heuristique de Christofides : ................................................................................. 15
a. Principe : .................................................................................................................... 15
3.2 Les heuristiques d’amélioration : ........................................................................................ 18
3.2.1 Algorithme de recherche local ...................................................................................... 18
a. 2-opt heuristique : ...................................................................................................... 18
b. 3-opt heuristique : ...................................................................................................... 18
c. k-Opt : ........................................................................................................................ 19
3.3 Les métaheuristiques :......................................................................................................... 20
3.3.1 Algorithme génétique : .............................................................................................. 20
a. Principe : .................................................................................................................... 21
b. L’algorithme génétique pour TSP : ........................................................................... 21
3.3.2 Recherche de tabou : ................................................................................................. 21
3.3.3 L’euristique de colonie de fourmis : .......................................................................... 22
a. Principe : .................................................................................................................... 23
4. Conclusion ............................................................................................................................. 24
Chapitre 3……………………………………………………………………………………..25
1. Introduction...................................................................................................................................25
2. Conception de TSP: ......................................................................................................................25
2.1. Description de TSP : .............................................................................................................25
2.2. Description de notre approche : ..........................................................................................26
2.2.1. Description d’heuristique de plus proche voisin :......................................................26
2.2.2. Description d’heuristique 2-Opt :................................................................................28
2.2.3. L’heuristique 3-opt : .....................................................................................................30
2.2.4. Diagramme de classe : ..................................................................................................30
2.2.5. La complexité des algorithmes :...................................................................................32
3. Implementation .............................................................................................................................33
3.1. Outils de développement ..................................................................................................33
Java .......................................................................................................................33
NetBeans ......................................................................................................................34
3.2. Description du prototype réalisé : ...................................................................................34
4. Conclusion ...............................................................................................................41
Conclusion générale………………………………………………………………………….42Côte titre : MAI/0259 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0259 MAI/0259 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : La Résolution des anaphores pronominales dans le TAL Type de document : texte imprimé Auteurs : SAHRAOUI, Brahim ; Refoufi,A, Directeur de thèse Editeur : Setif:UFA Année de publication : 2011 Importance : 1 vol (70 f .) Format : 29 cm Catégories : Thèses & Mémoires:Informatique Mots-clés : Anaphores pronominales
Résolution d'anaphores pronominales
Chaîne de coréférence
Filtre syntaxique
Calcul de saillanceIndex. décimale : 004 Informatique Résumé :
La résolution des liens anaphorique est importante pour la « compréhension» d'un texte en langue naturelle par un ordinateur. Dans ce travail, nous nous intéressons aux anaphores pronominales dont l’antécédent est un groupe nominalLa résolution consiste à parcourir la représentation syntaxique en recherchant les pronoms et les groupe nominaux qui les précèdent. Ensuite, on éliminera les candidats selon des critères morphosyntaxiques, s’il nous reste plus qu’un candidat en sélection un selon des préférences. Et pour tester notre algorithme nous l’avons implémenté en PrologCôte titre : MI/0003-0004 En ligne : http://dspace.univ-setif.dz:8888/jspui/bitstream/123456789/2058/1/sahraoui.pdf La Résolution des anaphores pronominales dans le TAL [texte imprimé] / SAHRAOUI, Brahim ; Refoufi,A, Directeur de thèse . - [S.l.] : Setif:UFA, 2011 . - 1 vol (70 f .) ; 29 cm.
Catégories : Thèses & Mémoires:Informatique Mots-clés : Anaphores pronominales
Résolution d'anaphores pronominales
Chaîne de coréférence
Filtre syntaxique
Calcul de saillanceIndex. décimale : 004 Informatique Résumé :
La résolution des liens anaphorique est importante pour la « compréhension» d'un texte en langue naturelle par un ordinateur. Dans ce travail, nous nous intéressons aux anaphores pronominales dont l’antécédent est un groupe nominalLa résolution consiste à parcourir la représentation syntaxique en recherchant les pronoms et les groupe nominaux qui les précèdent. Ensuite, on éliminera les candidats selon des critères morphosyntaxiques, s’il nous reste plus qu’un candidat en sélection un selon des préférences. Et pour tester notre algorithme nous l’avons implémenté en PrologCôte titre : MI/0003-0004 En ligne : http://dspace.univ-setif.dz:8888/jspui/bitstream/123456789/2058/1/sahraoui.pdf Exemplaires (2)
Code-barres Cote Support Localisation Section Disponibilité MI/0003 MI/0003- 0004 Mémoire Bibliothéque des sciences Français Disponible
DisponibleMI/0004 MI/0003- 0004 Mémoire Bibliothéque des sciences Français Disponible
Disponible
