این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
رایانش نرم و فناوری اطلاعات، جلد ۹، شماره ۳، صفحات ۲۴۴-۲۵۵
عنوان فارسی ارائه مدلی بهینه جهت یافتن کوتاهترین مسیرهای تخمینی با پوشش کامل گراف
چکیده فارسی مقاله با توجه به افزایش حجم اطلاعات در شبکه های اجتماعی و فضای وب، نیاز به الگوریتم های سریع برای آنالیز محتوای گراف بیش از پیش احساس می شود. یکی از مهمترین عملیات ها در گراف، یافتن کوتاهترین مسیر بین دو گره است که می تواند کاربردهای مختلفی در مسیریابی و ارتباطات داشته باشد. الگوریتم های کلاسیک برای حل این مسئله بسیار کند و استفاده از آن ها عملا غیرممکن است، بنابراین می توان ازالگوریتم های تخمینی استفاده کرد که اغلب مبتنی بر لندمارک هستند. در این مقاله چهار مدل تخمینی مبتنی بر لندمارک معرفی می گردد که با استفاده از روش های ابتکاری، گره های لندمارک به صورت برون خط انتخاب می گردند. همچنین از یک الگوریتم ابتکاری برای خوشه بندی گره ها استفاده شده و سپس کوتاهترین مسیرها در هر خوشه محاسبه می گردد، همچنین از داده ساختار هش استفاده می شود تا دسترسی به گره ها به صورت مستقیم صورت پذیرد و در زمان اجرای پرس وجو به صورت برخط، با سرعت و دقت بالا مورد استفاده قرار گیرد. روش های پیشنهادی با هدف پوشش کل گراف می تواند خطای قابل محاسبه را به 0/0016 کاهش دهد.
کلیدواژه‌های فارسی مقاله کوتاهترین مسیر، لندمارک، خطای تقریبی، گراف، خوشه،
عنوان انگلیسی Provide an Optimal Model for Finding the Shortest Estimated Paths with Full Graph Coverage
چکیده انگلیسی مقاله Due to the increasing volume of information in social networks and the web, the need for efficient and fast algorithms for analyzing graph content is felt more than ever. One of the most important operations in a graph is to find the shortest path between two nodes, which can have different applications in routing and communication. Classic algorithms are very slow and computationally expensive, nearly impossible, so algorithms using approximation approaches are often used based on Landmark nodes. In this study, four landmark models are introduced. Using innovative methods, landmark nodes are selected for each nodes cluster, the shortest paths are pre-computed and the results are Hashing for direct access. Hence, a fast, efficient and precise result retrieval is possible when an online query is executed. The proposed methods cover the entire graph can reduce the error rate by 0.0016.
کلیدواژه‌های انگلیسی مقاله کوتاهترین مسیر, لندمارک, خطای تقریبی, گراف, خوشه
نویسندگان مقاله شکوفه بستان |
گروه مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران

علی محمد زارع بیدکی |
دانشیار، دانشکده مهندسی برق و کامپیوتر، دانشگاه یزد، یزد، ایران

نشانی اینترنتی https://jscit.nit.ac.ir/article_111569_a3ecfceda0172a207c1c3feecea512e6.pdf
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات