{"id":2892,"date":"2016-02-18T10:57:25","date_gmt":"2016-02-18T09:57:25","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2892"},"modified":"2022-12-03T22:59:01","modified_gmt":"2022-12-03T21:59:01","slug":"algorithme-a-etoile","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-estrella\/","title":{"rendered":"Algoritmo de estrella"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2892\" class=\"elementor elementor-2892\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-d54af08 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"d54af08\" 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-8d25de7\" data-id=\"8d25de7\" 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-2a622eb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"2a622eb\" 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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/\">\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\">B\u00fasqueda de ruta<\/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-e9ffdaf\" data-id=\"e9ffdaf\" 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-9569a74 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"9569a74\" 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\/es\/\">\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\">Pagina de inicio<\/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-7b548ab\" data-id=\"7b548ab\" 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-d019261 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"d019261\" 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_A*\" 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-5de78237 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5de78237\" 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-6674a8f8\" data-id=\"6674a8f8\" 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-3c7a590a elementor-widget elementor-widget-text-editor\" data-id=\"3c7a590a\" 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\">Contenido<\/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=\"Tabla de contenido alternativo\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Palanca<\/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-estrella\/#Algorithme-A-etoile\" >Algoritmo de estrella<\/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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-estrella\/#Fonction-devaluation\" >Funci\u00f3n de evaluaci\u00f3n<\/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\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-estrella\/#Algorithme-A-etoile-2\" >Algoritmo de estrella<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-estrella\/#Exemple\" >Ejemplo<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Algorithme-A-etoile\"><\/span>Algoritmo de estrella<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>La idea del algoritmo A star o A star o A * es evitar desarrollar caminos considerados demasiado costosos en comparaci\u00f3n con los conocidos. Para ello, el algoritmo se referir\u00e1 a una funci\u00f3n para evaluar su costo total. El principio es similar a branch &amp; bound o branch &amp; price.<\/p>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Fonction-devaluation\"><\/span>Funci\u00f3n de evaluaci\u00f3n<span class=\"ez-toc-section-end\"><\/span><\/h2>\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;\">Sea f (n) una funci\u00f3n de evaluaci\u00f3n para un v\u00e9rtice <strong>no<\/strong>, h(n)a <a href=\"https:\/\/complex-systems-ai.com\/es\/optimizacion-combinatoria\/\">heur\u00edstico<\/a> costo estimado para llegar a un estado final, y g(n) el costo real para llegar a la cima <strong>no<\/strong>. Entonces f (n) = h (n) + g (n). La funci\u00f3n f (n) se puede describir como el costo total estimado para pasar a un estado final a trav\u00e9s de <strong>no<\/strong>.<\/div>\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;\">La heur\u00edstica debe ser admisible, es decir, h (n) \u2264h &#039;(n) donde h&#039; (n) es el verdadero costo a partir de <strong>no<\/strong> hacia un estado final. La heur\u00edstica nunca sobreestima la distancia real. Y es consistente, es decir, para todo y que desciende de x, h (x) \u2264h (y) + costo (xay).<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Algorithme-A-etoile-2\"><\/span>Algoritmo de estrella<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Nota <strong>s<\/strong> el estado inicial, <strong>T<\/strong> el conjunto de estados terminales, k (x, y) el costo de <strong>X<\/strong> Para <strong>y<\/strong>, <strong>F<\/strong> el conjunto de estados desarrollados - cuyos sucesores se han generado (conjunto de cerrados) - y <strong>O<\/strong> el conjunto de estados generados pero no desarrollados. El algoritmo de una estrella es el siguiente:<\/p>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<pre>O Siempre que O &lt;&gt; \u00d8 extraiga de O el elemento x tq f (x) es m\u00ednimo; Inserte x en F;\n    <strong>s\u00ed<\/strong> x pertenece a T entonces <b>Terminado: Soluci\u00f3n encontrada<\/b>\n    <strong>De lo contrario<\/strong>\n      <strong>Por todo<\/strong> y sucesor de x do\n        <strong>s\u00ed<\/strong> y no pertenece a F <small>U<\/small> O o g (y)&gt; g (x) + k (x, y) entonces g (y) End If\n      <strong>Fin para<\/strong>\n   <strong> Terminara si<\/strong>\n  <strong>Finalizar mientras \/ CODIGO +\n<\/strong><\/pre>\n<\/div>\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exemple\"><\/span>Ejemplo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n<p>Para ilustrar el algoritmo de la estrella A, tomaremos el problema de los 8 acertijos como ejemplo. Este problema es una matriz de 3 * 3 que contiene 8 casillas rellenas con los n\u00fameros del 1 al 8 y una casilla vac\u00eda. Cada cuadrado puede moverse a un cuadrado adyacente en la matriz, y solo a un cuadrado vac\u00edo. En este caso, permitimos el valor de la caja con la caja vac\u00eda. El objetivo del 8-puzzle es ordenar las casillas en orden ascendente de izquierda a derecha y de arriba a abajo de la matriz. Concretamente, es una broma.<\/p>\n\n<p>La heur\u00edstica utilizada para este ejemplo es la Distancia de Manhattan. Esta distancia es la suma de los movimientos &quot;en l\u00ednea recta&quot; a realizar para que cada casilla est\u00e9 en el lugar correcto. En efecto, es una heur\u00edstica admisible y consistente porque consideramos que todos los movimientos de las cajas son legales. La funci\u00f3n g (n) tendr\u00e1 el valor<strong> no<\/strong>, el n\u00famero de movimientos realizados para llegar a la configuraci\u00f3n <strong>no<\/strong>.<\/p>\n\n<p>Tomemos una configuraci\u00f3n aleatoria inicial, tenemos para la primera iteraci\u00f3n el siguiente \u00e1rbol:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-2928 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/astarbegin.png\" alt=\"algoritmo de ruta m\u00e1s corta A algoritmo de estrella A*\" width=\"545\" height=\"201\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/astarbegin.png 545w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/astarbegin-300x111.png 300w\" sizes=\"(max-width: 545px) 100vw, 545px\" \/><\/figure>\n<\/div>\n\n<p>El algoritmo tiene en el conjunto F la ra\u00edz y en el conjunto O las 4 configuraciones generadas. La configuraci\u00f3n de la derecha tiene la estimaci\u00f3n m\u00e1s peque\u00f1a del costo total, por lo que se quita de O para ser explorada y finalmente se coloca en F. Obtenemos el siguiente \u00e1rbol:<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2932 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/astar.png\" alt=\"algoritmo de ruta m\u00e1s corta A algoritmo de estrella A*\" width=\"548\" height=\"336\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/astar.png 548w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/astar-300x184.png 300w\" sizes=\"(max-width: 548px) 100vw, 548px\" \/><\/figure>\n<\/div>\n\n<p>Hemos encontrado una soluci\u00f3n final tal que su costo es m\u00ednimo, el algoritmo de estrella A se detiene.<\/p>\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>","protected":false},"excerpt":{"rendered":"<p>Path Finding Homepage Wiki Algoritmo A star La idea del algoritmo A star o A star o A*, es evitar desarrollar caminos\u2026 <\/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-2892","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2892","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=2892"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2892\/revisions"}],"predecessor-version":[{"id":17925,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/2892\/revisions\/17925"}],"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=2892"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}