الگوریتم A-star

[aram_2]

سلام دوستان خسته نباشید.برای جستجوی آ-استار کمک میخواستم.مفهومش رو می دونم .حتی برای هشت وزیر هم بلدم.اما مساله من اینه که میخوام در یه فضای بسیار بزرگ دنبال جواب بهینه بگردم.مشکلم و تابع هیورستیک اونه.من 1000 تا فایل دارم و هر کدوم دارای یه عدد تصادفی بین 0و1 هستش.حالا میخوام اون فایلهایی که دارای بزرگترین عدد هستن رو انتخاب کنم.اما محدودیت من اینه که مجموع این فایلها نباید از 1 گیگ بیشتر بشه.حجم هر فایل هم متوسط 2 مگا بایته.ممنون

[soroushp]

سلام شما هم خسته نباشید - میشه یک مقدار بیشتر روی کارت توضیح بدی ؟ تا یک هیوریستیک براش پیدا کنیم !
منظورت چیه می خوای بزرگترین عدد رو انتخاب کنی ؟

[Negin.cs]

سلام
خب از
IDA*: A Memory-Efficient Variation of A* استفاده کنید!

http://webdocs.cs.ualberta.ca/~aixplore/search/IDA/index.html

[aram_2]

ببینید من یه مجموعه فایل دارم که باید رو سرور قرار بدم.این فایلها هر کدوم دارای یه ضریب محبوبیت هستن که نشون میده رو هر سرور چقدر محبوب هستن.یعنی تو هر سرور دارای محبوبیت متفاوتی هستن.حالا من میخوام اون فایلها که دارای بیشترین محبوبیت هستن رو در سرور قرار بدم.محدودیت هر سرور هم یک گیگا بایته.و اندازه فایلها هم میانگین 2 مگابایت.

[soroushp]

g که می تونید براساس یک الگوریتم مرتب سازی مثلا 20 تا فایلی که بیشترین بازدید رو داشتند بذارید اما برای h کلمات کلیدی در متن فایلها رو به عنوان ضریب محبوبیت در نظر بگیرید مثلا در گوگل بیشترین سرچ انجام شده(کلمات کلیدی )= hو بیشترین صفحات باز شده =g در ابتدای لینک هاش نمایش داده می شه !
f(n)=g(n)+h(n)

[aram_2]

ممنون.مشکل اینجاس که این ضریب محبوبیت از تعداد بازدیدها بدست اومده.و برای هیوریستیک من نمی تونم اونجور عمل کنم.چون من فقط اندازه فایل رو دارم و بس!

[soroushp]

اگر بخواهید تخمینی از تعداد رجوع به قایل مورد نظر در آینده داشته باشید حتما باید ورودی مثل متن فایل رو داشته باشید اما اگر صرفا می خواهید بیشترین محبوبیت رو دسته بندی کنید و فقط اندازه فایل رو دارید می تونید از روشهای مرتب سازی یا n روش دیگه استفاده کنید ؛ چون در A* حداقل تابع هدف و ورودی رو باید داشته باشیم که شما فقط اندازه فایل رو دارید که اصلا نمیشه تخمین زد که کاربر با چه احتمالی در آینده این فایل رو بازدید می کنه چون از محتویات فایل با خبر نیستید !

[aram_2]

خب من با همون ضریب فایل می دونم که در آینده چقدر به یه فایل درخواست داده میشه.

[soroushp]

خب اگر می دونید پس چرا از A* استفاده می کنید ؟:بامزه:

[aram_2]

اخه اون ضزیب نشون دهنده g(n) هست.البته اینجور فکر می کنم.خب من از A* برای پیدا کردن هدف دارم استفاده می کنم.هدف من قرار دادن فایلهای با ضریب بالا در سرور هاست.اون ضرایب برای هر سرور فرق می کنه.

[soroushp]

من مسئله شما رو یکبار تعریف می کنم هر جا یی که اشتباه بود بگید :
شما 1000 تا فایله 2 مگابایت دارید که می خواهید از بین اونها مثلا 20 تا که بزرگترین هستش رو انتخاب کنید بعد هر فایل به وسیله کاربر که محبوبیت اون فایل رو مشخص می کنه ارزیابی میشه شما می خواهید اون فایلهایی رو تو سرور آپلود کنید که بیشترین محبوبیت رو داشته اند چون مشکل حافظه دارید
؟!

[aram_2]

اولا همه فایلها دو مگابایت نیستند.میانگین اونها دو مگ هست.بعد هم من فایل بزرگ رو نمیخوام انتخاب کنم بلکه فایلی که محبوبیت بیشتری داره.و محبوبیت رو درست گفتید.محدودیت حافظه هم درست بود.مساله همینه!

[soroushp]

ببینید هیوریستیک میاد تخمین می زنه ، تو مساله شما تخمینی نداریم چون میشه بزرگترین ها رو sort کرد از روی همون محبوبیتی که گفتید دارید یعنی مسئله حریصانه ست نه A*- سواله من این بود که چی می خواین تخمین بزنید !

[aram_2]

ببینید من حریصانه حل کردم و به جواب رسیدم.حالا میخوام الگوریتم خودم رو بیام مقایسه کنم با کارهای دیگه ببینم در چه سطحیه.حالا میخواستم ببینم با A* چجور می تونم اینکارو انجام بدم.ممنون.

[soroushp]

مشکل حریصانه اینه که فایل ها یی که در ابتدا به نظر می رسه محبوبیت زیادی دارند ممکنه در آینده این فایل ها اهمیت خودشون رو از دست بدند و فایل ها ی دیگه ای جایگزین بشند - چون کاربر طرف شماست نه مسئله هشت وزیر یا جاده رومانی نمی تونید بگید علاقه کاربر به چیه و بیاید روانشناسی کنید تا یک هیوریستیک براش بسازید - بله میشه اما هیوریستیک دقیقی نمیشه چون همه یک جور فکر نمی کنند مگر اینکه خود فایل رو در اختیار داشته باشید !
به هر حال مسئله به نظرم حریصانه ست چون کاربر غیر قابل پیش بینی هست !

[aram_2]

خب قضیه اینجاس که این محبوبیت ها در طولانی مدت بدست اومده.مثلا شما یک ماه سیستم رو لاگ می کنی بعد میبینی درخواست به این فایل اینقدره و... حالا بنظر شما من این الگوریتم رو با چی مقایسه کنم؟ راستی هدف من هم اینه که اون بیشترین درخواست ها رو پاسخ بدم.

[soroushp]

من تو نظرم neural network بود- مثلا شما یک dataset از علاقه کاربران به موضوعات خاص تهیه می کنی(نظر سنجی ) -بعد دسته بندی می کنی بعد تو اون دسته بندی موضوعی که بین همه مشترک هست و همه به اون علاقه مند هستند رو در میاری بعد اون فایلی که مورد اتفاق همه هستش رو رو سرور آپلود می کنی اینطوری میشه !
اما اگر بخوای یک هیوریستیک پیدا کنی که علاقه کاربران رو تخمین بزنه غیر ممکنه چون n کاربر داریم و n سلیقه ! حداقل اینه که من راهی براش پیدا نکردم و همون حریصانه بهتره !

[aram_2]

ممنون.راستش نخندیدا!! من اون محبوبیت رو با یه تابع توزیع بدست آوردم.یعنی من لاگ فایل ندارم! حالا هم نمی تونم از نئورال با این ایده استفاده کنم.

[soroushp]

از چه توزیعی استفاده کردی ؟ می تونی یک مثال بزنی ؟

[aram_2]

من از تابع Zipf استفاده کردم.این توزیع میگه فایل iام داای محبوبیت یا حالا رتبه ای با نسبت 1/n که n کل فایلها.

[soroushp]

یکی از راه ها استفاده از احتمالات هست اما نه هر احتمالی یکی از اونها قضیه بیز هست که برای تصمیم گیری max جوابها رو میگیره شاید بشه !

[aram_2]

بیشتر توضیح میدید؟

[soroushp]

این لینک رو ببین (http://fa.wikipedia.org/wiki/قضیه_بیز)، من فکر می کنم با احتمالات بشه مسئله رو تخمین زد !