A Heuristic Algorithm for the Steiner Tree Problem in the Euclidean Plane
سال انتشار: 1390
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 2,356
فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CSCCIT01_150
تاریخ نمایه سازی: 8 بهمن 1390
چکیده مقاله:
Euclidean Steiner tree problem is to find the tree with minimal Euclidean length spanning a set of fixed points in the plane, allowing the addition of auxiliary points to the set (Steiner points). The problem is NP-hard, so polynomial-time heuristics are desired. We present a novel heuristic for the Euclidean Steiner tree problem. The lgorithm utilizes the straight skeleton of simple polygon to generate candidate Steiner points, and a path heuristic to constructing Steiner minimum tree by using some of the candidate Steiner points in Euclidean plane. We present computational results on the Soukup test problems.
کلیدواژه ها:
نویسندگان
Ali Nourollah
Department of Electrical and Computer Engineering of Shahid Rajaee Teacher Training University
elham pashaei
Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
Elnaz pashaei
Department of Electrical, Computer and IT Engineering, Qazvin Islamic Azad University
Alireza Bagheri
Department of Computer Engineering and Information Technology, Amirkabir University
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :