بهینه سازی جستجوی اول عمق درخت عمومی با الگوریتم موازی

تکنیک های هوش مصنوعی انواع مختلفی از روش های جستجو را در ساختار درختی ارائه می کنند و این روش ها به صورت متوالی وموازی با استفاده از برنامه نویسی ساخت یافته پیاده سازی می شوند. جستجوی عمقی، یک الگوریتم جستجوی درختی است که پیمایشاز گره مبدا به گره های همسایه مجاور گره مبدا را، در یک گراف امکان پذیر می کند و به صورت متوالی به این روش پیاده سازی میشود. بهبود جستجوی متوالی اول عمق در چندین مطالعه تحقیقاتی بررسی شده است. در این مقاله ما جستجوی اول عمق درختعمومی را با استفاده از زبان برنامه نویسی C++ با الگوریتم ترتیبی پیاده سازی کردیم و میانگین زمان اجرای الگوریتم ترتیبی را بهدست آوردیم و سپس با ابزار موازی سازی mpi الگوریتم موازی درخت را پیاده سازی کردیم و میانگین زمان اجرای الگوریتم را باتعداد پردازنده و تعداد گره های متفاوت بدست آوردیم و نتایج زمان اجرای دو الگوریتم ترتیبی و موازی را با هم مقایسه کردیم ومشاهده شد که بطور متوسط از حدود ۵۰۰۰ گره به بالا، افزایش سرعت حالت موازی با ۲ پردازنده، حدودا بیش از ۲ برابر بوده است وبا افزایش تعداد گره ها، میزان بهبود حالت ۲ پردازنده ای نیز بیشتر شده است.

Keywords:

درخت عمومی , جستجوی عمق اول , الگوریتم ترتیبی , الگوریتم موازی , بهینه سازی