Created
October 6, 2023 20:35
-
-
Save TheAlchemistKE/e7d33820e47c64667c926a9c770d16d6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"math" | |
) | |
func hungarianAlgorithm(costMatrix [][]int) ([]int, int) { | |
rows := len(costMatrix) | |
cols := len(costMatrix[0]) | |
// Step 1: Subtract the minimum value in each row from all elements in that row. | |
for i := 0; i < rows; i++ { | |
minVal := math.MaxInt32 | |
for j := 0; j < cols; j++ { | |
if costMatrix[i][j] < minVal { | |
minVal = costMatrix[i][j] | |
} | |
} | |
for j := 0; j < cols; j++ { | |
costMatrix[i][j] -= minVal | |
} | |
} | |
// Step 2: Subtract the minimum value in each column from all elements in that column. | |
for j := 0; j < cols; j++ { | |
minVal := math.MaxInt32 | |
for i := 0; i < rows; i++ { | |
if costMatrix[i][j] < minVal { | |
minVal = costMatrix[i][j] | |
} | |
} | |
for i := 0; i < rows; i++ { | |
costMatrix[i][j] -= minVal | |
} | |
} | |
// Step 3: Cover all the zeros with the minimum number of lines. | |
rowCovered := make([]bool, rows) | |
colCovered := make([]bool, cols) | |
for i := 0; i < rows; i++ { | |
for j := 0; j < cols; j++ { | |
if costMatrix[i][j] == 0 && !rowCovered[i] && !colCovered[j] { | |
rowCovered[i] = true | |
colCovered[j] = true | |
} | |
} | |
} | |
// Step 4: Check if all rows are covered. If yes, the optimal assignment is found. | |
assignment := make([]int, rows) | |
for i := 0; i < rows; i++ { | |
for j := 0; j < cols; j++ { | |
if costMatrix[i][j] == 0 && !colCovered[j] && assignment[i] == 0 { | |
assignment[i] = j | |
colCovered[j] = true | |
break | |
} | |
} | |
} | |
// Calculate the total cost of the assignment. | |
totalCost := 0 | |
for i := 0; i < rows; i++ { | |
j := assignment[i] | |
totalCost += costMatrix[i][j] | |
} | |
return assignment, totalCost | |
} | |
func main() { | |
// Define the cost matrix. | |
costMatrix := [][]int{ | |
{3, 2, 7}, | |
{1, 4, 6}, | |
{5, 8, 9}, | |
} | |
// Find the optimal assignment using the Hungarian Algorithm. | |
assignment, totalCost := hungarianAlgorithm(costMatrix) | |
// Print the result. | |
fmt.Println("Assignment:") | |
for i, j := range assignment { | |
fmt.Printf("Worker %d assigned to Task %d\n", i, j) | |
} | |
fmt.Println("Total Cost:", totalCost) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment