در این مطلب، ویدئو ساختارها و الگوریتم های پیشرفته داده در پایتون: پایین ترین اجداد مشترک | packtpub.com با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:10:03
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:01,580 –> 00:00:03,640
شما
2
00:00:08,200 –> 00:00:11,020
در این بخش با
3
00:00:11,020 –> 00:00:12,910
چند نمودار نظری
4
00:00:12,910 –> 00:00:15,640
که شامل کمترین مشکل جد مشترک
5
00:00:15,640 –> 00:00:17,650
و دیگری شامل
6
00:00:17,650 –> 00:00:19,750
بسط کمتر شناخته شده مشکل کوتاه ترین
7
00:00:19,750 –> 00:00:22,720
مسیر است نتیجه گیری می کنیم در این ویدیو قصد
8
00:00:22,720 –> 00:00:25,349
داریم در مورد پایین ترین جد مشترک پایین ترین جد مشترک صحبت کنیم.
9
00:00:25,349 –> 00:00:28,150
مشکل یا
10
00:00:28,150 –> 00:00:31,660
به اختصار LCA دو گره داده شده زیر
11
00:00:31,660 –> 00:00:33,880
در یک درخت است که می خواهیم
12
00:00:33,880 –> 00:00:36,489
پایین ترین جد مشترک آنها را پیدا
13
00:00:36,489 –> 00:00:40,360
14
00:00:40,360 –> 00:00:42,730
15
00:00:42,730 –> 00:00:46,030
16
00:00:46,030 –> 00:00:48,970
کنیم. اگر به این درخت 8 در 7
17
00:00:48,970 –> 00:00:53,410
داده شود LCA آنها 6 می شود اگر 2 داده می شود و برای
18
00:00:53,410 –> 00:00:57,250
LCA آنها 1 می شود بیایید
19
00:00:57,250 –> 00:00:59,440
دوباره همان درخت را در نظر بگیریم تور اویلر زیر را دارد.
20
00:00:59,440 –> 00:01:03,010
تور اویلر یک
21
00:01:03,010 –> 00:01:06,250
نوع خاص از پیمایش درخت است که با عمق مشابه است.
22
00:01:06,250 –> 00:01:09,430
-اولین جستجو اما همچنین
23
00:01:09,430 –> 00:01:11,680
خروجی والد را بین هر
24
00:01:11,680 –> 00:01:15,340
خروجی فرزندان متوالی می دهد، به
25
00:01:15,340 –> 00:01:17,319
عنوان مثال می توانید ببینید که
26
00:01:17,319 –> 00:01:19,810
مانند جستجوی عمقی اول تا
27
00:01:19,810 –> 00:01:24,670
8 قبل از 1 به 6 انجام می شود و 8 اما سپس
28
00:01:24,670 –> 00:01:28,689
خروجی 6 را می دهد و سپس 7 و سپس 6 را
29
00:01:28,689 –> 00:01:31,840
دوباره خروجی می دهد و برای کل درخت یکسان می شود،
30
00:01:31,840 –> 00:01:34,310
31
00:01:34,310 –> 00:01:36,700
بنابراین اگر ابزار اویلر را محاسبه
32
00:01:36,700 –> 00:01:40,460
کنیم، اجازه دهید عمق را نیز محاسبه کنیم. عمق
33
00:01:40,460 –> 00:01:43,430
I همان عمق گره است.
34
00:01:43,430 –> 00:01:46,149
در اینجا برای هر
35
00:01:46,149 –> 00:01:49,929
گره، LCA a و B به سادگی
36
00:01:49,929 –> 00:01:53,140
حداقل از این عبارت است، بنابراین اول
37
00:01:53,140 –> 00:01:55,329
از همه اولین وقوع a را
38
00:01:55,329 –> 00:01:58,329
در اویلر و اولین وقوع B را
39
00:01:58,329 –> 00:02:01,090
در ابزار اویلر مییابیم، سپس حداقل را از عبارت اویلر میگیریم.
40
00:02:01,090 –> 00:02:04,509
عمق
41
00:02:04,509 –> 00:02:08,440
پلک بین این دو موقعیت قرار می گیرد، بنابراین
42
00:02:08,440 –> 00:02:09,818
می توانید ببینید که ما
43
00:02:09,818 –> 00:02:13,360
مشکل را به یک محدوده جستجوی حداقل کاهش داده ایم،
44
00:02:13,360 –> 00:02:16,900
بیایید یک مثال بنویسیم عمق هشت
45
00:02:16,900 –> 00:02:21,940
سه عمق از 7 است همچنین سه اولین
46
00:02:21,940 –> 00:02:24,460
وقوع هشت در موقعیت سه است
47
00:02:24,460 –> 00:02:27,250
، اول وقوع هفت در
48
00:02:27,250 –> 00:02:30,430
موقعیت پنج است و حداقل بین
49
00:02:30,430 –> 00:02:34,240
عمق جزیره سه عمق جزیره
50
00:02:34,240 –> 00:02:37,450
و چهار و عمق جزیره
51
00:02:37,450 –> 00:02:40,930
پنج گره شش است زیرا باید به
52
00:02:40,930 –> 00:02:44,650
این موقعیت ها نگاه کنیم که حداقل 6 است و
53
00:02:44,650 –> 00:02:48,610
عمق آن شش LCA است. از ei ght
54
00:02:48,610 –> 00:02:51,550
و هفت بیایید وارد ویرایشگر کد خود شویم
55
00:02:51,550 –> 00:02:55,060
و یک بار دیگر این را پیاده سازی
56
00:02:55,060 –> 00:02:56,800
کنیم، ما از یک کلاس پایتون برای
57
00:02:56,800 –> 00:03:00,160
ذخیره اطلاعات مربوط به گره ها استفاده
58
00:03:00,160 –> 00:03:02,380
می کنیم که برای هر گره
59
00:03:02,380 –> 00:03:06,520
برچسب آن لیستی از فرزندان و
60
00:03:06,520 –> 00:03:08,500
والد آن را ذخیره می کنیم. برای
61
00:03:08,500 –> 00:03:11,820
پیادهسازی راهحل ساده برای LCA مفید است،
62
00:03:11,820 –> 00:03:14,380
اجازه دهید اکنون اویلر را در یک تابع پیادهسازی کنیم،
63
00:03:14,380 –> 00:03:17,620
بنابراین ابتدا بررسی میکنیم که آیا
64
00:03:17,620 –> 00:03:20,680
گره فعلی یک برگ است که فرزندی ندارد،
65
00:03:20,680 –> 00:03:21,370
66
00:03:21,370 –> 00:03:25,480
بنابراین اگر نه فرزندان گره بالا، آنگاه
67
00:03:25,480 –> 00:03:27,220
به سادگی فهرستی از
68
00:03:27,220 –> 00:03:30,580
برچسب گرههای جاری چون برگها فقط
69
00:03:30,580 –> 00:03:34,120
یک بار خروجی میشوند پس از آن، یک
70
00:03:34,120 –> 00:03:36,709
متغیر نتیجه را اعلام
71
00:03:36,709 –> 00:03:40,040
میکنیم که با لیستی از برچسبهای گرههای فعلی مقداردهی اولیه میکنیم،
72
00:03:40,040 –> 00:03:43,519
سپس برای هر یک از
73
00:03:43,519 –> 00:03:47,209
فرزندان گرههای فعلی،
74
00:03:47,209 –> 00:03:50,420
نتیجه خود را با چیزی که یک فراخوان بازگشتی
75
00:03:50,420 –> 00:03:53,420
برای فرزند فعلی میدهد گسترش میدهیم. ما
76
00:03:53,420 –> 00:03:56,799
متد توسعه در اینجا اساساً به عنوان یک لیست الحاقی کار می کند
77
00:03:56,799 –> 00:04:00,290
زیرا این یک لیست را برمی گرداند و
78
00:04:00,290 –> 00:04:03,560
به سادگی هر عنصر
79
00:04:03,560 –> 00:04:08,200
در آن لیست را به لیست نتایج ما اضافه می کند و همچنین
80
00:04:08,200 –> 00:04:11,900
پس از آن به t نیاز داریم. o
81
00:04:11,900 –> 00:04:16,789
برچسب گره های فعلی را به نتیجه خود اضافه می کنیم در
82
00:04:16,789 –> 00:04:21,160
پایان ما به سادگی متغیر نتیجه خود را برمی گردانیم
83
00:04:22,170 –> 00:04:26,320
این کد درخت نشان داده شده در اسلایدهای ما را می
84
00:04:26,320 –> 00:04:30,930
سازد و همچنین تور اویلر خود را چاپ می کند
85
00:04:30,930 –> 00:04:34,390
سپس ما چند تابع کمکی
86
00:04:34,390 –> 00:04:37,090
داریم که توضیح خواهیم داد تا بتوانیم دریافت کنیم.
87
00:04:37,090 –> 00:04:39,490
تابع عمق است که از یک
88
00:04:39,490 –> 00:04:41,350
تابع درونی برای محاسبه
89
00:04:41,350 –> 00:04:45,040
دیکشنری استفاده میکند که در آن عمق I
90
00:04:45,040 –> 00:04:49,000
عمق گره با برچسب I ما یک
91
00:04:49,000 –> 00:04:50,680
فرهنگ لغت است، بنابراین لازم نیست
92
00:04:50,680 –> 00:04:53,160
نگران بزرگ بودن
93
00:04:53,160 –> 00:04:56,730
لیستهایمان باشیم، این کد بسیار ساده است.
94
00:04:56,730 –> 00:04:59,980
تابع داخلی به عنوان پارامتر
95
00:04:59,980 –> 00:05:02,760
عمق فعلی در نظر گرفته می شود و گره فعلی
96
00:05:02,760 –> 00:05:06,250
عمق را بر اساس آن تنظیم می کند و
97
00:05:06,250 –> 00:05:08,820
خود را به صورت بازگشتی برای هر فرزندی
98
00:05:08,820 –> 00:05:12,650
که از D به اضافه 1