三维匹配算法

三维匹配算法（3d-matching algorithm），理学-计算机科学技术-计算机科学理论-算法-组合算法，三维匹配算法是求解三维匹配问题的算法。三维匹配是三部超图中一组独立（没有公共顶点）超边，三维匹配是二部图匹配（相当于二维匹配）的推广。三维匹配问题求的是最大三维匹配（指边数最多或总权值最大）。定义三维匹配(3d-matching)是一个NP完全问题（见NP完全性）。假设存在3个固定符号集A1、A2、A3,使得任何两个符号集之间都不存在公共符号。对于三元组中所有元素的集合S，S中的一个匹配M是S的一个子集，使得M中的任意两个三元组没有公共元素。三维匹配问题要求寻找S中最大的匹配。