{"id":792,"date":"2016-01-29T13:19:11","date_gmt":"2016-01-29T12:19:11","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=792"},"modified":"2022-12-03T22:57:31","modified_gmt":"2022-12-03T21:57:31","slug":"algorithme-de-bellman","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-bellman\/","title":{"rendered":"El algoritmo de Bellman"},"content":{"rendered":"\t\t<div data-elementor-type=\"wp-page\" data-elementor-id=\"792\" class=\"elementor elementor-792\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-4263457 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4263457\" 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-0e04846\" data-id=\"0e04846\" 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-5632a94 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5632a94\" 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\/recherche-de-chemin-theorie-des-graphes\/\">\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\">Recherche de chemin<\/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-d2490ad\" data-id=\"d2490ad\" 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-ab161a9 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"ab161a9\" 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-0721851\" data-id=\"0721851\" 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-f635193 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f635193\" 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\/Graphe_orient%C3%A9_acyclique\" 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-211a8d50 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"211a8d50\" 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-305a7cb9\" data-id=\"305a7cb9\" 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-4686b02 elementor-widget elementor-widget-text-editor\" data-id=\"4686b02\" 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\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=\"Alternar tabla de contenidos\"><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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-bellman\/#Algorithme-de-Bellman\" >Algorithme de Bellman<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-de-Bellman\"><\/span>Algorithme de Bellman<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>L&rsquo;algorithme de Bellman est bas\u00e9 sur l&rsquo;observation suivante: si nous connaissons toutes les valeurs des arcs (u, v) avec u dans un sous-graphe et v \u00e0 l&rsquo;ext\u00e9rieur de ce sous-graphe. Si nous connaissons tous les chemins les plus courts vers u, donc nous pouvons calculer d(v) = min{d(u) + poids(u,v)}.\u00a0L&rsquo;algorithme de Bellmann est un <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/\">algorithme<\/a> de <a href=\"https:\/\/complex-systems-ai.com\/es\/algoritmico\/programacion-dinamica-2\/\">programmation dynamique<\/a> gourmand (similaire \u00e0 une premi\u00e8re recherche de pain), il visite toutes les solutions possibles.<\/p>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<p><strong>Conditions<\/strong>.<\/p>\n<ul style=\"text-align: justify;\">\n<li>Pas de cycle<\/li>\n<li>Arc uniquement<\/li>\n<li>Nombre de sommets fini<\/li>\n<li>Une source (et accessoirement une cible) d\u00e9finie<\/li>\n<\/ul>\n<\/div>\n\n<p>L&rsquo;algorithme de Bellman prend en entr\u00e9e un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">graphe<\/a> orient\u00e9 pond\u00e9r\u00e9 par des r\u00e9els positifs et un sommet source. Il s&rsquo;agit de construire progressivement un sous-graphe dans lequel sont class\u00e9s les diff\u00e9rents sommets par ordre croissant de leur distance minimale au sommet de d\u00e9part. La distance correspond \u00e0 la somme des poids des arcs emprunt\u00e9s.<\/p>\n\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;\">Au d\u00e9part, on consid\u00e8re que les distances de chaque sommet au sommet de d\u00e9part sont infinies sauf pour le sommet de d\u00e9part pour lequel la distance est de 0. Le sous-graphe de d\u00e9part est l&rsquo;ensemble vide.<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>\u00a0Au cours de chaque it\u00e9ration, on choisit en dehors du sous-graphe un sommet tel que tous ses successeurs soient dans le sous-graphe et on l&rsquo;ajoute au sous-graphe. Ensuite, on met \u00e0 jour les distances des sommets voisins de celui ajout\u00e9. La mise \u00e0 jour s&rsquo;op\u00e8re comme suit\u00a0: la nouvelle distance du sommet voisin est le minimum entre <em>la distance existante<\/em> et celle obtenue en ajoutant <em>le poids de l&rsquo;arc entre sommet voisin et sommet ajout\u00e9 \u00e0 la distance du sommet ajout\u00e9<\/em>.<\/p>\n<p style=\"text-align: justify;\">On continue ainsi jusqu&rsquo;\u00e0 \u00e9puisement des sommets (ou jusqu&rsquo;\u00e0 s\u00e9lection du sommet d&rsquo;arriv\u00e9e).<\/p>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-6303 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/bellman1.png\" alt=\"plus court chemin algorithme de bellman source unique DAG\" width=\"618\" height=\"233\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/bellman1.png 618w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/bellman1-300x113.png 300w\" sizes=\"(max-width: 618px) 100vw, 618px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6304 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/bellman2.png\" alt=\"plus court chemin algorithme de bellman source unique DAG\" width=\"713\" height=\"419\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/bellman2.png 713w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/bellman2-300x176.png 300w\" sizes=\"(max-width: 713px) 100vw, 713px\" \/><\/figure>\n<\/div>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-6305 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/dag.png\" alt=\"plus court chemin algorithme de bellman source unique DAG\" width=\"588\" height=\"504\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/dag.png 588w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/dag-300x257.png 300w\" sizes=\"(max-width: 588px) 100vw, 588px\" \/><\/figure>\n<\/div>\n\n<p>Pour des raisons pratiques, la r\u00e9solution du l&rsquo;algorithme de Bellman ne retourne qu&rsquo;un vecteur contenant le sommet visit\u00e9, la liste des pr\u00e9d\u00e9cesseurs (les sommets d\u00e9j\u00e0 valid\u00e9s) et les valeurs des plus courts chemins vers tous les autres sommets mise \u00e0 jour. Ce qui correspond \u00e0 une ligne courante du tableau pr\u00e9sent\u00e9.<\/p>\n\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;\">\n<p><strong>Optimalit\u00e9<\/strong><\/p>\n<p>Un sommet est valid\u00e9 si tous ses pr\u00e9d\u00e9cesseurs sont valid\u00e9s. C&rsquo;est-\u00e0-dire que l&rsquo;on conna\u00eet le <a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">plus court chemin<\/a> de tous ses pr\u00e9d\u00e9cesseurs. \u00c0 l&rsquo;\u00e9tat initiale, nous avons valid\u00e9 l&rsquo;origine et nous connaissons les chemins de taille 1 partant de l&rsquo;origine. Le prochain sommet \u00e0 valider poss\u00e8de donc un chemin avec uniquement des sommets valid\u00e9s. Par r\u00e9currence nous en d\u00e9duisons que nous avons valid\u00e9 le plus court chemin de l&rsquo;origine \u00e0 ce sommet.<\/p>\n<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>D[0] = 0;      \n<strong>pour<\/strong> chaque sommet i \u0081\u201a 0 faire  \n    C[i] = 0; D[i] = L[1, i];   \n<strong>pour<\/strong> k = 1 a n - 1 faire  \n    <strong>pour<\/strong> chaque i successeur de k faire  \n        <strong>si<\/strong> (D[k] + L[k, i] &lt; D[i]) alors         \n            D[i] = D[k] + L[k, i];        \n            C[i] = k;            \n        <strong>fin      <\/strong>\n    <strong>fin    <\/strong> \n<strong>fin\n<\/strong>Retourner<strong> D\n<\/strong><\/pre>\n<\/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<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Path Finding Wiki Home Page Algoritmo de Bellman El algoritmo de Bellman se basa en la siguiente observaci\u00f3n: si conocemos todos los valores de los arcos... <\/p>","protected":false},"author":1,"featured_media":0,"parent":362,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-792","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/792","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/comments?post=792"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/792\/revisions"}],"predecessor-version":[{"id":17923,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/792\/revisions\/17923"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/362"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=792"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}