Análisis de heurísticos para el problema del cartero rural

1. Benavent López, Enric
2. Campos Aucejo, Vicente
3. Corberán Salvador, Ángel
4. Mota Vidal, Enrique

Exportar

Exportar

×

MLA

modern-language-association

APA

apa

Chicago

chicago-fullnote-bibliography

Harvard

harvard-cite-them-right

Vancouver

vancouver-author-date

---

RIS BibTex

Exportar

×

El documento no se puede exportar porque pertenece a otro portal.

Texto completo

lock_openTexto completo externo

DOI: 10.1007/BF02888609 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Trabajos de estadística e investigación operativa

Resumen

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.

Fuente de los datos: Dialnet