基于图的算法使用 pyhton 在网络上移动火车

Question

我正在寻找一种算法，它可以为我提供要执行的火车运动，以将火车定位在进行较少运动的好车站。

这是网络图
`

`# Matrice représentant les mouvements possibles entre les gares
M = [
  [0, 1, 0, 0, 0, 0, 0, 0],
  [1, 0, 1, 0, 0, 0, 0, 1],
  [0, 1, 0, 1, 0, 1, 1, 1],
  [0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 1, 0],
  [0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 1, 0, 0, 0],
  [0, 1, 1, 0, 0, 0, 0, 0]
]``

我有8个车站，我想定义当前的火车位置如下

# Positions actuelles des trains (index de la gare + 1, 0 signifie non présent) train_positions = [1, 4, 3, 0, 0, 0, 0, 0]

here train_position[i]=trainID and i=station, in the example, train3 is in station 3, station 4-8 are empty (no train) 

# Positions souhaitées des trains (index de la gare + 1, 0 signifie aucune préférence) train_wishes = [1, 0, 2, 3, 4, 0, 0, 0] 

train_wishes 是想要的位置，例如，train3 必须从车站 3 移动到车站 4。

知道如何解决这个问题吗？
我们可以认为站点之间的成本相同=1，因此从站点1移动到站点2是=1，从站点1到站点5是5，从站点3到站点6也是1。

作为第一步，知道要做的动作会很棒
第二次，我想考虑操作条件，这意味着我正在移动带有调车器的火车，它可以同时乘坐两列火车（调车器位于中间），我的目标是避免将调车器从铁轨

我尝试使用基本的bfs和djikstra算法，但我不知道如何正确设置问题

更新

我设法让 BFS 工作，所以步骤 1 没问题，这里是代码

    import networkx as nx
    import matplotlib.pyplot as plt
    from collections import deque
    
    # Définition de la fonction BFS avec mouvements enregistrés
    def bfs_with_moves(train_positions, train_wishes, M):
        initial_state = (tuple(train_positions), [])  # État initial : positions des trains et liste de mouvements
        visited = set()  # Pour suivre les états déjà explorés
        queue = deque([initial_state])  # File pour BFS
    
        while queue:
            current_positions, moves = queue.popleft()  # Prend le premier état de la file
            if current_positions == tuple(train_wishes):
                return moves  # Si l'état souhaité est atteint, renvoie la liste de mouvements
            
            if current_positions in visited:
                continue  # Ignore les états déjà visités
            visited.add(current_positions)
    
            for i in range(len(current_positions)):
                if current_positions[i] is None:
                    continue  # Ignore les gares vides
                for j in range(len(M[i])):
                    if M[i][j] == 1 and current_positions[j] is None:
                        new_positions = list(current_positions)  # Copie des positions actuelles pour modification
                        new_positions[j] = new_positions[i]  # Déplace le train de la gare i à j
                        new_positions[i] = None
                        new_moves = moves + [(i + 1, j + 1)]  # Enregistre le mouvement effectué (indices 1-based)
                        queue.append((tuple(new_positions), new_moves))  # Ajoute le nouvel état à la file
        
        return None  # Si aucune solution n'est trouvée
    
    # Matrice représentant les mouvements possibles entre les gares
    M = [
        [0, 1, 0, 0, 0, 0, 0, 0, 1],
        [1, 0, 1, 0, 0, 0, 0, 0, 0],
        [0, 1, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 1, 0, 1, 1, 0, 0, 0],
        [0, 0, 0, 1, 0, 0, 1, 0, 0],
        [0, 0, 0, 1, 0, 0, 0, 0, 0],
        [0, 0, 1, 0, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 1, 0, 0, 1],
        [1, 0, 0, 0, 0, 0, 0, 1, 0],
    ]
    
    # Noms des gares associés aux indices
    station_names = {
        1: "ITE",
        2: "VES1",
        3: "VES2",
        4: "VES3",
        5: "VED",
        6: "VC",
        7: "VD",
        8: "HALL",
        9: "SKID"
    }
    
    # Noms des trains associés aux indices
    train_names = {
        
        1: "RERNG T23",
        2: "ZEFIRO",
        3: "CDGX",
        4: "RERNG 5"
        # ... Ajoutez les autres noms de trains ici ...
    }
    
    # Positions actuelles des trains (None signifie gare vide, indice du train sinon)
    train_positions = [None, 1, None, 3, None, 4, None, 2,None]
    # Positions finales des trains (None signifie gare vide, indice du train sinon)
    train_positions_final = [None, 3, 2, None, 4, None, None, None, 1]
    
    # Appelle la fonction BFS pour trouver les mouvements nécessaires
    moves = bfs_with_moves(train_positions, train_positions_final, M)
    
    # Affiche les résultats
    if moves is not None:
        print("Movements to be made:")
        train_positions_copy = list(train_positions)  # Copie des positions actuelles pour modification
        for move in moves:
            source_train = train_positions_copy[move[0] - 1]
            dest_train = train_positions_copy[move[1] - 1]
            source_station = station_names[move[0]]
            dest_station = station_names[move[1]]
            print(f"Move train '{train_names[source_train]}' from station {source_station} to station {dest_station}")
            train_positions_copy[move[1] - 1] = source_train  # Met à jour les positions pour les prochaines étapes
            train_positions_copy[move[0] - 1] = None
    else:
        print("No solution found.")
    
    # Création d'un graphe pour le graphe initial
    G_initial = nx.Graph()
    
    # Ajout des noms de gares en tant qu'attributs
    for i, name in station_names.items():
        G_initial.add_node(i, name=name)
    
    # Ajout des arêtes en fonction de la matrice M
    for i in range(len(M)):
        for j in range(i+1, len(M[i])):
            if M[i][j] == 1:
                G_initial.add_edge(i+1, j+1)
    
    # Création d'un graphe pour le graphe final
    G_final = nx.Graph()
    
    # Ajout des noms de gares en tant qu'attributs
    for i, name in station_names.items():
        G_final.add_node(i, name=name)
    
    # Ajout des arêtes en fonction de la matrice M
    for i in range(len(M)):
        for j in range(i+1, len(M[i])):
            if M[i][j] == 1:
                G_final.add_edge(i+1, j+1)
    
    # Création de la figure avec deux sous-graphes
    plt.figure(figsize=(12, 6))
    
    # Calcul des couleurs des nœuds en fonction des positions des trains
    node_colors_initial = ["orange" if train_positions[i] is not None else "green" for i in range(len(train_positions))]
    node_colors_final = ["orange" if train_positions_final[i] is not None else "green" for i in range(len(train_positions_final))]
    
    # Utilise la grille de sous-graphes (1 ligne, 2 colonnes) pour afficher les deux graphes
    plt.subplot(1, 2, 1)
    pos_initial = nx.spring_layout(G_initial, seed=42)
    nx.draw(G_initial, pos_initial, labels=station_names, with_labels=True, node_size=1000, font_size=10, font_color="black", node_color=node_colors_initial)
    for i, train in enumerate(train_positions):
        if train is not None:
            plt.text(pos_initial[i+1][0], pos_initial[i+1][1] + 0.1, train_names[train], ha='center', fontsize=8, color="black")
    plt.title("Graphe de Gares (Initial)")
    
    plt.subplot(1, 2, 2)
    pos_final = nx.spring_layout(G_final, seed=42)
    nx.draw(G_final, pos_final, labels=station_names, with_labels=True, node_size=1000, font_size=10, font_color="black", node_color=node_colors_final)
    for i, train in enumerate(train_positions_final):
        if train is not None:
            plt.text(pos_final[i+1][0], pos_final[i+1][1] + 0.1, train_names[train], ha='center', fontsize=8, color="black")
    plt.title("Graphe de Gares (Final)")
    
    plt.tight_layout()
    plt.show()

现在我需要考虑 Locotractor，这意味着基本上我需要引入更多限制：

• 调车员可以同时移动2列火车
• 一旦完成第一次移动（调车员上轨），调车员只能移动可以通过空车站到达的列车。举个例子，我们在一条直线上，车站编号从 1 到 5，我们有一列火车在 2+3+4 上，如果我们移动 2 号火车，我们将无法移动 4 号火车，因为 3 号火车在中间。

希望我说清楚了，等待反馈

Answer 1

我认为分流问题可以使用动态规划算法来解决。请参阅 https://en.wikipedia.org/wiki/Dynamic_programming 特别是“计算机科学”部分。

子问题是选择前往目的地的火车的最佳下一步运动。这可以在子图中使用 BFS 方法（你说你已经解决了）来完成，其中代表静止列车占用的车站的顶点已被删除。