WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Optimisation heuristique du problème d'entreposage d'objets en trois dimensions.

( Télécharger le fichier original )
par Mulindwa Chirac RUHAMYA
Universite adventiste de Lukanga - Licence 2012
  

précédent sommaire suivant

Chapitre deuxième : METHODOLOGIE DU TRAVAIL

Ce chapitre de notre travail nous permettra de donner une présentation générale des différentes méthodes que nous aurons à utiliser pour trouver solution à l'énoncé théorique de notre problème. Les concepts qui nous intéresserons dans ce chapitre sont : la méthode algorithmique, le prototypage, l'expérimentation et l'argumentation.

II.1.Methode Algorithmique

Un algorithme répond à un problème. Il est composé d'un ensemble d'étapes simples nécessaires à la résolution d'un problème, dont le nombre varie en fonction du nombre d'éléments à traiter. D'autre part, plusieurs algorithmes peuvent répondre à un même problème. Pour savoir quelle méthode est plus efficace il faut les comparer. Pour cela, on utilise une mesure que l'on appelle la complexité. Elle représente le nombre d'étapes qui seront nécessaires pour résoudre le problème pour une entrée de taille donnée.

II.1.1. Problèmes algorithmiques

Un problème algorithmique est un problème posé de façon mathématique, c'est-à-dire qu'il est énoncé rigoureusement dans le langage des mathématiques. On distingue deux types de problèmes :

- Les problèmes de décision : ils posent une question dont la réponse est oui ou non ;

18

- Les problèmes d'optimisation : ils comportent une question ou plutôt une injonction de la forme « trouver un élément tel que ...» dont la réponse consiste à fournir un tel élément.

La théorie de la complexité étudie principalement (mais pas uniquement) les problèmes de décisions. Dans ce travail le type de problème dont nous aurons à traiter est celui d'optimisation.

II.1.2. Classes de Complexité

La théorie de la complexité est un domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement la quantité de ressources (en temps et en espace) nécessaire pour la résolution de problèmes au moyen de l'exécution d'un algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes posés mathématiquement.

Les classes de complexité sont des ensembles de problèmes qui ont la même complexité selon un certain critère. Dans ce qui suit nous allons définir trois classes de complexité les plus étudiées en une liste qui va de la complexité la plus basse à la complexité la plus haute : la classe P, la classe NP et la classe NP-C.

a. La classe P

Un problème de décision est dans P s'il peut être décidé sur une machine déterministe en temps polynomial par rapport à la taille de la donnée. On qualifie

alors le problème de polynomial. C'est un problème de complexité O(nk), pour un certain k. On admet, en général, que les problèmes dans P sont ceux qui sont faciles à

résoudre.

b. La classe NP

La classe NP possède une définition moins naturelle que celle de P, et ne signifie pas "non polynomial", mais polynomial non-déterministe. La classe NP est donc une

19

extension de la classe P, en autorisant des choix non déterministes pendant l'exécution de l'algorithme. Si le modèle de calcul est celui des machines de Turing, on autorise plusieurs transitions à partir d'un état et d'un symbole lu sur la bande.

c. La classe NP-Complet

En théorie de la complexité, un problème NP-complet est un problème vérifiant les propriétés suivantes :

- Il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP.

- Tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de la classe NP.

Un problème NP-difficile est un problème qui remplit la seconde condition, et donc peut être dans une classe de problème plus large et donc plus difficile que la classe NP.

Bien qu'on puisse vérifier rapidement toute solution proposée d'un problème NP-complet, on ne sait pas en trouver efficacement. C'est le cas, par exemple, du problème du voyageur de commerce, celui du sac à dos ou encore celui de remplissage des paniers.

Une question reste ouverte et fait partie des problèmes non résolus en mathématiques les plus importants à ce jour. Celui de prouver s'il existe un algorithme polynomial pour résoudre un quelconque des problèmes NP-complets, si oui, alors tous les problèmes de la classe NP peuvent être résolus en temps polynomial. Trouver un algorithme polynomial pour un problème NP-complet ou prouver qu'il n'en existe pas permettrait de savoir si P = NP ou P ? NP.

20

En pratique, les informaticiens et les développeurs sont souvent confrontés à des problèmes NP-complets, ce qui est d'ailleurs le cas pour nous dans ce travail. Savoir que le problème sur lequel on travaille est NP-complet est une indication du fait que le problème est difficile à résoudre, donc qu'il vaut mieux chercher des solutions approchées en utilisant des algorithmes d'approximation ou des heuristiques pour trouver des solutions approximatives.

précédent sommaire suivant







9Impact, le film from Onalukusu Luambo on Vimeo.



Appel aux couturier(e)s volontaires

Hack the pandemiuc !

Moins de 5 interactions sociales par jour



BOSKELYWOOD from Ona Luambo on Vimeo.