{"id":81679,"date":"2018-03-10T00:05:33","date_gmt":"2018-03-10T00:05:33","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/metodos-heura%c2%adsticos-para-el-problema-de-steiner-en-grafos\/"},"modified":"2018-03-10T00:05:33","modified_gmt":"2018-03-10T00:05:33","slug":"metodos-heura%c2%adsticos-para-el-problema-de-steiner-en-grafos","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/matematicas\/metodos-heura%c2%adsticos-para-el-problema-de-steiner-en-grafos\/","title":{"rendered":"M\u00e9todos heur\u00edsticos para el problema de steiner en grafos."},"content":{"rendered":"<h2>Tesis doctoral de <strong> Pere Guitart Colom <\/strong><\/h2>\n<p>El problema de steiner en grafos (psg) e sun problema de optimizaci\u00f3n combinatoria cl\u00e1sico perteneciente a la clase np-hard y, por lo tanto, son necesarios m\u00e9todos heur\u00edsticos para obtener aproximaciones al \u00f3ptimo enun tiempo razonable. Aquellos m\u00e9todos heur\u00edsticos que compiten para obtener los mejores resutlados realizan un n\u00famero relativamente alto de ejecucciones de un algoritmo simple, o algoritmo de base, con el fin de obtener una soluci\u00f3n mejor. Los dos alforitmos de base m\u00e1s com\u00fanmente usados son la shortest path heuristic (sph), propuesta por takahaski y matsuyama en 1980, yla distance network heuristic (dnh), propuesta por choukhmane en 1978,a pesar de que suele ariburise a kou et al. (1981).  los dos objetivos pricipales de la tesis son el dise\u00f1o y la construcci\u00f3n de m\u00e9todos competitivos para el psg, y el estudio y mejora de la sph y la dnh. Se han propuesto dos nuevos m\u00e9todos competitivos cuyos resutlados experimentales, cuando se utilizan las instancias de prueba m\u00e1s comunes, superan los de los mejores m\u00e9todos conocidos.El primero es un algoritmo gen\u00e9tico (ag) que mejora el propuesto por esbensen en 1995 el cual, a su vez, es una neuva versi\u00f3ndle ag propeusto por kapsalis et al. En 1993. es de destacar el an\u00e1lisis del funcionamiento del algoritmo de forma independiente a us interpretaci\u00f3n en clave gen\u00e9tica.El segundo es un m\u00e9todo iterativo basado en la sph e incluye algunas funciones que pueden ser utilizadas para mejorar otros m\u00e9odos.  en cuanto al segundo objetivo, se han propuesto una nueva implementaci\u00f3n de la sph que reduce su complejidad, y dos nuevas variantes de este algoritmo que mejoran su rendimiento.Todas ellas pueden ser utilizadas para incrementar el rendimiento de los m\u00e9todos competitivos basados enla sph o en la dnh.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>M\u00e9todos heur\u00edsticos para el problema de steiner en grafos.<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 M\u00e9todos heur\u00edsticos para el problema de steiner en grafos. <\/li>\n<li><strong>Autor:<\/strong>\u00a0 Pere Guitart Colom <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Aut\u00f3noma de barcelona<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 15\/12\/1999<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li> Basart Mu\u00f1oz Josep M.<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: josep Rifa loma <\/li>\n<li>kostas Isouros (vocal)<\/li>\n<li>Miguel \u00e1ngel Fiol mora (vocal)<\/li>\n<li>josep Domingo ferrer (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de Pere Guitart Colom El problema de steiner en grafos (psg) e sun problema de optimizaci\u00f3n combinatoria cl\u00e1sico [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[1890,37303,2528,30372,126],"tags":[174157,40351,174158,174159,15610,174156],"class_list":["post-81679","post","type-post","status-publish","format-standard","hentry","category-ciencia-de-los-ordenadores","category-heuristica","category-inteligencia-artificial","category-lenguajes-algoritmicos","category-matematicas","tag-basart-munoz-josep-m","tag-josep-domingo-ferrer","tag-josep-rifa-loma","tag-kostas-isouros","tag-miguel-angel-fiol-mora","tag-pere-guitart-colom"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/81679","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=81679"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/81679\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=81679"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=81679"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=81679"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}