algorithm - 在强制唯一节点属性的同时进行寻路——我应该使用哪种算法？

Question

2011 年 12 月 28 日更新:这是一篇博文，对我试图解决的问题、我的工作以及我当前的解决方案进行了较为清晰的描述:Watching Every MLB Team Play A Game

---

我正在尝试解决一种奇怪的寻路挑战。我有一个非循环有向图，每条边都有一个距离值。我想找到最短路径。简单吧？嗯，有几个原因我不能只使用 Dijkstra 或 A*。

1. 我根本不关心我的路径的起始节点是什么，也不是结束节点。我只需要一条恰好包含 10 个节点的路径。但是:
2. 每个节点都有一个属性，比方说它是颜色。每个节点都有 20 种不同的可能颜色之一。
3. 我试图找到的路径是恰好有 10 个节点的最短路径，其中每个节点都是不同的颜色。我不希望路径中的任何节点与任何其他节点具有相同的颜色。
4. 如果能够强制我的路径为其中一个属性设置一个值(例如，“至少一个节点必须是蓝色的”)，那会很好，但这并不是真正必要的。

这是一个简化的例子。我的完整数据集实际上具有每个节点的三个不同属性，这些属性必须都是唯一的，并且我有 2k+ 个节点，每个节点平均有 35 个出边。由于获得完美的“最短路径”可能需要指数时间或阶乘时间，因此穷举搜索确实不是一种选择。我真正要寻找的是满足 #3 下标准的“好路径”的一些近似值。

谁能指出我可能会使用(甚至经过修改)的算法？

---

我的完整数据集的一些统计数据:

• 节点总数:2430
• 总边数:86524
• 没有传入边的节点:19
• 没有出边的节点:32
• 最多出边:42
• 每个节点的平均边数:35.6(每个方向)
• 由于数据的性质，我知道该图是无环的
• 在完整数据集中，我正在寻找长度为 15 而不是 10 的路径

Answer 1

当问题实际上包含大部分答案时就是这种情况。

从所有根节点开始进行广度优先搜索。当并行搜索路径的数量超过某个限制时，丢弃最长的路径。可以对路径长度进行加权:最后的边可能具有权重 10，边在 9 跳之前通过 - 权重 1。也可以为具有首选属性的所有路径或通过弱连接节点的路径分配较小的权重。将最后 10 个节点存储在哈希表的路径中以避免重复。并在某处保留最后 9 条边长的最小总和以及最短路径。