Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > مقدمات هوش مصنوعی > حل مسائل معروف هوش مصنوعي


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۸-۱-۱۳۸۸, ۰۵:۵۵ بعد از ظهر   #1 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Arrow حل مسئله کوله پشتي به روش هاي مختلف

دوستان بياييد مسئله کوله پشتي را با روش هاي مختلف با هم حل کنيم
حل مسئله با روش هايي مثل:
الگوريتم ژنتيک
الگوريتم عقبگرد
و غيره
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
meysam.ai (۰۷-۱۲-۱۳۹۱), raha90 (۰۳-۷-۱۳۹۰), sinarock (۰۹-۹-۱۳۹۲)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۸-۱-۱۳۸۸, ۰۶:۲۱ بعد از ظهر   #2 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Question

مسئله کوله پشتی چیست؟
فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از 1 تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد به عنوان نمونه ای از مسائلی که می توانند بصورت مساله کوله پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متاسفانه تعداد چنین بردارهایی است.بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و دهها قرن برای n = 65 والی اخر. با این وجود ،با استفاده از الگوریتمهایی خاص می توان در بسیاری موارد مسئله ای با n = 100 000 را در عرض چند ثانیه روی یک کامپیوترکوچک حل کرد
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده است:
raha90 (۰۳-۸-۱۳۹۰)
قديمي ۰۸-۱-۱۳۸۸, ۰۷:۱۱ بعد از ظهر   #3 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

در لينک زير برنامه کوله پشتي را که از طريق الگوريتم ژنتيک حل شده (در متلب )
دانلود کنيد:

دانلود کد حل مسئله کوله پشتی توسط الگوریتم ژنتیک


در ضمن مطالعه مقالات (انگليسي) زير هم براي حل اين مسئله با الگوريتم ژنتيک بسيار مفيد است:
فايل ضميمه
نوع فايل: pdf Knapsack01app.pdf (739.2 كيلو بايت, 3604 نمايش)
نوع فايل: pdf db425.pdf (185.5 كيلو بايت, 1813 نمايش)
نوع فايل: pdf SI090308.pdf (554.9 كيلو بايت, 2228 نمايش)
نوع فايل: pdf nikgakn.pdf (67.9 كيلو بايت, 1349 نمايش)
نوع فايل: pdf tabusearchKnapsack.pdf (486.6 كيلو بايت, 2111 نمايش)

ويرايش شده توسط Astaraki; ۱۱-۸-۱۳۸۹ در ساعت ۰۶:۲۸ بعد از ظهر
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
alijy (۰۳-۵-۱۳۸۹), lotfi1008 (۰۴-۱۷-۱۳۹۴), niloofar_f (۰۲-۸-۱۳۹۱), raha90 (۰۳-۸-۱۳۹۰), sorayadaniali (۱۰-۶-۱۳۹۳), ایمان رئال (۰۳-۱۱-۱۳۹۱)
قديمي ۰۸-۱-۱۳۸۸, ۰۷:۴۵ بعد از ظهر   #4 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink مسئله کوله پشتی صفر و یک

در این مسئله مجمو عه ای از قطعات داریم که هر یک دارای وزن و ارزش معین است.

- اوزان و ارزش ها اعداد مثبتی هستند.

- دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبتW فراتر رود، کوله پشتی پاره می شود.

الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک
كد:
   void knapsack ( index i ,
 int profit , int weight)
 {
 if ( weight ≤ W &&  profit > maxprofit ) {
 maxprofit = profit ;
 numbest = i ;
 bestset = include;
 }
  if ( promising (i)) {
 include [ i + 1 ] = “yes”;
 knapsack ( i + 1, profit + p [ i + 1] , weight +
 w [ i +1 ]);
 include [ i +1] = “ no”;
 knapsachk ( i +1 , profit , weight );
 }
 }
 bool promising ( index i )
 {
  index j , k ;
 
 int totweight ;
 float bound;
 if ( weight ≥ W)
  return  false ;
 {
 j = i +1 ;
 bound = profit ;
 totweight = weight ;
  while ( j <= n && totweight + w[j] <= W) {
 totweight = totweight + W [j];
 
  bound = bound + p[j];
 j++;
 }
 k = j;
 if ( k <= n)
 bound = bound + (W – totweight) * p [k]/w[k];
  return bound > max profit ;
 }
 }
مقایسه الگوریتم برنامه نویسی پویا و الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک

- تعداد عناصری که توسط الگوریتم برنامه نویسی پویا برای مسئله کوله پشتی صفر و یک محاسبه می شود دربدترین حالت به O (minimum (2ⁿ , nW)) تعلق دارد.

- در بدترین حالت ، الگوریتم عقبگرد (ⁿ 2)θ گره را چک می کند.

- الگوریتم عقبگرد معمولا کارایی بیشتری نسبت به الگوریتم برنامه نویسی پویا دارد.

- هوروویتز و شانی ، روش تقسیم و حل را با روش برنامه نویسی پویا ترکیب کرده الگوریتمی برای مسئله کوله پشتی صفر و یک بسط داده اند که دربدترین حالت به O(2^n/2)
تعلق دارد.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
daniel_atish (۰۳-۱-۱۳۹۳), mahdiheart (۰۶-۲۰-۱۳۹۳), raha90 (۰۳-۸-۱۳۹۰), ایمان رئال (۰۳-۱۱-۱۳۹۱)
قديمي ۰۸-۱-۱۳۸۸, ۰۷:۴۹ بعد از ظهر   #5 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Question

سورس کد کوله پشتی به روش 0 و 1

كد:
# include
# include
using namespace std;
void bi(int t[],int n){
for(int i=0; n!=0;i++){
t[i]=n%2;
n/=2;
}

}
int main()
{
int n,i,s,sum,b=-1;
cout<<"enter number of gold pocket :"; 
cin>>n;
cout<<"enter sum:";
cin>>s;
int temp[10]={0},a[10];
for( i=0;i
cin>>a[i];
for(int j=1;j
bi(temp,j);
sum=0;
for(int k=0;k
if(temp[k]!=0)
sum+=a[k];}
if (sum==s){
for(int k=0;k
if (temp[k]==1)
cout<<<" ";
b=1;
cout<

}
if (b==-1)
cout<<"there is not such set"<
return 0;
}
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
green_Dream (۱۲-۶-۱۳۸۸), norozi_a_2007 (۰۳-۱۷-۱۳۹۱), raha90 (۰۳-۸-۱۳۹۰), ایمان رئال (۰۳-۱۱-۱۳۹۱)
قديمي ۰۸-۱-۱۳۸۸, ۰۷:۵۰ بعد از ظهر   #6 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,306 تشكر در 3,125 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

يک الگوریتم داینامیک برای حل مسئله کوله پشتی
كد:
Dynamic-0-1-knapsack (v, w, n, W)

FOR w = 0 TO W
DO c[0, w] = 0
FOR i=1 to n
DO c[i, 0] = 0
FOR w=1 TO W
DO IFf wi ≤ w
THEN IF vi + c[i-1, w-wi]
THEN c[i, w] = vi + c[i-1, w-wi]
ELSE c[i, w] = c[i-1, w]
ELSE
c[i, w] = c[i-1,w]
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
maryam.eng (۰۲-۹-۱۳۹۲), ایمان رئال (۰۳-۱۱-۱۳۹۱)
قديمي ۱۱-۱-۱۳۹۲, ۰۹:۲۱ قبل از ظهر   #7 (لینک دائم)
عضو جدید
 
آواتار helmaa
 
تاريخ عضويت: آذر ۱۳۹۲
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

سلام خواهش می کنم اگر کسی میتونه کد الگوریتم ژنتیک این مسٔله رو توضیح بده بد جوری نیاز دارم ممنون
helmaa آفلاين است   پاسخ با نقل قول
قديمي ۰۵-۳-۱۳۸۹, ۰۸:۵۲ قبل از ظهر   #8 (لینک دائم)
عضو جدید
 
آواتار hadiabc
 
تاريخ عضويت: خرداد ۱۳۸۹
پست ها: 5
تشكرها: 0
15 تشكر در 4 پست
My Mood: Narahat
پيش فرض

سلام
در این وبلاگ
پرو‍‍‍‍‍ژه طراحي الگوريتم و هوش مصنوعي
hadiabc آفلاين است   پاسخ با نقل قول
از hadiabc تشكر كرده اند:
Astaraki (۱۰-۱۹-۱۳۸۹), hjafari (۰۱-۱۶-۱۳۹۰)
قديمي ۰۵-۲۸-۱۳۹۲, ۰۵:۵۷ بعد از ظهر   #9 (لینک دائم)
عضو فوق فعال
 
آواتار masood
 
تاريخ عضويت: خرداد ۱۳۸۸
محل سكونت: اسالم
پست ها: 98
تشكرها: 291
37 تشكر در 30 پست
My Mood: Khoshhal
ارسال پيغام Yahoo به masood
پيش فرض

نقل قول:
نوشته اصلي بوسيله hadiabc نمايش پست
متاسفانه دیگه این وبلاگ در دسترس نیست.
__________________
یک روز یک ماشین برای انتخابات ریاست جمهوری ثبت نام می کند
چه بخواهیم چه نخواهیم این اتفاق می افتد.
masood آفلاين است   پاسخ با نقل قول
قديمي ۱۰-۱۸-۱۳۸۹, ۱۱:۴۱ بعد از ظهر   #10 (لینک دائم)
عضو جدید
 
آواتار ziaye
 
تاريخ عضويت: دي ۱۳۸۹
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

لطفا" اگر امكان داشته باشه مسئله كوله پشتي رو به زبان #c برام بفرستين
ziaye آفلاين است   پاسخ با نقل قول
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۹:۱۰ قبل از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design