Поиск кратчайшего пути между N наборами в ориентированном невзвешенном графе

Question

Я хочу найти алгоритм для решения следующей проблемы: учитывая ориентированный граф G с начальной точкой s и N наборами узлов, мне нужно найти путь, который начинается в начальном узле и затем идет по крайней мере к одному узлу из каждый набор. Не все узлы входят в наборы - только некоторые из них. Нет узлов более чем в одном наборе.

Например:

1. начальная точка: [n1]
2. Первый набор: [n5, n6, n8, n9]
3. Второй набор: [n2, n10]
4. Третий набор: [n4, n7]
5. Четвертый набор: [n3]
6. Другие узлы: [m1..m7]

Отображение ребер графа:

In this case a shortest path will be:

• [n1,m3,m4,m5,n3,m6,n2,m7,n9]
• [n1,m1,n7,m5,n3,m6,n2,m7,n9]

This problem is similar to the generalization of the Traveling salesman problem ( wikipedia ), но в этом случае график является направленным и невзвешенный. Кроме того, у нас есть известная начальная точка, у нас есть больше, чем просто узлы в наборах, и мы можем пройти по одному узлу более одного раза.

Я попытался начать с ленивого быстрого способа поиска ближайшего узел от начала до всех узлов во всех наборах с помощью Дейкстры, а затем удалив набор из расчета и продолжите поиск следующего ближайшего узла из всех наборов с этой точки.

Это легко заметить что этот путь не дает кратчайшего пути, но настоящая проблема в том, что иногда он заходит в тупик и возвращает «нет пути», даже если путь есть.

Наивный способ, который я вижу это может быть использовано для создания функции для вычисления для каждой конкретной c перестановки наборов и использования алгоритма, подобного предложенному здесь , для решения близкой, но более простой задачи.

Это будет взять O (| N |! * 2 ^ (количество всех узлов во всех N наборах))

Добавление кода ленивого способа (извините за беспорядок).

    from Queue import Queue
    from my_utils import RGBtoHex
    from igraph import *
    from random import choice
    
    
    class path_info:
        def __init__(self, way, length_of_way, satisfied_goal):
            self.way = way
            self.length_of_way = length_of_way
            self.satisfied_goal = satisfied_goal
    
    
    class graph_actions():
        # Goal point has a "start" node and all other goal points are saved in a dictionary
        def __init__(self, graph, goal_points):
            self.graph = graph
            self.goal_points = goal_points
            self.best_path = list()
    
        def calculate_best_path(self):
            self.best_path = list()
            queued_best_path = scatter(self.graph, self.goal_points)
    
            while not queued_best_path.empty():
                self.best_path.append(queued_best_path.get())
    
            return self.best_path
    
    
    def scatter(graph, goal_points):
        best_path = Queue()
        starting_point = goal_points["start"]
        del goal_points["start"]
    
        paths_dict = dict()
        return find_best_way(best_path, goal_points, graph, paths_dict, starting_point)
    
    
    def find_best_way(best_path, goal_points, graph, paths_dict, starting_point):
        last = -1
        while len(goal_points) > 0:
            vertex_color = known_colors[choice(known_colors.keys())]
            for vertex in goal_points.keys():
                # Find shortest paths from vertex
                # Color vertex
                graph.vs.find(str(vertex).encode('ascii', 'replace'))["Fill Color"] = RGBtoHex(vertex_color)
                # Find shortest path if exist with igraph function
                way = graph.get_shortest_paths(starting_point, vertex)
                if len(way[0]) != 0:
                    if (last != -1):
                        # Taking out the first node that is the end of the last route taken
                        way[0].pop(0)
                    paths_dict[vertex] = path_info(way, len(way[0]), goal_points[vertex])
    
            # Find the closest node
            stage = min(paths_dict, key=lambda x: paths_dict[x].length_of_way)
    
            # Transfer from list to queue
            for step in paths_dict[stage].way[0]:
                best_path.put(step)
                last = step
    
            # Delete the other nodes with of the same group from the goal list
            for key, value in goal_points.items():
                if paths_dict.has_key(stage) and value == paths_dict[stage].satisfied_goal:
                    del goal_points[key]
                    if key != stage:
                        del paths_dict[key]
            del paths_dict[stage]
    
            # Saving the last node of this route
            starting_point = last
        graph.save("states_graph_color.graphml", "graphml")
        return best_path

Есть ли кстати что лучше наивного? Если нет, могу ли я использовать для этого способ heuristi c? Мне также интересно, есть ли у igraph трюк для этого более чистым способом.

Даже если возможен только наивный способ, я не уверен, как его реализовать.