Munkresalgoritme

Munkresalgoritme, også kendt som Kuhn–Munkres-algoritmen, er en algoritme til at løse tildelingsproblemet. Formålet er at tildele hver opgave til en person med mindst mulig total omkostning givet en omkostningsmatrice C af størrelse n × n. Algoritmen blev udviklet af James Munkres i 1957 som en forbedring af Kuhns oprindelige Hungarian-algoritme og betegnes derfor ofte som Kuhn–Munkres-algoritmen.

Den opererer i to faser. Først udføres en række-reduktion og kolonne-reduktion: fra hver række trækkes den mindste værdi, og dernæst trækkes den mindste værdi i hver kolonne. Dette sikrer, at matrixen indeholder nulpunkter, som kan bruges til tilordninger. Herefter bygges en delvis tilordning ved hjælp af nulpunkter, bl.a. gennem markering af nogle nulpunkter som stjernede for at danne en uafhængig parring. Hvis der findes n uafhængige stjernede nulpunkter, foreligger en komplet tilordning.

Hvis antallet af stjernede nulpunkter ikke når n, findes en mindste dækning af alle nulpunkter ved hjælp af rækker og kolonner. Er dækningsnummeret mindre end n, oprettes primede nulpunkter og der findes en forlængelsessti bestående af primede og stjernede nulpunkter; ved at følge stigen opdateres markeringerne og dækningsmønsteret, og processen gentages indtil en fuld tilordning foreligger.

Kompleksitet og anvendelse. Tid: O(n^3) for en n × n matrix, hukommelse: O(n^2). Algoritmen kan tilpasses rektangulære matricer ved at tilføje dummyrækker eller -kolonner. Anvendelser inkluderer optimeret personale- og opgavetildeling i produktion, logistik, og dataassociation i sporing og tracking.

Relaterede koncepter: Kuhns algoritme, Hungarian-algoritmen.