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

Question

更新2011-12-28:这是一篇博文,对我试图解决的问题,我的工作以及我目前的解决方案的描述不那么模糊:观看每个MLB团队玩游戏

---

我正试图解决一种奇怪的寻路挑战.我有一个非循环方向图,每个边都有一个距离值.我想找到一条最短路径.简单吧？好吧,有几个原因我不能只使用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 条边长的最小总和以及最短路径保留在某处。