Skip to content

hungarian ​

hungarian(costMatrix) atribui linhas a colunas distintas com custo total mínimo. A entrada é uma matriz de custos i32[][] e o resultado contém o custo ótimo e os pares linha-coluna.

AssinaturaRetornoComplexidade
hungarian(costMatrix: i32[][])[i32, [usize, usize][]]O(n³) para matriz n × n

Para matrizes retangulares, cada linha é atribuída quando há colunas suficientes. Custos positivos e negativos são aceitos.

Exemplo ​

tyrus
import { hungarian } from "tyrus:algorithm";

const result: [i32, [usize, usize][]] = hungarian([[4, 1], [2, 3]]);
print(result[0]); // 3

Resultado para estudo ​

tyrus
interface HungarianInfo {
    assignments: [usize, usize][];
    totalCost: i32;
    potentialAdjustmentCount: usize;
    matrixIterationCount: usize;
}
tyrus
import { HungarianInfo, hungarianInfo } from "tyrus:algorithm";
const info: HungarianInfo = hungarianInfo([[4, 1], [2, 3]]);
print(info.assignments); // [[1, 0], [0, 1]]
print(info.totalCost); // 3
print(info.potentialAdjustmentCount); // 4
print(info.matrixIterationCount); // 2