با عرض سلام
سوال زیر رو من اینجوری حل کردم که باید طولانی ترین مسیر در یک گراف جهت دار و وزن دار رو پیدا کنیم که این کار توسط الگوریتم DFS و با مرتبه ی زمانی O(n + e) امکان پذیر هسن که اگه ماتریس خلوت باشه می شه O(n) . چرا گفته جواب ۲ می شه ؟
با تشکر
سلام. وقت بخیر.
فرمایشتون در مورد مرتبه درسته. ولی این سوال یه ابهام داره اونم اینکه نگفته مقدار n برابر تعداد عناصره یا تعداد سطرها. کنکور ۹۶ دکتری هم یه چیز مشابه با این اومد و اونجا گفته بود که تعداد عناصر سطر آخره. با این فرض جواب میشه [tex]\theta(n^2)[/tex]. راه حلی که من پیشنهاد میدم یه چیز شبیه به heapify هست. چون با DFS به نظرم دچار مشکل بشیم. چون هر گره دوتا والد داره و اگه ارتفاعمون بشه k، برگ‌ها به اندازه [tex]2^k[/tex] مرتبه پیمایش میشن.
با عرض سلام
از پاسختون سپاسگزارم، موفق و پیروز باشید
(۲۹ اسفند ۱۳۹۵ ۰۹:۰۴ ب.ظ)Jooybari نوشته شده توسط: سلام. وقت بخیر.سلام استاد.جسارتا با فرمایش شما مبنی بر ابهام دربارهn موافق نیستم در اینجا هم مثل بسیاری از مسائل دیگر که اطلاعی درباره n داده نشده n را تعداد ورودی مسئله میگیریم.پس بحث روی پیاده سازی این مثلت اعداد طوری که به عنوان ورودی الگوریتم جستجو بتواند اعمال شود است.با توجه به توضیحات سوال می توان این مثلث را به صورت DAG با لیست یا ماتریس پیاده سازی کرد (هر عدد یک راس و از ان عدد دو یال خروجی به دو فرزند چپ و راستش با وزن همان عدد(پدر) و تا به قاعده مثلث برسیم یک راس اضافی پایین قاعده قرار می دهیم و از اعداد موجود در قاعده یک یال جهت دار باوزن هر عدد(وزن راس اول یال)رسم می کنیم)و روال یافتن طولانی ترین مسیر از یک راس به سایر رئوس راروی dag اعمال می کنیم (ار راس نماینده بالاترین عدد تا راس اضافی که پایین قاعده قراردادیم)که اگر از لیست استفاده کنیم از مرتبه[tex]O(n+e)[/tex] و اگر از ماتریس مجاورتی استفاده شود[tex]O(n^2)[/tex] می شود.
فرمایشتون در مورد مرتبه درسته. ولی این سوال یه ابهام داره اونم اینکه نگفته مقدار n برابر تعداد عناصره یا تعداد سطرها. کنکور ۹۶ دکتری هم یه چیز مشابه با این اومد و اونجا گفته بود که تعداد عناصر سطر آخره. با این فرض جواب میشه [tex]\theta(n^2)[/tex]. راه حلی که من پیشنهاد میدم یه چیز شبیه به heapify هست. چون با DFS به نظرم دچار مشکل بشیم. چون هر گره دوتا والد داره و اگه ارتفاعمون بشه k، برگ‌ها به اندازه [tex]2^k[/tex] مرتبه پیمایش میشن.
سلام
از پاسختون سپاسگزارم، یعنی استدلال من از سوال درست بود ؟ فقط روش پیاده سازی گراف در تعیین مرتبه زمانی اهمیت داشت ؟
(۳۰ اسفند ۱۳۹۵ ۱۲:۱۱ ق.ظ)alimamala نوشته شده توسط: سلامسلام
از پاسختون سپاسگزارم، یعنی استدلال من از سوال درست بود ؟ فقط روش پیاده سازی گراف در تعیین مرتبه زمانی اهمیت داشت ؟
دوست گرامی استدلال شما مبنی بر یافتن طولانی ترین مسیر با مرتبه [tex]O(n+e)[/tex] برای گراف جهت دار وزن دار اون هم به کمک dfs استدلال درستی نیست . برای رسیدن به این مرتبه گراف بایدdag (گراف جهت دار بدون سیکل) باشد و اون هم نه با dfs بلکه به کمک مرتب سازی توپولوژی (البته در مرتب سازی از dfs استفاده می شود)و relax و ... البته ممکن است با dfs هم امکان داشته باشه ولی من اطلاعی دراین باره ندارم اگر چنین روالی وجود داردلطفا مطرح کنید... در مورد درستی پاسخ من هم تا تایید اقای جویباری ودیگر دوستان منتظر بمانید
(۳۰ اسفند ۱۳۹۵ ۰۲:۱۹ ق.ظ)msour44 نوشته شده توسط:(30 اسفند ۱۳۹۵ ۱۲:۱۱ ق.ظ)alimamala نوشته شده توسط: سلامسلام
از پاسختون سپاسگزارم، یعنی استدلال من از سوال درست بود ؟ فقط روش پیاده سازی گراف در تعیین مرتبه زمانی اهمیت داشت ؟
دوست گرامی استدلال شما مبنی بر یافتن طولانی ترین مسیر با مرتبه [tex]O(n+e)[/tex] برای گراف جهت دار وزن دار اون هم به کمک dfs استدلال درستی نیست . برای رسیدن به این مرتبه گراف بایدdag (گراف جهت دار بدون سیکل) باشد و اون هم نه با dfs بلکه به کمک مرتب سازی توپولوژی (البته در مرتب سازی از dfs استفاده می شود)و relax و ... البته ممکن است با dfs هم امکان داشته باشه ولی من اطلاعی دراین باره ندارم اگر چنین روالی وجود داردلطفا مطرح کنید... در مورد درستی پاسخ من هم تا تایید اقای جویباری ودیگر دوستان منتظر بمانید
سلام. وقت بخیر.
با استفاده از مفاهیم DAG هم میشه از همون مرتبه به جواب رسید. (چون گراف خلوته) اینکه گفتم ابهام داره برای این بود که تو کنکور امسال مشابه همین سوال اومد و n رو به شکلی که گفتم تعریف کرد. اینجا هم مثل اینکه کلید سنجش مرتبه [tex]n^2[/tex] بوده. وگرنه توی مرتبه زمانی با توجه به اندازه مثلث بحثی ندارم و جوابتون رو قبول دارم.
بابت تایید پاسخ شما باید بگم متاسفانه امکان تایید پاسخ صحیح برای ارسالهایی که در پاسخ به یه ارسال دیگه اومدن وجود نداره. ارسالهایی که کنارشون عدد نوشته و مثبت و منفی میگیرن رو میتونیم تایید کنیم.
(۳۰ اسفند ۱۳۹۵ ۰۳:۰۷ ق.ظ)Jooybari نوشته شده توسط:سلام.منظورم دریافت پاسخ درست نبودبلکه این بود که اگر ایرادی بر ان وارد است مطلع شوم.از شما استاد گرامی بابت تمامی پاسخ ها و راهنمای هایتان وکمک های ارزشمندتان بسیار متشکرم.(30 اسفند ۱۳۹۵ ۰۲:۱۹ ق.ظ)msour44 نوشته شده توسط:(30 اسفند ۱۳۹۵ ۱۲:۱۱ ق.ظ)alimamala نوشته شده توسط: سلامسلام
از پاسختون سپاسگزارم، یعنی استدلال من از سوال درست بود ؟ فقط روش پیاده سازی گراف در تعیین مرتبه زمانی اهمیت داشت ؟
دوست گرامی استدلال شما مبنی بر یافتن طولانی ترین مسیر با مرتبه [tex]O(n+e)[/tex] برای گراف جهت دار وزن دار اون هم به کمک dfs استدلال درستی نیست . برای رسیدن به این مرتبه گراف بایدdag (گراف جهت دار بدون سیکل) باشد و اون هم نه با dfs بلکه به کمک مرتب سازی توپولوژی (البته در مرتب سازی از dfs استفاده می شود)و relax و ... البته ممکن است با dfs هم امکان داشته باشه ولی من اطلاعی دراین باره ندارم اگر چنین روالی وجود داردلطفا مطرح کنید... در مورد درستی پاسخ من هم تا تایید اقای جویباری ودیگر دوستان منتظر بمانید
سلام. وقت بخیر.
با استفاده از مفاهیم DAG هم میشه از همون مرتبه به جواب رسید. (چون گراف خلوته) اینکه گفتم ابهام داره برای این بود که تو کنکور امسال مشابه همین سوال اومد و n رو به شکلی که گفتم تعریف کرد. اینجا هم مثل اینکه کلید سنجش مرتبه [tex]n^2[/tex] بوده. وگرنه توی مرتبه زمانی با توجه به اندازه مثلث بحثی ندارم و جوابتون رو قبول دارم.
بابت تایید پاسخ شما باید بگم متاسفانه امکان تایید پاسخ صحیح برای ارسالهایی که در پاسخ به یه ارسال دیگه اومدن وجود نداره. ارسالهایی که کنارشون عدد نوشته و مثبت و منفی میگیرن رو میتونیم تایید کنیم.
(۳۰ اسفند ۱۳۹۵ ۰۲:۱۹ ق.ظ)msour44 نوشته شده توسط:سلام(30 اسفند ۱۳۹۵ ۱۲:۱۱ ق.ظ)alimamala نوشته شده توسط: سلامسلام
از پاسختون سپاسگزارم، یعنی استدلال من از سوال درست بود ؟ فقط روش پیاده سازی گراف در تعیین مرتبه زمانی اهمیت داشت ؟
دوست گرامی استدلال شما مبنی بر یافتن طولانی ترین مسیر با مرتبه [tex]O(n+e)[/tex] برای گراف جهت دار وزن دار اون هم به کمک dfs استدلال درستی نیست . برای رسیدن به این مرتبه گراف بایدdag (گراف جهت دار بدون سیکل) باشد و اون هم نه با dfs بلکه به کمک مرتب سازی توپولوژی (البته در مرتب سازی از dfs استفاده می شود)و relax و ... البته ممکن است با dfs هم امکان داشته باشه ولی من اطلاعی دراین باره ندارم اگر چنین روالی وجود داردلطفا مطرح کنید... در مورد درستی پاسخ من هم تا تایید اقای جویباری ودیگر دوستان منتظر بمانید
توی کتاب مدرسان گفته که این کار رو با کمی تغییر در الگوریتم DFS انجام میدیم:
پس منظورش از "اندکی تغییر" روالی هست که شما فرمودید، یعنی با کمک مرتب سازی توپولوژیک.
با تشکر
از راهنمایی و کمک دوستان گرامی بسیار سپاسگزرم
موفق و پیروز باشید
(۳۰ اسفند ۱۳۹۵ ۰۸:۵۸ ق.ظ)alimamala نوشته شده توسط: سلام
توی کتاب مدرسان گفته که این کار رو با کمی تغییر در الگوریتم DFS انجام میدیم:
پس منظورش از "اندکی تغییر" روالی هست که شما فرمودید، یعنی با کمک مرتب سازی توپولوژیک.
با تشکر
از راهنمایی و کمک دوستان گرامی بسیار سپاسگزرم
موفق و پیروز باشید
این سوال با سوال قبل فرق داره. توی این سوال هر گره فقط یه فرزند داره. ولی تو سوال قبل اینطور نیست.