{"id":362,"date":"2016-01-26T16:30:19","date_gmt":"2016-01-26T15:30:19","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=362"},"modified":"2024-02-11T19:52:24","modified_gmt":"2024-02-11T18:52:24","slug":"recherche-de-chemin-theorie-des-graphes","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/","title":{"rendered":"Encontrar caminos 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"362\" class=\"elementor elementor-362\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c39f8aa elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c39f8aa\" 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-e9bd86a\" data-id=\"e9bd86a\" 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-10edd0b elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"10edd0b\" 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\/2020\/04\/03\/teorias-y-algoritmos-2\/\">\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\">Teor\u00edas<\/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-5acdfa9\" data-id=\"5acdfa9\" 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-846d48f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"846d48f\" 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-b552b0d\" data-id=\"b552b0d\" 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-5712c05 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"5712c05\" 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=\"\">\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-f437607 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"f437607\" 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-65bbee3\" data-id=\"65bbee3\" 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-370c6b8 elementor-widget elementor-widget-toggle\" data-id=\"370c6b8\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5771\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-5771\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Ruta m\u00e1s corta, fuente \u00fanica (b\u00fasqueda de ruta)<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5771\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-5771\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/\">grafico<\/a> no dirigido\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-dijkstra\/\">Algoritmo de Dijkstra<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-johnson-2\/\">Dijkstra con mont\u00f3n binario<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_heap\" target=\"_blank\" rel=\"noopener\">Dijkstra con mont\u00f3n de Fibonacci<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Thorup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Gr\u00e1fico dirigido con ponderaciones no negativas\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-bellman\/\">El algoritmo de Bellman<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-ford-bellman-2\/\">Algoritmo de Ford-Bellman<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/programacion-lineal\/metodo-simplex\/\">Algoritmo de Danzig<\/a><\/li>\n<li><a href=\"https:\/\/link.springer.com\/article\/10.1007\/BF01386390?error=cookies_not_supported&#038;code=43bcb593-58ff-408e-9ca3-59cadf5ea764\" target=\"_blank\" rel=\"noopener\">Dijkstra con lista<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-johnson-2\/\">Dijkstra con mont\u00f3n binario<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_heap\" target=\"_blank\" rel=\"noopener\">Dijkstra con mont\u00f3n de Fibonacci<\/a><\/li>\n<li><a href=\"https:\/\/link.springer.com\/article\/10.1007\/BF01786986?error=cookies_not_supported&#038;code=51bb4a86-7420-4e9f-bae3-e6233ac3061d\" target=\"_blank\" rel=\"noopener\">Johnson<\/a><\/li>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Gabow%27s_algorithm\" target=\"_blank\" rel=\"noopener\">Gabow<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/doi\/10.1145\/77600.77615?cookieSet=1\" target=\"_blank\" rel=\"noopener\">Ahuja y col.<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S002200000400042X\" target=\"_blank\" rel=\"noopener\">Thorup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Gr\u00e1fico dirigido con todo tipo de pesos\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-ford-bellman-2\/\">Algoritmo de Ford-Bellman<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Basado en una heur\u00edstica\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-estrella\/\">Algoritmo A *<\/a><\/li>\n<li><a href=\"http:\/\/robots.stanford.edu\/papers\/Likhachev03b.pdf\" target=\"_blank\" rel=\"noopener\">Reparaci\u00f3n en cualquier momento A * (ARA *)<\/a><\/li>\n<li><a href=\"http:\/\/www.cs.cmu.edu\/~ggordon\/likhachev-etal.anytime-dstar.pdf\" target=\"_blank\" rel=\"noopener\">En cualquier momento din\u00e1mico A *<\/a><\/li>\n<li><a href=\"https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.15.3683\" target=\"_blank\" rel=\"noopener\">D *<\/a><\/li>\n<li><a href=\"https:\/\/web.archive.org\/web\/20090219220415\/http:\/\/www.cs.ualberta.ca\/~games\/pathfind\/publications\/cig2005.pdf\" target=\"_blank\" rel=\"noopener\">Franja<\/a><\/li>\n<li><a href=\"https:\/\/www.ijcai.org\/Proceedings\/07\/Papers\/385.pdf\" target=\"_blank\" rel=\"noopener\">Ahorro marginal A * (FSA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.researchgate.net\/publication\/221455192_Generalized_Adaptive_A\" target=\"_blank\" rel=\"noopener\">Adaptativo generalizado A * (GAA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.researchgate.net\/publication\/220605574_Incremental_Heuristic_Search_in_AI\" target=\"_blank\" rel=\"noopener\">B\u00fasqueda heur\u00edstica incremental<\/a><\/li>\n<li><a href=\"http:\/\/www.eng.tau.ac.il\/~bengal\/GTA.pdf\" target=\"_blank\" rel=\"noopener\">B\u00fasqueda informativa<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0004370285900840\" target=\"_blank\" rel=\"noopener\">Profundizaci\u00f3n iterativa A * (IDA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/SOCS\/SOCS12\/paper\/viewFile\/5396\/5212\" target=\"_blank\" rel=\"noopener\">B\u00fasqueda de punto de salto<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/SOCS\/SOCS12\/paper\/viewFile\/5396\/5212\" target=\"_blank\" rel=\"noopener\">Planificaci\u00f3n de por vida A * (LPA *)<\/a><\/li>\n<li><a href=\"https:\/\/ieeexplore.ieee.org\/document\/8994527\" target=\"_blank\" rel=\"noopener\">A * acelerado por multiplicador (MAA *)<\/a><\/li>\n<li><a href=\"https:\/\/repub.eur.nl\/pub\/16100\/ei2009-10.pdf\" target=\"_blank\" rel=\"noopener\">Nuevo bidireccional A * (NBA *)<\/a><\/li>\n<li><a href=\"https:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.105.7839\" target=\"_blank\" rel=\"noopener\">Memoria simplificada acotada A * (SMA *)<\/a><\/li>\n<li><a href=\"https:\/\/www.semanticscholar.org\/paper\/Real-Time-Heuristic-Search-Korf\/2fda10f6079156c4621fefc8b7cad72c1829ee94?p2df\" target=\"_blank\" rel=\"noopener\">Tiempo real A *<\/a><\/li>\n<li><a href=\"http:\/\/web.cs.du.edu\/~sturtevant\/papers\/TBA.pdf\" target=\"_blank\" rel=\"noopener\">De duraci\u00f3n determinada A * (TBA *)<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5772\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-5772\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Camino m\u00e1s corto, m\u00faltiples fuentes<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5772\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-5772\"><ul>\n<li>Gr\u00e1fico no dirigido\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/\">Algoritmo de Floyd-Warshall<\/a><\/li>\n<\/ul>\n<ul>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000085710781\" target=\"_blank\" rel=\"noopener\">Seidel<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Williams<\/a><\/li>\n<li><a href=\"https:\/\/archive.org\/details\/proceedingsofthi2002acms\/page\/267\" target=\"_blank\" rel=\"noopener\">Pettie y Ramachandran<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Thorup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Gr\u00e1fico dirigido\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-de-cierre-transitivo-floyd-warshall\/\">Algoritmo de Floyd-Warshall<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Williams<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/algoritmo-johnson-2\/\">Dijkstra con mont\u00f3n binario<\/a><\/li>\n<li><a href=\"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750300402X\" target=\"_blank\" rel=\"noopener\">Pettie<\/a><\/li>\n<li><a href=\"https:\/\/dl.acm.org\/action\/cookieAbsent\" target=\"_blank\" rel=\"noopener\">Hagerup<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Gr\u00e1fico estoc\u00e1stico\n<ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/proceso-de-markov\/\">Viterbi (ver proceso estoc\u00e1stico)<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/proceso-de-markov\/\">Hacia atr\u00e1s-adelante (ver proceso estoc\u00e1stico)<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5773\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-5773\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Camino, \u00e1ngulo y navegaci\u00f3n m\u00e1s cortos<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5773\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-5773\"><ul>\n<li>Basado en A *\n<ul>\n<li><a href=\"http:\/\/robots.stanford.edu\/isrr-papers\/final\/final-23.pdf\" target=\"_blank\" rel=\"noopener\">Campo D *<\/a><\/li>\n<li><a href=\"http:\/\/idm-lab.org\/bib\/abstracts\/papers\/aaai07a.pdf\" target=\"_blank\" rel=\"noopener\">Theta *<\/a><\/li>\n<li><a href=\"https:\/\/webdocs.cs.ualberta.ca\/~holte\/Publications\/aaai11PeterYapFinal.pdf\" target=\"_blank\" rel=\"noopener\">Bloque A *<\/a><\/li>\n<li><a href=\"http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.70.9276&amp;rep=rep1&amp;type=pdf\" target=\"_blank\" rel=\"noopener\">Campo D de resoluci\u00f3n m\u00faltiple *<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/ICAPS\/ICAPS13\/paper\/viewFile\/6060\/6194\" target=\"_blank\" rel=\"noopener\">ANYA<\/a><\/li>\n<li><a href=\"https:\/\/www.aaai.org\/ocs\/index.php\/ICAPS\/ICAPS16\/paper\/view\/13049\" target=\"_blank\" rel=\"noopener\">Theta recursiva estricta *<\/a><\/li>\n<li><a href=\"https:\/\/www.cambridge.org\/core\/journals\/robotica\/article\/abs\/cwave-theory-and-practice-of-a-fast-singlesource-anyangle-path-planning-algorithm\/15B1D45E7C4467A0C33020525ABD9B33\" target=\"_blank\" rel=\"noopener\">CWave<\/a><\/li>\n<\/ul>\n<\/li>\n<li>Basado en RRT\n<ul>\n<li><a href=\"https:\/\/arxiv.org\/abs\/1005.0416\" target=\"_blank\" rel=\"noopener\">Gr\u00e1fico aleatorio de exploraci\u00f3n r\u00e1pida (RRG)<\/a><\/li>\n<li><a href=\"https:\/\/arxiv.org\/abs\/1105.1186\" target=\"_blank\" rel=\"noopener\">RRT *<\/a><\/li>\n<li><a href=\"https:\/\/ieeexplore.ieee.org\/document\/6942976\/\" target=\"_blank\" rel=\"noopener\">RRT informado *<\/a><\/li>\n<\/ul>\n<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-5774\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-5774\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Solucionadores<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-5774\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-5774\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/es\/busqueda-de-ruta-de-teoria-de-grafos\/resolucion-de-ruta-mas-corta-con-excel\/\">Resoluci\u00f3n de ruta m\u00e1s corta con Excel<\/a><\/li>\n<li>Cambie de una fuente \/ sumidero m\u00faltiple a una \u00fanica<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-e0897ee elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e0897ee\" 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-45fe2293\" data-id=\"45fe2293\" 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-2364a569 elementor-widget elementor-widget-text-editor\" data-id=\"2364a569\" 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_84 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\/#Recherche-de-chemin\" >B\u00fasqueda de ruta<\/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\/#Probleme-sous-optimal\" >Problema sub\u00f3ptimo<\/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\/#Arbre-de-chemins\" >\u00c1rbol de caminos<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Recherche-de-chemin\"><\/span>B\u00fasqueda de ruta<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">los <b>b\u00fasqueda de ruta<\/b>, comunmente llamado <i><b><span lang=\"en\" xml:lang=\"en\">camino <\/span><\/b><\/i>consiste en encontrar c\u00f3mo moverse en un entorno entre un punto de partida y un punto final teniendo en cuenta varias limitaciones.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><strong>Definici\u00f3n de un gr\u00e1fico valorado<\/strong><\/p>\n<p>Una gr\u00e1fica valorada es una gr\u00e1fica a cuyos arcos asociamos un n\u00famero real llamado longitud del arco.<\/p>\n<p>Denotamos por w (x, y) la longitud del arco (x, y) entre los v\u00e9rtices xey.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Por analog\u00eda con la matriz de adyacencia, podemos representar un gr\u00e1fico valorado por una matriz cuadrada, cuyos coeficientes corresponden a la valoraci\u00f3n de los arcos.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Sea un gr\u00e1fico valorado cuyos v\u00e9rtices se han numerado de 1 a n. La matriz de valoraci\u00f3n de G es la matriz cuadrada M = m<sub>ij<\/sub>, de tama\u00f1o n * n, definido por<\/p>\n<p><\/p>\n<div>\n<figure><img decoding=\"async\" class=\"alignnone wp-image-427 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/131.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"277\" height=\"77\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Aqu\u00ed hay un ejemplo:<\/p>\n<p><\/p>\n<div>\n<figure><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-425 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/14.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"530\" height=\"150\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/14.png 530w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/14-300x85.png 300w\" sizes=\"(max-width: 530px) 100vw, 530px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Por tanto, podemos deducir el siguiente programa lineal, con x<sub>ij<\/sub>= 1 si el arco es parte de la ruta m\u00e1s corta, 0 en caso contrario:<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>minimizar <img decoding=\"async\" class=\"alignnone\" src=\"https:\/\/upload.wikimedia.org\/math\/c\/c\/0\/cc0b9c5d99fd91926a1b436785781cf1.png\" alt=\"ruta de b\u00fasqueda de ruta m\u00e1s corta\" width=\"82\" height=\"40\" title=\"\"> con A el conjunto de arcos<\/li>\n<li>sujeto a <img loading=\"lazy\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/upload.wikimedia.org\/math\/d\/7\/b\/d7b89f725185c1fd9984123cbaa89612.png\" alt=\"ruta de b\u00fasqueda de ruta m\u00e1s corta\" width=\"47\" height=\"17\" title=\"\"><\/li>\n<\/ul>\n<p><\/p>\n<p class=\"wp-block-paragraph\">y para todos <em>I<\/em>, <img loading=\"lazy\" decoding=\"async\" class=\"alignnone\" src=\"https:\/\/upload.wikimedia.org\/math\/8\/a\/c\/8acfff4159658f8e55922120c4f3e303.png\" alt=\"ruta de b\u00fasqueda de ruta m\u00e1s corta\" width=\"320\" height=\"84\" title=\"\"><\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6292 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"769\" height=\"521\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath.png 769w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath-300x203.png 300w\" sizes=\"(max-width: 769px) 100vw, 769px\" \/><\/figure>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6293 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath2.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"380\" height=\"431\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath2.png 380w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/lppath2-265x300.png 265w\" sizes=\"(max-width: 380px) 100vw, 380px\" \/><\/figure>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Aunque se trata de programaci\u00f3n lineal, este m\u00e9todo puede resultar muy caro en memoria, e incluso imposible de configurar en determinados casos (por ejemplo, si se trata de un sistema distribuido). Otro m\u00e9todo para conocer el camino m\u00e1s corto ser\u00eda conocer el m\u00e1s peque\u00f1o de todos los caminos de un v\u00e9rtice a otro.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Definimos el peso de un camino <strong>c = (u,\u2026, v)<\/strong><\/p>\n<p>como la suma de los pesos de los arcos que lo constituyen anotado <strong>WC).<\/strong>Luego definimos la distancia m\u00ednima (camino m\u00e1s corto) entre dos v\u00e9rtices u y v por:<\/p>\n<p><\/p>\n<div>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-413 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/12.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"466\" height=\"66\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/12.png 466w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/01\/12-300x42.png 300w\" sizes=\"(max-width: 466px) 100vw, 466px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Nos gustar\u00eda tener un m\u00e9todo capaz, para cualquier gr\u00e1fico y para cualquier par de v\u00e9rtices. <em><strong>X<\/strong><\/em> y<em><strong> y<\/strong><\/em>, para determinar el camino m\u00e1s corto entre ellos. Para ello, debemos comprender y caracterizar lo mejor posible la estructura de una soluci\u00f3n: \u00bfcu\u00e1les son las propiedades de un camino m\u00e1s corto?<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\"><strong>Lema de Koenig.<\/strong> Un camino m\u00e1s corto entre 2 v\u00e9rtices es elemental. Un sendero es elemental si cada uno de los picos de la ruta se visita una sola vez.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Enumerar todos los caminos para determinar el m\u00e1s corto revela un grave defecto: su tiempo de ejecuci\u00f3n. Si el n\u00famero de caminos elementales es finito, no obstante sigue siendo muy grande, del orden de <em><strong>\u00a1no!<\/strong><\/em> en un gr\u00e1fico de orden <em><strong>no<\/strong><\/em>.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Probleme-sous-optimal\"><\/span>Problema sub\u00f3ptimo<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Necesitamos una segunda propiedad fundamental, la <em>suboptimalidad (ver Programaci\u00f3n din\u00e1mica)<\/em>. Es cuesti\u00f3n de notar que ser un camino m\u00e1s corto es recursivo: una secuencia de un camino m\u00e1s corto sigue siendo un camino m\u00e1s corto entre sus extremos. O si la ruta m\u00e1s r\u00e1pida entre <em><strong>tu <\/strong><\/em>y <em><strong>v<\/strong><\/em> pasa por 2 picos <em><strong>X<\/strong><\/em> y <em><strong>y<\/strong><\/em>, esta ruta necesariamente toma el camino m\u00e1s corto entre <em><strong>X<\/strong><\/em> y <em><strong>y.<\/strong><\/em><\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">s\u00ed <em><strong>p = (u,\u2026, v)<\/strong><\/em> es un camino m\u00e1s corto entre <em><strong>tu<\/strong><\/em> y <em><strong>v<\/strong><\/em>, luego para cualquier cumbre <em><strong>X<\/strong><\/em> en el camino <em><strong>pag<\/strong><\/em> :<\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>el subtrayecto de <em><strong>pag<\/strong><\/em> hasta <em><strong>X<\/strong><\/em>, <em><strong>(u,\u2026, x)<\/strong><\/em>, es un camino m\u00e1s corto de <em><strong>tu<\/strong><\/em> Para <em><strong>X<\/strong><\/em><\/li>\n<li>el subtrayecto de <em><strong>pag<\/strong><\/em> desde <em><strong>X<\/strong><\/em>, <em><strong>(x,\u2026, v)<\/strong><\/em>, es un camino m\u00e1s corto de <em><strong>X<\/strong><\/em> Para <em><strong>v<\/strong><\/em><\/li>\n<\/ul>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Para el absurdo supongamos que existe, por ejemplo, entre <em><strong>tu<\/strong><\/em> y <em><strong>X<\/strong><\/em> un camino <em><strong>q<\/strong><\/em> de longitud estrictamente menor que la de<em><strong> p = (u,\u2026, x,\u2026, v)<\/strong><\/em>. Para que podamos construir un nuevo camino <em><strong>pag &#039;<\/strong><\/em> Entre <em><strong>tu<\/strong><\/em> y <em><strong>v<\/strong><\/em> sustituyendo <em><strong>q<\/strong><\/em> seguro <em><strong>(u,\u2026, x)<\/strong><\/em> en la forma <em><strong>pag<\/strong><\/em>. El largo de <em><strong>pag &#039;<\/strong><\/em> es entonces estrictamente menor que el de <em><strong>pag<\/strong><\/em>, que contradice que <em><strong>pag<\/strong><\/em> es una forma m\u00e1s corta de <em><strong>tu<\/strong><\/em> Para <em><strong>v<\/strong><\/em>.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Arbre-de-chemins\"><\/span>\u00c1rbol de caminos<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Hay un <a href=\"https:\/\/complex-systems-ai.com\/es\/teoria-de-grafos\/arboles-y-arboles\/\">\u00e1rbol<\/a> Hay un \u00e1rbol que muestra los caminos m\u00e1s cortos desde un punto de partida a todos los dem\u00e1s. Suponga que la gr\u00e1fica est\u00e1 conectada, los bordes no est\u00e1n dirigidos y los pesos no son negativos. Desarrollamos una nube de v\u00e9rtices, comenzando con sy finalmente cubriendo todos los v\u00e9rtices. Almacenamos en cada v\u00e9rtice v una etiqueta d (v) que representa la distancia de v desde s en el subgrafo formado por la nube y sus v\u00e9rtices adyacentes. En cada paso: agregamos a la nube la parte superior fuera de la nube con la etiqueta de distancia m\u00e1s peque\u00f1a; actualizamos las etiquetas de los v\u00e9rtices adyacentes a u (ver \u00e1rbol de expansi\u00f3n).<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Considere una arista e = (u, z) tal que u es el v\u00e9rtice agregado m\u00e1s recientemente a la nube yz no est\u00e1 en la nube. La relajaci\u00f3n del borde e actualiza la distancia d (z) de la siguiente manera: d (z) \u2190 min {d (z), d (u) + peso (e)}<\/p>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6294 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/relax1.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"753\" height=\"322\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/relax1.png 753w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/relax1-300x128.png 300w\" sizes=\"(max-width: 753px) 100vw, 753px\" \/><\/figure>\n<p><\/p>\n<figure><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-6295 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2.png\" alt=\"pathfinding pathfinding ruta m\u00e1s corta teor\u00eda de grafos\" width=\"500\" height=\"500\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2.png 500w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2-300x300.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2018\/04\/realx2-150x150.png 150w\" sizes=\"(max-width: 500px) 100vw, 500px\" \/><\/figure>\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>","protected":false},"excerpt":{"rendered":"<p>Teor\u00edas P\u00e1gina de inicio Wiki I. Ruta m\u00e1s corta, fuente \u00fanica (b\u00fasqueda de ruta) Gr\u00e1fico no dirigido Algoritmo de Dijkstra Dijkstra con mont\u00f3n binario Dijkstra con Fibonacci \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-362","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/362","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=362"}],"version-history":[{"count":40,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/362\/revisions"}],"predecessor-version":[{"id":20409,"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/pages\/362\/revisions\/20409"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/es\/wp-json\/wp\/v2\/media?parent=362"}],"curies":[{"name":"gracias","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}