جملات زیر با پیش دانستهای ما د ر تناقض است:
کسی میتونه پاسخ بده:
۱///////////برای درخت بدون جهت t که هر یال t دارای وزن منفی می باشد. الگوریتمی از درجه o(n وجود دارد که کوچیک ترین مسیر های هم مبدا را پیدا میکند
۲///////////برای گراف بدون دور جهت دار t که راس های ان از ۰ تا n-1 پرچسپ خورده اند به طوری که هر یال <i,j> که در ان iکوچکتر از j می باشد وبه صورت لیست پیداه سازی شده است و هر یال ان میتواند وزن منفی داشته باشد الگوریتمی با درجه o(n+e) وجو داردکه کوتاه ترین (و با تعمیم طولانی ترین )مسیر های هم مبدا را پیدا میکند
۱ - "درخت" بدترین حالت وقتیه که درخت خطی مورب باشه یا مبدا یکی از برگها باشه. تعداد یالهای درخت حداقله پس مرتبه مون O(v+(v-1)) = O(V) Bfs
۲- نظرم اینه که bfs رو اجرا کنیم و اگه نودی که قبلا پیمایش شد رو دیدم اگه مسیر جدید کمتر(یا بیشتر )بود جایگزین بشه(شایدم من اشتباه می کنم)
فکر می کنم اگه پیمایش Dag رو مطالعه کنیدخیلی کمکتون کنه
پس یعنی این وزن منفی توی یک و دو و این صعودی بودن یالها توی ۲ تاثیری نداره؟
معمولا الگوریتم‌ها با دور منفی مشکل دارن نه با یال منفی( بجز دایکسترا )خوب در مورد ۱ که درخت داریم و در مورد ۲ که گفته بدون دور، پس اینجا اصلا قضیه دور منفی نداریم . پس یه dfs و یه مرتب سازی توپولوژیکی کار ما رو راه میندازه
(۲۵ بهمن ۱۳۹۰ ۰۱:۲۶ ب.ظ)saeedeh123 نوشته شده توسط:(25 بهمن ۱۳۹۰ ۰۱:۱۲ ب.ظ)Masoud05 نوشته شده توسط: معمولا الگوریتم‌ها با دور منفی مشکل دارن نه با یال منفی( بجز دایکسترا )خوب در مورد ۱ که درخت داریم و در مورد ۲ که گفته بدون دور، پس اینجا اصلا قضیه دور منفی نداریم . پس یه dfs و یه مرتب سازی توپولوژیکی کار ما رو راه میندازه
میشه در مورد مرتب سازی توپولوژیکی توضیح بیشتری بدید. ممنون.
مرتب سازی توپولوژیکی اینه:
روی درخت الگوریتم DFS رو اجرا می کنید و تمام نود را به ترتیب نزولی بر اساس زمان پایانشون مرتب می کنید. به ترتیب حاصل می گن ترتیب توپولوژیکی....
(۲۵ بهمن ۱۳۹۰ ۰۱:۲۶ ب.ظ)saeedeh123 نوشته شده توسط: میشه در مورد مرتب سازی توپولوژیکی توضیح بیشتری بدید. ممنون.
مرتب سازی توپولوژیکی در واقع همون مرتب سازی بر اساس پیش شرط‌ها هست . مثلا اگر از گره A به B یالی باشه یعنی A باید زودتر از B اجرا شود( مثل پیشنیاز در انتخاب واحد ).
نکته مهم اینه که مرتب سازی توپولوژیکی روی DAG اجرا میشه یعنی گراف جهتدار بدون دور . چون دور اگه در گراف باشه ترتیب خطی دیگه نخواهیم داشت . از اونجایی که گراف دور نداره پس مشکلی با دور منفی هم نداریم
به وسیله dfs روی DAG زمان خاتمه رئوس رو پیدا میکنیم و گره‌ها رو به ترتیب معکوس زمان خاتمه در خروجی مینویسیم تا اینطوری پیش نیاز‌ها رعایت بشه پس مرتبه الگوریتم همانند dfs خطیه .
(۲۵ بهمن ۱۳۹۰ ۰۱:۱۲ ب.ظ)Masoud05 نوشته شده توسط: معمولا الگوریتم‌ها با دور منفی مشکل دارن نه با یال منفی( بجز دایکسترا )خوب در مورد ۱ که درخت داریم و در مورد ۲ که گفته بدون دور، پس اینجا اصلا قضیه دور منفی نداریم . پس یه dfs و یه مرتب سازی توپولوژیکی کار ما رو راه میندازهدر مورد یک که بدون جهت هست باشه dfs جواب میده اما در مورد ۲ که جهت داره فکر کنم توپلوزیکی جواب بده مثلا برای این گراف سعیده فرض هم بزارین منفی نباشه عمقی نمی تونه ج را بده
(۲۵ بهمن ۱۳۹۰ ۱۲:۴۹ ب.ظ)anyone نوشته شده توسط: Dagیه DAG توی کامپایلر AHO داریم (Directed Acyclic Graph = گراف بدون دور جهت دار)، که منظور از دور ، بازگشت از یک گره به خودش بدون عبور از جای دیگه،)
DAG برای درخت دستور یا ساختار نحوی بکار می ره که توی فصل ۶ (کد میانی) از آیهو ترجمه جعفرنژاد صفحه ی ۳۴۲ به بعد میشه یادش گرفت.
==
آیا توی ساختمان داده ها هم DAG داریم؟ لطفا آدرس بدین