الگوریتم های جستجوی زیرگراف

[mehdi5106]

من بر روی الگوریتم های فوق باید تحقیق کنم ، ممنون میشوم اگر راهنماییم نمائید.


چه الگوریتم هایی برای جستجوی زیر گراف مناسب ترند؟
چه الگوریتم هایی پیچیدگی زمانی و مکانی پایین تری نسبت به بقیه دارند؟
کدامیک را می تواند بهبود بخشید؟

[مسعود اقدسی فام]

منظورتون از جستجوی زیرگراف چیه؟ با جستجوی گراف فرقی داره؟ یا صرفا باید محدوده رو رعایت کنیم که از زیرگراف بیرون نریم؟ یا منظورتون یافتن بزرگترین زیرگراف کامل (مساله کلیک) و مسائلی از این دست هستش؟

[mehdi5106]

منظورم از جستجوی زیرگراف اینه که بتونیم زیرگراف های مختلف با گره های دو تایی ، سه تایی و ... را در یک گراف بزرگتر جستجو کنیم.(جهت دار و بدون جهت)

[srahas]

بهترین الگوریتم جستجو *A ولی همیشه در پیاده سازی از ورژن های دیگه ی *A ، مثله IDA* , SMA* , RBFS استفاده میشه چون خود *A پیچیدگی حافظه اش به صورت نماییه !
اما سریعترین نوع الگوریتم همینه.

[srahas]

منم یه سوال در مورد همین *A داشتم ... :دی
موقع گسترش گره ها به این روش اگه به جایی رسیدیم که تابع هزینه ی یکی از گره های فرزند (گره هایی که با گسترش گره انتخابی مرحله قبل بوجود اومدن ) با یکی از گره های برادر (گره های همسطح گره گسترش یافته) برابر شد ، اونموقع کدوم انتخاب می شه ؟!
اینو می دونم که اگه تو یه سطح به این مشکل برخوردیم از نظر ترتیب الفبایی یکی رو انتخاب می کنیم و یا به ترتیب تولید شدن گره ها،از چپ به راست اولی رو انتخاب می کنیم. اما در این مورد نمی دونم تقدم با کدومه فرزند یا برادر ؟!

[maktoom]

سلام
الگوریتم هایی که در ذاتشون به نوعی تکرار نهفتست عملکرد بهتری دارند.
ازونجا که A* الگوریتمیه که گذشته رو هم ذخیره می کنه و از h استفاد می کنه پس بهتره از IDA* استفاده کنید که هر دو مزیت رو با هم داره.
البته اگه پیچیدگی زمانی تا حد واقعا مهمی براتون ارزش داره بهتره به مقالات در این زمینه رجوع کنید.

[mehdi5106]

از دوستان بابت راهنماییهاشون ممنون. اما بزارین مساله رو کمی بزرگتر در نظر بگیریم.
راه حل های ارائه شده ممکنه برای مسائل کوچک جواب قابل قبولی ارائه بده. اما اگر بخواهیم یک زیرگراف با 10 گره و یا بیشتر را در یک گراف با بیش از 1000 یا حتی بیشتر جستجو کنیم! چه راه حلی پیشنهاد می دهید؟!

[maktoom]

در ابعاد خیلی بزرگ بهتره به فکر الگوریتمهای مثل شبکه عصبی و ... باشید.
که البته دیگه هیچ کدوم از اینها به تنهایی جوبگو نیست. باید اینا رو ترکیب کنید تا جواب خوبی بگیرید.
یعنی باید از متلب استفاده کنید.
چیزی که مشخصه از روش های آگاهانه باید استفاده کنید. اما نحوه انجام و نوعش رو باید با شرایط محیطتون بسنجید.
1000 گره!!!

[mehdi5106]

ممنون.
میشه بیشتر راهنمایی کنید.من می خواهم یکی از الگوریتم هایی انتخاب بشه که بتوان مرتبه زمانی مساله فوق رو کاهش داد. حالا این می خواد یه الگوریتم ترکیبی باشه یا هر چیزه دیگه.
شبکه عصبی خوبه اما فکر نمی کنید که بار سیستم برای همچین مساله بیشتر میشه!
من روی یه چیزهایی بین ترکیب الگوریتم ژنتیک و امثال آن با یکسری الگوریتم های دیگه فکر می کنم.
می خوام با نظرات دوستان به یک راه حل کلی برسیم.

[srahas]

در مورد الگوریتم های جستجو اگر حافظه اولویت بالاتری براتون داشته باشه ، الگوریتم های RBFS و *SMA بهترین عملکرد رو دارن و پیچیدگی حافظشون به صورت خطیه ! بهترین حالت ممکن !
برای ترکیب می تونید از یکی از این دو الگوریتم استفاده کنید.

[mehdi5106]

در مسائل این چنینی به نظر بنده حافظه زیاد مهم نیست ، چون می توان آن را حل نمود. بیشترین جیزی که از اهمیت بیشتری برخوردار است ، زمان می باشد و در مرحله بعدی حافظه...

[srahas]

بله درسته کلا این مورد بستگی به خود مسئله داره. :چشمک:

البته این رو هم باید در نظر گرفت که در مسائل بزرگ تر ممکنه قبل از تموم شدن زمان، حافظه تموم بشه.