{"id":1677,"date":"2016-02-08T12:04:33","date_gmt":"2016-02-08T11:04:33","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1677"},"modified":"2022-12-03T22:58:52","modified_gmt":"2022-12-03T21:58:52","slug":"algorithme-naif-glouton-enumeration","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/","title":{"rendered":"Naive \/ greedy \/ enumeration algorithm"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"1677\" class=\"elementor elementor-1677\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-baf06d3 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"baf06d3\" data-element_type=\"section\" data-e-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-33 elementor-top-column elementor-element elementor-element-c5f06ac\" data-id=\"c5f06ac\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-5b7b668 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5b7b668\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/algorithmique\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Algorithmique<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\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<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-7f7830f\" data-id=\"7f7830f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-261da89 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"261da89\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Page d'accueil<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\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<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-a88c42f\" data-id=\"a88c42f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0598717 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0598717\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Algorithme_glouton\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\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<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-bcec69b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"bcec69b\" data-element_type=\"section\" data-e-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-4ddcf8c3\" data-id=\"4ddcf8c3\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2efe62b8 elementor-widget elementor-widget-text-editor\" data-id=\"2efe62b8\" data-element_type=\"widget\" data-e-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\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contenus<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/#Algorithme-naif\" >Algorithme naif<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/#Algorithme-glouton-methode-intuitive\" >Algorithme glouton (m\u00e9thode intuitive)<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/algorithm-naif-greedy-enumeration-2\/#Force-brute-ou-enumeration\" >Force brute ou \u00e9num\u00e9ration<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algorithme-naif\"><\/span>Algorithme naif<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Un <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithme<\/a> naif a pour vocation de fournir un r\u00e9sultat de base \u00e0 un probl\u00e8me. La m\u00e9thode na\u00efve ne fait aucun calcul pr\u00e9paratoire et se sert uniquement des donn\u00e9es de base du probl\u00e8me.<\/div>\n<p><\/p>\n<p>Prenons pour exemple un probl\u00e8me du <a href=\"https:\/\/complex-systems-ai.com\/en\/industrial-problems-and-polynomial-reduction\/backpack-problem\/\">sac \u00e0 dos<\/a>. L&rsquo; algorithme naif consisterait \u00e0 prendre en premi\u00e8re les objets de la taille la plus petite jusqu&rsquo;\u00e0 ne plus pouvoir mettre de nouvel objet dans le sac.<\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre><b>pour<\/b> i <b>de<\/b> 1 <b>\u00e0<\/b> n\n<b>   si<\/b> w[i] + w_conso \u2264 W <b>alors<\/b>\n      x[i] := 1\n      w_conso := w_conso + w[i]\n<b>   sinon<\/b>\n      x[i] := 0\n   <b>fin si<\/b>\n<b>fin pour <\/b><\/pre>\n<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algorithme-glouton-methode-intuitive\"><\/span>Algorithme glouton (m\u00e9thode intuitive)<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Comme l&rsquo;algorithme naif, un algorithme dit glouton se construit sur un principe simple : lors d&rsquo;une it\u00e9ration, l&rsquo;algorithme prend toujours la d\u00e9cision du \u00ab\u00a0meilleur choix\u00a0\u00bb. Il faut donc un choix localement optimal dans l&rsquo;objectif que ce choix conduira \u00e0 la solution optimale globale. Cependant, l&rsquo;algorithme ne donne aucune garantie que la derni\u00e8re solution soit une solution optimale.<\/div>\n<p><\/p>\n<p>Intuitivement, nous pouvons nous dire que pour maximiser l&rsquo;utilit\u00e9 dans le probl\u00e8me du sac \u00e0 dos, il suffit de mettre l&rsquo;\u00e9l\u00e9ment ayant la plus grande utilit\u00e9 (avec une taille compatible avec la taille restante dans le sac) jusqu&rsquo;\u00e0 ne plus avoir assez de place dans le sac.<\/p>\n<p><\/p>\n<p>Pour cela, nous allons consid\u00e9rer <strong>x<\/strong> et <strong>w<\/strong> les vecteurs du choix de l&rsquo;objet et de son poids tri\u00e9s par ordre d\u00e9croissant d&rsquo;efficacit\u00e9 (<em>efficacit\u00e9 = utilit\u00e9\/poids<\/em>). Puis l&rsquo;algorithme fonctionne comme la m\u00e9thode na\u00efve.<\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">Un exemple simple permet de comprendre que ce choix n&rsquo;est pas toujours optimal : prenons un objet de taille <strong>1<\/strong> et d&rsquo;utilit\u00e9 <strong>2<\/strong>, et un objet de taille et d&rsquo;utilit\u00e9 \u00e9gaux \u00e0 la taille du sac. Dans ces conditions le premier objet \u00e0 la plus grande utilit\u00e9, il sera choisi en premier. Il n&rsquo;y a plus de place pour placer le second objet. La solution optimale serait de choisir uniquement le deuxi\u00e8me objet dans le sac.<\/div>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Force-brute-ou-enumeration\"><\/span>Force brute ou \u00e9num\u00e9ration<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Contrairement \u00e0 l&rsquo; algorithme naif, cette m\u00e9thode garantit l&rsquo;optimale globale, mais son temps d&rsquo;ex\u00e9cution et sa consommation m\u00e9moire peuvent d\u00e9passer rapidement les limites d&rsquo;un PC. Le principe est simple, il faut \u00e9num\u00e9rer toutes les solutions possibles du probl\u00e8me et choisir la meilleure solution.<\/div>\n<p><\/p>\n<p>G\u00e9n\u00e9ralement, l&rsquo;arbre de solution est repr\u00e9sent\u00e9 comme le nom l&rsquo;indique sous forme d&rsquo;arbre. Prenons l&rsquo;exemple du probl\u00e8me du sac \u00e0 dos avec quatre objets avec les param\u00e8tres suivants et une taille de sac de 30 :<\/p>\n<p><\/p>\n<div style=\"text-align: justify;\">\n<table>\n<tbody>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div>objet<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>1<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>2<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>4<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div>u_i<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>7<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>3<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>4<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>3<\/div>\n<\/td>\n<\/tr>\n<tr>\n<td align=\"center\" valign=\"top\">\n<div>w_i<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>13<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>8<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>12<\/div>\n<\/td>\n<td align=\"center\" valign=\"top\">\n<div>10<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<p><\/p>\n<p>L&rsquo;arbre se construit par it\u00e9ration : \u00e0 chaque it\u00e9ration, les nouvelles feuilles repr\u00e9sentent le fait de prendre ou non le prochain objet. Nous obtenons l&rsquo;arbre binaire suivant :<\/p>\n<p><\/p>\n<figure><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-1712 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/kpbrute.png\" alt=\"algorithme na\u00eff algorithme glouton force brut \u00e9num\u00e9ration\" width=\"506\" height=\"655\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/kpbrute.png 506w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/kpbrute-232x300.png 232w\" sizes=\"(max-width: 506px) 100vw, 506px\" \/><\/figure>\n<p><\/p>\n<p>Les sommets en rouge d\u00e9passe la taille maximale du sac, le sommet en violet est la solution optimale. Comme vous pouvez le remarquer, le nombre de feuille est \u00e9gale \u00e0 2<sup>(n-1)<\/sup> pour l&rsquo;objet <strong>n<\/strong>. Le nombre de n\u0153uds g\u00e9n\u00e9r\u00e9s jusqu&rsquo;\u00e0 l&rsquo;objet n est donc 2<sup>n<\/sup> -1.<\/p>\n<p><\/p>\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<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Algorithms Wiki homepage Naive algorithm A naive algorithm aims to provide a basic result to a problem. The naive method does not... <\/p>","protected":false},"author":1,"featured_media":0,"parent":1062,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1677","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1677","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=1677"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1677\/revisions"}],"predecessor-version":[{"id":17942,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1677\/revisions\/17942"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1062"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1677"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}