読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

『問題をどう解くか 問題解決の理論』が面白かった

はじめに

何らかのプログラミングを書くときに、多くの場合、何らかの「問題」に対して、どういう風にアプローチし、解決するかという目的があるように思う。その時に、何らかの問題に対して、どういう風に接したらいいのかわからないことがたまにある。

大抵の場合は経験則であったりとか、あるいは試行錯誤の末に解答に何とか辿り着くというパターンがあると思う。もちろん、こういう側面があるのは仕方ないけれど、もう少し体系立ったものにしたい、と思って、本屋をうろついてたら、ちょうどちくま学芸文庫のMath & Scienceシリーズから下の本が出ていたので読んでいたら、思いの他面白かったので、書評を書こうと思う。

問題をどう解くか: 問題解決の理論 (ちくま学芸文庫)

問題をどう解くか: 問題解決の理論 (ちくま学芸文庫)

  • 作者: ウェイン・A.ウィケルグレン,Wayne A. Wickelgren,矢野健太郎
  • 出版社/メーカー: 筑摩書房
  • 発売日: 2014/08/06
  • メディア: 文庫
  • この商品を含むブログを見る

本書の位置づけ

例えば、日本においても、解法の参考書として親しまれている本の一つに、下の本がある。

いかにして問題をとくか

いかにして問題をとくか

文庫版の解説にも書かれている通り、この本は、上記本に影響を受けているらしい。また、この解法のモデリングの仕方が、例えば人工知能の話に似ているのが非常に面白い。

例えば、この本の「第五章」は「状態評価と山登り法」という章なのだが、ここにおいて「ゴールの状態も含むすべての状態に対して、1つの評価関数を定義する」とし、「ゴールの状態により近い評価をもつ次の状態を達成するために、任意の与えられた状態における行動を選ぶ」ことを、一つの解決法としている。本書には、このことを「山登り法」としている。

このあとに書くけれども、ある問題に対して、本当にゴールに向かっているかどうか、というものを評価する関数を定義するという方法については、例えば「将棋においてどのような手を打てば有利なのか」ということを判別するために使われる方法だと記憶している。

明確に、この本は第一章の「諸言」において、「人工頭脳の研究」と「人間が問題を解くことの計算機シミュレーションを可能にした1950年以降」における影響を隠してはいない。

本書の面白さについて

とはいえ、このように書いたとしても、別に「人工頭脳」とか、そういう素養が無くても十分に読み進められる。むしろ、本書の特色はパズルブックみたいな形で問題が与えられ、その問題に対するアプローチを一つ一つ段階的にヒントとして与えていくという形で、いつの間にか「考え方」の筋道を与えていく部分にあると思う。

引用

例えば、本書から一つ問題を引用してみよう。これはたぶん勘のいい人ならすぐに解けるかもしれないけれど。

abcabcの形のすべての6桁の数(たとえば416416, または258258)は、13で(きっちり)割りきれることを証明せよ.

検証としては簡単で、

  • aには1-9の9種類
  • bにはaの数を除き、0を含む9種類
  • 最後のcに関してはa, bを除く 8種類

の積である 9 * 9 * 8 = 648の組み合わせを虱潰しに13で割っていけばいい。

例えば、下のような検証用のRubyのコードを書けば、全ての組み合わせが13で割りきれることが確認できるはずだ。

seed = "1234567890".each_char.to_a
abc_list = []

def all_combination(process, result=[])

  # Array.combinationを使うと [1, 2, 3]と[3, 2, 1]の表現が
  # 出来ないので、改めてそのような関数を定義する
  
  start_process = []
  if result.length == 3
    if result[0] != "0" && result.uniq.length == 3 
      return [(result.join * 2).to_i]
    end
    return []
  else
    process.each do |x|
      start_process += all_combination(process.select {|y| y != [x]} , result + [x])
    end
    return start_process
  end
end

abc_list = all_combination(seed)
puts "組み合わせ数 :: #{abc_list.length} "

mod13 = abc_list
  .map { |x| x % 13 }
  .select { |x| x == 0 }
  .length

puts "mod13 :: #{mod13}"

確かに、この手の力技の解決方法は、四色問題においてなされることではあるものの、上記の問題には、ちゃんとした解決が載っている。ちゃんとした証明について、気になった人は本書のp.57を見てもらうとして、この問題について、どういう風にアプローチを使うべきかのヒントが書かれている。この問題の場合ならば

  • 決定的なステップは、abcaabcの形の数の なんらかの数値的な性質を知っているかどうかを考えてみるところ
  • abcabcの形の数の数値的性質を抜き出すことを考えてみよ
  • abcabcの形の数を他の数との積に因数分解できないかどうかを考えよ

というヒントが、随時与えられる。このように、一つずつ、解法を具体的にしていくというプロセスが書いてあり、それをトレースすることによって、いわば「解法を具体的にする」という考え方について分かるようになっているところがいいところだと思う。

問題と解決とはなにか

とはいえ、これだけだと若干寂しいので、そもそも「問題」とは何か、ということをここにメモしておく。問題に与えられている情報は、下の三つに分けられると本書では述べている。

  1. 所与(与えられた表現)
  2. 操作(1つまたはいくつかの表現に変形するもの)
  3. ゴール(目的の表現)

つまり、「何らかの状態」が与えられ、それに伴い利用が許されている操作があり、そして、何らかの「ゴール」が表現出来ると言うことができる。また、解決というのは下のように定義されている。

  1. 所与の完全な指示。ゴールが、許される一連の操作によって導くことができる、一意に決められた所与の状態
  2. 用いられるべき操作の集合の完全な指示
  3. ゴールの完全な指示
  4. 所与の状態から出発して、ゴールの状態に終わり、その次々の状態のおのおのが、その前の状態から許される行動(その前の状態における1つまたはそれ以上の表現にあてはめられる操作)によって得られるような、問題の状態の順序ずけられた系列

例えば、あるゴールが決められているということは、そのゴールに合致する「所与の状態」というのもまた存在することになる。もちろん、ゴールの種類にも二つあって、完全なゴールと、不完全なゴールが存在している。つまり、既にゴールするべき状態がはっきりしている場合と、そもそもまだどのような状態になっているかわからない状態があるということだ。

当然ながら、あるゴールを満たすためには、もっと細かいゴール条件を経路する必要が出てくることもある。これをサブゴールと本書では説明している。

まとめ

単純な問題集としても面白いのだけれど、それよりもまず、「問題を解く」といった場合や、例えば何らかの課題を解決するコードに対して、解決が出来ない場合というのは、大抵は、「解決に対する接近の仕方がわからない」場合があり、その接近の仕方を実践的に教えてくれるので、とてもよい。

ややもすれば、こういう問題と言うのはGoogleで検索して、それで済ませてしまう場合が多く、単純に「解法」だけを知るだけではなく、その「解法」の間にどういう風にその解法を導き出せばいいのか、ということを教えてくれる。

もちろん、では体系的な解法を知れば、万事解決というわけではなく、手段のために目的が転倒してしまう場合もある。例えばデザインパターンの問題も、そういうところがあると思う。普段から問題を解くことに慣れ親しんでいて、その上で、改めて「自分がやっていなかったこと」を振り返ってみて、「こういうことを意識してなかったな」ということを振り返ることが重要であるように感じた。

なので、この本でもヒントのステップのたびに「問題を解くことを試みること」ということが書いてある。それはプログラミングの場合でも同じで、体系的な理解だけではなく、実際に動かしてみて確認するという、「手を動かす」こと、つまり実践が重要なのだなと感じたりしたのだった。

問題をどう解くか: 問題解決の理論 (ちくま学芸文庫)

問題をどう解くか: 問題解決の理論 (ちくま学芸文庫)

  • 作者: ウェイン・A.ウィケルグレン,Wayne A. Wickelgren,矢野健太郎
  • 出版社/メーカー: 筑摩書房
  • 発売日: 2014/08/06
  • メディア: 文庫
  • この商品を含むブログを見る