ROceloth / LeChristofides

Algoritmo de aproximación para TSP Metric
0 stars 0 forks source link

Mejora para mWPMn #1

Open ROceloth opened 4 years ago

ROceloth commented 4 years ago

Me parece que no es del todo correcta la función de mWPMn, hay que investigar mas sobre la teoria del minimum perfect match en especial para el tipo de graficas que operan hasta ese punto en el algoritmo

ROceloth commented 4 years ago

Entre la investigación hay dos candidatos a implementar, el método Hungariano y el algoritmo por propagación Blossom, el ultimo es una mejora para el primero, aunque tratarlo con matrices y mas aun las matrices adecuadas a este concepto requiere de mas esfuerzo, el caso esta, en el método hungariano como marcar con lineas las matrices, y que estas sean las mínimas que cubran los zeros