知能科学：グラフと経路計画

Size: px

Start display at page:

Download "知能科学：グラフと経路計画"

としみいくのや
5 years ago
Views:

2 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 ()

86 ) two-person zero-sum finite deterministic perfect information =

88 + 0

94 (+) ( ) (e.g ) ()

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 ],

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