Bagaimana cara melacak jalur dalam Pencarian Luas-Pertama?

104

Bagaimana Anda melacak jalur Pencarian Breadth-First, seperti dalam contoh berikut:

Jika mencari kunci 11, kembalikan daftar terpendek yang menghubungkan 1 hingga 11.

[1, 4, 7, 11]
Christopher Markieta
sumber
6
Itu sebenarnya adalah tugas lama yang saya bantu teman beberapa bulan lalu, berdasarkan Hukum Kevin Bacon. Solusi terakhir saya sangat ceroboh, pada dasarnya saya melakukan pencarian Breadth-first lainnya untuk "mundur" dan mundur. Saya tidak ingin menemukan solusi yang lebih baik.
Christopher Markieta
21
Luar biasa. Saya mempertimbangkan untuk meninjau kembali masalah lama dalam upaya untuk menemukan jawaban yang lebih baik menjadi sifat yang mengagumkan dalam diri seorang insinyur. Saya berharap Anda berhasil dalam studi dan karier Anda.
Peter Rowell
1
Terima kasih atas pujiannya, saya hanya percaya jika saya tidak mempelajarinya sekarang, saya akan menghadapi masalah yang sama lagi.
Christopher Markieta

Jawaban:

194

Anda harus melihat http://en.wikipedia.org/wiki/Breadth-first_search terlebih dahulu.


Di bawah ini adalah implementasi cepat, di mana saya menggunakan daftar daftar untuk mewakili antrian jalur.

# graph is in adjacent list representation
graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, start, end):
    # maintain a queue of paths
    queue = []
    # push the first path into the queue
    queue.append([start])
    while queue:
        # get the first path from the queue
        path = queue.pop(0)
        # get the last node from the path
        node = path[-1]
        # path found
        if node == end:
            return path
        # enumerate all adjacent nodes, construct a new path and push it into the queue
        for adjacent in graph.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

print bfs(graph, '1', '11')

Pendekatan lain akan mempertahankan pemetaan dari setiap node ke induknya, dan saat memeriksa node yang berdekatan, catat induknya. Setelah pencarian selesai, cukup lacak balik sesuai pemetaan induk.

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def bfs(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            if node not in queue :
                parent[adjacent] = node # <<<<< record its parent 
                queue.append(adjacent)

print bfs(graph, '1', '11')

Kode di atas didasarkan pada asumsi bahwa tidak ada siklus.

qiao
sumber
2
Ini luar biasa! Proses berpikir saya membuat saya percaya dalam membuat beberapa jenis tabel atau matriks, saya belum belajar tentang grafik. Terima kasih.
Christopher Markieta
Saya juga mencoba menggunakan pendekatan penelusuran belakang meskipun ini tampak jauh lebih bersih. Apakah mungkin membuat grafik jika Anda hanya mengetahui awal dan akhir tetapi tidak ada node di antaranya? Atau bahkan pendekatan lain selain grafik?
Christopher Markieta
@ChristopherM Saya gagal memahami pertanyaan Anda :(
qiao
1
Apakah mungkin untuk mengadaptasi algoritma pertama sehingga itu akan mengembalikan semua jalur dari 1 hingga 11 (dengan asumsi ada lebih dari satu)?
Maria Ines Parnisari
1
Direkomendasikan untuk menggunakan collections.deque daripada menggunakan list. kompleksitas list.pop (0) adalah O (n) sementara deque.popleft () adalah O (1)
Omar_0x80
23

Saya sangat menyukai jawaban pertama qiao! Satu-satunya hal yang hilang di sini adalah menandai simpul sebagai telah dikunjungi.

Mengapa kita perlu melakukannya?
Mari kita bayangkan bahwa ada node lain nomor 13 yang terhubung dari node 11. Sekarang tujuan kita adalah menemukan node 13.
Setelah sedikit dijalankan, antrian akan terlihat seperti ini:

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]]

Perhatikan bahwa ada DUA jalur dengan simpul nomor 10 di akhir.
Artinya jalur dari node nomor 10 akan diperiksa dua kali. Dalam hal ini tidak terlihat terlalu buruk karena node nomor 10 tidak memiliki anak .. Tetapi bisa sangat buruk (bahkan di sini kita akan memeriksa node itu dua kali tanpa alasan ..)
Node nomor 13 tidak ada jalur tersebut sehingga program tidak akan kembali sebelum mencapai jalur kedua dengan node nomor 10 di akhir .. Dan kami akan memeriksanya kembali ..

Yang hilang hanyalah satu set untuk menandai node yang dikunjungi dan tidak untuk memeriksanya lagi ..
Ini adalah kode qiao setelah modifikasi:

graph = {
    1: [2, 3, 4],
    2: [5, 6],
    3: [10],
    4: [7, 8],
    5: [9, 10],
    7: [11, 12],
    11: [13]
}


def bfs(graph_to_search, start, end):
    queue = [[start]]
    visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

Output dari program ini adalah:

[1, 4, 7, 11, 13]

Tanpa pemeriksaan ulang yang tidak perlu ..

Atau Kazaz
sumber
6
Hal ini mungkin berguna untuk digunakan collections.dequeuntuk queuesebagai list.pop (0) dikenakan O(n)gerakan memori. Juga, demi anak cucu, jika Anda ingin melakukan DFS cukup setel path = queue.pop()dalam hal ini variabel queuebenar-benar bertindak seperti a stack.
Sudhi
11

Kode yang sangat mudah. Anda terus menambahkan jalur setiap kali Anda menemukan sebuah node.

graph = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))
SeasonalShot
sumber
2
Saya menemukan kode Anda sangat mudah dibaca, dibandingkan dengan jawaban lain. Terima kasih banyak!
Mitko Rusev
8

Saya pikir saya akan mencoba kode ini untuk bersenang-senang:

graph = {
        '1': ['2', '3', '4'],
        '2': ['5', '6'],
        '5': ['9', '10'],
        '4': ['7', '8'],
        '7': ['11', '12']
        }

def bfs(graph, forefront, end):
    # assumes no cycles

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]]

    for node,path in next_forefront:
        if node==end:
            return path
    else:
        return bfs(graph,next_forefront,end)

print bfs(graph,[('1','1')],'11')

# >>>
# 1, 4, 7, 11

Jika Anda menginginkan siklus, Anda dapat menambahkan ini:

for i, j in for_front: # allow cycles, add this code
    if i in graph:
        del graph[i]
robert king
sumber
setelah Anda membangun next_for_front. Sebuah pertanyaan lanjutan, bagaimana jika grafik berisi loop? Misalnya jika node 1 memiliki edge yang menghubungkan kembali ke dirinya sendiri? Bagaimana jika grafik memiliki banyak sisi di antara dua node?
robert king
1

Saya suka jawaban pertama @Qiao dan penambahan @ Or. Demi sedikit pemrosesan, saya ingin menambahkan jawaban Or.

Dalam jawaban @ Or melacak node yang dikunjungi sangat bagus. Kami juga dapat mengizinkan program untuk keluar lebih cepat dari saat ini. Di beberapa titik di loop for, current_neighbourharus menjadi end, dan begitu itu terjadi jalur terpendek ditemukan dan program dapat kembali.

Saya akan memodifikasi metode sebagai berikut, perhatikan loop for

graph = {
1: [2, 3, 4],
2: [5, 6],
3: [10],
4: [7, 8],
5: [9, 10],
7: [11, 12],
11: [13]
}


    def bfs(graph_to_search, start, end):
        queue = [[start]]
        visited = set()

    while queue:
        # Gets the first path in the queue
        path = queue.pop(0)

        # Gets the last node in the path
        vertex = path[-1]

        # Checks if we got to the end
        if vertex == end:
            return path
        # We check if the current node is already in the visited nodes set in order not to recheck it
        elif vertex not in visited:
            # enumerate all adjacent nodes, construct a new path and push it into the queue
            for current_neighbour in graph_to_search.get(vertex, []):
                new_path = list(path)
                new_path.append(current_neighbour)
                queue.append(new_path)

                #No need to visit other neighbour. Return at once
                if current_neighbour == end
                    return new_path;

            # Mark the vertex as visited
            visited.add(vertex)


print bfs(graph, 1, 13)

Output dan yang lainnya akan sama. Namun, kode akan membutuhkan waktu lebih sedikit untuk diproses. Ini sangat berguna pada grafik yang lebih besar. Saya harap ini membantu seseorang di masa depan.

Darie Dorlus
sumber