# فصل ۰۷ — گرافی که منفجر می‌شود

<div dir="rtl">

# فصل ۰۷ — گرافی که منفجر می‌شود

## در این فصل چه یاد می‌گیری

فصلِ قبل با یک جملهٔ آرام تمام شد: «پیمایشِ گراف تقریباً همیشه ارزان است». **این فصل دربارهٔ سؤال‌هایی است که ارزان نیستند.**

نقطهٔ شروع یک درخواستِ بی‌گناه است: «همهٔ مسیرها را بده». روی یک گرافِ کاملِ یازده‌گره‌ای جوابش `986,410` مسیر است و **ستونِ نسبتش `7.00`، `8.00`، `9.00` — نسبتی که خودش با `n` بزرگ می‌شود.** بعد جدولی می‌سازیم از بزرگ‌ترین `n`ی که هر مرتبهٔ رشد در یک بودجهٔ مشخص جا می‌کند: **با هزار برابر کردنِ بودجه، آن `n` برای `O(n!)` فقط از `12` به `14` می‌رود.**

![شبکه‌ای کوچک که تعدادِ بی‌شماری مسیرِ درهم از میانش رد می‌شود و در لبهٔ تصویر به انبوهی تبدیل شده](/lesson-assets/t5-s07-graph-explodes/prompt/01-image-path-explosion.png)

آخر این فصل می‌توانی:

- بگویی «همهٔ مسیرها» چرا تقریباً همیشه صورتِ مسئلهٔ غلط است
- **مرزِ عملیِ `n` را برای هر مرتبهٔ رشد حساب کنی**، نه حدس بزنی
- یک جوابِ تقریبی بسازی و **خطایش را روی اندازه‌هایی که جوابِ دقیق داری اندازه بگیری**

## قبل از شروع

**از ترمِ ۱ فصلِ ۶:** شش خانوادهٔ رشد و جدولِ «اگر `n` هزار برابر شود». **این فصل همان جدول را برعکس می‌پرسد: اگر بودجه هزار برابر شود، `n` چقدر بزرگ‌تر می‌شود؟**

**از فصلِ ۶:** `DFS` و مجموعهٔ دیده‌شده‌ها.

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | حدودِ نیم دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-07-graph-explodes.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. کوچک‌ترین نسخهٔ ممکن، با دست

چهار گره که همه به هم وصل‌اند. **از گرهٔ `0` تا گرهٔ `3` چند مسیرِ ساده هست؟** (مسیرِ ساده یعنی مسیری که از هیچ گره‌ای دو بار رد نمی‌شود.) با دست بشمار: مستقیم؛ از راهِ `1`؛ از راهِ `2`؛ از راهِ `1` و بعد `2`؛ از راهِ `2` و بعد `1`. **پنج تا.**

</div>

```python
def complete(node_count):
    """گرافی که در آن هر گره به هر گرهِ دیگری وصل است."""
    return {node: sorted(x for x in range(node_count) if x != node)
            for node in range(node_count)}


def count_paths(graph, node, goal, seen, total):
    """همهٔ مسیرهای ساده — مسیرهایی که از هیچ گره‌ای دو بار رد نمی‌شوند."""
    if node == goal:
        total[0] += 1
        return
    for nbr in graph[node]:
        if nbr not in seen:
            seen.add(nbr)
            count_paths(graph, nbr, goal, seen, total)
            seen.discard(nbr)


def all_paths(node_count):
    total = [0]
    count_paths(complete(node_count), 0, node_count - 1, {0}, total)
    return total[0]


tiny = complete(4)
print("گرافِ کاملِ ۴ گره:", tiny)
print("مسیرهای سادهٔ ۰ تا ۳:", all_paths(4))
```

```text
گرافِ کاملِ ۴ گره: {0: [1, 2, 3], 1: [0, 2, 3], 2: [0, 1, 3], 3: [0, 1, 2]}
مسیرهای سادهٔ ۰ تا ۳: 5
```

<div dir="rtl">

**خطِ `seen.discard(nbr)` همان یک خطی است که این کد را از `DFS` فصلِ قبل جدا می‌کند.** در پیمایش، گره‌ای که دیدی برای همیشه دیده‌شده می‌ماند؛ این‌جا فقط **در طولِ همین مسیر** دیده‌شده است و بعد از برگشتن آزاد می‌شود. **همین آزادسازی است که همه‌چیز را منفجر می‌کند.**

> 🌱 **ریشه‌اش کجاست:** پنج مسیرِ بالا از یک شمارشِ ساده درآمد: یا مستقیم برو، یا یکی از دو گرهِ میانی را انتخاب کن، یا هر دو را به یکی از دو ترتیبِ ممکن. **اصلِ ضرب و جایگشت** — همان چیزی که [ریشه ترمِ ۶ فصل ۱](/courses/risheh/lessons/term-6-probability-statistics/session-01-counting) می‌سازد: وقتی برای هر گام چند انتخاب داری، تعدادِ کلِ راه‌ها **ضربِ** انتخاب‌هاست، نه جمعشان. **و ضرب است که منفجر می‌شود.**

## ۲. حالا بزرگش کن

> 🤔 **اول حدس بزن:** به گرافِ کامل یک گره اضافه می‌کنیم — فقط **یکی**. تعدادِ مسیرها چند برابر می‌شود؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
table([(n, all_paths(n)) for n in (8, 9, 10, 11)], "مسیرِ ساده", ",d")
```

```text
         n        مسیرِ ساده     نسبت به سطر قبل
         8             1,957                   —
         9            13,700                7.00
        10           109,601                8.00
        11           986,410                9.00
```

<div dir="rtl">

**این تنها جدولِ این دوره است که نردبانش دوبرابری نیست، و دلیلش خودِ موضوعِ فصل است:** اگر `n` را از ۸ به ۱۶ می‌بردیم، سطرِ دوم هرگز تمام نمی‌شد.

و ستونِ نسبت را ببین: `7.00`، `8.00`، `9.00`. **این ستون ثابت نیست؛ خودش دارد بزرگ می‌شود و دقیقاً برابرِ `n - 2` سطرِ قبل است.** در `O(n²)` نسبت همیشه `4` می‌ماند هرچقدر `n` بزرگ شود؛ این‌جا نمی‌ماند. **هر ستونِ نسبتی که خودش رشد کند، یعنی مرتبه از هر توانی بدتر است.**

حالا امضای دوره: اگر نسبت `n - 2` است، برای `n = 12` باید ده برابرِ سطرِ قبل باشد.

</div>

```python
predicted = 10 * 986_410
measured = all_paths(12)
print(f"پیش‌بینی برای n = 12: {predicted:,}")
print(f"اندازه‌گیری          : {measured:,}")
print(f"خطای پیش‌بینی        : {measured - predicted}")
print(f"با همین قاعده برای n = 13: {11 * measured + 1:,} مسیر")
```

```text
پیش‌بینی برای n = 12: 9,864,100
اندازه‌گیری          : 9,864,101
خطای پیش‌بینی        : 1
با همین قاعده برای n = 13: 108,505,112 مسیر
```

<div dir="rtl">

**خطا: یکی.** آن یکی هم بی‌دلیل نیست — قاعدهٔ دقیق `(n - 2)` برابرِ سطرِ قبل **به‌علاوهٔ یک** است، و آن «یک» همان مسیرِ مستقیم است که هیچ گرهِ میانی ندارد.

> ⚠️ **مواظب باش:** سطرِ `n = 12` چند ثانیه طول کشید و **همین‌جا ایستادیم**. سطرِ بعدی `108,505,112` مسیر دارد و **حدودِ یازده برابرِ آن** وقت می‌خواهد؛ سطرِ بعدترش بیش از صد برابر. **اگر `all_paths(14)` را در Colab صدا بزنی، سلولت تمام نمی‌شود.** انتخابِ بزرگ‌ترین اندازهٔ یک جدولِ انفجاری بخشی از طراحیِ آزمایش است، نه چیزی که وسطِ اجرا کشفش کنی.

## ۳. مرزِ عملیِ `n`، برای هر مرتبه

سؤالِ واقعیِ مهندسی این نیست که «این مرتبه چقدر بد است»؛ این است که **«با این مرتبه، تا چه `n`ی می‌توانم جلو بروم؟»**

فرض کن ماشینت در یک واحدِ زمان یک میلیارد گامِ ساده برمی‌دارد. **این عدد فقط برای مقایسهٔ مرتبه‌هاست، نه یک مشخصهٔ سخت‌افزاری** — چیزی که اهمیت دارد ستونِ دوم در برابرِ ستونِ سوم است.

</div>

```python
import math

BUDGET = 10 ** 9


def largest_n(steps, budget):
    """بزرگ‌ترین n که کارش هنوز زیرِ budget می‌ماند."""
    high = 1
    while steps(high) <= budget:
        high *= 2
    low = 1
    while low < high:
        middle = (low + high + 1) // 2
        if steps(middle) <= budget:
            low = middle
        else:
            high = middle - 1
    return low


ORDERS = [
    ("O(n)", lambda n: n),
    ("O(n log n)", lambda n: n * math.log2(n + 1)),
    ("O(n^2)", lambda n: n * n),
    ("O(n^3)", lambda n: n * n * n),
    ("O(2^n)", lambda n: 2 ** n),
    ("O(n!)", lambda n: math.factorial(n)),
]

print(f"{'مرتبه':>12}{'n در یک میلیارد گام':>24}{'n در هزار برابرِ آن':>24}")
for name, fn in ORDERS:
    print(f"{name:>12}{largest_n(fn, BUDGET):>24,}{largest_n(fn, 1_000 * BUDGET):>24,}")
```

```text
       مرتبه     n در یک میلیارد گام     n در هزار برابرِ آن
        O(n)           1,000,000,000       1,000,000,000,000
  O(n log n)              39,620,077          28,781,593,877
      O(n^2)                  31,622               1,000,000
      O(n^3)                   1,000                  10,000
      O(2^n)                      29                      39
       O(n!)                      12                      14
```

<div dir="rtl">

**این جدول را حفظ نکن؛ نگهش دار.** دو ستونِ آخر را با هم بخوان: **هزار برابر کردنِ ماشین، برای `O(n)` هزار برابر `n` می‌خرد، برای `O(n²)` سی و دو برابر، برای `O(2^n)` ده واحد، و برای `O(n!)` دو واحد.**

**برای مرتبه‌های پایینِ جدول، ماشینِ بهتر جوابِ مسئله نیست.** اگر `n` تو ۲۰ است و الگوریتمت `O(n!)` است، هیچ سخت‌افزاری نجاتت نمی‌دهد؛ **باید صورتِ مسئله را عوض کنی.**

## ۴. جوابِ تقریبی، و اندازه‌گیریِ خطایش

سؤالِ نمونه: **بلندترین مسیرِ ساده در یک گراف چند یال دارد؟** جوابِ دقیقش همان انفجارِ بخشِ ۲ را دارد. ولی یک جوابِ **تقریبی** ارزان هست: از هر گره شروع کن و هر بار سراغِ همسایه‌ای برو که **کمترین همسایهٔ دیده‌نشده** را دارد. **و کاری که اکثرِ گزارش‌ها نمی‌کنند این است: خطای تقریب را روی اندازه‌هایی که جوابِ دقیق هنوز در دسترس است، اندازه می‌گیریم.**

</div>

```python
def make_graph(node_count, edge_count, seed=SEED):
    rng = random.Random(seed)
    edges = set()
    while len(edges) < edge_count:
        a = rng.randrange(node_count)
        b = rng.randrange(node_count)
        if a != b:
            edges.add((min(a, b), max(a, b)))
    graph = {node: [] for node in range(node_count)}
    for a, b in sorted(edges):
        graph[a].append(b)
        graph[b].append(a)
    for node in graph:
        graph[node].sort()
    return graph


def walk_longest(graph, node, seen, length, best, work):
    work[0] += 1
    if length > best[0]:
        best[0] = length
    for nbr in graph[node]:
        if nbr not in seen:
            seen.add(nbr)
            walk_longest(graph, nbr, seen, length + 1, best, work)
            seen.discard(nbr)


def longest_exact(graph):
    """جوابِ دقیق: هر مسیرِ ممکن از هر گره."""
    best, work = [0], [0]
    for start in sorted(graph):
        walk_longest(graph, start, {start}, 0, best, work)
    return best[0], work[0]


def longest_greedy(graph):
    """جوابِ تقریبی: از هر گره، هر بار سراغِ تنگ‌ترین همسایه."""
    best, work = 0, 0
    for start in sorted(graph):
        seen = {start}
        node = start
        length = 0
        while True:
            options = []
            for x in graph[node]:
                work += 1
                if x not in seen:
                    options.append(x)
            if not options:
                break
            pick, fewest = options[0], None
            for x in options:
                free = 0
                for y in graph[x]:
                    work += 1
                    if y not in seen:
                        free += 1
                if fewest is None or free < fewest:
                    pick, fewest = x, free
            node = pick
            seen.add(node)
            length += 1
        best = max(best, length)
    return best, work


print(f"{'V':>6}{'دقیق':>8}{'کارِ دقیق':>16}{'تقریبی':>10}{'کارِ تقریبی':>16}")
for v in (12, 16, 20, 24, 28, 32):
    graph = make_graph(v, 3 * v // 2)
    exact, exact_work = longest_exact(graph)
    guess, guess_work = longest_greedy(graph)
    print(f"{v:>6}{exact:>8}{exact_work:>16,}{guess:>10}{guess_work:>16,}")
```

```text
     V    دقیق       کارِ دقیق    تقریبی     کارِ تقریبی
    12      10           3,788        10             795
    16      13          18,484         9             821
    20      16         125,606        13           1,693
    24      20         593,642        17           2,414
    28      20         930,334        13           2,115
    32      26       9,982,418        21           3,084
```

<div dir="rtl">

**ستونِ «کارِ دقیق» از `3,788` به `9,982,418` رفت، در حالی که `V` فقط از ۱۲ به ۳۲ رسید.** ستونِ «کارِ تقریبی» در همان بازه از `795` به `3,084` رفت.

**و ستونِ خطا صادقانه بد است:** در `V = 12` تقریب دقیقاً درست بود، در `V = 16` جوابِ `9` داد به‌جای `13`، و در `V = 28` جوابِ `13` به‌جای `20`. **گاهی نزدیک، گاهی خیلی دور، و بدونِ هیچ الگوی مرتبی.**

**این را باید گفت، نه پنهان کرد:** یک جوابِ تقریبی بدونِ اندازه‌گیریِ خطایش، یک عددِ بی‌پشتوانه است.

</div>

```python
BIG = [500, 1_000, 2_000, 4_000]
print(f"{'V':>10}{'کار':>18}{'نسبت به سطر قبل':>20}{'بلندترین مسیر':>16}")
previous = None
for v in BIG:
    found, work = longest_greedy(make_graph(v, 3 * v // 2))
    ratio = "—" if not previous else f"{work / previous:.2f}"
    print(f"{v:>10,}{work:>18,}{ratio:>20}{found:>16,}")
    previous = work
```

```text
         V               کار     نسبت به سطر قبل   بلندترین مسیر
       500            47,955                   —              27
     1,000           110,612                2.31              50
     2,000           241,197                2.18              64
     4,000           470,322                1.95              59
```

<div dir="rtl">

**ستونِ نسبت `2.31`، `2.18`، `1.95` — حولِ `2`، یعنی جوابِ تقریبی خطی است.** روی گرافِ ۴٬۰۰۰ گره‌ای `470,322` گام خرج کرد؛ جوابِ دقیق روی همان گراف حتی قابلِ شروع کردن نیست.

**و ستونِ آخر را با احتیاط بخوان:** عددهای `27`، `50`، `64`، `59` **حدِ پایین**‌اند، نه جواب. تنها چیزی که می‌دانیم این است: مسیری به این طول **وجود دارد**، چون پیدایش کردیم.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** جست‌وجوی کاملِ همهٔ مسیرها با یک تقریبِ حریصانه، روی گرافِ یکسان و با شمارندهٔ یکسان. **در کدام بازهٔ `n`؟** گرافِ کاملِ ۸ تا ۱۲ گره برای شمارشِ مسیرها، ۱۲ تا ۳۲ گره برای مقایسهٔ دقیق و تقریبی، و ۵۰۰ تا ۴٬۰۰۰ گره برای خودِ تقریب. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا؛ شمارش قطعی است.

> ✅ **چک کن:** در `count_paths` خطِ `seen.discard(nbr)` را بردار و بخشِ ۲ را دوباره بگیر. **جوابِ هر چهار سطر باید `1` شود** — چون بدونِ آزادسازی، هر گره فقط یک بار در کلِ جست‌وجو دیده می‌شود و کد به `DFS` معمولیِ فصلِ ۶ برمی‌گردد. **همان یک خط، تفاوتِ `O(V+E)` و انفجار است.**

> 🔧 **اگر کار نکرد:** وقتی با این عددها کار می‌کنی، اولین چیزی که می‌شکند خودِ حسابِ اعشاری است:

</div>

```python
try:
    print(math.factorial(200) / 1_000_000_000)
except OverflowError as err:
    print(f"{type(err).__name__}: {err}")
print("با تقسیمِ صحیح، بدونِ خطا:", len(str(math.factorial(200) // 1_000_000_000)), "رقم")
```

```text
OverflowError: integer division result too large for a float
با تقسیمِ صحیح، بدونِ خطا: 366 رقم
```

<div dir="rtl">

**عدد آن‌قدر بزرگ است که در یک `float` جا نمی‌شود.** پایتون خودش عددِ صحیحش را نگه می‌دارد — ۳۶۶ رقم — ولی لحظه‌ای که تقسیمِ اعشاری کنی، `float` کم می‌آورد. **راهِ حل `//` است، یا کار کردن با تعدادِ رقم‌ها به‌جای خودِ عدد. و این خطا خودش یک پیام دارد:** وقتی جوابِ یک مسئله در نوعِ عددیِ استاندارد جا نمی‌شود، آن مسئله را با هیچ ماشینی نمی‌شود شمرد.

> 🤖 **از دستیارت بپرس:** **جدولِ بخشِ ۳ را جلویش بگذار:** «برنامه‌ام `O(2^n)` است و `n` من ۵۰ است؛ ماشینِ هزار برابر سریع‌تر کمکم می‌کند؟» — جوابِ درست باید بگوید نه و عدد بدهد. بعد: **«چه سؤالِ دیگری می‌توانم بپرسم که جوابش برایم کافی باشد؟»**

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| simple path | سیمپل پث | مسیرِ ساده: مسیری که از هیچ گره‌ای دو بار رد نمی‌شود |
| combinatorial explosion | کامبیناتوریال اکسپلوژن | انفجارِ ترکیبیاتی: رشدی که از هر توانی تندتر است |
| backtracking | بک‌ترکینگ | برگشتن و آزاد کردنِ گره، تا مسیرِ دیگری امتحان شود |
| approximation | اپراکسیمیشن | جوابِ تقریبی: جوابی که ارزان است و درستیِ کاملش تضمین نشده |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: ستونِ نسبتی که خودش با `n` بزرگ می‌شود، چه چیزی دربارهٔ مرتبه می‌گوید؟

**تمرینِ اجباری:** جدولِ بخشِ ۲ را روی گرافی بگیر که **کامل نیست** — مثلاً `make_graph(n, 2 * n)` — برای چهار مقدارِ `n`. **سؤالِ اصلی: ستونِ نسبت هنوز رشد می‌کند یا نه؟** جوابت باید نقشِ چگالی را بگوید و یک عدد از جدولت پشتش باشد.

**تمرینِ ستاره‌دار ⭐:** تقریبِ بخشِ ۴ را عوض کن: به‌جای شروع از همهٔ گره‌ها، فقط از **ده گرهِ کم‌درجه‌تر** شروع کن. **قبل از اجرا پیش‌بینی کن** کدام ستونِ جدولِ بخشِ ۴ عوض می‌شود: کیفیتِ جواب، هزینه، یا هر دو. حالا اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **و سؤالِ آخر: چطور می‌فهمی تقریبت بهتر شده، وقتی جوابِ دقیق را نداری؟**

## در فصل بعد

همه‌چیزِ این ترم روی یک شبکهٔ واقعی‌شکل جمع می‌شود: ۴٬۰۰۰ گره، `11,994` یال، و چند گرهِ پرترافیک. **و مثلِ همین فصل، محدودیتمان را با عدد اعلام می‌کنیم:** قطرِ دقیقِ آن شبکه `111,952,000` گام می‌خواهد و ما با `55,976` گام یک حدِ پایین می‌گیریم — که در یکی از دو اندازهٔ آزمایش، **یک واحد کمتر از جوابِ درست** درآمد.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s07-graph-explodes (یادستان, Yaadestan)
