クイズ「狼と山羊とキャベツ」（関係と行列表現とその演算）栗原正純電気通信大学情報通信工学科（2007．６．４）（2007.12.4修正） 2015/9/30 1 男、狼、山羊、キャベツ男狼山羊キャベツ 2015/9/30 2 男、狼、山羊、キャベツ、船、川船川 2015/9/30 3 船に乗る組み合わせ 2015/9/30 4 食べ（食べられ）てしまう組み合わせ男がいなくても安全な組合せ 2015/9/30 5 2015/9/30 6 2015/9/30 7 問題 1/2 • 川の左岸から右岸へ、男が、他に１つしか乗せられない船で、狼、山羊、キャベツを安全に運ぶには、どうしたらよいかを考えよう。 • ただし、男が一緒にいないと、「狼は山羊を食べてしまう」、「山羊はキャベツを食べてしまう」。 2015/9/30 8 問題 2/2 • 問１．どのような順番で運べばよいか、具体的な手順（方法）を示せ。 • 問２．少なくとも船を何回利用する必要があるかを示せ。すなわち、利用する最小回数を示せ。 • 問３．最小回数で実行できる手順は何通りあるか。また、そのすべての手順を示せ。 2015/9/30 9 M Man 男 W Wolf 狼 G Goat 山羊 C Cabbage キャベツ 2015/9/30 10 組合せ（状態）の列挙左岸 0 1 2 3 W 1 1 1 1 G C 1 1 1 1 1 1 右岸 M 1 1 W G C 1 1 M 1 1 “１” いる “０” いない。“０”を省略。各行には４個の１がたつ。たとえば、０：すべてが、左岸にいる状態。１：男のみが、右岸に渡った状態。２：男がキャベツをもって、右岸に渡った状態。３：２の状態から、男のみが、左岸に戻った状態。 2015/9/30 11 組合せ（状態）の列挙左岸右岸 W G C M 0 1 1 1 1 1 2 1 1 1 1 1 3 1 1 4 1 1 5 6 1 1 1 7 1 G C 1 1 1 1 9 1 1 10 11 1 1 1 1 1 1 1 1 1 1 1 1 13 1 1 1 1 1 1 1 1 1 12 M 1 1 8 14 15 2015/9/30 W 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 12 安全性が確保される状態左岸右岸 W G C M 0 1 1 1 1 1 2 1 1 1 1 1 3 1 1 4 1 1 5 6 1 1 1 7 1 G C 1 1 1 1 9 1 1 10 11 1 1 1 1 1 1 1 1 1 1 1 1 13 1 1 1 1 W 1 1 G C 1 1 1 1 1 M 1 1 1 1 1 12 M 1 1 8 14 15 2015/9/30 W 安全でない組合せ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 13 可能な状態推移 W G C M 0 1 1 1 1 1 2 1 1 1 1 1 3 1 1 4 1 1 5 6 1 1 1 7 1 1 9 1 1 10 11 1 1 1 1 1 1 1 1 1 1 1 12 1 13 1 1 1 0  5 1 1 2   7,11 1 3  4  5,7,13 1 5 6  0,4  1 7  8  11,13 1 9  1 10  11,15 11  2,8,10 1 1 1 M 1 1 1 2015/9/30 G C 1 8 14 15 W 1 1 1 1 1 1 1 1 1 1 1 1 2,4 12  1 1 1 13  1 14  15  10 4,8 14 関係 0  5 2  7,11 4  5,7,13 5  0,4 7  8  11,13 2,4 10  11,15 11  2,8,10 13  4,8 15  10 2015/9/30 左の情報から集合 X とその上の関係 R を作る X  0,2,4,5,7,8,10,11,13,15 (0,5), (2,7), (2,11), (4,5), (4,7), (4,13), (5,0), (5,4), (7,2), (7,4),    R  (8,11), (8,13), (10,11), (10,15),  (11,2), (11,8), (11,10),    (13,4), (13,8), (15,10)  15 関係 R の行列表現 M 0  5 2  7,11 4  5,7,13 5  0,4 7  8  11,13 2,4 10  11,15 11  2,8,10 13  4,8 15  10 2015/9/30 0 2 4 5 7 8 10 11 13 15 0 0  4 0  5 1 7 0  8 0 10 0  11 0 13 0 15 0 0 2 M  0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0  0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0  0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1  1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0  0 0 0 0 0 1 0 0 0 16 n 関係 R と行列 M n Rn  (a, b) | aから bへnステップで到達可能 1 2 3 4 5 6 7  8 M , M , M , M , M , M , M , M ,... 行列 M のベキ乗を順々に計算し、 (0,15)成分の P 値が最初に非ゼロとなった行列 M の指数部 P の値が、「求める最小利用回数」であり、非ゼロである (0,15)成分の値が「最小回数で実行できる手順（方法）の数」に対応する。 2015/9/30 17 7 実際に計算してみると M のときに、初めて (0,15) 成分の値が非ゼロの値２になる。従って、船を利用する最小回数は７回であり、７回で実行できる方法は２通りであることが示せた。具体的な方法は、次に示すグラフ表現が役に立つ。 M  7 2015/9/30 0 2 4 5 7 8 10 11 13 15 0 1 3 12 24 23 1 0 16 23 2 18 状態遷移 0  5 2  7,11 4  5,7,13 5  0,4 7  8  11,13 0 5 13 2 8 11 4,8 15  10 2015/9/30 7 2,4 10  11,15 11  2,8,10 13  4 15 10 19 以上 2015/9/30 20