State-Space Search as Shortest-Path DP — நிலை கிராஃப் தேடல்

BFS = DP — நிலை கிராஃப்.

உண்மை உலகில் இது ஏன் முக்கியம்?

புதிர்; சொல் ஏணி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

deque+visited.

Pythonில் முயற்சி செய்வோம்

from collections import deque


def min_steps_to_target(start: int, target: int) -> int:
    q = deque([(start, 0)])
    seen = {start}
    while q:
        x, d = q.popleft()
        if x == target:
            return d
        for y in (x + 1, x * 2):
            if 0 <= y <= 2 * target and y not in seen:
                seen.add(y)
                q.append((y, d + 1))
    return -1


print(min_steps_to_target(1, 10))

அடிக்கடி நேரும் தவறுகள்

• மோசமான மீண்டும்.
• பிரிவு.

முக்கியச் சுருக்கக் குறிப்புகள்

• இரு திசை BFS.