正義

私は相手を見誤っている

皆、これ以上はない、完璧だ
そう思って行動している

あるいは、これはできない
○○があるから
それぞれが見えている条件や、深く根付いている感情
それ故に、行動しない

そういう人に
こうすればいいのにって
思ったり言ったりして

そうしなかったら
私の言う事聞かないなとか
私の事嫌いなんだろうなとか

やってることも感じてることも
相手にとっては精一杯なのに
それはくだらないとか簡単にどうとでもなるみたいに言って
傷つける

やりがちだけども
愚の骨頂なんだよなって
この世で最もな邪悪なんだよなって

ほんのちょっとでも
それでもその人は頑張っていると思ってあげられれば
何も失わずに済んだじゃないか、って

そうできずに
今でこそ、心の底から失いたくないと思う何かを失い続けて
手元には何も残らない
そんな私が私は嫌いだ

けれどまぁ
そこにいたらいたで
私が傷つき続けるのかもしれないけれど

それはそうとして
自分はまだまだ、なんてのを
他人に思うのは、やめたい

いつか戦わなくていい日がくるのかな
それとも死ぬまでバカみたいに、かな

鬱

自分は誰の役にも立たない
数字も生み出せないし
誰かより何かができるわけでもなく
面白い話もできない
何のために生きてるんだろう

そんなこと考えても無駄なんて分かってる

でも

そう思い悩む最後の自分まで否定しないでよ
辛い時は何もなくたって辛いのは真実じゃん
全部分かった上で悔しくて悔しくてしょうがないんだよ

鬱々としてる
何が出来ないとも思えない
けれど何もしたくない
遠大な構想とか一つ目で挫折するし
不意に力が抜けて、物を落としたりとか
またスマホが割れちゃった

こういう辛い時は
「やらなきゃいけないこと」だけじゃなく
「やるべき心がけ」みたいなものも捨ててみる
人に優しくするとか、恨みつらみを言わないとか
ばかばかしい
できないんだよ
そんな余裕ないから

そう、私は
ただの嫌なやつだ
それでいい

経路探索とA*アルゴリズム

スタートからゴールまでの最短経路を調べる

ある地点からある地点まで移動する際のルートを調べたい。
そのルートが最短であってほしい。
ゲームの自動行動や敵AIなどを作るのに使ったりする「経路探索」の考え方と「A*アルゴリズム」について解説する。

経路探索の基本

そもそも経路探索は何をするのか？

ざっくり

スタート地点から移動可能な場所を調べる。
調べた移動可能な場所から、また移動可能な場所を調べることを繰り返す。

ゴールへたどり着いたら探索完了である。
経路を作るには、ゴールへたどり着く一つ前の場所、そこからまた一つ前の場所と、逆を辿る。

こまかく

ノードの展開

調べた移動可能な場所は「ノード」と呼ばれる。
このように「調べる」ことを「ノードを展開する」とも言ったりする。
一か所を調べて得られるノードは大抵の場合一つではない。
そのため、展開したノードは何らかのデータ構造によって管理される。
配列(可変長)、キュー・スタック、二分ヒープなどだ。

ノードには以下の情報を持たせる。

• 自ノードから他ノードを展開するための情報(X, Y座標など)
• ゴールから逆を辿り経路を作成するための「自ノードの展開元のノードのポインタ」

他にも移動時の向きや行動内容などを含ませることがある。

一度探索した場所を再度探索することは原則行わない。
同じルートをぐるぐる調べ続けることになるためだ。

最短経路を知るには

ダイクストラ法

最短経路を知るには、展開したノードをスタートから近いものから優先して調べることが重要。
それがダイクストラ法である。
近いというのは移動コストのことであり、このようなグリッド構造では「歩数」ともいえる。

このコストには加算ができる。

• 険しい山道なので移動が遅いので+1
• 毒沼はできれば通りたくないので+100

というのが一例で、状況を考慮に入れた最短経路探索というのも出来る。

移動コストは重みとも呼ばれる。
グリッド構造で各ノード間の移動コストが均一であり、重みを考慮しなくていいという場合、先に見つけたものから優先*1して調べる「幅優先探索」でも同様に最短経路が求められる。

A*アルゴリズム

ダイクストラ法+距離の予想

ダイクストラ法の移動コストに
「自ノードからゴールまでの予想距離」を加えたものが
「A*(エースター)アルゴリズム」である。

評価のよい(値の低い)ノードから優先して探索が進められる。
ゴールとは反対方向も均一に調べるダイクストラ法に比べ、A*は場合によってはゴールに一直線。

評価に使う予想距離の計算式は、移動方法によっても変わる。

• 上下左右 → *2

• 斜め移動も可 → *3 または *4

この予想距離の計算に用いられる関数は「ヒューリスティック関数」と呼ばれる。

ノードを管理するデータ構造

youtu.be

ダイクストラ法やA*では、評価の良いノードから優先して探索していく。
そのため、複数ある探索予定のノードから最良のノードを探して取り出すことが繰り返される。

ノード管理をごく普通の配列で行えば、最良ノードを知るのには線形探索、取り出しでは大移動と効率が悪い。
そのため、最小値を一手で知れて、要素の追加・削除も高速な「ヒープ」がよく用いられる。

ヒープにはそのままノードを放り込むこともあれば、ヒープ+配列で管理することもある。
各ノードの評価値がばらける場合は前者、良くて数通りなら後者の方が効率が良いだろう。

なお

• A*アルゴリズム
• 上下移動のみ考慮 → 予想距離 =

という組み合わせであれば、評価値は常に2通りとなる。
2つの配列 low・high を入れ替えながら管理すれば効率もいいし実装も簡単。

A*の手順(概略)

• nodes → ノードを管理するデータ構造。
• current_node → 現在のノード。展開を行う基準地点
• goal_node → 基本は空。ゴールにたどり着いたノードを代入

nodesが空になるまでループ↓

1. current_node = nodesから最良のノードを取り出し
2. current_nodeをもとにノードを展開する。
   • 移動可能であること、既に展開されたことのあるノードでないことを確認。
   • ゴールに到達したノードであれば、goal_nodeに代入。
   • ノードには座標、スタートからの重みの累計(合計歩数)、親ノードなどの情報を持たせる。
   • 予想距離を計算。親の重み+親から自ノードへの重みを足したものが評価となる。
   • 評価の値を添えてnodesにノードを追加。
3. goal_nodeが存在すればループ中断。

↑ループここまで

goal_nodeが空でなければルートを作成する。

ワンポイント

• 調べるノードが多すぎて処理が重い場合、ノードの作成数をもとにループを打ち切らせる。
  最良ノードを記録しながら探索すれば、ある程度の精度での最短経路は見つけてくれる。
• グリッド構造では移動時の向きを考慮すれば、ノードの展開時、調べるマスを一か所減らせる。

*1:ノードをキューで管理する

*2:マンハッタン距離・都市ブロック距離

*3:ユークリッド距離

*4:チェビシェフ距離

【Ruby】最小個数部分和問題を動的計画法で解く

1 2 3 4 5

ここにある数字を好きに組み合わせて足していき、目標となる値を作れるか？
そんな問題を「部分和問題」という。

9を目標の数とする場合

• 1, 3, 5
• 2, 3, 4
• 4, 5

目標の数となる組み合わせはいくつかあり、その中でも4, 5が手っ取り早い。
このような
「目標の数を作るために、必要な数の個数は最小で何個か？」
というのを考えるのが「最小個数部分和問題」である。

これを「動的計画法」を用いて効率よく解く方法を解説する。

動的計画法を使う

1. 表を用意する

縦は計算で使用する各要素(i)、横は目標となる値(j)。
"-" の行は、いずれの要素も使用していない時を表す。

	0	1	2	3	4	5	6	7	8	9
-
1
2
3
4
5

2. 初期値を埋める

	0	1	2	3	4	5	6	7	8	9
-	0	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	0
2	0
3	0
4	0
5	0

各マスの意味は以下の通り。

要素を先頭から i 種使用して、合計 j となる時の最小個数

すると、以下の条件の時の値は、計算せずに求められる。

• j = 0

目標の値が0の時は、要素を使わずに作れるため、最小個数も0。

• i = 0, j = 1..9(目標の値)

要素を一つも使わずに0より大きな値を作ることはできないため、解なしとして∞を代入。

3. 各マスの計算

	0	1	2	3	4	5	6	7	8	9
-	0	∞	∞	∞	∞	∞	∞	∞	∞	∞
1	0	1	∞	∞	∞	∞	∞	∞	∞	∞
2	0	1	1	2	∞	∞	∞	∞	∞	∞
3	0	1	1	1	2	2	3	∞	∞	∞
4	0	1	1	1	1	2	2	2	3	3
5	0	1	1	1	1	1	2	2	2	2

i番目の要素をwとしたとき、dp[i + 1][j] の値は以下の通り。

j < w なら

• dp[i][j]

j ≧ w なら 以下の二つの内、小さい方。

• dp[i][j]
• dp[i][j - w] + 1

実装

個数制限あり

各要素は一回のみ使用可能なバージョン。

ITEM = [1, 2, 3, 4, 5]

N = ITEM.size
A = 9

memo = Array.new(N + 1) { Array.new(A + 1) }
(0..N).each { |i| memo[i][0] = 0 }
(1..A).each { |i| memo[0][i] = Float::INFINITY }

i = 0
while i < N
  j = 1
  while j <= A
    w = ITEM[i]
    memo[i + 1][j] = (
      if j >= w
        k = memo[i][j]
        l = memo[i][j - w] + 1
        k < l ? k : l
      else
        memo[i][j]
      end
    )

    j += 1
  end 
  i += 1
end

p memo[N][A]

個数制限なし

各要素は何度でも再利用可能なバージョン。

• dp[i][j - w] + 1

を

• dp[i +1][j - w] + 1

に書き換えただけである。

ITEM = [1, 3, 2, 4]

N = ITEM.size
A = 17

memo = Array.new(N + 1) { Array.new(A + 1) }
(0..N).each { |i| memo[i][0] = 0 }
(1..A).each { |i| memo[0][i] = Float::INFINITY }

i = 0
while i < N
  j = 1
  while j <= A
    w = ITEM[i]
    memo[i + 1][j] = (
      if j >= w
        k = memo[i][j]
        l = memo[i + 1][j - w] + 1
        k < l ? k : l
      else
        memo[i][j]
      end
    )

    j += 1
  end
  i += 1
end

p memo[N][A]

個数制限あり・一次元配列

ループは逆順。

ITEM = [1, 2, 3, 4, 5]
N = ITEM.size
A = 9

memo = Array.new(A + 1, Float::INFINITY)
memo[0] = 0

i = 0
while i < N
  j = A
  while j > 0
    w = ITEM[i]
    if j >= w
      k = memo[j]
      l = memo[j - w] + 1
      memo[j] = k < l ? k : l
    end
    
    j -= 1
  end
  i += 1
end

p memo[A]

個数制限なし・一次元配列

ループは普通順。

ITEM = [1, 3, 4, 2]
N = ITEM.size
A = 17

memo = Array.new(A + 1, Float::INFINITY)
memo[0] = 0

i = 0
while i < N
  j = 0
  while j <= A
    w = ITEM[i]
    if j >= w
      k = memo[j]
      l = memo[j - w] + 1
      memo[j] = k < l ? k : l
    end
    
    j += 1
  end
  i += 1
end

p memo[A]

貪欲法

ITEM = [500, 100, 50, 10, 5, 1]
A = 650

a = A
i = 0
c = 0
s = ITEM.size

while i < s
  c += v = a / ITEM[i]
  a %= ITEM[i]
  i += 1
end

p c

硬貨問題を解く場合、日本の通貨体系であれば、貪欲法でも最小個数が求められる場合がある。
各要素で、隣り合う要素が割り切れる関係にあればいいらしい*1が、もう少し詳しく条件を説明している所があるので、そちらを参照。
(算数が怪しい私にはぶっちゃけよくわからない)

qiita.com

余談

「K個以内部分和問題」というものがある。
部分和問題に個数の制約が加わったものだ。
制約が加わっているために「メモの次元も増やして考えなければいけないのか？」と一瞬思う。
しかし、実際には最小個数部分和問題の解は最適解なので、それをもとに判定すればいい。

今回は5種もコードを書いた挙句よく理解もしてないのでバグ取りが怪しいです。
あったら教えて下さい（丸投げ）

*1:例外として2,000円札はオッケー

【Ruby】「編集距離」を動的計画法で計算する

yukari
yukkuri

ある二つの文字列がある。
この二つを全く同じ文字列にするのに、一文字ずつの挿入・削除・置換を行う。
それらの操作は最小で何回だろうか？
このような「最小操作回数」のことを「編集距離」*1と呼ぶ。

バージョン管理や分析、つまりは差分や類似度を求める際などに用いられるらしい。
これを動的計画法を使って簡単に求める方法を記す。

編集距離の計算

まず、実際の最小操作回数を見てみる。

• yukari
• yukkuri

1. "a" を "k" に置換

• yukari → yukkri

2. "u" を "k" の後に挿入

• yukkri → yukkuri

このように yukari ↔ yukkuri 間の変換というのは二手でできることが分かる。
つまりは、最小操作回数 = 2。

動的計画法を使う

1. 表を用意する

'' は 文字無し を意味する(後で分かる)。

2. 初期値を埋める

表内の値の意味はこうだ。
変換元の文字X、変換先の文字Y、インデックスi, j として

dp[i][j] = X[0, i] をY[0, j] に変換するための最小操作回数

• X[0, i]はXの先頭からi文字とったもの
• Y[0, j]はYの先頭からj文字とったもの

という解釈。

すると例えば

• Xの先頭から0文字とったもの → ''
• Yの先頭から7文字とったもの → yukkuri

ここからXからYへの変換を考える。
Xは完全に空のため、Yには足りない7文字を挿入するほかない。
つまり変換するための最小操作回数は7であると、計算せずに分かる。

空から空へは当然0回だし、逆の yukari → '' への変換は、削除を繰り返した6回である。
このようにしてメモを初期化する。

3. 各マスを計算していく

初期値をもとにそれ以外のマスを計算していく。
各マスの計算は、以下の3通りの内の最小値を求める。

• 上のマスに1を足したもの
• 左のマスに1を足したもの
• 左上のマスの値。ただし、現在のマスの行と列が示す文字が異なる場合は1を足す

上と左はそれぞれ現在のマスとは一文字異なる関係のため、操作回数+1と考えてよいだろう。

左上の場合を例えるなら

• X → yu
• Y → yu

　↓

• X → yuk
• Y → yuk

この時の最小操作回数の変化を計算する、ということだ。
XYに追加された文字が共に等しければ、双方一文字少ない時と、最小操作回数は同じ。
異なれば置換が必要ということになるので、最小操作回数は+1になる。

そうしてそれぞれの変遷元の中で、最も操作回数の少ないものを記録していけば、最小操作回数が求められるというわけだ。

実装

X = "yukari"
Y = "yukkuri"

wx = X.size + 1
wy = Y.size + 1

memo = Array.new(wx) { Array.new(wy) }

# 初期値埋め

memo[0][0] = 0

i = 1
while i < wx
  memo[i][0] = i
  i += 1
end

i = 1
while i < wy
  memo[0][i] = i
  i += 1
end

# 各マスの計算

i = 1

while i < wx
  j = 1
  while j < wy
    memo[i][j] = (
      # 上
      v = memo[i][j - 1] + 1

      # 左
      o = memo[i - 1][j] + 1
      v = o if o < v

      # 左上
      o = memo[i - 1][j - 1]
      o += 1 unless X[i - 1] == Y[j - 1]
      v = o if o < v

      v
    )
    j += 1
  end
  i += 1
end

puts memo[X.size][Y.size]

*1:またの名をレーベンシュタイン距離

壁

どうにもならないような巨大な壁。
それは逆に言えば、いくらでも果てしなくぶつかっていける。
監獄の中の永久にも思えるが、捉えようでは、究極の娯楽なのかもしれない。

非の打ちどころが無くなって、現実は一つ一つ片づければよくなって。
そんな人生に不満は無いかもしれないけれど。
同時になんのやる気も出なくて、何も成せなくなった。

優れた人間は、常人では踏み込めない領域に敢えて踏み込んでゆく。
そんな領域を、楽しんでいるようにさえ見える。
それはなぜか。

もうそれは、逆にどうやっても上手くいかない領域しか、楽しめないからだろう。
どうやっても上手くいかない領域は、どうやってもいい領域でもある。
そこはまるで、自由と不自由の境界線のようだ。

何かを作っていて、上手く行かない。
その感覚は現実であり、真実であり、正常なものなのだろう。
であれば「上手く行かない」ことは手を止める理由にはならない。
この苦しい世界は、楽しくも思えるはずだ。

この世界はきっと、永遠に浸れてしまうだろう。
それでは何も成せない、得られない。
この問題に結果をもたらす、もっとも原始的な指標は、時間だろう。
「いつまでに終わらせる」それがもっともシンプルだ。

それはそうと。
一つ一つで片付くような問題は、いつでもできるからと怠惰になりがちだが。
それはまるで、その問題が自分にとって難しくなるのを待っているかのようである。
そんなのは自堕落だから、やめた方がいい。
たぶん無理だけど。

【Ruby】動的計画法を考える③「部分和問題」

10になるカードの組み合わせはある？

数字の書かれたカードが並んでいる。
この中から好きなカードを選び、書かれた数字の合計が10になる組み合わせは存在するか？
このような「部分和問題」を「動的計画法」を使って効率よく解く方法を考える。

→②ナップサック問題

部分和問題を考える

部分和問題はナップサック問題の一種として考えることができる。
ナップサック問題では要素(荷物)に

• 重さ
• 価値

という二つの属性があったが、部分和問題では「重さ=価値」として扱える。

また、動的計画法にて計算をメモする場合、通常のナップサック問題では

memo[i][j] = v # i番目の要素を選択すると残りの持てる重さはj、その際の価値はv

というようにメモしていた。
しかし部分和問題では重さ=価値、j = v。
jはメモに記録されるのだから、vにはその組み合わせが「存在する印」をつけるだけでいい。
つまり、vの値は「存在するor存在しない」の二択、真偽値またはビットに省略できる。

実装

ループ

ITEM = [3, 4, 5, 6]

# 要素数
N = ITEM.size

# 目標
A = 10

memo = Array.new(N + 1) { Array.new(A + 1, false) }
memo[0][0] = true

i = 0
while i < N
  j = 0
  while j <= A
    v = ITEM[i]
    memo[i + 1][j] ||= memo[i][j] || (j >= v && memo[i][j - v])
    j += 1
  end
  i += 1
end

puts memo[N][A] # => true

「memo[0][0] = true」については、
「合計が0になる組み合わせは、要素を一つも選ばなければ常に達成できる」
という前提をもとに初期化している。

ビットDP

ITEM = [3, 4, 5, 6]

# 要素数
N = ITEM.size

# 目標
A = 10

r = 1
i = 0
while i < N
  r |= r << ITEM[i]
  i += 1
end

puts ((r >> A) & 1) == 1 # => true

部分和問題を解く上で必要な情報は、目標値になる組み合わせが存在するかどうか。
これはなんと、2進数で管理し、ビット演算だけで計算できてしまう。

r = 1に対し、まずは、3のカードがきた場合、rの値は以下の様に変化する。

0001 |= (0001 << 3)
↓
0001 |= 1000
↓
1001

0と3番目のビットが立っていることが分かる。
次に、4のカードが来た場合を考える。
現時点では3のカードに4のカードを加える場合と、カード無しに4を加える場合があるので…

00001001 |= (0001001 << 4)
↓
00001001 |= 10010000
↓
10011001

0, 3, 4, 7になる組み合わせのカードがあり、そのビットが立っていることが分かる。
このように、ビットシフトとOR演算だけで、組み合わせの加算を計算できる。
計算を終えたら、あとは目標値A番目のビットが立っているかを調べるだけ。
巨大な値や長大なビット列を扱えるプログラミング言語であれば簡潔に書けていい。

書こうと思えば1行でも、しかも割と分かりやすく書けてしまう。

puts ITEM.inject(1) { |r, i| r |= r << i }[A] == 1