کاربرد برنامه نویسی در مهندسی صنایع

[armin_mehrara]

کسی چیزی در رابطه با درخت حداقل هزینه میدونه ؟

[meisam3322]

با سلام.

در اینجور مواقع ابتدا اگوریتم ، یعنی همون روابط ریاضی یا مهندسی تو اون رشته رو میان تفسیر میکنن بعد میشه خیلی راحت اونو با یکی از زبانهای برنامه نویسی پیاده سازی کرد. اگه بیشتر در این خصوص توضیح بدی ، شاید بشه کمکی کرد

[maktoom]

سلام
اگه منظورت درختیه که از یک راس شروع کنه و کوتاهترین مسیر رو(یعنی کمتری وزن یا همون هزینه) طی کنه تا به یکی از رئوس بره، به این روش می گن الگوریتم پیدا کردن کوتاهترین مسیر که معروفه به دایکسترا.
در این الگوریتم با شروع از راسی که خواسته شده با بررسی کمتری وزن یال(هزینه جابه جایی از اون یال به یال مجاور) که ازون راس خارج شده شروع می کنیم. در هر گام به کل رئوسی که طی کردیم نگاه می کنیم هر مسیری رو خواستیم انتخاب کنیم بررسی می کنیم آیا در مجموع وزن یالهایی که با انتخاب کردن اون مسیر بدست میاد آیا اون هزینه کمترین هزینه است یا نه. اگر جواب بله هست که اون راس جدید به مجموعه رئوس اضافه میشه و گرنه سراغ راس مجاور دیگه می ریم. یعنی در کل باید همیشه هزینه رو برای تمامی رئوسی که قابل انتخاب هستن در نظر بگیریم و نه فقط یک مسیر. و همچنین برای کل مسیر طی شده و نه مسیر پیش رو.

[maktoom]

یه سرچ توی ویکی بزن. به انگلیسی میشه "Minimum Spanning Tree" . اما نکته ای که این داره اینکه باید از تمامی رئوس با شرطی که گفتم بگذره.