Artificial Intelligence - هوش مصنوعی

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)
-   حل مسائل معروف هوش مصنوعي (http://artificial.ir/intelligence/forum102.html)
-   -   حل مسئله کوله پشتي به روش هاي مختلف (http://artificial.ir/intelligence/thread620.html)

Astaraki ۰۸-۱-۱۳۸۸ ۰۵:۵۵ بعد از ظهر

حل مسئله کوله پشتي به روش هاي مختلف
 
دوستان بياييد مسئله کوله پشتي را با روش هاي مختلف با هم حل کنيم:rolleyes:
حل مسئله با روش هايي مثل:
الگوريتم ژنتيک
الگوريتم عقبگرد
و غيره

Astaraki ۰۸-۱-۱۳۸۸ ۰۶:۲۱ بعد از ظهر

مسئله کوله پشتی چیست؟
فرض کنید که جهانگردی می خواهدکوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از 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 ۰۸-۱-۱۳۸۸ ۰۷:۱۱ بعد از ظهر

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

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


در ضمن مطالعه مقالات (انگليسي) زير هم براي حل اين مسئله با الگوريتم ژنتيک بسيار مفيد است:;)

Astaraki ۰۸-۱-۱۳۸۸ ۰۷:۴۵ بعد از ظهر

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

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

- دزدی درنظر دارد قطعاتی که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در آن کوله پشتی از یک عدد صحیح مثبت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 ۰۸-۱-۱۳۸۸ ۰۷:۴۹ بعد از ظهر

سورس کد کوله پشتی به روش 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 ۰۸-۱-۱۳۸۸ ۰۷:۵۰ بعد از ظهر

يک الگوریتم داینامیک برای حل مسئله کوله پشتی
كد:

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 ۰۸-۱-۱۳۸۸ ۰۷:۵۱ بعد از ظهر

اینم یه کد دیگه برای الگوریتم کوله پشتی

كد:

Algorithm greedy_knapsock(p,w,m,x,n)
//object ordered so that (P[i]/W[i])>(P[i+1]/W[i+1])
m=0
cu=m //remaning capacity
for i=1 to n
if w[i]>cu then exit
x[i]=1
cu=cu-w[i]
next i
if i<=n then x[i]=cu/w[i]
end


Astaraki ۰۸-۱-۱۳۸۸ ۰۷:۵۳ بعد از ظهر

سورس کد کوله پشتی در سی
كد:

void Knapsack(){
int a[n, w], c[n], v[n], n, w, i, c;
for(c = 0; c <= w; c++){
a[0, c] = 0;
}
for(i = 1, i <= n; i++){
a[i, 0] = 0;
for(c = 1; c <= w; c++){
if(c[i] <= c){
if(v[i] + a[i-1, c-c[i]] > a[i-1, c])
a[i, c] = v[i] + c[i-1, c-c[i]];
else
a[i, c] = a[i-1, c];
}
else
a[i, c] = a[i-1, c];
}
}
}


Astaraki ۰۸-۱-۱۳۸۸ ۰۸:۳۱ بعد از ظهر

1(ها)ضميمه
اين مقاله هم در زمينه حل مساله کوله پشتي چندبعدي با استفاده از اتوماتاهاي يادگير است:)

Astaraki ۰۸-۱-۱۳۸۸ ۰۹:۲۴ بعد از ظهر

الگوریتم گریدی برای مساله کوله پشتی با مطلب

سريعترين راه براي يافتن يك جواب تقريبي KP استفاده از اين واقعيت است كه جواب آزاد سازي پيوسته مسئله فقط داراي يك متغير اعشاري است. الگوریتم گریدی از این مطلب برای حل مساله کوله پشتی استفاده می نماید. می توان ثابت کرد که جواب بدست آمده بطور متوسط نزدیک به جواب بهینه است.
برنامه الگوريتم گريدي برای مساله کوله پشتی با مقادیر ۰ و ۱ به زبان مطلب و بصورت پنجره فعال بصورت زیر است.
فرض می شود اشیا براساس نسبت وزنی مرتب شده اند
كد:

n=input('n = ');
c=input('c = ');
d=1:n;
p=input('(pj) = ');
w=input('(wj) = ');
 
bn=0;
for bb=1:n-1;
    if (p(bb)/w(bb))<(p(bb+1)/w(bb+1))
        bn=1;
        break;
    end
end
if bn>0
    ERROR=' The items not sorted correct  TRY AGAIN '
    break;
end
 
cc=c;
s=0;
jj=1;
for j=1:n
    if w(j)>cc
        d(j)=0;
    else
        d(j)=1;
        cc=cc-w(j);
        s=s+p(j);
    end
    if p(j)>p(jj)
        jj=j;
    end
end
if p(j)>s
    s=p(jj);
    for j=1:n
        d(j)=0;
    end
    d(jj)=1;
end
x=d
zq=s



زمان محلي شما با تنظيم 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.