{"id":58258,"date":"2021-04-09T11:25:59","date_gmt":"2021-04-09T10:25:59","guid":{"rendered":"https:\/\/datascientest.com\/?p=58258"},"modified":"2023-11-09T14:07:49","modified_gmt":"2023-11-09T14:07:49","slug":"lalgorithme-a-a-star-algorithm","status":"publish","type":"post","link":"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm","title":{"rendered":"L\u2019algorithme A* (A star algorithm)"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-post\" data-elementor-id=\"58258\" class=\"elementor elementor-58258\" data-elementor-post-type=\"post\">\n\t\t\t\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-f770113 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f770113\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-7c65f81\" data-id=\"7c65f81\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ff8d9ad elementor-widget elementor-widget-heading\" data-id=\"ff8d9ad\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-heading-title{padding:0;margin:0;line-height:1}.elementor-widget-heading .elementor-heading-title[class*=elementor-size-]>a{color:inherit;font-size:inherit;line-height:inherit}.elementor-widget-heading .elementor-heading-title.elementor-size-small{font-size:15px}.elementor-widget-heading .elementor-heading-title.elementor-size-medium{font-size:19px}.elementor-widget-heading .elementor-heading-title.elementor-size-large{font-size:29px}.elementor-widget-heading .elementor-heading-title.elementor-size-xl{font-size:39px}.elementor-widget-heading .elementor-heading-title.elementor-size-xxl{font-size:59px}<\/style><h2 class=\"elementor-heading-title elementor-size-default\">On a trait\u00e9 dans un pr\u00e9c\u00e9dent article de l\u2019importance des algorithmes de recherche de plus court chemin en th\u00e9orie des graphes, notamment avec l\u2019exemple de l\u2019algorithme de Dijkstra.\nIl existe d\u2019autres algorithmes encore plus performants dans certaines situations, comme en cartographie ou dans le gaming. On retient par exemple l\u2019algorithme A*, dit \u2018A star algorithm\u2019 en anglais. D\u00e9couvrons son fonctionnement dans cet article :<\/h2>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-e5993c5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e5993c5\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-690a861\" data-id=\"690a861\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-93571ef elementor-widget elementor-widget-text-editor\" data-id=\"93571ef\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-text-editor.elementor-drop-cap-view-stacked .elementor-drop-cap{background-color:#69727d;color:#fff}.elementor-widget-text-editor.elementor-drop-cap-view-framed .elementor-drop-cap{color:#69727d;border:3px solid;background-color:transparent}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap{margin-top:8px}.elementor-widget-text-editor:not(.elementor-drop-cap-view-default) .elementor-drop-cap-letter{width:1em;height:1em}.elementor-widget-text-editor .elementor-drop-cap{float:left;text-align:center;line-height:1;font-size:50px}.elementor-widget-text-editor .elementor-drop-cap-letter{display:inline-block}<\/style>\t\t\t\t<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">L\u2019algorithme A* est un algorithme heuristique qui permet de trouver <\/span><b>tr\u00e8s rapidement<\/b><span style=\"font-weight: 400;\"> un plus court chemin entre deux points avec d\u2019\u00e9ventuels obstacles. Outre sa vitesse, cet algorithme est r\u00e9put\u00e9 pour <\/span><b>garantir<\/b><span style=\"font-weight: 400;\"> une solution en sortie.<\/span><\/span><\/p><p><span style=\"font-weight: 400; color: #000000;\">NB : Un algorithme heuristique est un proc\u00e9d\u00e9 qui permet d\u2019obtenir une solution r\u00e9alisable tr\u00e8s rapidement \u00e0 un probl\u00e8me d\u2019optimisation complexe. La solution fournie en sortie de l\u2019algorithme n\u2019est cependant pas garantie d\u2019\u00eatre optimale.<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ac5c55b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ac5c55b\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-0765264\" data-id=\"0765264\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-32d5598 elementor-widget elementor-widget-heading\" data-id=\"32d5598\" data-element_type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<h3 class=\"elementor-heading-title elementor-size-default\">Comment fonctionne-t-il ? <\/h3>\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-acf446c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"acf446c\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c84fcaa\" data-id=\"c84fcaa\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2bb183e elementor-widget elementor-widget-text-editor\" data-id=\"2bb183e\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Illustrons le fonctionnement de cet algorithme par un exemple :\u00a0<\/span><\/span><\/p><p><strong><span style=\"color: #000000;\">Un individu cherche \u00e0 se d\u00e9placer d\u2019un point A \u00e0 un point B sur un chemin d\u2019obstacles.<\/span><\/strong><\/p><p><span style=\"font-weight: 400;\"><span style=\"color: #000000;\">La situation est repr\u00e9sent\u00e9e par les sch\u00e9mas ci-dessous\u00a0:<\/span> <\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-338bfda elementor-widget elementor-widget-image\" data-id=\"338bfda\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t<style>\/*! elementor - v3.15.0 - 02-08-2023 *\/\n.elementor-widget-image{text-align:center}.elementor-widget-image a{display:inline-block}.elementor-widget-image a img[src$=\".svg\"]{width:48px}.elementor-widget-image img{vertical-align:middle;display:inline-block}<\/style>\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"1109\" height=\"1586\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-11tableau_prerequis_maths.png\" class=\"attachment-full size-full wp-image-59214\" alt=\"Tableau apache maths\" loading=\"lazy\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-11tableau_prerequis_maths.png 1109w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-11tableau_prerequis_maths-210x300.png 210w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-11tableau_prerequis_maths-716x1024.png 716w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-11tableau_prerequis_maths-768x1098.png 768w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-11tableau_prerequis_maths-1074x1536.png 1074w\" sizes=\"(max-width: 1109px) 100vw, 1109px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-238c835 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"238c835\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-bf84d86\" data-id=\"bf84d86\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-ad36b8c elementor-widget elementor-widget-text-editor\" data-id=\"ad36b8c\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"color: #000000;\">Les cases vertes repr\u00e9sentent le point de d\u00e9part et l\u2019arriv\u00e9e. Les cases fonc\u00e9es repr\u00e9sentent les obstacles, et les bleues celles o\u00f9 il est possible de se d\u00e9placer. Sur le sch\u00e9ma num\u00e9ro 2, les cases violet claires repr\u00e9sentent un chemin th\u00e9orique \u00e9ligible pour mod\u00e9liser l\u2019heuristique, aussi repr\u00e9sent\u00e9 avec la fl\u00e8che verte.\u00a0<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-56545fd elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"56545fd\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-90332c1\" data-id=\"90332c1\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2e5d6c7 elementor-widget elementor-widget-text-editor\" data-id=\"2e5d6c7\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">L\u2019enjeu ici est de trouver le plus court chemin menant \u00e0 B, l\u2019individu ne pouvant pas emprunter les cases noires.<\/span><\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-891a121 elementor-widget elementor-widget-text-editor\" data-id=\"891a121\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"color: #000000;\">Un algorithme heuristique traditionnel \u00e9valuerait tous les chemins possibles et comparerait leur distance, tandis que l\u2019algorithme A* nous renvoie directement le premier chemin qu\u2019il a d\u00e9termin\u00e9.<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-ee99ad6 elementor-widget elementor-widget-text-editor\" data-id=\"ee99ad6\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Le caract\u00e8re optimal de ce chemin d\u00e9pendra du param\u00e8tre d\u2019heuristique choisi. Dans notre cas, l\u2019heuristique sert \u00e0 fournir une <\/span><b>estimation de la distance restante<\/b><span style=\"font-weight: 400;\"> \u00e0 chaque \u00e9tape de l\u2019algorithme. Cette estimation d\u00e9pend de la m\u00e9trique choisie dans notre probl\u00e8me d\u2019optimisation, et n\u2019a pas \u00e0 rendre une distance exacte.\u00a0<\/span><\/span><\/p><p><span style=\"font-weight: 400;\"><span style=\"color: #000000;\">Dans notre cas, on pourrait choisir comme heuristique la distance de Manhattan s\u00e9parant A et B, ou la distance en ligne droite entre ces deux points, calcul\u00e9e \u00e0 l\u2019aide du th\u00e9or\u00e8me de Pythagore.<\/span><\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-2cbe1b2 elementor-widget elementor-widget-image\" data-id=\"2cbe1b2\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"1171\" height=\"1821\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-9tableau_prerequis_maths-1.png\" class=\"attachment-full size-full wp-image-58268\" alt=\"\" loading=\"lazy\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-9tableau_prerequis_maths-1.png 1171w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-9tableau_prerequis_maths-1-193x300.png 193w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-9tableau_prerequis_maths-1-658x1024.png 658w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-9tableau_prerequis_maths-1-768x1194.png 768w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/tableau_apacheFichier-9tableau_prerequis_maths-1-988x1536.png 988w\" sizes=\"(max-width: 1171px) 100vw, 1171px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<div class=\"elementor-element elementor-element-e1eada0 elementor-widget elementor-widget-text-editor\" data-id=\"e1eada0\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"font-weight: 400;\">L\u2019algorithme A* essaye par cons\u00e9quent de minimiser la somme F = G+H, o\u00f9 G est la distance parcourue depuis le point de d\u00e9part et H l\u2019estimation de la distance restante \u00e0 parcourir jusqu\u2019\u00e0 l\u2019arriv\u00e9e, en fonction de l\u2019heuristique d\u00e9finie au d\u00e9part de l\u2019algorithme. Ainsi, en entr\u00e9e, l&rsquo;algorithme prend\u00a0:\u00a0<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Les positions des points de d\u00e9part et d\u2019arriv\u00e9e<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">La liste des distances entre chaque case de la grille et le point d\u2019arriv\u00e9e.\u00a0<\/span><\/li><\/ul><p><span style=\"font-weight: 400;\">A chaque \u00e9tape, l\u2019algorithme A* met ainsi \u00e0 jour deux listes\u00a0:\u00a0<\/span><\/p><ul><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Celle des grandeurs G, repr\u00e9sentant la distance <\/span><b>r\u00e9elle <\/b><span style=\"font-weight: 400;\">parcourue depuis le point A\u00a0<\/span><\/li><li style=\"font-weight: 400;\" aria-level=\"1\"><span style=\"font-weight: 400;\">Celle des estimations H d\u00e9crivant la distance \u00e0 parcourir jusqu\u2019\u00e0 l\u2019arriv\u00e9e.<\/span><\/li><\/ul><blockquote><p><span style=\"font-weight: 400;\">Ainsi, l\u2019algorithme choisit \u00e0 chaque \u00e9tape la case lui permettant de se rapprocher de l\u2019arriv\u00e9e, et stocke dans une autre liste d&rsquo;autres options moins optimales aux premiers abords.<\/span><\/p><\/blockquote><p><span style=\"font-weight: 400;\">Cette liste secondaire permet de <\/span><b>choisir une autre option<\/b><span style=\"font-weight: 400;\"> au cas o\u00f9 l\u2019algorithme rencontre un obstacle, ce qui garantit la justesse de l\u2019algorithme.\u00a0<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-7c3add6 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"7c3add6\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-c9c245f\" data-id=\"c9c245f\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-245a2d5 elementor-widget elementor-widget-image\" data-id=\"245a2d5\" data-element_type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"1177\" height=\"1821\" src=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/schema_2-1.png\" class=\"attachment-full size-full wp-image-59838\" alt=\"algorithme a*\" loading=\"lazy\" srcset=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/schema_2-1.png 1177w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/schema_2-1-194x300.png 194w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/schema_2-1-662x1024.png 662w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/schema_2-1-768x1188.png 768w, https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/schema_2-1-993x1536.png 993w\" sizes=\"(max-width: 1177px) 100vw, 1177px\" \/>\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-899287c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"899287c\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-e0927d6\" data-id=\"e0927d6\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-7ee3dbd elementor-widget elementor-widget-text-editor\" data-id=\"7ee3dbd\" data-element_type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<p><span style=\"color: #000000;\"><span style=\"font-weight: 400;\">Le choix de l\u2019heuristique d\u2019estimation est <\/span><b>crucial<\/b><span style=\"font-weight: 400;\"> pour l\u2019optimalit\u00e9 du chemin renvoy\u00e9. Si l\u2019on surestime le chemin restant \u00e0 parcourir \u00e0 chaque \u00e9tape, l\u2019algorithme risque de ne pas renvoyer le chemin le plus court. En revanche, si l\u2019on sous-estime l\u2019heuristique, la complexit\u00e9 de l\u2019algorithme augmentera, ce qui lui fera perdre son atout principal qu\u2019est sa vitesse (l\u2019heuristique nulle repr\u00e9sente l\u2019algorithme de Dijsktra). Si l\u2019estimation est juste, l\u2019algorithme n\u2019explorera pas toutes les options possibles et renverra une solution optimale. On dit dans ce cas que l\u2019heuristique fournie est <\/span><b>admissible.\u00a0<\/b><\/span><\/p><p><span style=\"font-weight: 400; color: #000000;\">Cet article vous a plu\u00a0? Notre\u00a0<\/span><a href=\"https:\/\/datascientest.com\/formation-data-scientist\" target=\"_blank\" rel=\"noopener\">formation data scientist<\/a><span style=\"font-weight: 400; color: #000000;\">\u00a0vous propose un cours sur la th\u00e9orie des graphes, pour que vous puissiez, vous aussi, comprendre et impl\u00e9menter un tel algorithme sur\u00a0<\/span><a href=\"https:\/\/www.python.org\/\" target=\"_blank\" rel=\"noopener\">Python<\/a><span style=\"font-weight: 400; color: #000000;\">.\u00a0<\/span><\/p>\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-ab9a062 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"ab9a062\" data-element_type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-d301c7c\" data-id=\"d301c7c\" data-element_type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b2a72a9 elementor-align-center button-principale elementor-widget elementor-widget-button\" data-id=\"b2a72a9\" data-element_type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm elementor-animation-grow\" href=\"https:\/\/datascientest.com\/formations-data\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t<span class=\"elementor-button-text\">DECOUVRIR LA FORMATON<\/span>\n\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>On a trait\u00e9 dans un pr\u00e9c\u00e9dent article de l\u2019importance des algorithmes de recherche de plus court chemin en th\u00e9orie des graphes, notamment avec l\u2019exemple de l\u2019algorithme de Dijkstra. Il existe d\u2019autres algorithmes encore plus performants dans certaines situations, comme en cartographie ou dans le gaming. On retient par exemple l\u2019algorithme A*, dit \u2018A star algorithm\u2019 [&hellip;]<\/p>\n","protected":false},"author":77,"featured_media":58721,"comment_status":"open","ping_status":"open","sticky":false,"template":"elementor_theme","format":"standard","meta":{"content-type":"","inline_featured_image":false},"categories":[2497],"tags":[],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v21.7 (Yoast SEO v21.7) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>L\u2019algorithme A* (A star algorithm) | DataScientest.com<\/title>\n<meta name=\"description\" content=\"D\u00e9couvrez tout ce qu&#039;il faut savoir sur l&#039;algorithme A*, l&#039;algorithme qui permet d&#039;optimiser les chemins dans le cadre d&#039;une IA.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm\" \/>\n<meta property=\"og:locale\" content=\"fr_FR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"L\u2019algorithme A* (A star algorithm)\" \/>\n<meta property=\"og:url\" content=\"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm\" \/>\n<meta property=\"og:site_name\" content=\"Formation Data Science | DataScientest.com\" \/>\n<meta property=\"article:published_time\" content=\"2021-04-09T10:25:59+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2023-11-09T14:07:49+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/illu_algo_blog-112.png\" \/>\n\t<meta property=\"og:image:width\" content=\"4267\" \/>\n\t<meta property=\"og:image:height\" content=\"2342\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/png\" \/>\n<meta name=\"author\" content=\"Raphael Kassel\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u00c9crit par\" \/>\n\t<meta name=\"twitter:data1\" content=\"Raphael Kassel\" \/>\n\t<meta name=\"twitter:label2\" content=\"Dur\u00e9e de lecture estim\u00e9e\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm\",\"url\":\"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm\",\"name\":\"L\u2019algorithme A* (A star algorithm) | DataScientest.com\",\"isPartOf\":{\"@id\":\"https:\/\/datascientest.com\/#website\"},\"datePublished\":\"2021-04-09T10:25:59+00:00\",\"dateModified\":\"2023-11-09T14:07:49+00:00\",\"author\":{\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\"},\"description\":\"D\u00e9couvrez tout ce qu'il faut savoir sur l'algorithme A*, l'algorithme qui permet d'optimiser les chemins dans le cadre d'une IA.\",\"inLanguage\":\"fr-FR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm\"]}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/datascientest.com\/#website\",\"url\":\"https:\/\/datascientest.com\/\",\"name\":\"Formation Data Science | DataScientest.com\",\"description\":\"Leader de la formation en Data Science\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/datascientest.com\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"fr-FR\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1\",\"name\":\"Raphael Kassel\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"fr-FR\",\"@id\":\"https:\/\/datascientest.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"contentUrl\":\"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg\",\"caption\":\"Raphael Kassel\"},\"description\":\"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \\\"Chef de projet IA\\\" et \\\"Data Product Manager\\\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.\",\"sameAs\":[\"https:\/\/www.linkedin.com\/in\/raphaelkassel\/\",\"Data Science\"],\"url\":\"https:\/\/datascientest.com\/author\/raphaelkassel\"}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"L\u2019algorithme A* (A star algorithm) | DataScientest.com","description":"D\u00e9couvrez tout ce qu'il faut savoir sur l'algorithme A*, l'algorithme qui permet d'optimiser les chemins dans le cadre d'une IA.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm","og_locale":"fr_FR","og_type":"article","og_title":"L\u2019algorithme A* (A star algorithm)","og_url":"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm","og_site_name":"Formation Data Science | DataScientest.com","article_published_time":"2021-04-09T10:25:59+00:00","article_modified_time":"2023-11-09T14:07:49+00:00","og_image":[{"width":4267,"height":2342,"url":"https:\/\/datascientest.com\/wp-content\/uploads\/2021\/04\/illu_algo_blog-112.png","type":"image\/png"}],"author":"Raphael Kassel","twitter_card":"summary_large_image","twitter_misc":{"\u00c9crit par":"Raphael Kassel","Dur\u00e9e de lecture estim\u00e9e":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm","url":"https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm","name":"L\u2019algorithme A* (A star algorithm) | DataScientest.com","isPartOf":{"@id":"https:\/\/datascientest.com\/#website"},"datePublished":"2021-04-09T10:25:59+00:00","dateModified":"2023-11-09T14:07:49+00:00","author":{"@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1"},"description":"D\u00e9couvrez tout ce qu'il faut savoir sur l'algorithme A*, l'algorithme qui permet d'optimiser les chemins dans le cadre d'une IA.","inLanguage":"fr-FR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/datascientest.com\/lalgorithme-a-a-star-algorithm"]}]},{"@type":"WebSite","@id":"https:\/\/datascientest.com\/#website","url":"https:\/\/datascientest.com\/","name":"Formation Data Science | DataScientest.com","description":"Leader de la formation en Data Science","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/datascientest.com\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"fr-FR"},{"@type":"Person","@id":"https:\/\/datascientest.com\/#\/schema\/person\/6eca16f63daaafcbc96e15549b9d4ee1","name":"Raphael Kassel","image":{"@type":"ImageObject","inLanguage":"fr-FR","@id":"https:\/\/datascientest.com\/#\/schema\/person\/image\/","url":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","contentUrl":"https:\/\/datascientest.com\/wp-content\/uploads\/2023\/11\/raph.jpeg","caption":"Raphael Kassel"},"description":"Raphael Kassel est le Head of Data Programs chez DataScientest. Il supervise une \u00e9quipe Data, impl\u00e9mente de nouveaux parcours comme \"Chef de projet IA\" et \"Data Product Manager\", et contribue \u00e0 la modernisation des op\u00e9rations du groupe. En collaboration \u00e9troite avec l'\u00e9quipe de d\u00e9veloppement, il adapte l'accompagnement acad\u00e9mique aux \u00e9volutions de l'\u00e9quipe data et \u00e0 l'internationalisation.","sameAs":["https:\/\/www.linkedin.com\/in\/raphaelkassel\/","Data Science"],"url":"https:\/\/datascientest.com\/author\/raphaelkassel"}]}},"_links":{"self":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/58258"}],"collection":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/users\/77"}],"replies":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/comments?post=58258"}],"version-history":[{"count":0,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/posts\/58258\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media\/58721"}],"wp:attachment":[{"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/media?parent=58258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/categories?post=58258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/datascientest.com\/wp-json\/wp\/v2\/tags?post=58258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}