Algoritmo húngaro

Problemas de asignación.

  1. Reste el número más pequeño de cada fila a cada fila, esta operación se denomina "reducción por filas"
  2. Puede también restar el número más pequeño de cada columna de la tabla a cada número de la columna
  3. Pruebe si se puede hacer una asignación optima, hágalo mediante la determinación del número mínimo de líneas necesario para cubrir todos los ceros, si el número de líneas es igual al número de filas es posible hacer una asignación optima, en ese caso se continua directamente con el 6º Paso, de lo contrario se continua con el 4º Paso
  4. Si el número de líneas es menor que el número de filas modifique la tabla de la siguiente manera:
  5. Reste el número menor de entre todos los números no cubiertos de la tabla
  6. Sume el número no cubierto más pequeño a los números que se encuentran en las intersecciones de las líneas
  7. Los números cruzados pero que no se encuentran en las intersecciones de las líneas permanecen sin cambio en la siguiente tabla
  8. Repita el paso 3º y 4º hasta que sea posible realizar un conjunto de asignaciones óptimas
  9. Haga las asignaciones una a una en las posiciones con elemento "cero". Comience con las filas y columnas que tienen solo un cero, como cada fila y cada columna necesita recibir una exactamente una asignación, deseche tanto la fila como la columna para hacer cada asignación. Después continúe con las filas y columnas que aún no han sido seleccionadas dando siempre preferencia a la fila o columna que solo tenga un cero. Continúe con el proceso hasta que todas las filas y columnas tengan exactamente una asignación.

Algoritmo húngaro Rating: 4.5 Diposkan Oleh: Ing. Civil

0 comentarios::

Publicar un comentario