使用匈牙利算法实现最大匹配的案例

我就是我 2022-04-22 05:50 151阅读 0赞

在生活中常常遇到两组元素多对多匹配而又数目有限的情况，我们需要对其进行最大匹配数的分配，使效率最大化。  
        本案例实现的功能是：从excel文档中读取一组压缩气缸和一组压缩活塞的数据，每一个型号的压缩气缸有一个固定的内径大小，每一个型号的压缩活塞可以匹配内径在一定范围内的气缸，使用匈牙利算法得到活塞和气缸对大匹配数的方案。

--------------------

## 1. Excel表格数据 ##

**压缩气缸数据：**  
| ![在这里插入图片描述][20181102162107573.png]  
**压缩活塞数据：**  
![\*\*代码展示：\*\*][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NTg3OTk3_size_16_color_FFFFFF_t_70]

--------------------

## 2. 编写实体类 ##

**压缩气缸实体类：**

/** * 气缸实体类 * * @author liuxiaofeng * @date 2018/10/29 17:11 */
    public class Cylinder { 
    
        private Integer id;
    
        /** * 压缩气缸编号 */
        private String numberYQ;
    
        /** * 气缸尺寸 */
        private Double innerDiameter;
    
    
        public Integer getId() { 
            return id;
        }
    
    
        public void setId(Integer id) { 
            this.id = id;
        }
    
    
        public String getNumberYQ() { 
            return numberYQ;
        }
    
    
        public void setNumberYQ(String numberYQ) { 
            this.numberYQ = numberYQ;
        }
    
    
        public Double getInnerDiameter() { 
            return innerDiameter;
        }
    
    
        public void setInnerDiameter(Double innerDiameter) { 
            this.innerDiameter = innerDiameter;
        }
    
    
        @Override
        public String toString() { 
            return "Cylinder{" +
                    "id=" + id +
                    ", numberYQ='" + numberYQ + '\'' +
                    ", innerDiameter=" + innerDiameter +
                    '}';
        }
    }

**压缩活塞实体类：**

/** * 活塞实体类 * * @author liuxiaofeng * @date 2018/10/29 17:16 */
    public class Piston { 
    
        private Integer id;
    
        /** * 活塞编号 */
        private String numberYH;
    
        /** * 活塞尺寸 */
        private Double outerDiameter;
    
        /** * 可配对气缸最小尺寸 */
        private Double lowerInnerDiameter;
    
        /** * 可配对气缸最大尺寸 */
        private Double upperInnerDiameter;
    
    
        public Integer getId() { 
            return id;
        }
    
    
        public void setId(Integer id) { 
            this.id = id;
        }
    
    
        public String getNumberYH() { 
            return numberYH;
        }
    
    
        public void setNumberYH(String numberYH) { 
            this.numberYH = numberYH;
        }
    
    
        public Double getOuterDiameter() { 
            return outerDiameter;
        }
    
    
        public void setOuterDiameter(Double outerDiameter) { 
            this.outerDiameter = outerDiameter;
        }
    
    
        public Double getLowerInnerDiameter() { 
            return lowerInnerDiameter;
        }
    
    
        public void setLowerInnerDiameter(Double lowerInnerDiameter) { 
            this.lowerInnerDiameter = lowerInnerDiameter;
        }
    
    
        public Double getUpperInnerDiameter() { 
            return upperInnerDiameter;
        }
    
    
        public void setUpperInnerDiameter(Double upperInnerDiameter) { 
            this.upperInnerDiameter = upperInnerDiameter;
        }
    
    
        @Override
        public String toString() { 
            return "Piston{" +
                    "id=" + id +
                    ", numberYH='" + numberYH + '\'' +
                    ", outerDiameter=" + outerDiameter +
                    ", lowerInnerDiameter=" + lowerInnerDiameter +
                    ", upperInnerDiameter=" + upperInnerDiameter +
                    '}';
        }
    }

--------------------

## 3. 工具类编写 ##

**读取Excel文件并封装对象的工具类：**

/** * 读取Excel表格数据并封装对象的工具类 * * @author liuxiaofeng * @date 2018/10/29 17:24 */
    public class ExcelReader { 
    
        /** * 根据Excel文档的全路径读取文件并返回该文档的对象 * * @param excelPath Excel表格文件的全路径 * @return 返回一个表格文件封装的对象 * @throws Exception 文件流异常 */
        public static Workbook creatWorkbook(String excelPath) throws Exception { 
            //1.创建文件对象
            File excel = new File(excelPath);
    
            //2.创建Workbook对象
            Workbook workbook = null;
            //3.判断文件是否存在
            if (excel.exists() && excel.isFile()) { 
                //4.获取文件名
                String excelName = excel.getName();
    
                //5.判断文件拓展名是否为xls/xlsx
                String extension1 = ".xls";
                String extension2 = ".xlsx";
                if (excelName.endsWith(extension1)) { 
    
                    //5.1.1.文件拓展名为xls，获取文件读入流对象
                    FileInputStream fis = new FileInputStream(excel);
                    //5.1.2.通过文件流创建Excel表格对象
                    workbook = new HSSFWorkbook(fis);
                } else if (excelName.endsWith(extension2)) { 
    
                    //5.2.文件拓展名为xlsx，直接通过文件对象获取Excel表格对象
                    workbook = new XSSFWorkbook(excel);
                } else { 
                    throw new IllegalArgumentException("文件格式错误！");
                }
            }
            //6.返回Excel表格对象
            return workbook;
        }
    
    
        /** * 获取压缩气缸对象集合 * 根据Excel中对应的工作表的id，获取数据并封装成气缸对象 * * @param workbook Excel表格对象 * @param sheetId 存储气缸数据的工作表id * @return 气缸对象集合 */
        public static List<Cylinder> readCylinderBySheetId(Workbook workbook, int sheetId) { 
            //1.创建一个空的气缸对象集合
            List<Cylinder> cylinderList = new ArrayList<>();
    
            //2.根据工作表ID获取气缸表（sheet）对象
            Sheet cylinderSheet = workbook.getSheetAt(sheetId);
    
            //3.遍历每一行，封装数据
            //3.1.获取第一个有数据的行的下标，下标从0开始，数值为行数-1
            int firstRowNum = cylinderSheet.getFirstRowNum();
            //3.2.获取最后一个有数据的行的下标，数值为行数-1
            int lastRowNum = cylinderSheet.getLastRowNum();
    
            //3.3.第一行为表头，数据从第二行开始
            for (int rowIndex = firstRowNum + 1; rowIndex <= lastRowNum; rowIndex++) { 
                //4.获取当前行对象
                Row row = cylinderSheet.getRow(rowIndex);
    
                //5.判断该行是否为空
                if (row != null) { 
                    //7.创建压缩气缸对象
                    Cylinder cylinder = new Cylinder();
                    //8.获取第一个有数据的单元格的列数，和行不同，是从1开始
                    short firstCellNum = row.getFirstCellNum();
    
                    //9.设置id
                    cylinder.setId(rowIndex);
                    //10.设置气缸编号，第一列
                    cylinder.setNumberYQ(row.getCell(firstCellNum).toString());
                    //11.设置气缸内径，第二列
                    cylinder.setInnerDiameter(row.getCell(firstCellNum + 1).getNumericCellValue());
    
                    //12.将气缸对象存入集合
                    cylinderList.add(cylinder);
                }
            }
    
            //13.返回气缸对象集合
            return cylinderList;
        }
    
    
        /** * 获取压缩活塞对象集合 * 根据Excel中对应的工作表的id，获取数据并封装成活塞对象 * * @param workbook Excel表格对象 * @param sheetId 存储活塞数据的工作表id * @return 活塞对象集合 */
        public static List<Piston> readPistonBySheetId(Workbook workbook, int sheetId) { 
            //1.创建一个空的活塞对象集合
            List<Piston> pistonList = new ArrayList<>();
            //2.根据工作表ID获取活塞表（sheet）对象
            Sheet pistonSheet = workbook.getSheetAt(sheetId);
    
            //3.遍历每一行，封装数据
            //3.1.获取第一个有数据的行的下标，下标从0开始，数值为行数-1
            int firstRowNum = pistonSheet.getFirstRowNum();
            //3.2.获取最后一个有数据的行的下标，数值为行数-1
            int lastRowNum = pistonSheet.getLastRowNum();
    
            //3.3.第一行为表头，数据从第二行开始
            for (int rowIndex = firstRowNum + 1; rowIndex <= lastRowNum; rowIndex++) { 
                //4.获取当前行对象
                Row row = pistonSheet.getRow(rowIndex);
    
                //5.判断该行是否为空
                if (row != null) { 
                    //7.创建压缩活塞对象
                    Piston piston = new Piston();
                    //8.获取第一个有数据的单元格的列数，和行不同，是从1开始
                    short firstCellNum = row.getFirstCellNum();
    
                    //9.设置id
                    piston.setId(rowIndex);
                    //10.设置活塞编号，第一列
                    piston.setNumberYH(row.getCell(firstCellNum).toString());
                    //11.设置活塞外径，第二列
                    piston.setOuterDiameter(row.getCell(firstCellNum + 1).getNumericCellValue());
                    //12.设置匹配气缸尺寸下限，第三列
                    piston.setLowerInnerDiameter(row.getCell(firstCellNum + 2).getNumericCellValue());
                    //13.设置匹配气缸尺寸上限，第四列
                    piston.setUpperInnerDiameter(row.getCell(firstCellNum + 3).getNumericCellValue());
    
                    //14.将气缸对象存入集合
                    pistonList.add(piston);
                }
            }
    
            return pistonList;
        }
    }

**使用匈牙利算法进行完美匹配的工具类：**

/** * 对气缸和活塞进行匹配的工具类 * * @author liuxiaofeng * @date 2018/10/29 20:25 */
    public class Matching { 
    
        /** * 二分图的左边顶点数目，对应气缸的数目。 */
        private static int left = 0;
    
        /** * 二分图的右边顶点数目，对应活塞的数目。 */
        private static int right = 0;
    
    
        /** * 将气缸和活塞进行匹配，并返回匹配结果双列集合 * * @param cylinderList 气缸集合 * @param pistonList 活塞集合 * @return 气缸编号为key，活塞编号为value，最大匹配的双列集合 */
        public static Map<String, String> getMatching(List<Cylinder> cylinderList, List<Piston> pistonList) { 
            //1.初始化压缩气缸数目
            left = cylinderList.size();
            //2.初始化压缩活塞数目
            right = pistonList.size();
    
            //3.获取存储可连接关系的二位数组
            boolean[][] matchMap = getMatchMap(cylinderList, pistonList);
    
            //4.获取最大匹配数组。索引为活塞的角标，索引对应的值为气缸的角标
            int[] maxMatch = getMaxMatch(matchMap);
    
            //5.创建一个存储气缸编号和活塞编号的双列集合
            Map<String, String> matching = new ConcurrentHashMap<>(16);
    
            //6.遍历最大匹配数组，相当于遍历活塞
            for (int i = 0; i < maxMatch.length; i++) { 
                //7.获取气缸的角标
                int j = maxMatch[i];
    
                //8.判断气缸角标是否存在（该活塞是否匹配了气缸）
                if (j >= 0) { 
                    //9.获取气缸编号
                    String numberYQ = cylinderList.get(j).getNumberYQ();
                    //10.获取活塞编号
                    String numberYH = pistonList.get(i).getNumberYH();
    
                    //11.存入集合
                    matching.put(numberYQ, numberYH);
                }
            }
            //12.返回最大匹配集合
            return matching;
        }
    
    
        /** * 将气缸集合和活塞集合的可配对关系解析为二维数组 * * @param cylinderList 气缸对象集合 * @param pistonList 活塞对象集合 * @return 气缸和活塞可配对关系的二维数组 */
        private static boolean[][] getMatchMap(List<Cylinder> cylinderList, List<Piston> pistonList) { 
            //1.创建气缸和活塞可连接关系的二维数组
            boolean[][] matchMap = new boolean[left][right];
    
            //2.遍历气缸集合
            for (int i = 0; i < cylinderList.size(); i++) { 
                //3.获取气缸内径
                Double innerDiameter = cylinderList.get(i).getInnerDiameter();
    
                //4.遍历活塞集合
                for (int j = 0; j < pistonList.size(); j++) { 
                    //5.获取活塞对象
                    Piston piston = pistonList.get(j);
                    //6.获取活塞匹配气缸的内径下限
                    Double lowerInnerDiameter = piston.getLowerInnerDiameter();
                    //7.获取活塞匹配气缸的内径上限
                    Double upperInnerDiameter = piston.getUpperInnerDiameter();
    
                    //8.进行配对，并标记配对结果
                    matchMap[i][j] = lowerInnerDiameter <= innerDiameter && innerDiameter <= upperInnerDiameter;
                }
            }
            //9.返回结果二维数组
            return matchMap;
        }
    
    
        /** * 通过气缸和活塞之间的可连接关系，筛选出拥有最大匹配数的连接关系数组 * * @param matchMap 气缸和活塞可连接关系的二维表 * @return 索引为活塞角标，对应值为气缸角标的最大匹配关系数组 */
        private static int[] getMaxMatch(boolean[][] matchMap) { 
            //1.初始化最大匹配数组，将每个活塞匹配的气缸角标设置为-1（无连接）
            int[] linked = new int[right];
            for (int i = 0; i < right; i++) { 
                linked[i] = -1;
            }
    
            //2.遍历气缸，给气缸寻找连接
            for (int i = 0; i < left; i++) { 
                //2.1.初始化right部分顶点均未被访问（布尔值数组初始值为false）
                boolean[] used = new boolean[right];
                //2.2.从气缸顶点i出发寻找一条增广路径
                connection(matchMap, used, linked, i);
            }
            return linked;
        }
    
    
        /** * 给气缸连接一个活塞，连接成功返回true，没有可连接活塞或者可连接活塞已连接且不可挪动，则返回false * * @param matchMap 气缸和活塞可连接关系的二维表 * @param used 活塞顶点访问状态数组 * @param linked 索引为活塞角标，对应值为气缸角标的最大匹配关系数组 * @param start 正在寻找连接的气缸的角标 * @return 该气缸是否找到可与其配对的空闲活塞 */
        private static boolean connection(boolean[][] matchMap, boolean[] used, int[] linked, int start) { 
            //遍历活塞
            for (int i = 0; i < right; i++) { 
                //该活塞未被访问且与本次寻找连接的气缸是可连接的
                if (!used[i] && matchMap[start][i]) { 
                    //该活塞的访问状态改为已被访问
                    used[i] = true;
                    //该活塞未在结果数组中记录匹配的气缸，或者与其匹配的气缸能找到其他可匹配活塞
                    if (linked[i] == -1 || connection(matchMap, used, linked, linked[i])) { 
                        //将当前匹配成功的一组活塞和气缸记录到最大匹配关系数组
                        linked[i] = start;
                        return true;
                    }
                }
            }
            return false;
        }
    }

--------------------

## 4. 最终结果测试 ##

**测试类代码展示：**

/** * @author liuxiaofeng * @date 2018/10/29 19:56 */
    public class MatchingTest { 
    
        /** * 气缸对象集合 */
        private List<Cylinder> cylinderList = null;
    
        /** * 活塞对象集合 */
        private List<Piston> pistonList = null;
    
    
        /** * 自动加载对象的初始化方法 */
        @Before
        public void init() throws Exception { 
            //获取resource下表格文件的路径
            String excelPath = MatchingTest.class.getClassLoader().getResource("match.xlsx").getPath();
    
            //获取Excel表格对象
            Workbook workbook = ExcelReader.creatWorkbook(excelPath);
    
            //获取气缸对象
            cylinderList = ExcelReader.readCylinderBySheetId(workbook, 0);
    
            //获取活塞对象
            pistonList = ExcelReader.readPistonBySheetId(workbook, 1);
        }
    
    
        /** * 读取气缸数据的方法 */
        @Test
        public void testReadCylinders() { 
            cylinderList.forEach(System.out::println);
        }
    
    
        /** * 读取活塞数据的方法 */
        @Test
        public void testReadPistons() { 
            pistonList.forEach(System.out::println);
        }
    
    
        /** * 打印匹配结果的方法 */
        @Test
        public void testMaxMatching() { 
            //获取匹配结果集合
            Map<String, String> matching = Matching.getMatching(cylinderList, pistonList);
    
            //遍历结果集
            Set<Map.Entry<String, String>> entries = matching.entrySet();
            entries.forEach(s -> System.out.println("气缸编号：" + s.getKey() + " \t活塞编号：" + s.getValue()));
            System.out.println("最大配对数：" + matching.size());
        }
    
    }

**匹配结果：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NTg3OTk3_size_16_color_FFFFFF_t_70 1]

[20181102162107573.png]: /images/20220422/1034a944f2f8437e9cce8a2227e5ead7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NTg3OTk3_size_16_color_FFFFFF_t_70]: /images/20220422/b205f56f10244dcaad961d413f89327d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NTg3OTk3_size_16_color_FFFFFF_t_70 1]: /images/20220422/ef202ee6d8d94596a9c8d369867aa802.png