如何使用 dijkstra 找到所有最佳对齐方式

Question

我目前正在尝试在给定跟踪模型和 Petri 网模型的情况下找到与 dijkstra 算法的所有最佳对齐。现在我正在使用 pm4py 库，确切地说是 pm4py.algo.conformance.alignments.petri_net.variants.dijkstra_less_memory.apply ，它可以帮助我找到一种最佳对齐方式。有没有办法获得所有最佳对齐而不是第一个？

我创建了一种方法，可以在不使用该方法的情况下找到所有最佳对齐方式，并且我发现了两个最佳对齐方式

用我的方法输出：

1. [('T0', 'T0'), ('T1', 'T1'), ('T2', 'T2'), ('T4', 'T4'), ('>>', 'T5 '), ('>>', 'T7'), ('T6', 'T6'), ('T8', 'T8')]
2. [('T0', 'T0'), ('T1', 'T1'), ('T2', 'T2'), ('T4', 'T4'), ('>>', 'T5 '), ('T6', 'T6'), ('>>', 'T7'), ('T8', 'T8')]

使用 dijkstra_less_memory.apply 输出：

1. [('T0', 'T0'), ('T1', 'T1'), ('T2', 'T2'), ('T4', 'T4'), ('>>', 'T5 '), ('T6', 'T6'), ('>>', 'T7'), ('T8', 'T8')]

Answer 1

我认为“pm4py.algo.conformance.alignments.petri_net.variants.dijkstra_less_memory.apply”函数集成了Dijkstra算法，该算法旨在识别迹线和Petri网模型之间的单个最佳对齐，但这并不意味着直接提供每一个理想的对准。 如果您必须使用 PM4Py 库并且需要能够直接从库中提取所有最佳比对，您可能需要研究替代方法或扩展当前方法才能启用此功能。作为替代方案，您可以通过后处理 Dijkstra 算法结果来发现并返回与最佳对齐成本相同的所有对齐。