December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
238
■
7
章
AI
における経路探索
7.9.4
分析
A*
探索
の計算量的な振る舞いは、ヒューリスティック関数に全面的に依存する。
Russel
と
Norvig
（
2003
）は効果的なヒューリスティック関数の特性をまとめている。
Barr
と
Feigenbaum
（
1981
）は、適格な
h*(n)
関数を効率的に計算できない場合の
代替方式をいくつか提示している。盤面がより複雑になると、ヒューリスティック
関数は、それだけ重要になり、設計がさらに複雑だ。計算効率が悪いと、探索プロ
セス全体に非常に悪影響を与える。一方で、簡単なヒューリスティック関数でも、
探索空間を劇的に刈り込むことが可能になる。例えば、
4
×
4
の盤面に
15
駒を置い
た、
8
パズルの拡張である
15
パズルを考えよう。この
15
パズル用の
GoodEvaluator
は、
8
パズルの
GoodEvaluator
を拡張して、ほんの
2
、
3
分で作ることができる。図
7-24左の目標状態と、図7-24 右の初期状態に
おいて、
A*
探索
は
39
個の盤面状態を
処理して、
15
手の解を迅速に見つける。探索終了時、
43
個の盤面状態がオープン
集合に残っていた。
15
手の深さ制限があると
深さ優先探索
では
22,125
個の盤面状態を探索した後で
も解を見つけられない。
幅優先探索
は、
172,567
個の盤面状態を探索した後で（ク
ローズ集合が
85,213
個、オープン集合が
87,354
個残っている）、
64MB RAM
の
メモリだとメモリオーバーになる。もちろん、メモリを増やしたり、深さ限界を増
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.