سلام به همگی
در فصل ششم (نظریه گرافها) کتاب اقای قلی زاده در مورد الگوریتم دیکسترا (الگوریتم نزدیکترین همسایه)
میخواستم نحوه کار این الگوریتم را بدونم؟ (مرحله به مرحله)
لطفا توضیحات به صورت کد زبان برنامه نویسی نباشد.
در فصل هفتم (درختها) الگوریتم پریم مانند الگوریتم قبلی نحوه کار ان را بدونم؟ (مرحله به مرحله)
لطفا توضیحات به صورت کد زبان برنامه نویسی نباشد.
و در مورد پیمایش پیش ترتیبی و پس ترتیبی و میان ترتیبی نمی دونم از کجا بایستی شروع کنم مخصوصا پیمایش میان ترتیبی اگر در مورد هر کدام از این سه پیمایش توضیح جامع بدهید ممنون میشوم؟
برای مثال در صفحه ۳۲۱ یک مثال اورده شده کتاب ساختمان گسسته از اقای قلی زاده که من ضمیمه کرده‌ام (شکل شماره۲ نتیجه پیمایش میان ترتیبی از سمت چپ به راست بخوانید p j q f c k g a d r b h s m e i t n u
در این مثال از پایین ترین راس شروع کرده یعنی p
ولی در شکل شماره ۱ که ضمیمه کرده‌ام نتیجه پیمایش میان ترتیبی از سمت چپ به راست بخوانید: B H G A D C F
در این مثال از راس B شروع کرده چرا از راس H شروع نکرده است؟
با تشکر
در نمایش میان ترتیبی اول فرزند سمت جپ بعد پدر بعد فرزند سمت راست نوشته می شه در شکل ۱، اول به ریشه نگاه می کنه می بینه فرزند سمت چپ داره پس سراغ اون می ره(B) بعد به B نگاه می کنه ولی اون فرزند سمت چپ نداره پس طبق قانون فرزند چپ نداره پس نوبت به پدر میرسه بنابراین خود گره B نوشته می شه بعد سراغ فرزند راست B میره که G باشه دوباره برای G همین عملبات تکرار می شه یعنی بهش نگاه می کنه فرزند چپ داره پس اول اون نوشته می شه (H) بعد سراغ پدر میاد و نوشته می شه(G) بعد tرزند راست که نداره . حالا به ریشه درخت برمی گرده و به سمت راست میره و این عملیات دوباره تکرار می شه.
در مورد شکل ۲ از اون جایی که گره j فرزند چپ داره و اون هم p هست بنابراین اول اون نوشته می شه. همین روند رو ادامه بدید به جواب میرسید.کلا در پیمایش میان ترتیب، الین گرهی که نوشته می شه سمت چپ ترین گره در راستای ریشه درخته یعنی از ریشه برید سمت چپ تا جایی که دیگه سمت چپ نداشته باشه و اون گره نوشته می شه مثلا در مثال ۱ گره B این شرط رو داره و در شکل ۲ گره p
در نمایش پیش ترتیب همونطور که از اسمش مشخصه باید ریشه اول نوشته بشه بعد فرزند چپ بعد فرزند راست مثلا شکل ۱ رو در نظر بگیرید.اول باید ریشه نوشته بشه پس اول A رو می نویسیم بعد سراغ فرزند چپ میریم حال فرض کنید یه درخت جدید با ریشه B داریم دوباره اول ریشه نوشته می شه که همون B باشه بعد سمت چپ میریم ولی فرزند چپ نداره که بنویسیم بعد سمت راست میایم که به G میرسیم دوباره اول ریشه G بعد سمت چپ که H باشه بعد سمت راست که نداره پس تا این جا شد A B G H حالا همین عکلیات برای سمت راست درخت تکرار می شه.
پس در نمایش پیش ترتیب همیشه ریشه اولین گره ایست که نوشته می شه.
حالا واسه پس ترتیب هم همین عملیات رو تکرار کنید ولی ریشه باید اخر باشه اول فرزند چپ بعد فرزند راست بعد ریشه .هر مرحله که پایین رفتید برای زیر درخت دوباره این عملیات رو تکرار کنید.در نهایت اون چیزی که بدست میارید ریشه اخرین گره خواهد بود.
[attachment=1557]خیلی ممنون از راهنماییتان
من یک شکل دیگه هم ضمیمه کرده‌ام لطفا پیمایش میان ترتیبی چگونه است؟
اگه طبق همون روند که گفتم پیش برید به heabdcgfjirmspknvtwqu می رسید اگه جاییش اشتباه بود یا نیاز به توضیح بیشتر بود بگید تا توضیح بدم
ممنون با تشکر از صبر و حوصله تان
جواب شما درست است
استدلال من این گونه است که (اگر اشتباه است اصلاح کنید جمله مرا اصلاح کنید)
یک درخت داریم ریشه اش r است از سمت چپ شروع میکنیم ما یک زیر درخت داریم که
راس ان j است دو فرزند با نامهای h,i دارد طبق قاعده از فرزند چپ شروع کرده یعنی h
را نوشته بعد بایستی به سراغ فرزند راست یعنی i برویم اما چون یک زیر درخت دیگری پایین
هست فرزند راست را نمینویسیم پس به سراغ زیر درخت دیگری با راس g رفته که شامل
فرزند چپ e فرزند راست f است باز مانند قبل نمی تونیم فرزند راست را بنویسیم چون
فرزند چپ پایین ان زیر درخت دیگری است با ریشه d و با فرزندان چپ a,b فرزند راست c
تو این مرحله دیگر چون زیر درخت دیگری نداریم طبق قاعده عمل میکنیم و بعد فرزندان راست
نوشته نشده را مینویسیم تا به ریشه اصلی یعنی r رسیده درخت بعدی را هم با این روش
پیمایش میکنیم.
اگر با یه راسی مانند h در این شکل روبرو شدیم که شامل یک زیر درخت باشد همیشه
بایستی یک مکث کرد یعنی ان زیر درخت بایستی تا اخر پیمایش شود بعد قاعده مورد نظر را رویش
پیاده کرد؟
در پیمایش پس ترتیبی همیشه از پایین‌تر سطح شروع کرده چون میگیم فرزند چپ و فرزند راست
بعد ریشه فکر کنم مثل این میمونه که بخواهی یک دیوار درست کنی که همیشه اجرها از پایین
چیده میشه میاید بالا درسته؟
در مورد الگوریتم دیکسترا مرحله اولش را میدونم مابقی مراحلش را خوب نمیدونم اگر
می دونید مرا راهنمایی کنید
با تشکر دوست عزیز
واسه میان ترتیبی اول فرزند چپ بعد ریشه بعد فرزند راست
حالا واسه این درخت:
ریشه درخت r هست .سراغ فرزند چپ میریم که باز هم یه زیر درخته با ریشه j. سراغ فرزند چپ که h باشه میریم.بز هم یه زیر درخت داریم.در این حالت باید مجددا ابترا سراغ فرزند چپ بریم بعد ریشه بعد فرزند راست. فرزند چپ نداره پس ریشه نوشته می شه یعنی h. حال سراغ فرزند راست میریم که اونم یه زیر درخته.د.باره تکرار این روند. یعنی ابتدا به فرزند چپش نگاه می کنیم که یه زیر درخته با ریشه e .فرزند چپ نداره که بنویسیم پس ریشه که e باشه نوشته می شه بعد میریم سراغ فرزند راست.باز زیر درخته با ریشه d .فرزند چپش باز یه زیر درخته با ریشه d .هرزند چپ اون a هست اون رو می نویسیم بعد ریشه که d باشه. بعد میایم بالا و ریشه زیر درخت یعنی d رو می نویسیم بعد سرراغ فرزند راست رفته و c رو نوشته .خوب حالا زیر درخت چپ g تموم شد پس ریشه یعنی g رو می نویسیم بعد فرزند راست یعنی f . خوب زیر درخت راست h هم تموم شد حالا زیر درخت چپ j هم تموم شد و ریشه یعنی خود J رو می نویسیم بعد فرزند راست یعنی i رو می نویسیم حالا زیر درخت چپ r تموم شد نوبت به ریشه میرسه یعنی r رو می نویسیم بعد سراغ زیر درخت راست میریم و ادامه عملیات .....
الگوریتم دایکسترا رو دقیقا یادم نیست اگه پیداش کردم براتون توضیحش رو می نویسم.
ممنون انرژی مثبت! من با روشی که یاد گرفته بودم فکر میکردم جواب یه چیزه دیگه میشه !
البته فکر میکنم روش های خیلی خیلی راحت تری واسه توضیح این ۳ پیمایش هست !
اگر تمرین کنید نیازی به رفتن تمامی این مراحل نخواهید داشت در واقع در کمتر از یه دقیقه می تونید پیمایش رو دربیارید هر مسئله ای نیاز به تمرین و حل موارد مشابه داره