知能科学:グラフと経路計画
|
|
- としみ いくのや
- 5 years ago
- Views:
Transcription
1
2 4 5
3
4
5
6 MTLB names = {,,,...,,,,...,,, }; snode = [,,, 4, 5, 5,... 6, 7, 7,,, 0 ]; tnode = [,, 4, 5, 6, 8,... 7,,, 9, 0, ]; dist = [ 4, 6, 8, 56,, 69,... 46,, 7, 0, 9, 54 ]; g = graph(snode,tnode,dist,names);
7 MTLB plot(g);
8 MTLB plot(g, EdgeLabel,g.Edges.Weight);
9 MTLB x = [ 4,, 0,, 5, 7, 6, 6, 0, 0, 4.5 ]; y = [ 0, 0, 0,,,, 0, 5,, -, - ];
10 MTLB plot(g, XData,x, YData,y);
11 MTLB plot(g, XData,x, YData,y, EdgeLabel,g.Edges
12 (shortest path) >> shortestpath(g,, ) ans = 6 cell
13 B D E 5 G C 6 F 4 G
14 B D E 5 G C 6 F 4 B E D G = = 9
15 B D E 5 G C 6 F 4 B, E, D B, E, D G
16 4 B D E G C F
17 4 B D E G C F 4 G
18 S G S S G G S G
19 Edsger Dijkstra (90 00) (959) 97
20 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z
21 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z
22 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z
23 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z = 9 + =
24 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z = 9 + = = =
25 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z = 9 + = = = 4 + = 5
26 S 0 4 P 9 6 Q 8 R 4 4 X U Y V W Z = 9 + = = = 4 + = = S P Y
27 S 0 P 9 Q 8 R X Y Z U V W Y = Y
28 S 0 P 9 Q 8 R X Y Z U V W P Y X S P X
29 0 B C D E F 5 4 G : ( 0)
30 0 B = =0 0+= 6 C D E F 5 4 G
31 0 B = =0 0+= 6 C D E F 5 4 G
32 0 B C D E F 5 4 G C
33 0 B E =4 0 D 0+0=0 +6=9 6 +=6 C F 5 4 G
34 0 B E =4 0 D 0+0=0 +6=9 6 +=6 C F 5 4 G
35 0 B C D E F 5 4 G B
36 0 B E =8 0 D 0+0=0 +6=9 6 +=6 C F 4+=5 5 4 G
37 0 B E =8 0 D 0+0=0 +6=9 6 +=6 C F 4+=5 5 4 G
38 0 B C D E 5 F 5 4 G E
39 0+0=0 +6=9 += C D E B F G =8 5+5=0 5+=7
40 0+0=0 +6=9 += C D E B F G =8 5+5=0 5+=7
41 0 B C D E 5 6 F 5 4 G F
42 0+0=0 +6= C D E B F G =8 5+5=0 5+=7 6+4=0 6+=9
43 0+0=0 +6= C D E B F G =8 5+5=0 5+=7 6+4=0 6+=9
44 0 B C D 7 E 5 6 F 5 4 G D
45 0 B C E 5+5=0 5 5 D G 7+= =0 6 4 F
46 0 B C E 5+5=0 5 5 D G 7+= =0 6 4 F
47 0 B C D 7 E 5 6 F 5 4 G 9
48 , ()
49 ,? B 4,? 4 0,? 6 C D,? E,?,? F 5 4 G,? : :?
50 B 4,? 4 0 0,,? C 6 D,? E,?,? F 5 4 G,? 0,
51 0+4=4< 0, C D E B F G 5 4,?,?,?,?,?,? 0+0=0< 0+=<
52 0, B E 4 4, 4,? 0 D 0,,?, 6,? 4 C F 5 G <
53 0, B E 4 4, 4,? 0 D 0,,?, 6,? 4 C F 5 G
54 0, B E 4 4, 4,? 0 D G 0,,?, 6,? 4 C F C 5
55 0, B E 4 4, 4,? 0 D G +6=9<0 0,,?, 6,? 4 C F +=6< 5
56 0, B E 4 4, 4,? 0 D 9,C,?, 6 6,C 4 C F 5 G <
57 0, B E 4 4, 4,? 0 D 9,C,?, 6 6,C 4 C F 5 G
58 0, B E 4 4, 4,? 0 D 9,C,?, 6 6,C 4 C F B 5 G
59 0, B E 4 4, 4,? 4+4=8<9 0 D 4+=5< 9,C,?, 6 6,C 4 C F 5 G
60 0, B E 4 4, 4 5,B 0 D 8,B,?, 6 6,C 4 C F 5 G <
61 0, B E 4 4, 4 5,B 0 D 8,B,?, 6 6,C 4 C F 5 G
62 0, B E 4 4, 4 5,B 5 0 D 8,B,?, 6 6,C 4 C F E G
63 0, B E 5+5=0< 4 4, 4 5,B 5 5+=7<8 0 D G 8,B,?, 6 6,C 4 C F
64 0, B E 4 4, 4 5,B 0 D 7,E 0,E, 6 6,C 4 C F 5 G <
65 0, B E 4 4, 4 5,B 0 D 7,E 0,E, 6 6,C 4 C F 5 G
66 0, B E 4 4, 4 5,B 0 D G 7,E 0,E, 6 6,C 4 C F F 5
67 0, B E 4 4, 4 5,B 5 0 D G 6+=9>7 7,E 0,E, 6 6,C 4 6+4=0=0 C F
68 0, B E 4 4, 4 5,B 0 D 7,E 0,E, 6 6,C 4 C F 5 G <
69 0, B E 4 4, 4 5,B 0 D 7,E 0,E, 6 6,C 4 C F 5 G
70 0, B E 4 4, 4 5,B 0 D G 7,E 0,E, 6 6,C 4 C F D 5
71 0, B E 4 4, 4 5,B 5 0 D G 7+=9<0 7,E 0,E, 6 6,C 4 C F
72 0, B E 4 4, 4 5,B 0 D 7,E 9,D, 6 6,C 4 C F 5 G <
73 0, B E 4 4, 4 5,B 0 D 7,E 9,D, 6 6,C 4 C F 5 G
74 0, B E 4 4, 4 5,B 0 D 7,E 9,D, 6 6,C 4 C F G 5 G
75 () 007 () () ()
76 /
77 05 06 ()
78
79
80
81
82
83
84
85
86 ) two-person zero-sum finite deterministic perfect information =
87
88 + 0
89
90
91
92
93
94 (+) ( ) (e.g ) ()
95
96
97
98
99 (mini-max)
100 局面における場合の数 知能科学 グラフ と経路計画 平井 慎一 目次 < グラフ < 最短経路問題 ダイクストラのア ルゴリズム 原理 例 ラベリング ゲーム木 まとめ < <
101
102
U(a, b) U(a, b) ( a, b ) X U(0, 1) Y U(a, b) Y = (b a)x + a S 1 = x 2 dx y = 1 x 2 y x N(0, 1) randn 0 1 p(x) = 1 e x2 2 2π x [ 0, 1 ],
uniform.m 1 2 3 4 >> uniform 0.81472 0.90579 0.12699 0.91338 0.63236 0.09754 0.2785 0.54688 0.95751 0.96489 >> uniform 0.15761 0.97059 0.95717 0.48538 dice.m 0.80028 0.14189 0.42176 0.91574 0.79221 function
More information2007.3„”76“ƒ
76 19 27 19 27 76 76 19 27 19 27 76 76 19 27 19 27 76 76 19 27 19 27 76 1,27, 2, 88, 8,658 27, 2,5 11,271,158 1,712,876 21,984,34 1,, 6, 7, 2, 1,78, 1,712,876 21,492,876 27, 4, 18, 11,342 27, 2,5 491,158
More information1631 70
70 1631 1631 70 70 1631 1631 70 70 1631 1631 70 70 1631 1631 70 70 1631 1631 70 70 1631 9,873,500 9,200,000 673,500 2,099,640 2,116,000 16,360 45,370 200,000 154,630 1,000,000 1,000,000 0 648,851 730,000
More information72 1731 1731 72 72 1731 1731 72 72 1731 1731 72 72 1731 1731 72 72 1731 1731 72 12,47,395 4, 735,5 1,744 4,5 97, 12,962,139 6,591,987 19,554,126 9,2, 4, 7, 2, 9,96, 6,591,987 16,551,987 2,847,395 35,5
More informationQ.5-1 Ans.
5 Q.5-1 Q.5-2 Q.5-3 Q.5-4 Q.5-5 Q.5-6 Q.5-7 Q.5-8 Q.5-9 Q.5-10 Q.5-11 Q.5-12 Q.5-13 Q.5-14 Q.5-15 Q.5-1 Ans. Q.4-5 1 Q.5-3 Check Q.5-2 200 203 197 199 Q.5-2 Ans. Check Q.5-3 Ans. Q.5-2 12 Q.6-4 69 56
More informations t 1, 2,..., 10 s t a, b,..., k t s 1, 2,..., 10 1 a, b,..., k 1 s t ts 1 0 ( 2.25) ½ ¾ ½¼ x 1j = 1 x 2c = 1 x 3e = 1
72 2 2 2 2.24 2 s t, 2,..., 0 s t a, b,..., k t s, 2,..., 0 a, b,..., k s t 0 ts 0 ( 2.25) 2.24 2 ½ ¾ ½¼ x j = x 2c = x 3e = x 4s = x 5g = x 6i = x 7d = x 8h = x 9f = x 0k = x ta = x tb = x ts = 9 2.26
More information2 ZERO07 11 4 DNA
1 2 ZERO07 11 4 DNA http://www7a.biglobe.ne.jp/~hakatabay/tvsyoukai353.pdf 3 4 5 5 6 7 8 http://ja.wikipedia.org/wiki/%e5%85%ab%e5%8d%a6 http://ryugen.exblog.jp/12094785 9 10 11 23-1 1-3 3-5 5-7 7-9 9-11
More informationuntitled
1. 2. 3. 4. 5. 6. 7. 8. 9. 07060121 07060121 07060121 07060121 KA12345 200,000 1301 0089-339 1 07060121 KA12345 200,000 1 1301 0089-339 07060121 07060121 A 100,000 07060121 07060121 07060121 07060121 07060121
More informationCity Information City Information City Information City Information City Information City Information City Information City Information City Information City Information http://www.jmsfmml.or.jp/msm.htm
More informationt s s A
%7 25802FAX 025872 http://www.ity.nok.niit.jp 2 6 6000 9 9 t s s A NAGAOKA NAGAOKA 2 3 4 8.5 65 65 8.5 8 65 0.5 0.75.25.5,,,,,,,,,,,,,,, 65 NAGAOKA 23 25 25 8 2 6 7 8 9 3 FAX NAGAOKA 0 2 4 2 6 00 3 2 t
More informationPowerPoint Presentation
最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}
More information70 3 70 70 70 70 3 70 70 300 3 5
70 3 2611 25920 70 3 70 70 70 70 3 70 70 300 3 5 70 1 1 2 2 MAX 3 1 1 2 2 MAX 3 25 27 30 50 70 1 2 3 1 70 3 P oint 300 P oint 20 30 40 50 3 2 1 1 14 15 10 11 8 5 5 5 5 95.2 68.7 95.7 94.0 97.7 P oint
More informationExcel基礎講座演習-表紙とはじめにv1.3.doc
Future Lifestyle Inc. IT Microsoft Excel 2000 Microsoft Microsoft Corporation B4 11 14 1999 1 C4 E7 C4 E7 2 =C4+D4+E4 SUM MAX MIN B3 F7 Sheet2 1999 2000 3 B3 F7 C4 F7 Delete C4 F7 SUM SUM() C4 SUM 4 B3
More informationuntitled
Excel A D-2 B-2 D-2 B2 C-2 D-2 C2-23 - Enter D-2 B2(1000) C2(5) 5000 D-2 (D-2) (D-2) (D-3) (D-6) - 24 - (D-3) (D-6) D (D-2) =B2*C2 (D-3) =B3*C3 (D-4) =B4*C4 Excel - 25 - $A$1 1000 A-1 (B-1) =$A$1 (B-1)
More informationNetworkKogakuin12
最短経路をもとめるダイクストラ法 ダイクストラ法はグラフの各点から特定の点への最短距離 ( 経路 ) を逐次的に (= 1 台のコンピュータで ) もとめる方法である. ダイクストラ法 = ダイクストラののアルゴリズム 数学的なネットワーク ( グラフ ) のアルゴリズムとしてもっとも重要なものの ひとつである. 入力 グラフ ( ネットワーク ) グラフ上の終点 ( 特定の点 ) 14 3 4 11
More information21 22 4 5 23 3 11 24 4 23 FAQ 2
21 22 4 5 23 3 11 24 4 23 FAQ 2 3 4 A 15 5 8 19 13 19 5 6 14 5 16 5 9 20 22 18 B 29 30 5 17 47 51 26 18 21 22 27 5 3 48 103 11 3 10 C 7 22 44 103 107 117 127 7 18 5 7 8 5 1 2011 5 24 2 6 22 3 7 27 4 9
More information財務情報
50 Financial Information >> 52 54 66 68 69 71 72 51 2004 4,625,151 2,605,343 2,019,807 N/A 373,435 139,401 234,034 (7,603) 2005 2006 2007 2008 2008 4,664,514 4,637,657 4,769,387 6,409,727 $ 63,976 2,650,586
More informationmedical product information 74
73 medical product information medical product information 74 75 medical product information 76 medical product information 77 medical product information 78 medical product information 79 medical product
More informationuntitled
1 Report 3 4 8 10 14 16 Topics 18 18 19 19 20 20 21 21 22 23 Information 25 25 2013.9 No.80 1 2 2013.9 No.80 Report 2013.9 No.80 3 4 2013.9 No.80 2013.9 No.80 5 6 2013.9 No.80 2013.9 No.80 7 8 2013.9 No.80
More informationuntitled
Report 1 2 2 3 5 7 10 12 14 Topics 16 17 18 19 20 21 Information 25 25 Report 2015.9 No.86 1 2 2015.9 No.86 2015.9 No.86 3 4 2015.9 No.86 2015.9 No.86 5 6 2015.9 No.86 2015.9 No.86 7 8 2015.9 No.86 2015.9
More information