Biasanya ketika masalah seperti ini muncul, jawabannya adalah semacam infinite loop. Tetapi saya mengalami kesulitan mencari tahu di mana itu bisa diperkenalkan dalam kode saya.

Katakanlah kita berurusan dengan papan catur 8x8 standar dan saya ingin menemukan jalur paling efisien dari satu kotak ke kotak lainnya, katakanlah dari merah ke hijau. Solusinya adalah 3 gerakan.

enter image description here

def calculate_dest(curr, path):
    return (curr[0] + path[0], curr[1] + path[1])

def curr_is_valid(curr):
    return 0 <= curr[0] <= 7 and 0 <= curr[1] <= 7

def helper(dest, soFar):
    # if len(soFar) > 4:
    #     return 63
    if not curr_is_valid(soFar[-1]):
        return 63
    elif soFar[-1] in soFar[:-1]:
        return 63
    elif soFar[-1] == dest:
        return len(soFar) - 1
    else:
        return min(helper(dest, soFar + [calculate_dest(soFar[-1], p)]) for p in [(2, 1),
                                                                                  (2, -1),
                                                                                  (-2, 1),
                                                                                  (-2, -1),
                                                                                  (1, 2),
                                                                                  (1, -2),
                                                                                  (-1, -2),
                                                                                  (-1, 2)])

dest: titik tujuan direpresentasikan sebagai tupel (yaitu (0, 1))

soFar: catatan semua titik yang dilalui, direpresentasikan sebagai daftar tupel (yaitu [(0, 1), (1, 3)])

Ketika saya menjalankan kode di atas dengan komentar tidak dikomentari, helper((0, 1), [(0, 0)]) mengembalikan 3 seperti yang saya harapkan dalam 2 detik. Tidak bagus, tetapi ketika saya memasukkan komentar kembali karena fungsinya seharusnya berfungsi untuk sejumlah gerakan di sekitar papan, itu terus berjalan, pada dasarnya selamanya (saya mencoba menunggu beberapa menit tetapi pada saat itu Anda tahu ada sesuatu yang salah) .

Saya cukup yakin kasus dasar soFar[-1] in soFar[:-1] seharusnya menangani jalur yang mulai menyilang ulang, yang tentunya kemudian akan memperkenalkan infinite loop, jadi saya tidak yakin, mengapa fungsi berjalan ke infinite-ish loop ?

Mungkin juga cara saya mendesain fungsi saya pada dasarnya tidak efisien. Pemikiran saya adalah bahwa rekursi akan diperlukan dalam kasus ini.

0
notacorn 5 Juli 2020, 00:19

1 menjawab

Jawaban Terbaik

Anda ingin melakukan BFS karena dijamin akan mengembalikan jalur terpendek.

Berikut kodenya:

def is_valid(curr):
    return 0 <= curr[0] <= 7 and 0 <= curr[1] <= 7

def get_neighbors(cur):
    for offset in [(2, 1),
                    (2, -1),
                    (-2, 1),
                    (-2, -1),
                    (1, 2),
                    (1, -2),
                    (-1, -2),
                    (-1, 2)]:
        nxt = (cur[0] + offset[0], cur[1] + offset[1])
        if is_valid(nxt):
            yield nxt

def helper(start, dest):
    visited = set()
    q = [(start, 0)]
    while q:
        front, distance = q.pop(0)
        visited.add(front)
        if front == dest:
            return distance
        for neighbor in get_neighbors(front):
            if neighbor not in visited:
                q.append((neighbor, distance + 1))
print(helper((0, 0), (0, 1)))

Keluaran:

3
3
Balaji Ambresh 4 Juli 2020, 21:41