Max Propagation and Relaxation-Style DP — தளர்வு பரவல் DP

தளர்வு — விளிம்பு வழி மதிப்பு பரவல்.

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

அட்டவணை; கணினி பார்வை.

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

மீண்டும் தளர்வு.

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

def relax_edges(n: int, edges: list[tuple[int, int, int]]) -> list[int]:
    dist = [-(10**18)] * n
    dist[0] = 0
    for _ in range(n - 1):
        ch = False
        for u, v, w in edges:
            if dist[u] + w > dist[v]:
                dist[v] = dist[u] + w
                ch = True
        if not ch:
            break
    return dist


print(relax_edges(3, [(0, 1, 2), (1, 2, 3), (0, 2, 1)]))

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

• சுழற்சி.
• topo விட்டு redundant.

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

• மாறாதபோது நிறுத்தம்.