English
日本語
한국어
简体中文
繁體中文
Italiano
español
Deutsch
Русский
前回はプログラミングで何ができるのかについてお話しました。
今回はその逆で、プログラミングでできないことについてお話したいと思います。
ひとくくりに「できないこと」、といっても何通りか種類があるので、 今回は長ーい時間がかかる系の「できない」にフォーカスしたいと思います。
みなさんパソコンを使っていて「すごい待たされるなー」とか思ったことはありませんか？ たとえばOSのアップデートとか…たまに一晩とかかかりますよね。
でも今回お話する「長い時間」というのはその比ではありません。
宇宙ができたタイミングで計算をスタートしてもいまだに終わらないかも…というレベルの「長い時間」です。
この類の問題で一番よく知られている問題といえば「巡回セールスマン問題」です。
こういう問題です。
「あるセールスマンが、コンビニに営業をかけに行くことになりました。コンビニの数はとてもたくさんあるので、と考えました。そのためにはどの順番でコンビニを巡ればよいでしょうか？」
- リストアップしたすべてのコンビニを1度ずつ訪問しながら
- でも最短距離で回りたい
あの順番・この順番…とあれこれ試しながら探していくわけですが、今のところ、これを確実に短時間で解ける方法というのはまだ見つかっていません。
存在するかしないかもはっきりしないので、もしかしたら一発逆転があるかもしれないのですが、多くの研究者は悲観的です。
念のためですが、お店の数が少なければ解けます。
Wikipediaを観ると、「20以上になると現実的でない」と書かれていますね。
世界中のコンビニ全部とかになると宇宙が終わる方が早いかもしれません。
さて、「こんな問題、どこで使うの？」と思われた方もいらっしゃるかもしれません。
実は、うっかりこの形になってしまう事がよくあります。
たとえば機械翻訳(英語を日本語に訳すような)も、初期のころの翻訳方法はこれと同じ問題をはらんでいたと指摘されています。(Knight, 1999)
ものすごい大ざっぱな説明を試みてみましょう。 何語でも良いんですが、今回は英日翻訳を考えます。
当時の翻訳は大きく分けて2ステップからなっていました。
- 入力された英単語について、対応する日本語の単語を列挙します。
- その日本語の単語を1つずつ使いながら正しい順番に並べます。
ここでいう、日本語単語が巡回セールスマン問題でいう「コンビニ」、単語の順番が「コンビニを巡る順番」です。
さらに、出力される日本語文が元の英文の翻訳になっている確率というのを考えるのですが、これが巡回セールスマン問題の「距離」に対応します。
「できるだけ良い翻訳を探そう」という動機でがむしゃらに翻訳文を生成しようとすると、すごい時間がかかってしまうということになります。
実際にはそれでは使い物にならないので、適当な計算でごまかして早く結果を求める工夫をしていました。
コンピュータでできること・できないことについてのお話はいかがでしたか？
できないことの話はちょっと後ろ向きでしたね。
でもこういった問題を何とか解こうとしている研究者も沢山います。
「ちょっと速くなった」というニュースが流れたらその裏では研究者の涙ぐましい努力があることでしょう。
【参考文献】
【宣伝】
Cafetalk開講記念クーポンを用意してます。興味を持っていただいた方はのぞいてみてくださいね。
============================
クーポン名: Cafetalk開講記念クーポン！
コード: 0dd52b94
割引率: 20%
適用レッスン: あなたもきっと作れる！プログラミング入門〜初級 (Python)
対象受講期間: 2018年4月3日 ~ 2018年4月30日
クーポンのURL: http://cafetalk.com/coupons/detail/?id=681238&lang=ja
(GMT+09:00 Tokyo)
============================
回應 (0)