n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i

Similar documents
job-shop.dvi

soturon.dvi

23 A Comparison of Flick and Ring Document Scrolling in Touch-based Mobile Phones

AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len(

..,,,, , ( ) 3.,., 3.,., 500, 233.,, 3,,.,, i

i


Wide Scanner TWAIN Source ユーザーズガイド

1 1 tf-idf tf-idf i

4.1 % 7.5 %

2 The Bulletin of Meiji University of Integrative Medicine 3, Yamashita 10 11

23 Study on Generation of Sudoku Problems with Fewer Clues

NotePC 8 10cd=m 2 965cd=m Note-PC Weber L,M,S { i {

28 TCG SURF Card recognition using SURF in TCG play video

28 Horizontal angle correction using straight line detection in an equirectangular image

IPSJ SIG Technical Report Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for

,,,,., C Java,,.,,.,., ,,.,, i

セゾン保険_PDF用.indd

WebRTC P2P Web Proxy P2P Web Proxy WebRTC WebRTC Web, HTTP, WebRTC, P2P i

28 Docker Design and Implementation of Program Evaluation System Using Docker Virtualized Environment

23 The Study of support narrowing down goods on electronic commerce sites

7,, i

21 Quantum calculator simulator based on reversible operation

27 1 NP NP-completeness of Picross 3D without segment-information and that with height of one

DTN DTN DTN DTN i



161 J 1 J 1997 FC 1998 J J J J J2 J1 J2 J1 J2 J1 J J1 J1 J J 2011 FIFA 2012 J 40 56

220 28;29) 30 35) 26;27) % 8.0% 9 36) 8) 14) 37) O O 13 2 E S % % 2 6 1fl 2fl 3fl 3 4

Web Basic Web SAS-2 Web SAS-2 i

o 2o 3o 3 1. I o 3. 1o 2o 31. I 3o PDF Adobe Reader 4o 2 1o I 2o 3o 4o 5o 6o 7o 2197/ o 1o 1 1o


25 Removal of the fricative sounds that occur in the electronic stethoscope


178 5 I 1 ( ) ( ) ( ) ( ) (1) ( 2 )

生活設計レジメ

44 4 I (1) ( ) (10 15 ) ( 17 ) ( 3 1 ) (2)

I II III 28 29


Web Web Web Web Web, i

IT,, i

Web Stamps 96 KJ Stamps Web Vol 8, No 1, 2004

, IT.,.,..,.. i

第 55 回自動制御連合講演会 2012 年 11 月 17 日,18 日京都大学 1K403 ( ) Interpolation for the Gas Source Detection using the Parameter Estimation in a Sensor Network S. T

19 Systematization of Problem Solving Strategy in High School Mathematics for Improving Metacognitive Ability

2007-Kanai-paper.dvi

12) NP 2 MCI MCI 1 START Simple Triage And Rapid Treatment 3) START MCI c 2010 Information Processing Society of Japan

Studies of Foot Form for Footwear Design (Part 9) : Characteristics of the Foot Form of Young and Elder Women Based on their Sizes of Ball Joint Girth

( ) [1] [4] ( ) 2. [5] [6] Piano Tutor[7] [1], [2], [8], [9] Radiobaton[10] Two Finger Piano[11] Coloring-in Piano[12] ism[13] MIDI MIDI 1 Fig. 1 Syst

1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [

先端社会研究　★５★号／４．山崎

卒業論文2.dvi

FIG 7 5) 7 FIG ) 7) 8) 9) 10) 11) 12) 3 18 Gymnastik 13) 1793 J. Ch. F. Guts Muths Gymnastik fuer die Juegend 1816 F. L. Jahn Turnkunst Rhythm

ii

SOM SOM(Self-Organizing Maps) SOM SOM SOM SOM SOM SOM i

(1 ) (2 ) Table 1. Details of each bar group sheared simultaneously (major shearing unit). 208

若者の親子・友人関係とアイデンティティ

.N...[..7...doc

untitled

i

AccessflÌfl—−ÇŠš1

kut-paper-template.dvi

2 1 ( ) 2 ( ) i

技術研究報告第２６号

29 Short-time prediction of time series data for binary option trade

58 10

2

WebRTC P2P,. Web,. WebRTC. WebRTC, P2P, i

24 Region-Based Image Retrieval using Fuzzy Clustering

On Sapir's Principles of Historical Linguistics (I) An Interpretation on Sapir's View of Language Contact Nobuharu MIWA Abstract This paper is an atte

29 jjencode JavaScript

Virtual Window System Virtual Window System Virtual Window System Virtual Window System Virtual Window System Virtual Window System Social Networking

(2003)

<836F F312E706466>

A Feasibility Study of Direct-Mapping-Type Parallel Processing Method to Solve Linear Equations in Load Flow Calculations Hiroaki Inayoshi, Non-member

kut-paper-template2.dvi

Validation of a Food Frequency Questionnaire Based on Food Groups for Estimating Individual Nutrient Intake Keiko Takahashi *', Yukio Yoshimura *', Ta



PC PDA SMTP/POP3 1 POP3 SMTP MUA MUA MUA i

九州大学学術情報リポジトリ Kyushu University Institutional Repository 看護師の勤務体制による睡眠実態についての調査 岩下, 智香九州大学医学部保健学科看護学専攻 出版情報 : 九州大学医学部保健学


,,.,.,,.,.,.,.,,.,..,,,, i

B_01田中.indd

kiyo5_1-masuzawa.indd

近畿圏鉄道市場における競争の特質

P2P Web Proxy P2P Web Proxy P2P P2P Web Proxy P2P Web Proxy Web P2P WebProxy i

14 CRT Color Constancy in the Conditions of Dierent Cone Adaptation in a CRT Display

P2P P2P Winny 3 P2P P2P 1 P2P, i

ISSN NII Technical Report Patent application and industry-university cooperation: Analysis of joint applications for patent in the Universit

149 (Newell [5]) Newell [5], [1], [1], [11] Li,Ryu, and Song [2], [11] Li,Ryu, and Song [2], [1] 1) 2) ( ) ( ) 3) T : 2 a : 3 a 1 :

86 7 I ( 13 ) II ( )

17 Proposal of an Algorithm of Image Extraction and Research on Improvement of a Man-machine Interface of Food Intake Measuring System

Abstract This paper concerns with a method of dynamic image cognition. Our image cognition method has two distinguished features. One is that the imag


SURF,,., 55%,.,., SURF(Speeded Up Robust Features), 4 (,,, ), SURF.,, 84%, 96%, 28%, 32%.,,,. SURF, i

untitled

<91818C E90B690EA97708CF696B188F58D758DC0838A815B83742E706466>

エンタープライズサーチ･エンジンQ u i c k S o l u t i o n ® の開発


Transcription:

15 Comparison and Evaluation of Dynamic Programming and Genetic Algorithm for a Knapsack Problem 1040277 2004 2 25

n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i

Abstract Comparison and Evaluation of Dynamic Programming and Genetic Algorithm for a Knapsack Problem KAKETANI Kou Knapsack problem is described as follows: there are some items with given value and volum. A knapsack has given capacity. Selected a proper subset of items to maximize the total value of selected items such that the total volume of the selected items is less than or equal to hte capacity of the knapsack. One of the easy methods for solving the problem is to investigate whole subsets of items, however, there are 2 n subsets where n is the number of items. Therefore, this brute force method is an exponentially time complexity. By this research, in order to solve a problem is two solution methods, Dynamic Programming(DP) and Genetic Algorithm(GA), are taken up, those solution methods are compared and evaluated. key words Knapsack Problem, Dynamic Programming Genetic Algorithm ii

1 1 2 3 2.1.................................. 3 2.2.................................... 3 2.3...................................... 4 3 5 3.1.............................. 5 3.2............................ 6 4 8 4.1........................... 8 4.2....................... 8 4.3........................ 10 4.3.1......................... 10 4.3.2............................. 10 4.3.3............................... 13 4.3.4.................................. 14 4.3.5................................ 17 4.3.6................................ 18 5 19 5.1............................. 19 5.1.1............................... 19 iii

5.1.2........................... 20 5.2................................. 22 6 23 25 26 iv

4.1............................ 9 4.2................................ 10 4.3 STEP1-1............................. 11 4.4 STEP1-2............................. 11 4.5 STEP1-3............................. 12 4.6 STEP2-3............................. 12 4.7 STEP2-4............................. 13 4.8................................ 13 4.9............................... 14 4.10.................................... 15 4.11................................. 15 4.12................................. 16 4.13................................. 16 4.14 2.................................... 17 4.15 2................................... 17 4.16 2................................... 18 4.17.................................... 18 v

2.1............................ 4 5.1 DP................... 20 5.2 GA................... 21 5.3.................... 22 vi

1 ( ) NP- [1] NP- [2] 2 3. 1

2

2 2.1 W p i w i n i(1 i n) J {1,2,, n} w j W p j [1] j J p j J w j j J W p j j J j J j J 2.2 3

2.3 2.3 2.3 2.1 1 12 10 2 5 3 3 2 5 4 3 1 5 8 7 10 2 5 13 1 12, 10 4 5 11 8. 4

3 3.1 (Dynamic Programming) [1] 1. 2. 3. [2] W w i 5

3.2 3.2 2.1 v[k, c](k = 1, 2, 3,, n; c = 0, 1, 2,, W ) 3.1 3.2 3.3 3.4 3.1 0 0 0 v[k, 0] = 0 (1 k n) (3.1) 3.2 1 0 p 1 v[1, c] = { 0 (0 c < w1 ) p 1 (w 1 c W ) (3.2) 3.3 3.1 3.2 v[k, c] v[k 1, c] w k v[k-1,c] w k v[k 1, c w k ] + p k v[k, c] v[v[k 1, c], v[k 1, c w k ] + p k ] 6

3.2 v[k, c] = { v[k 1, c] (c < wk ) v[v[k 1, c], v[k 1, c w k ] + p k ] (w k c) (3.3) 3.4 k 3.4 k 3.4 c w k v[k 1, c w k ] + p k = v[k, c] (3.4) w j W p j j J j J p j j J 7

4 4.1 [2] 4.2 8

4.2 No Yes 4.1 9

4.3 4.3 GA [3] 4.3.1 n l 4.2 4 7 4 0 6 2 5 1 3 0 5 2 3 1 4 6 5 6 0 3 1 4 2 3 1 5 2 0 6 4 n = 4 l = 7 4.2 4.3.2 1 2 2 1 W p i w i 10

4.3 1 1 [2310] W 8 p 0 1 p 1 5 p 2 4 p 3 2 w 0 1 w 1 3 w 2 2 w 3 5 STEP1-1 4.3 2 5 8 p 2 2 3 1 0 [p2, w2] 4.3 STEP1-1 STEP1-2 4.4 2 3 w 2 w 3 5 8 p 2 p 3 2 3 1 0 [p3, w3] 4.4 STEP1-2 STEP1-3 4.5 3 1 STEP1-2 5 w 1 10 8 1 [2310] 6 2 1 11

4.3 2 3 1 0 [p1, w1] 4.5 STEP1-3 2 1 2 [2310] 1 2 STEP2-1,2-2 1 STEP1-1,1-2 STEP2-3 4.6 3 1 STEP2-2 5 w 1 10 8 w 1 1 2 3 1 0 [p1, w1] 4.6 STEP2-3 STEP2-4 4.7 4 0 STEP2-3 5 w 0 8 8 ST EP 2 3 p 0 2 [2310] 7 12

4.3 2 3 1 0 [p0, w0] 4.7 STEP2-4 4.3.3 1 2 4.8 A 111 B 75 C 60 D 39 E 15 E 5% D 13% C 20% A 37% B 25% 4.8 13

4.3 M M/2 M 4.9 2 4 4 3 2 1 4 3 2 4 3 1 2 1 4 3 2 4 3 1 4.9 4.3.4 1 ( ) ( ) 1 (Order Crossover : OX) (Partially Mapped Crossover : PMX) (Cycle Crossover : CX) (Uniformed Order Crossover : UOX) 4 2 P 1, P 2 P 1 O 1 P 1 P 2 O 1 P 2 O 2 4.10 14

4.3 P1 : 4 0 1 5 3 2 P2 : 1 2 3 5 4 0 O1 : * * * 2 3 5 P2 O1 : 4 0 1 2 3 5 4.10 2 P 1, P 2 P 2 O 1 P 1 P 2 P 2 O 1 O 2 4.11 P1 : 4 0 1 5 3 2 P2 : 1 2 3 0 4 5 O2 : 1 2 3 * * * P1 : 4 0 1 5 3 2 P2 : 1 2 3 0 4 5 O2 : 1 2 3 5 4 * P1 : 4 0 1 5 3 2 P2 : 1 2 3 0 4 5 O2 : 1 2 3 5 4 0 4.11 P 1 1 O 1 O 1 1 P 2 1 P 1 O 1 P 2 15

4.3 4.12 P1 : 4 0 1 5 3 2 P2 : 1 2 3 5 4 0 O1 : 4 * 1 * 3 * P1 : 4 0 1 5 3 2 P2 : 1 2 3 5 4 0 O1 : 4 2 1 5 3 0 P1 : 4 0 1 5 3 2 P2 : 1 2 3 5 4 0 O1 : 4 2 1 * 3 0 4.12 2 2 1 P 1 O 1 2 0 P 2 O 2 O 1 O 2 4.13 P1 : 4 0 1 5 3 2 P2 : 1 2 3 5 4 0 T : 0 0 1 0 1 1 P1,P2 P1 : 5 4 0 P2 : 3 4 0 O1 : * * 1 * 3 2 O2 : 1 2 * 5 * * O1 : 5 4 1 0 3 2 O2 : 1 2 3 5 4 0 4.13 16

4.3 4.3.5 1 [4] 2 2 2 3 2 2 2 P1 : 4 0 1 5 3 2 P1 : 4 2 1 5 3 0 4.14 2 2 2 2 P1 : 4 0 1 5 3 2 P1 : 4 2 3 5 1 0 4.15 2 2 2 2 17

4.3 P1 : 4 0 1 5 3 2 P1 : 4 3 2 0 1 5 4.16 2 4.3.6 4.17 Fittness( ) Generation( ) T Fittness T Generation 4.17 18

5 5.1 5.1 3. ( ) = ) ( ) (5.1) 5.1.1 5.1 20 19

5.1 5.1 DP (sec) 100 10,000 0.011 10 6 250 4,000 0.012 500 2,000 0.014 100 100,000 0.110 10 7 200 50,000 0.123 500 20,000 0.115 250 400,000 1.503 10 8 500 200,000 1.331 625 160,000 1.342 5.1.2 2 10 3 2 50 100 5,10,50 3 50 50,100,200 100 2 1 100 5 5.2 50,100,200 20 5.2 20

5.1 5.2 GA (sec) 50 100 0.20004 50 300 0.14657 50 500 0.244389 50 1,000 0.186743 50 10,000 0.244376 100 100 0.968563 100 300 0.984723 100 500 1.124372 100 1,000 1.074637 100 10,000 0.987432 200 100 3.973007 200 300 3.223305 200 500 3.352162 200 1,000 3.223874 200 10,000 3.352948 21

5.2 5.2 4 20 100,000 1,000,000 10,000,000 100,000,000 5.3 10 5, 10 6, 10 7, 10 8 20 10 5 = 2, 000 50 10 6 = 12, 500 80 10 7 = 100, 000 100 8 = 625, 000 160 5.3 10 5 10 6 10 7 10 8 (DP) 558 647 771 1,201 (GA) 556 626 748 1,081 DP (sec) 0.001 0.012 0.129 1.306 GA (sec) 0.050 0.146 0.284 0.554 22

6 20 5.1 5.1 5.1 5.2 5.3 10 8 23

24

2002 7 2004 2 25

[1] 2003. [2] : 2002. [3] GA 2002. [4] 1993. [5] T. C. R. [ 2 ] 1995. 26

2024 © docsplayer.net プライバシー | 利用規約 | フィードバック