Essayer de trouver tous les chemins possibles d'un sommet de départ à un sommet de fin. c'est ce que j'ai jusqu'à présent.

def all_paths(adj_list, source, destination):
paths = []
for neighbour,_ in adj_list[source]:
    path = [source,neighbour]
    state = ['U'] * len(adj_list)
    state[neighbour] = 'D'
    path = finder(adj_list, neighbour, state, path, destination)
    paths.append(path)
return paths

def finder(adj_list, current, state, path, end):
    for neighbour,_ in adj_list[current]:
        if neighbour == end:
            path.append(neighbour)
            return path
        if state[neighbour] == 'U':
            state[neighbour] = 'D'
            path.append(finder(adj_list, neighbour, state, path, end))
            return path

Le tableau d'état est de s'assurer qu'aucun sommet n'est visité deux fois (U n'est pas découvert et D est découvert.) Une adj_list est une liste d'adjacence d'un graphique, donc à l'index [i] de la liste, il a une liste de tous les sommets qui sont reliés à i par un bord (les Nones sont le poids dudit bord)

L'entrée est

adj_list = [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]


print(sorted(all_paths(adj_list, 0, 2)))

La sortie attendue est

[[0, 1, 2], [0, 2]]

Et ma sortie est

[[0, 1, 2, [...]], [0, 2, 2, [...], [...]]]

Vous ne savez pas comment obtenir ces points et les 2 répétés dans le deuxième chemin?

0
Martin Lopez 19 mars 2019 à 02:44

2 réponses

Meilleure réponse

Logique très similaire à votre code mais nettoyée, épuisant le fait que Python peut vérifier si un élément est dans une liste, donc n'utilisez pas un tableau séparé en «U» ou «D».

ajs =  [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]

def paths(node, finish):
    routes = []

    def step(node, path):
        for nb,_ in ajs[node]:

            if nb == finish:
                routes.append( path + [node, nb] )

            elif nb not in path:
                step(nb, path + [node])

    step(node, [])
    return routes

print paths(0,2)
1
Mike Robins 19 mars 2019 à 03:39

Voici une variante de votre code qui obtient la réponse souhaitée. Cela dit, c'est une façon déroutante de résoudre le problème. Il me semble que l'algorithme est réparti sur deux fonctions, alors qu'il devrait être résoluble avec une seule fonction récursive.

def main():
    adj_list = [
        [(1, None), (2, None)],
        [(0, None), (2, None)],
        [(1, None), (0, None)],
    ]
    paths = sorted(all_paths(adj_list, 0, 2))
    print(paths)

def all_paths(adj_list, source, destination):
    paths = []
    for neighbour, _ in adj_list[source]:
        pth = [source, neighbour]
        if neighbour == destination:
            paths.append(pth)
        else:
            node = finder(
                adj_list,
                neighbour,
                ['U'] * len(adj_list),
                pth,
                destination,
            )
            paths.append(pth + [node])
    return paths

def finder(adj_list, current, state, pth, end):
    for neighbour, _ in adj_list[current]:
        if neighbour == end:
            state[neighbour] = 'D'
            return neighbour
        elif state[neighbour] == 'U':
            state[neighbour] = 'D'
            return finder(adj_list, neighbour, state, pth, end)

main()

Par exemple, voici une implémentation alternative:

def main():
    # An adjacency matrix for this example:
    #
    #    0 - 1
    #     \ /
    #      2
    #
    matrix = [
        [(1, None), (2, None)],
        [(0, None), (2, None)],
        [(1, None), (0, None)],
    ]
    # Print all paths from 0 to 2.
    paths = get_paths(matrix, 0, 2)
    for p in paths:
        print(p)

def get_paths(matrix, src, dst, seen = None):
    # Setup:
    # - Initialize return value: paths.
    # - Get an independent seen set.
    # - Add the source node to the set.
    paths = []
    seen = set(seen or [])
    seen.add(src)
    # Explore all non-seen neighbors.
    for nb, _ in matrix[src]:
        if nb not in seen:
            seen.add(nb)
            # Find the subpaths from NB to DST.
            if nb == dst:
                subpaths = [[nb]]
            else:
                subpaths = get_paths(matrix, nb, dst, seen)
            # Glue [SRC] to the those subpaths and add everything to paths.
            for sp in subpaths:
                paths.append([src] + sp)
    return paths

main()
0
FMc 19 mars 2019 à 16:36