算法通过向图比较引导路径的相似性

Question

我有带有两个向路径的有向图。

我想要一个算法来确定两个路径之间的相似性。

This post提到使用Levenshtein distance来确定近似相似。我也意识到Hamming distance使用了一个类似的指标。

我的问题是：

你是如何处理在两个路径平行于对方的情况。也就是说，如果这两条路径没有类似的节点，但它们会被认为是“相似的”，因为它们的路径沿着相互接近的相同方向传播。

感谢

Answer 1

简单的回答是，这是一个很难的问题，并依靠很多对你的什么“相似”是指在图形定义。在大多数图表中，您可以平面方式重新排列两条不相交路径的节点，以便看似“平行”运行。

开始寻找更高级的相似性度量标准的好地方是考虑图的邻接矩阵，并且看看各种各样的matrix similarity算法。

编辑：限制的问题，以欧氏图表

限制域欧几里德图形时，因为这是像GIS，机器学习应用到机器人领域适用的话题有大量活跃的研究这个问题，在社交网络/网络等人工网络上进行协作过滤。看看google scholar上的文章。