C语言实现的运筹学匈牙利解法：指派问题解决方案

4星 · 超过85%的资源需积分: 20 194 浏览量更新于2024-07-28 1 收藏 269KB DOC 举报

"这篇资源是关于使用C语言实现运筹学中的匈牙利解法解决指派问题的程序代码。程序适用于人与任务数量相等或不等的情况，旨在通过匈牙利算法找到最佳匹配。" 匈牙利解法是一种求解完全匹配问题的有效算法，尤其适用于解决指派问题，比如在任务分配、资源调度等领域。在这个C语言实现中，程序首先定义了两个关键数据结构：`ASS` 结构体用于存储矩阵中的元素，而 `TrueOrForse` 结构体用来标记元素是否已被处理。程序还包含了各种辅助函数，如输出函数，以便进行调试和结果展示。算法的核心流程分为以下几个步骤： 1. **初始化**：根据用户输入构建方阵，如果人数乘以每人能做的最大任务数小于任务总数，那么补充0行；反之，补充0列。输出这个方阵以供用户验证输入的正确性。 2. **标记过程**：根据规则，选择按行或按列减去最小值。如果人数乘以最大任务数小于或等于任务数，减去每行最小值；否则，减去每列最小值。接着标记含有0最多的行或列。如果标记的直线数未达到矩阵的行数或列数，就撤销所有标记，选择含0最少的行或列，减去非0最小值，并对相应列或行的元素进行调整。这个过程持续到标记的直线数等于矩阵的行数或列数。 3. **转换为0-1指派矩阵**：选择含0最少的行或列，将其中的0转换为一个非常大的数，同时进行标记。接着选择未被标记的0并同样转换，直到所有元素都被标记。最后，将这些大的数替换为1，其他元素替换为0，得到最终的0-1指派矩阵。这个C程序的源代码中，定义了一些常量，如 `MAXCOUNT` 表示最大人数和任务数，`TRUE` 和 `FALSE` 分别代表逻辑真和假，以及 `INDEF` 用于表示指派中不可能出现的数值。程序还使用了 `malloc` 和 `stdlib.h` 等库来进行动态内存分配，确保能处理不同规模的问题。这个资源提供了一个实用的C语言实现，可以帮助学习者理解和应用匈牙利解法来解决实际的指派问题。通过理解并运行这个程序，可以深入理解算法的工作原理，同时也能在编程实践中提升对C语言和运筹学的理解。

三、算法源程序

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <conio.h>

#include <string.h>

#define MAXCOUNT 50 // 最大的人数和任务数量

#define TRUE 1

#define FALSE 0

#define INDEF 10000 //指派中不可能出现的数

struct TrueOrForse

{

int marker;

}; //用于记录某元素是否被标记

typedef struct ASS

{

int assign[MAXCOUNT][MAXCOUNT];

struct TrueOrForse sign[MAXCOUNT][MAXCOUNT];

}Assign; //记录指派中各元素，及其是否被标记

void Print(int a[][MAXCOUNT],int Row,int Col); // 输出 0-1 指派构成的矩阵

void reduceRow(Assign*L,int Row,int Col); // 减去行中最小值

void reduceCol(Assign*L,int Row,int Col); // 减去列中最小值

int CountZero(Assign*L,int Row,int Col,int temp); // 计算其中的零元素，并返

回最大（temp 若为 0，则返回最小的）的行或列，若都标记完，则返回 0

void Zero_marker(Assign*L,int m,int n); // 若 m<n 标记 m 行；若

m>n 标记 m-n 列

void SearchAgainByRowReduce(Assign*L,int count,int m); // 搜索未被标记行元素继

续操作使其出现 0，并将所有数置为正数

void SearchAgainByColReduce(Assign*L,int m,int count); // 搜索未被标记列元素继续操

作使其出现 0，并将所有数置为正数

void removeMarker(Assign*L,int m); // 撤销所有标记

void ToBest(Assign*L,int count,int m); // 最后化为 0-1 指派

int main(void)

{

Assign *L = NULL;

int PersonCount = 0,ThingCount = 0; // 人数与任务数量

int OneDoMaxThing = 0; // 一个人最多工作的任务数量

int m; // 记录化成指派问题的行数与列数

剩余17页未读，继续阅读

a530317920

粉丝: 1
资源: 14

C语言实现的运筹学匈牙利解法：指派问题解决方案

二分图(匈牙利算法)归纳.md

匈牙利算法用C语言描述

运筹学指派问题C++实现

匈牙利算法c语言代码

C语言代码中的匈牙利命名法

匈牙利算法最优指派代码C++

匈牙利算法的matlab代码

匈牙利算法的matlab代码实现

匈牙利算法最优指派代码

匈牙利算法 指派问题代码

最新资源

匈牙利算法指派问题代码