مسیر بحرانی (شبکه‌ی AOE)

برنامه‌نویسی پویا
بازگشتی

در شبکه‌ی فعالیت‌ها، زودترین و دیرترین زمان هر رویداد را حساب می‌کند و فعالیت‌هایی را پیدا می‌کند که هیچ تأخیری نمی‌پذیرند.

در شبکه‌ی AOE (فعالیت روی یال) هر یال یک فعالیت با مدت‌زمان است و هر گره یک رویداد («همه‌ی فعالیت‌های ورودی تمام شده‌اند»). سؤال‌ها:

ادامه‌ی توضیح ↓

زمان: O(V + E)
حافظه: O(V)
هوروویتز–ساهنی، فصل ۶
CLRS، بخش ۲۲.۲

ورودی:

V=9 · E=11 · src=0خروجی PDF

نه رویداد و یازده فعالیت؛ طول پروژه ۱۸ است و دو مسیر بحرانی از 0 به 8 هست.

def critical_path(graph, src):
# The project starts at time 0; src is ignored.
seen = set()
order = []
for s in graph:
if s not in seen:
topo(graph, s, seen, order)
order.reverse()
early = {v: 0 for v in graph}
for u in order:
for v, w in graph[u]:
if early[u] + w > early[v]:
early[v] = early[u] + w
finish = max(early.values())
late = {v: finish for v in graph}
for u in reversed(order):
for v, w in graph[u]:
if late[v] - w < late[u]:
late[u] = late[v] - w
critical = []
for u in graph:
for v, w in graph[u]:
if early[u] + w == late[v]:
critical.append((u, v, w))
return finish, critical
def topo(graph, u, seen, order):
seen.add(u)
for v, _ in graph[u]:
if v not in seen:
topo(graph, v, seen, order)
order.append(u)

ناوردا: early[v] زودترین زمانی است که همه‌ی فعالیت‌های منتهی به v تمام شده‌اند و late[v] دیرترین زمانی است که v می‌تواند رخ دهد بی‌آنکه پروژه دیر شود.

شروع اجرا

گره‌ی جاری (u)
درخت کوتاه‌ترین مسیر تا اینجا
یالِ در حال بررسی

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

src'0'

نارنجی = در همین گام عوض شد

graph dict

'0': [('1', 6), ('2', 4), ('3', 5)]
'1': [('4', 1)]
'2': [('4', 1)]
'3': [('5', 2)]
'4': [('6', 9), ('7', 7)]
'5': [('7', 4)]
'6': [('8', 2)]
'7': [('8', 4)]
'8': []

Call stack

critical_path()خط 1

گام ۱ از ۲۴۲

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

forward
backward
ورودی فعلی (n=9)

نمایش به شکل جدول

n	forward	backward
4	5.2	5.2
8	13.8	13.8
12	20.8	20.8
16	28	28
20	35.4	35.4
24	37.2	37.2
28	47.2	47.2

توضیح

ایده

پروژه حداقل چقدر طول می‌کشد؟
کدام فعالیت‌ها بحرانی‌اند، یعنی هر تأخیرشان کل پروژه را عقب می‌اندازد؟

دو گذر

رو به جلو (به ترتیب توپولوژیک): early[v] = max(early[u] + w) روی یال‌های ورودی. بزرگ‌ترین early طول پروژه است. این همان طولانی‌ترین مسیر است.
رو به عقب (به ترتیب برعکس): late[u] = min(late[v] − w) روی یال‌های خروجی.

فعالیت u → v با مدت w اگر early[u] + w = late[v] باشد زمان شناوری ندارد و بحرانی است. مسیرهای بحرانی از یال‌های بحرانی ساخته می‌شوند.

در trace به چه چیزی نگاه کنی

عدد کنار هر گره early آن است؛ late در پنل حافظه است.
یال‌های رنگی فعالیت‌های بحرانی‌اند.