幅優先探索・深さ優先探索・A*アルゴリズムの説明
【この記事について】
8パズルを題材にして各アルゴリズムを説明する。
予備知識を必要としないように書いた。
【用語解説】キュー（queue）
先に入れたものが最初に出てくる箱。後に入れたものは後から出てくる。食堂で並んでいるときのように最初に来た人から処理される。
幅優先探索
①動かすことができる方向をすべて試す。
②試してみて目的の状態があった場合は終了。なかった場合は動かしてみてできた状態をすべてキューに入れる(このときキューに入れる順番は問わない)
③キューから一つ状態を取り出す。この状態で①からの作業を繰り返す。
以上を行うことで最初の状態から作ることができる状態を満遍なく試してみることができるが、当然効率はよくない。
(幅優先探索の例。8パズルと必ずしも一致しない。数字は試してみる順番で、1が最初の状態。Wikipediaより)
実装において
アルゴリズムを高速化するために、既に過去に一度試している状態に遭遇した場合は、その状態をキューに入れない処理を加える。
【用語解説】スタック（stack）
後から入れたものが先に出てくる箱。先に入れたものが後に出てくる。食器棚に積まれた皿を取り出すときと同じ。
深さ優先探索
①動かすことができる方向をすべて試す。
②試してみて目的の状態があった場合は終了。なかった場合は動かしてみてできた状態をすべてスタックに入れる(このときスタックに入れる順番は問わない)
③スタックから一つ状態を取り出す。この状態で①からの作業を繰り返す。
深さ優先探索ではひとつの動かせる方向を見つけたら、ひたすら突き進む。
(深さ優先探索の例。8パズルと必ずしも一致しない。数字は試してみる順番で、1が最初の状態。Wikipediaより)
実装において
8パズルでは空いたマスさえあれば駒を動かせることができる。そのため、特に深さ優先探索では途中で目的の状態に到達できればよいが、できなかった場合には無限に探索を続けることになる。そのため、8パズルの最大手数は31手ということを利用して、探す深さに31手という制限をかけた深さ制限探索を用いる。
【用語解説】マンハッタン距離
二つの座標の差（の絶対値）の総和。直線距離(ユークリッド距離)ではないやつ。
(二つの座標間のマンハッタン距離は一つに定まる。どのルートを通っても同じ距離となる。Wkipediaより)
A*アルゴリズム
目的の状態までのかかる手数を予想することで効率を改善したアルゴリズム。
①動かすことができる方向をすべて試す。
②試してみて目的の状態があった場合は終了。なかった場合は動かしてみてできた状態全てにおいて「最初の状態(①の状態ではなく一番最初に与えられた状態)から今の状態までにかかった手数＋h(x)」を計算し、箱に入れる。
③箱の中から計算結果が一番小さい状態を選び取り①に戻る。
h(x)をヒューリスティック関数という。これが目的の状態までかかる手数の予想を担う部分。８パズルにおけるh(x)は
・各駒の今の状態と目的の状態における配置とのマンハッタン距離の和
・各駒の今の状態と目的の状態における配置とのマンハッタン距離の二乗の和
・各駒の今の状態と目的の状態における配置とのマンハッタン距離の和＋マンハッタン距離の標準偏差
が考えられる。
また、h(x)を真の最短手数よりも短いものにしたときにA*アルゴリズムは最短距離を返す
【余談ではあるが】
Supremeのお香はこれらしい
Amazon | SATYA サイババナグチャンパ スティックタイプ 6箱セット | SATYA（サティヤ） | お香
【参考文献】
Java。A*アルゴリズムのプログラム例。ハッシュ関数に最小完全ハッシュ関数を使っている。各マスの動ける方向をハードコーディングしている。
リスト1●「8パズル」を幅優先探索で解くプログラム | 日経 xTECH（クロステック）
https://www.jstage.jst.go.jp/article/konpyutariyoukyouiku/21/0/21_78/_pdf
A*アルゴリズムの改良について。h'(x)に「マンハッタン距離」を使うと特定の状況では「目的の状態との異なるマスの数」に評価関数として劣ることを指摘。目的の状態とのマンハッタン距離が全てのコマで似た値となる場合、全てのコマを同じ程度の回数だけ動かせば目的の状態となることに着目し、
h'(x)=マンハッタン距離＋マンハッタン距離の標準偏差
を提案。
「(略)is not marked as serializable」が出る
【問題】
「Type 'hoge' in Assembly 'fuga, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null' is not marked as serializable.」が出る。
【状況】
のジェネリックメソッド版をVisual Studioで実装しようとしていたときに発生した。
【解決方法】
ディープコピーしたいクラス(hogeクラス)の先頭に
[Serializable]
public class hoge
{
（省略）
}
のように書き加える。
Pornhubの開発者ブログが面白かった。
Pornhubというポルノ動画共有サービスがある。PHPエンジニアを募集していることで有名。
大人気ポルノサイトなので世界中に大量のユーザがおり、大量のデータが残る。
それを統計的解析をしたのがPornhub insights(
https://www.pornhub.com/insights/)で、はてブできないことで有名になった。
以下の投稿が面白かった。
Pornhub Pizza Delivery: Always Hot and Fresh – Pornhub Insights
海外のポルノビデオの定番のシナリオとしてピザの配達員と行為に及ぶのがある。通称、ピザポルノ。「pizza delivery」「big sausage pizza」「pizza boy」でユーザが検索するほど定番らしい。ピザポルノが世界でもっとも人気のない国は日本とのこと。
https://www.pornhub.com/insights/os-battle
ユーザが使用しているOSの話。Linux,Windows2000でアクセスするユーザがわずかにいるのがすごい。ゲーム機だとWiiからのアクセスもある。Macユーザは平均9分31秒滞在し、8.85ページを閲覧するとかもある。Linuxでアクセスするユーザの2割がインドかららしい。理由がわからんが面白い。
https://www.pornhub.com/insights/fidget-spinner
ハンドスピナーが売れたとき、pornhubでも検索ワードとしてハンドスピナーが人気だった。
https://www.pornhub.com/insights/christmas-holiday-searches
クリスマスにおけるPornhubのアクセス動向。家族とクリスマスを過ごす習慣のある国である英国、オーストラリア、カナダ、イタリアではアクセス数が顕著に下がる。一方で、日本、インド、ロシアではアクセス数が増加する。Pornhubではこれらの国ではクリスマスを熱心に祝わないからだと結論している。また旅行の時期でもあるので、デスクトップPCからのアクセスは下がり、携帯用端末からのアクセスが増える。「いたずらなサンタ」や「クリスマスプレゼント」など季節感ある検索ワードも人気となる。
https://www.pornhub.com/insights/long-short-porn-watching
動画ジャンルごとの視聴時間について。下手に紹介するより本文を読んだほうが面白い。
emacsでCtrl+Cでコピー、Ctrl+Vで貼り付けをやる
emacsでWindows流の操作（Ctrl+Cでコピー、Ctrl+Vで貼り付け、Ctrl+Zで戻す）をわざわざ設定するとバカにされるが、まあ慣れとかそういうのもある。
やり方（Macの場合）
①ターミナルで「cd .emacs.d」と「emacs init.el」を叩く。
②以下を貼り付けて、保存。
(define-key global-map(kbd "C-z")'undo)
(define-key global-map(kbd "C-c C-c")'copy-region-as-kill)
(define-key global-map(kbd "C-v")'yank)
(define-key global-map(kbd "C-s")'save-buffer)
③emacs再起動。
注：コピーは設定の都合上、Ctrl+C(C-c)を２回叩く設定になっている。
Q. ~/.emacs.dが見当たらない！lsでも見つけられない。
A. 先頭に.がついているのは不可視フォルダなので 「ls -a」を打つと表示される。
Q. ~/.emacs.d/にinit.elがない！
A. 「emacs init.el」でinit.elを新規に作る。
Q. emacsのキーバインドをCtrl+C(C-c)でコピーに設定したが動かない！
A. Ctrl+C(C-c)は、終了コマンドの「Ctrl+C Ctrl+X(C-c C-x)」に代表されるようにキーの組み合わせとして頻繁に使われる。そのため、Ctrl+C(C-c)をコピーに設定すると他の膨大な数のコマンドに影響を与えるので設定できない。
参考:
https://emacs.stackexchange.com/questions/14322/ctrl-c-keybinding-is-having-no-effect
Herokuで画像が表示されない
【問題】
Heroku上で画像が表示されない。ローカル環境では表示される。フレームワークはSinatra。
【解決方法】
表示されない画像の拡張子が大文字の「.JPG」だった。小文字の「.jpg」に修正すると表示された。
【解決までの流れ】
①表示されない画像がHeroku上に確実にアップされていることを確認するためにターミナルで「heroku run bash」を叩いた。ファイル名を眺めていると拡張子が大文字の画像だけ表示されないことに気付いた。ローカルの場合は、拡張子が大文字の場合でも表示されたので発見が遅れた。
②ローカルの画像の拡張子を小文字に変更して、Herokuにアップし直しても直らない。おそらくファイル名の拡張子が大文字から小文字に変更された場合、Herokuはそれを変更と認識しないっぽい。
③結局、問題の画像ファイルを削除したものを一度アップすることでHeroku上から大文字の拡張子になっているファイルを削除し、拡張子を小文字に訂正したものをアップすることで問題を解決できた。
HerokuでSinatraが動かない
【問題】
HerokuにSinatraをつかったAppをデプロイした後、Appを開いても
「Application error
An error occurred in the application and your page could not be served. If you are the application owner, check your logs for details.」
と出てしまう
【解決方法】
①Appのディレクトリにconfig.ruという名前のファイルを作り、
require './hoge'
run Sinatra::Application
を書き込む。
※hogeの部分は同じディレクトリ内にあるhoge.rbに合わせる。app.rbの場合、require './app'となる。
②その後、再度デプロイ
【解決までの流れ】
①再デプロイ後、ターミナルで「heroku restart --app application_name」を打つが変化なし。
②ターミナルで「heroku logs」を打ち、ログを確認すると「 at=error code=H10 desc="App crashed" 」「configuration /app/config.ru not found」が出ていた。
③Deploying Rack-based Apps | Heroku Dev Centerを見ながらconfig.ruを追加すると直った。
・config.ruについて
config.ruはRack用の設定ファイルで、SinatraはRackを使っているのでHeroku上で動かすときに必要。
・Rackについて
サーバフレームワークとRubyフレームワークの橋渡しをするもの。Rackを間に挟むことで、サーバフレームワークはSinatraやRailsなどの各Rubyフレームワークに個別に対応する手間が省け、Rackに対応するだけでよくなる。逆にRubyフレームワーク側もApacheなどの各サーバフレームワークに個別に対応する手間が省ける。
※RailsもRackエンドポイントだからRackアプリケーションらしい
Railsのときには自動的に生成されて特に意識していなかったので、なかなかRackまで思い当たらず少し修正に手間取った。
【参考文献】
.gitフォルダが見当たらない
.(ドット)から始まる名前のフォルダは不可視フォルダ(隠しフォルダ)なので通常は表示されない。
ターミナル上で「ls -a」を打つと表示される。
.gitで検索しようとすると予測変換に「.git ない」とか「.git 表示」が出てくるので書いた。
