Título inglés |
Analysis of heuristics for the Rural Postman Problem. |
Título español |
Análisis de heurísticos para el problema del cartero rural. |
Autor/es |
Benavent, Enrique ; Campos, Vicente ; Corberán, Angel ; Mota, Enrique |
Organización |
Dep. Estad. Inv. Oper. Fac. Mat. Univ. Valencia, Valencia, España |
Revista |
0041-0241 |
Publicación |
1985, 36 (2): 27-38, 8 Ref. |
Tipo de documento |
articulo |
Idioma |
Español |
Resumen español |
En este artículo se estudia el comportamiento en el peor de los casos de dos algoritmos heurísticos propuestos para el Problema del Cartero Rural definido sobre un grafo no dirigido (RPP) y sobre un grafo dirigido (DRPP). En ambos problemas se determina el radio del peor caso de los heurísticos estudiados, que para el RPP es 3/2, mientras que para el DRPP no está acotado. Para conseguir cotas que sean más significativas, se ha determinado también este radio en función de ciertos parámetros que se pueden calcular a partir de los datos particulares de cada ejemplo, lo que ha permitido obtener una cota finita para el comportamiento en el peor caso del algoritmo heurístico para el DRPP. |
Resumen inglés |
In this paper we study the worst case performance of two heuristic algorithms proposed for the Rural Postman Problem on a non directed graph (RPP) and on a directed graph (DRPP). In both cases the worst case ratio is obtained; for the RPP this ratio is 3/2, whereas for the DRPP the ratio is unbounded. In order to obtain more significant bounds, this ratio has also been obtained as a function of certain parameters that can be computed from the particular data of each instance, thus producing a finite bound for the worst case ratio of the heuristic algorithm for the DRPP. |
Clasificación UNESCO |
120704 |
Palabras clave español |
Heurística ; Circuitos eulerianos ; Algoritmos ; Caso peor |
Código MathReviews |
MR0829696 |
Acceso al artículo completo |