AIの実装/α-β法 - 人工知能に関する断創録
ミニマックス法を改良したα-β法を実装してみます。α-β法は枝刈り（必要のないところは先読みしないこと）をすることによって効率的に先読みを行うアルゴリズムです。ミニマックス法より深く先読みができるためAIを強くすることができます。ゲーム木の解説はミニマックス法のページに書いてあるので先に見てください。 othello10.jar αカット 上の図は[N2]までの評価が決まった状態を表しています。[N2]はMINなので[N4]と[N5]のうち小さいほうを選択しています。次に [N1]に戻ります。[N1]は[N2]と[N3]の評価値のうちMAXを選ぶので[N3]の評価値がわからない現状では評価できません。しかし、[N1]の評価値は8より大きいことは確定しています。この理屈はわかるでしょうか？[N3]が8より小さければ[N2]の8が選ばれますし、[N3]が8より大きければ[N3]が選ばれます。ど
01ナップサック問題を動的計画法で解く場合の考え方
重さの単位はkgで、問題の都合上整数です。 その他のツッコミどころとかはスルーでお願いします。 まずはとっかかりとなる考え方として、それぞれの品を持っていく/置いていくで場合分けをして総当りのグラフを書きましょう。 1つ目の品はカメラの三脚(3kg、7千円)です。 荷物が何もないところから始まって、三脚を持って行かない場合はそのまま、持っていく場合はその分の重さと価値を足します。 次の品物は手提げ金庫(2kg、4千円)です。 総当りということで、場合分けの数は倍々に増えていきます。 次の品物はゲーム機(2kg、8千円)です。 また前の品物の倍のノードが追加されました。 図でこれ以上描くのは面倒ですね。 面倒かどうかはさておき、2の品数乗のノードが必要になるというのは性能的に問題があります。 例題は6個なので26+25+24...程度のノードしか使いませんが、品数が100個の場合2100+.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
