Dijkstra无重复组变体

Question

我试图写一个基于Dijkstra算法的优化过程来找到最优路径，但是稍微有点变化，在找到最优路径时不允许从同一组/族中选择项目。在

强力遍历所有的边来找到解决方案是np难的，这就是为什么我尝试（希望）使用Dijkstra的算法，但是我正在努力添加无重复组逻辑。在

把它想象成一个旅行推销员的问题，但我想从新的你到洛杉矶，并且有一个有趣的路线（从不访问同一组的两个相似的城市），并尽量减少我的燃料成本。大约有15天和40个城市，但为了定义我的计划，我把它缩减到4个城市和3天。在

有效路径不必访问每个组，它们只是不能访问同一组中的两个城市。{XL，L，S}是一个有效的解决方案，但是{XL，L，XL}无效，因为它访问了XL组两次。所有有效的解决方案都将是相同的长度（15天或边缘），但可以使用任何组的组合（不包括重复组），并且不必全部使用（自15天起，而是40个不同的城市组）。在

下面是我放在一起的一张图片来说明一个有效的和无效的路由：（FYI-groups是矩阵中的水平行）

**Day 1**
G1->G2 @ $10
G3->G4 @ $30
etc...
**Day 2**
G1->G3 @ $50
G2->G4 @ $10
etc...
**Day 3**
G1->G4 @ $30
G2->G3 @ $50
etc...

最佳路径是G1->；G2->；G3，但是标准Dijkstra解决方案返回G1-

我在网上找到并调整了这个示例代码，并用以下语法命名节点，这样我就可以通过切片第三个字符来快速检查它们属于哪一天&组：D[day#][group#]。在

^{pr2}$