ارائه مدلي بهينه جهت يافتن كوتاهترين مسيرهاي تخميني با پوشش كامل گراف

با توجه به افزايش حجم اطلاعات در شبكه هاي اجتماعي و فضاي وب، نياز به الگوريتم هاي سريع براي آناليز محتواي گراف بيش از پيش احساس مي شود. يكي از مهمترين عمليات ها در گراف، يافتن كوتاهترين مسير بين دو گره است كه مي تواند كاربردهاي مختلفي در مسيريابي و ارتباطات داشته باشد. الگوريتم هاي كلاسيك براي حل اين مسئله بسيار كند و استفاده از آن ها عملا غيرممكن است، بنابراين مي توان ازالگوريتم هاي تخميني استفاده كرد كه اغلب مبتني بر لندمارك هستند. در اين مقاله چهار مدل تخميني مبتني بر لندمارك معرفي مي گردد كه با استفاده از روش هاي ابتكاري، گره هاي لندمارك به صورت برون خط انتخاب مي گردند. همچنين از يك الگوريتم ابتكاري براي خوشه بندي گره ها استفاده شده و سپس كوتاهترين مسيرها در هر خوشه محاسبه مي گردد، همچنين از داده ساختار هش استفاده مي شود تا دسترسي به گره ها به صورت مستقيم صورت پذيرد و در زمان اجراي پرس وجو به صورت برخط، با سرعت و دقت بالا مورد استفاده قرار گيرد. روش هاي پيشنهادي با هدف پوشش كل گراف مي تواند خطاي قابل محاسبه را به 0/0016 كاهش دهد.