Chapitre 7 : L'heuristique

Description

C'est quoi? Selon le granddictionnaire.com, l'heuristique est une "méthode de recherche empirique ayant recours aux essais et erreurs pour la résolution de problèmes".

En d'autres mots, on essait de trouver une démarche pour résoudre un problème de façon non mathématique. C'est lorsque la pratique vient aider la théorie. L'idée est de tenter de cibler notre problème en but d'améliorer l'efficacité de notre solution.

Exemple du paintball: il y a un léger vent sur le terrain de paintball. Un adversaire est en avant de moi et je veux le marquer. En théorie, je pourrais calculer l'angle de tir en analysant la vitesse de la balle, le poids de la balle, la vitesse et la direction du vent, etc.. Mais ça serait beaucoup trop long et l'adversaire aurait eu le temps de se déplacer bien avant que je sorte ma T.I. et des feuilles pour mes calculs. Au lieu de faire cela, je peut adopter une approche heuristique. Je tire donc droit en avant de moi, je rate de 10 mètres à droite. Je change mon angle légèrement vers la gauche, pas assez loin. Finalement, je monte l'inclinaison de mon marqueur. Touché! Ce n'est pas tout à fait une approche aléatoire. En effet, on fait une prédiction au début et on corrige au fur et à mesure avec nos résultats.

Exemple de tri: on veut trier un très très gros tableau avec un tri rapide (quicksort) et améliorer sa vitesse. On insère un tri par insertion à l'intérieur de sorte que lorsque le quicksort essait de trier 10 éléments, il donne les 10 éléments au tri par insertion. Mais on ne sait pas si on devrait donner 10, 15 ou 100 éléments à notre tri par insertion. En utilisant une approche heuristique, on peut arriver à trouver un nombre clé. Ainsi, d'après le degré de désordre, il se peut qu'on s'aperçoit, en faisant varier le nombre de 10 à 50, que le meilleur nombre est 15. Donc, pour l'avenir, lorsque notre tableau possédera un degré de désordre de 50, une table externe pourrait nous dire que notre tri devrait utilisé le nombre 15 pour maximiser ses performances.

Des noms et des noms...

Algorithme de Dijkstra
Permet de trouver le chemin de coût minimal entre deux noeuds dans un graphe orienté. (voir Moore). Dynamique.
Algorithmes DSATUR (Brélaz 1979)
Permet de trouver des solutions optimales sur des graphes bipartites
Algorithme de Fisher-Price
Rappeler vous "jouet" et "boîtes". L'argorithme de Fischer-Price essait de mettre le maximum de Jouets dans le minimum de boîtes.
Algorithmes Gloutons
Algorithme qui utilise toujours le meilleur choix pour avancer et ne recule jamais en arrière. Il y a presque toujours un tri avant d'utiliser l'algorithme. Il n'est pas toujours correct. Le tri sert habituellement à fixer un ordre de parcours. Il est souvent d'ordre O(n).
  • Maximiser le nombre de projets, minimiser les ressources. (trier par coûts des ressources par projet)
  • Colorier un graphique avec le moins de couleurs possibles. (trier par nombres de liens par noeud)
  • Payer un montant avec le moins de pièces possibles. (trier par valeur des pièces)
Algorithmes Greedy
voir algorithmes gloutons
Algorithme de Huffman
Algorithme basé sur les férquences (de caractères par exemples) de type glouton.
  1. Trier les caractères en ordre de fréquences
  2. Choisir dans la liste les 2 noeuds (n1, n2) dont la fréquences est minimale.
  3. On les regroupe en un noeud pour former un sous-arbre dont la fréquence est la Somme des fréquences de N1 et N2.
  4. Ensuite la fréquence la plus élevé formera la chaîne 0, ensuite 10, 110, 111...
Algorithme de Prim/Kruskal
"Pour trouver un arbre de recouvrement minimal sur un graphe." (minimum spanning tree). L'algorithme de Prim est O(S²) mais avec une implémentation avec un heap, on obtient O(|A|log(S)) ou S est le nombre de sommet et A le nombre d'arrêtes?? Principes: 
1. Partir d'un noeud au hasard. 
2. Regarder son entourage. (remplir tableau)
3. Aller au noeud le moins loin.
4. Regarder son entourage. (remplir le tableau en regardant s'il n'est pas moins long d'un noeud déjà vu).
5. Répéter tant qu'on a pas visité tous les noeuds.
L'algorithme de Kruskal:
1. Trier les arcs par coût minimum.
2. Tant qu'il y a des sommets non lus
   2.1 Ajouter l'arc minimum si on ne forme pas de cycle ( cycle = 1-2-3-1 )
Algorithme de Moore
Permet de trouver le chemin minimal d'un graphe orienté (tous les chemins ont un coût de 1)
Algorithmes Voraces
voir algorithmes gloutons

Chapitre 8 : La programmation dynamique

Pourquoi calculer deux fois une réponse qui pourrait être stockée dans un tableau?

Nombre de produits scalaires pour le produit matriciel d'une matrice M (m1*c) avec la matrice N (c*n2) = m1*c*n2.

Lorsqu'on remplit le tableau, on trouve le minimum en utilisant les résultats précédents et en calculant les nouveaux.

Case (AB) = 4*2*3 = 24
Case (BC) = 2*3*1 =  6
Case (AC) = min( (AB)C,      A(BC) )
          = min(AB + (4x3)C, A(2x1) + BC) 
          = min(AB + 4x3x1 , 4*2*1 + BC)
          = min(24+12, 8+6)
          = 14

Chapitre 9- Non déterministes

Différence entre Monte Carlo et Las Vegas?

Monte Carlo
On arrive toujours à un résultat. Mais il est parfois incorrect. (étudiant bavard)
Las Vegas
On arrive toujours à une réponse correcte. Mais il ne la donne pas tout le temps. (étudiant bollé gêné)

Source et hyperliens...

Lire les commentaires | Laisser un commentaire