۰
subtitle
ارسال: #۱
  
عملکرد الگوریتمهای پریم و کروسکال با وجود دور منفی؟؟
سلام.
آیا این دو الگوریتم با وجود دور منفی درست کار میکنند؟؟؟
یه جا خونده بودم که درست کار میکنند ولی متاسفانه الان یادم نمیاد کجا خوندم.
آیا این دو الگوریتم با وجود دور منفی درست کار میکنند؟؟؟
یه جا خونده بودم که درست کار میکنند ولی متاسفانه الان یادم نمیاد کجا خوندم.
۱
ارسال: #۲
  
RE: عملکرد الگوریتمهای پریم و کروسکال با وجود دور منفی؟؟
سلام
این مسئله دور منفی بیشتر در الگوریتم های یافتن کوتاهترین مسیر، در یک گراف جهتدار اهمیت پیدا میکنه.
دو الگوریتم پریم و کروسکال روی گراف وزن دار(وزن خواه مثبت باشه خواه منفی) و بدون جهت عمل میکنند و توی یک گراف بدون جهت بیشتر داشتن یا نداشتن دور مهمه(منظورم اینه که مهم نیست دور منفی باشه یا مثبت) و هر دو الگوریتم پریم و کروسکال در هر مرحله چک میکنند که یالی که قراره به مجموعه جواب اضافه بشه ایجاد دور نکنه(حالا میخواد دور منفی باشه یا مثبت، این مهم نیست مهم ایجاد نشدن دور هست) پس میشه گفت که کلا این دو تا الگوریتم دور رو تشخیص می دهند(فرقی نداره دور مثبت باشه یا منفی)
این مسئله منفی بودن دور بیشتر تو گراف جهتدار اهمیت پیدا میکنه، مثلا الگوریتم هایی مثل بلمن فورد یا دیجسترا که روی یک گراف وزن دار و جهتدار عمل میکنند تا کوتاهترین مسیر رو پیدا کنند، اینکه بتونن دور منفی رو تشخیص بدن خیلی اهمیت داره چون وجود دور منفی باعث میشه فاصله بین دو راس منفی بی نهایت بشه.
این مسئله دور منفی بیشتر در الگوریتم های یافتن کوتاهترین مسیر، در یک گراف جهتدار اهمیت پیدا میکنه.
دو الگوریتم پریم و کروسکال روی گراف وزن دار(وزن خواه مثبت باشه خواه منفی) و بدون جهت عمل میکنند و توی یک گراف بدون جهت بیشتر داشتن یا نداشتن دور مهمه(منظورم اینه که مهم نیست دور منفی باشه یا مثبت) و هر دو الگوریتم پریم و کروسکال در هر مرحله چک میکنند که یالی که قراره به مجموعه جواب اضافه بشه ایجاد دور نکنه(حالا میخواد دور منفی باشه یا مثبت، این مهم نیست مهم ایجاد نشدن دور هست) پس میشه گفت که کلا این دو تا الگوریتم دور رو تشخیص می دهند(فرقی نداره دور مثبت باشه یا منفی)
این مسئله منفی بودن دور بیشتر تو گراف جهتدار اهمیت پیدا میکنه، مثلا الگوریتم هایی مثل بلمن فورد یا دیجسترا که روی یک گراف وزن دار و جهتدار عمل میکنند تا کوتاهترین مسیر رو پیدا کنند، اینکه بتونن دور منفی رو تشخیص بدن خیلی اهمیت داره چون وجود دور منفی باعث میشه فاصله بین دو راس منفی بی نهایت بشه.
ارسال: #۳
  
RE: عملکرد الگوریتمهای پریم و کروسکال با وجود دور منفی؟؟
(۱۳ بهمن ۱۳۹۳ ۰۱:۲۰ ب.ظ)Sakura نوشته شده توسط: سلام
این مسئله دور منفی بیشتر در الگوریتم های یافتن کوتاهترین مسیر، در یک گراف جهتدار اهمیت پیدا میکنه.
دو الگوریتم پریم و کروسکال روی گراف وزن دار(وزن خواه مثبت باشه خواه منفی) و بدون جهت عمل میکنند و توی یک گراف بدون جهت بیشتر داشتن یا نداشتن دور مهمه(منظورم اینه که مهم نیست دور منفی باشه یا مثبت) و هر دو الگوریتم پریم و کروسکال در هر مرحله چک میکنند که یالی که قراره به مجموعه جواب اضافه بشه ایجاد دور نکنه(حالا میخواد دور منفی باشه یا مثبت، این مهم نیست مهم ایجاد نشدن دور هست) پس میشه گفت که کلا این دو تا الگوریتم دور رو تشخیص می دهند(فرقی نداره دور مثبت باشه یا منفی)
این مسئله منفی بودن دور بیشتر تو گراف جهتدار اهمیت پیدا میکنه، مثلا الگوریتم هایی مثل بلمن فورد یا دیجسترا که روی یک گراف وزن دار و جهتدار عمل میکنند تا کوتاهترین مسیر رو پیدا کنند، اینکه بتونن دور منفی رو تشخیص بدن خیلی اهمیت داره چون وجود دور منفی باعث میشه فاصله بین دو راس منفی بی نهایت بشه.
درسته
منم نظرم همینه.
چون که توی هر مرحله وجود دور چک میشه ، مشکلی پیش نمیاد و درست کار میکنن.
-۱
ارسال: #۴
  
RE: عملکرد الگوریتمهای پریم و کروسکال با وجود دور منفی؟؟
ن فقط بلمن فورد با یال منفی درس کارمیکنه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close