Philosophie ou plutôt blabla
Pensant que toutes les réponses sont dans la nature, tout est résolvable ? Peut-être pas. Newton regardant une pomme tomber en a écrit la loi universelle de la gravitation pour enfin aboutir à la mécanique terrestre et la mécanique céleste. C'est beaucoup pour une pomme !
Et bien partant de ce principe, lorsque la logique d'un seul homme est trop limité pourquoi ne pas faire appel à quelqu'un d'autre ? C'est ainsi, par exemple, que je procède dans mon travail pour modéliser des raisonnements humains. Lorsqu'une personne explique son problème, elle n'est que rarement claire. Lorsque plusieurs personnes exposent ce même problème, il est plus simple d'en définir le fond. On en déduit donc le problème majeur.
En ce qui concerne la réponse à ce problème, appliquons le même principe. Pour en trouver la solution, le recoupement de plusieurs raisonnements différents menant au même résultat permettra de définir le raisonnement générique et efficace.
Tous les savoirs sont dans la nature, interrogeons la.
Prenons l'exemple du problème du voyageur de commerce, avant de partir dans des nuits de programmation, pourquoi ne pas poser la question ? C'est ainsi que je me suis aperçu que 73% des personnes à qui j'ai demandé de résoudre le problème ont utilisé le même raisonnement. En effet, ces personnes, lorsque je leur demande de m'expliquer leur raisonement me répondent que le parcours commencera en haut à gauche ! Simple habitude de lecture ? En revanche ces personnes m'expliquent qu'ils leur semble logique de dérouler le parcours de façon circulaire dans le sens horaire en partant d'un point de départ unanimement placé en haut à gauche. Que la personne soit secrétaire ou mécanicien ou encore motard, agée de 20 ans ou 60, elles utilisent presque toutes ce même raisonnement. Ne serait-il pas le bon ? Au mathématicien de le démontrer. Seulement si ce raisonnement revient si souvent c'est qu'il y a une bonne raison, mais laquelle ? Le français regarde trop sa montre ? Et si l'homme réfléchi ainsi, pourquoi est ce que l'ordinateur ne ferait pas de même ? A suivre ...
Le voyageur de commerce
Ennoncé :
Le problème est le suivant, un voyageur de commerce doit se rendre dans n villes. Son parcours doit être le plus court, sans passer plusieurs fois par la même ville et retourner à son point départ.
Axes de réflexion :
- Modélisation binaire
- Matriçage des distances inter-villes
- Raisonnement heuristique
- Raisonnement par théorèmes de la géométrie dans le plan
Etude actuelle :
Le raisonnement sur lequel je travaille en ce moment est simple. Il s'agit de décomposer la carte en n/3 secteurs angulaires (angle entre la ville v et la ville v+2 centré sur le point de départ). Pour chaque secteur j'utilise plusieurs théorèmes de la géométrie dans le plan pour déterminer le chemin le plus court sans tous les calculer (3!). Si par cette méthode je n'obtiens aucune réponse par cette méthode, je regarde alors quel est le chemin le plus court pour lier les 3 villes du secteur avec la prochaine ville.
Le découpage se fait de façon circulaire (point de départ comme centre) le découpage s'effectue dans le sens horaire. Le point de départ peut être désigné ou déduit.
Je n'ai pas encore écrit toutes les équations mathématiques. A suivre ...
Pour l'instant la solution (approximative je pense) sera en ~ O((n/3)x4!) dans le pire des cas.
