piqcy on Twitter: "言語モデルで実際文を生成するときに必要なDecodingについて、各種手法とTransformernによる実装を紹介している記事。単純に一番確率が高い単語をとっていくGreedy Searchから代表的なBeam Searchなど… https://t.co/faETArJFzQ"言語モデルで実際文を生成するときに必要なDecodingについて、各種手法とTransformernによる実装を紹介している記事。単純に一番確率が高い単語をとっていくGreedy Searchから代表的なBeam Searchなど… https://t.co/faETArJFzQ
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれ
IDA* -- Iterative Deepening A* - Qiita
自分は孫弟子にあたるらしいRichard E. Korf 先生の論文紹介です。 会ったことないですがKorf先生→ https://www.youtube.com/watch?v=EnX8cQPiB1M https://www.youtube.com/watch?v=TAjyI06Q1x8 IDAはAと同じく最適解を返すアルゴリズムですが、A*と異なり メモリ使用量が線形 であるという違いがあります。 Iterative Deepening Depth First Search だれだ反復深化深さ優先探索なんて長ったらしい名前を付けたのは。 反復Xは長いのでIDDFSと呼びましょう。 IDDFSは、ダイクストラの深さ優先版です。 ダイクストラやA*などの最良優先探索系、もとい幅優先探索系に共通する問題は、OPENリストを全部メモリに確保しておかないといけないという点です。 しかし、実際のコ
Interpolation Search - Negative/Positive Thinking
Interpolation Searchとは 補間探索、内挿探索 二分探索での範囲の中間値を利用する代わりに、範囲の両端の値から探したい値の位置にあたりをつけて、その値を利用して探索していく方法 二分探索では、配列の値に関係なく範囲の中間の値を利用して探索 探索時間はO(log log n) 二分探索では、O(log n) データに依っては、二分探索の方が速くなる場合もあり得る 計算例 配列vが「1,2,3,5,6,10,12」として、 left = 0, v[left] = 1 right = 6, v[right] = 12 である時、 2分探索では、mid = floor( (left + right) / 2 ) = floor( (0+6) / 2 ) = 3のように決めたりするが、 Interpolation Searchでは、値も考慮し、value=6を探したい場合、 mid
AlphaBeta探索で経路依存の値を判定する方法 - Qiita
なんぞ？ AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。 そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。 どうやるの？ ↓こんな感じ。 末端では、それが経路依存な性質を持つか否かでフラグを設定する。 αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。 αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。 β以上の子ノードがあった場合、そ
三分探索と黄金分割探索 - naoya_t@hatenablog
はい、毎度おなじみのグラフ描きたいだけのエントリですw 今回のお題は「三分探索（ternary search）」。 二分探索（binary search）は割とおなじみかと思うのですが、二分探索が単調増加(減少)関数fについてf(x)=kとなるxを求めるのに対し、三分探索（とか黄金分割探索）は凸関数の極値を求めるのに用います。 詳しくは http://d.hatena.ne.jp/ir5/20090630/1246349028 http://d.hatena.ne.jp/nodchip/20090303/1236058357 辺りを見て頂くとして。 三分探索 探索領域(x0,x3)を三等分するx1,x2を選びます。(x0,x1,x2,x3) で、f(x1)とf(x2)を比べ、f(x)が下に凸な関数なら値が大きい方、上に凸な関数なら値が小さい方の外側（x1ならx0-x1, x2ならx2-x3
メタヒューリスティクス - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "メタヒューリスティクス" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2023年8月) メタヒューリスティクスとは、組合せ最適化問題のアルゴリズムにおいて、特定の計算問題に依存しないヒューリスティクスのことである。 近年では、上記の定義から拡張され、特定の問題に依存しない、汎用性の高いヒューリスティクス全般を指すこともある。そのため、組合せ最適化問題のアルゴリズムに限らず、連続最適化問題に対するアルゴリズムも含む解釈も存在する。 通常ある問題に対しての「解法」が存在するとき、その解法が適用できる範囲はその問題に対してのみである。 と
4段階の思考スキルレベル - Chikirinの日記
将棋ソフトに関しておもしろかったのは、先日も書いた「探索」と「局面評価」という思考プロセスです。 １）探索＝とりうる選択肢を、自分の選択肢→相手の対応策（選択肢）→自分の選択肢、と深掘りしつつリストアップ ２）局面評価＝上記の過程で現れる局面を、どの程度、自分に有利か（不利か）評価する ３）その上で、自分にとって最も有利な局面につながる選択肢を選ぶ 探索とは、下記のような図＝探索木＝ツリーのイメージです。 （『人間に勝つコンピュータ将棋の作り方』より） この探索と局面評価というステップは、ビジネスや個人生活などあらゆる意思決定の場面で使われてます。 将棋のような完全情報ゲームでないため、より複雑ですが、ビジネスでは、 ・自社が値段を下げる→他社が対抗してくる→自社はどうする？・・・であったり、 ・自社が買収を提案する→第三者が価格を釣り上げる→公正取引委員会がいちゃっもんをつける→自社はど
暗記なんかで勝てたりしません - Chikirinの日記
今日は、将棋ソフトがどのように“将棋を学んできたのか”について、まとめておきます。 今から40年ほど前の 1975年頃、人工知能研究の一環として将棋ソフトの開発は始まったそうです。 その進化の流れは、ざっくり言えばこんな感じ？ １．ルールを覚えさせる ２．金言などをプログラム化する ３．探索と駒得で手を選ばせる ４．局面評価について、機械学習をさせる １の「ルールを覚えさせる」というのは、各駒の動ける場所を教え、“二歩”など反則となるルールを教えるってことです。 でも、駒の動かし方がわかるようになっただけでは勝てたりはしません。今の私と同じです。 ちなみに「反則にならない手」は合法手と呼ばれます。 次に「金言をプログラム化する」ってことが行われたみたいです。 将棋には勝ちやすくなるための格言がたくさんあります。 「玉飛接近すべからず」「二枚替えなら歩ともせよ」みたいな言葉ですが、そういうの
力まかせ探索 - Wikipedia
力まかせ探索（ちからまかせたんさく、英: brute-force search）またはしらみつぶし探索（英: exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 通りの配置を全て順にチェックしていく。バックトラッキングでは、2つのクイーンが互いに取り合える状態なら他のクイーンがどう配置されていても考慮に値しないという事実を使って、チェックすべき配置数を大幅に減らし、高速に解くことができる。 力まかせ探索は実
Beam search - Wikipedia
Beam search with width 3 (animation) In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is a modification of best-first search that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, onl
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier
IBM Developer
高速な最近某探索
Artificial Intelligence/Search/Heuristic search/Beam search - Wikibooks, open books for an open world
Site Under Maintenance
PathFinding.js
http://spheresofa.net/blog/?p=1044
1064 -- Cable master
なべさん on Twitter: "二分探索もいろいろ書き方があるんだなぁ。参考になります。個人的には解が[lo,hi]の閉空間にあると考えて、while(lo<=hi){mid=(lo+hi)/2; if(check){ hi=mid-1; } else { lo=mid+1; }}が紛れがないように思いました。"