واضی فایل
دانلود کتاب، جزوه، تحقیق | مرجع دانشجوییواضی فایل
دانلود کتاب، جزوه، تحقیق | مرجع دانشجوییپاورپوینت در مورد مسأله مجموع زیرمجموعه ها
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : .ppt ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 10 اسلاید
قسمتی از متن .ppt :
Backtracking
1
مسأله مجموع زیرمجموعه ها
n عدد صحیح مثبت wi و یک عدد صحیح مثبت M وجود دارد. هدف یافتن تمام زیرمجموعه های اعداد صحیح است به طوری که مجموع آنها M باشد.
مثال:
n=5, M=21, w=(11,5,6,16,10)
5+6+10=21, 5+16=21, 10+11=21
حل با استفاده از روش ایجاد درخت فضای حالت
Backtracking
2
0
2
0
2
2
0
0
درخت فضای حالت (n=3, M=6, w=(2,4,5
6
6
11
7
9
4
5
4
4
2
5
5
5
5
4
0
0
0
0
0
0
w2=4
w1=2
w3=5
تعداد گره ها: 1+2+22+…+2n=2n+1-1
Backtracking
3
حل مسأله
برای تعیین گره های وعده گاه اعداد را به صورت غیرنزولی مرتب می کنیم.
در سطح i ام , wi+1 کمترین وزن باقی مانده را دارد.
اگر weight مجموع اعداد تا گره سطح i باشد:
weight+ wi+1 >M ام غیر وعده گاه i گره
اگر total مجموع اعداد باقی مانده باشد:
weight+ total >M ام غیر وعده گاه i گره
اگر weight=M آنگاه یک جواب در آن گره به دست آمده و باید به عقب برگشت و مسیر جدید را شروع کرد.
آرایه include[1..n] : در صورتی که عدد iام انتخاب شود include[i]=“yes” در غیر اینصورت include[i]=“no”
Backtracking
4
درخت فضای حالت برای n=5, M=21, w=(5,6,10,11,16)
0
5
0
5
5
0
11
11
21
15
16
6
6
6
5
10
10
10
6
0
0
0
0
0
w2=6
w1=5
w3=10
0
w4=11
w5=16
5
16
11
0
21
16
5
0
6
17
11
0
16
10
10
0
10
21
11
0
