Algorisme hongarès
mètode d'optimització en control operatiu / From Wikipedia, the free encyclopedia
L'algorisme hongarès és un algorisme d'optimització el qual resol problemes d'assignació en temps . La primera versió coneguda del mètode Hongarès, va ser inventat i publicat per Harold W. Kuhn el 1955. Va ser revisat per James Munkres el 1957, i ha estat conegut des de llavors com l'algorisme hongarès, l'algorisme de l'assignació de Munkres, o l'algorisme de Kuhn-Munkres. L'algorisme desenvolupat per Kuhn està basat en els primers treballs d'altres dos matemàtics hongaresos: Dénes Kőnig i Jenő Egerváry, d'on prové el seu nom.[1][2] El gran avantatge del mètode de Kuhn és que és fortament polinòmic, cosa que redueix la seva complexitat computacional. L'algorisme hongarès construeix una solució del problema primal partint d'una solució no admissible (que correspon a una solució admissible del dual) fent-la a poc a poc més admissible.
El 2006 es va descobrir que matemàtic Carl Gustav Jacob Jacobi va solucionar aquest problema en el segle xix, i que la solució es va publicar com a obra pòstuma el 1890 en llatí.[3]