我正在开展一个项目，为实体关系图创建自动评估系统。现在我想出了一个抽象的匹配算法。
--首先对于图中的所有标签，它们只能从一组给定的关键字中选择，所以这不是问题。
-- 其次，对于标签与答案键中的标签匹配的每个元素(实体/关系)，可以创建本地度量。此指标中可能有一些标准，例如:
--每个标准都可以分配一些权重并进行评估。
以这种方式这样做似乎合理吗？
此外，我还被建议从 方面查看问题。图同构反而。因为在我的情况下标签必须匹配所以问题比这简单一点。我还需要一个部分匹配器并在匹配器之上构建一个评分系统。
我知道我说得太抽象了，但我需要一些指示，比如从哪里开始这个替代观点。
谢谢!!
最佳答案
确保您的解决方案围绕图同构。实际上，您想查看两个图(实际上是 ERD)是否同构。首先请记住，您正面临一个非常棘手的问题:
“它是属于 NP 的极少数问题之一，既不能在多项式时间内解决，也不能解决 NP 完全问题:它是 Garey & Johnson (1979) 列出的仅有的 12 个此类问题之一，也是仅有的两个问题之一其复杂性仍 Unresolved 列表。”(1)
当你在一个项目上工作时，运行时间对你来说是一个很大的问题，所以我建议你实现一个近似算法并特别阅读这篇论文:
V. Arvind 等人的近似图同构。
http://eccc.hpi-web.de/report/2012/078/download [+如果存在，请考虑版权。]
(1):http://en.wikipedia.org/wiki/Graph_isomorphism_problem
关于database-design - ER(实体关系)图的答案评估，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21737373/