探索アルゴリズムの名称について

質問

以下の探索もしくは組み合わせのアルゴリズムに名称があるのかを教えていただければ幸いです．

ある変数a1,a2,a3・・・，b1,b2,b3・・・があり（それぞれ小さい順にソートされている），
このaとbにより影響する評価関数が最小となる最適な組を探索するアルゴリズムです．

(1)まずa1・b1のペアを用いた時の値を算出する．
(2)次にa2・b1のペアとa1・b2のペアでの値をそれぞれ算出し，小さい方を見つける．
（今回はa1・b2のペアの方が小さかったとします．）
(3)次にa2・b2のペアとa1・b3のペアでの値をそれぞれ算出し，小さい方を見つける．

(2)，(3)の様な処理を繰り返し行い，最小となるa・bの組を探索する．

以上の様なアルゴリズムなのですが，名称があるのかをお聞きしたいと思います．
言葉で書くとイメージしづらいですが，小学・中学ぐらいで勉強した最短経路問題のように
格子状の図を書くと分かりやすいと思います．
二方向のみをみて探索していきます．

個人的には，二分木探索に近いと思うのですがどうでしょうか？
ただ，進み方によっては，同じ組み合わせを探索する事も出来るので，
完全な二分木探索ではないような気がします．

皆様のお力をお貸しいただければありがたいです．
お願いいたします．

回答No.4

Tacosan

解が見付からない例は既に書かれているので別の突っ込み:
「最小値は一つのみであるため，評価関数は単峰性の形をしている」って, この 2つは「ため」では繋がらないよね. 「最小値は 1つ」であっても「極小値が 1つ」とは限らない....

補足

文章の訂正有難うございます．
仰ることはまさに正論ですね．
最小値ではなく極値で話せば良かったと思います．
勉強になりました．

あと，タイトルにもある通り名称に関しては，無さそうですね．
敢えて言えば「分枝限定法」と言うアルゴリズムに近いのでしょうか？
評価関数が悪くなる方向は探索をしないと言う点で似てるのかなと思いました．
ちょっと推測で言ってるので，もう少し調べてみます．

回答No.3

MagicianKuma

このロジックで探索できると思えません。　評価関数に何らかの仮定が必要と思います。

質問者の例を考えてみると、

1)a1・b1のペア（スタート地点），a2・b1のペア，a1・b2のペアでの値をそれぞれ算出し，小さい方を見つける．
（今回はa1・b2のペアの方が小さかったとします．）
この場合、２度とb1は候補に入ってきません。下記の例のように（a3,b1)のとき評価値が最小だったとして見つかりますか？

例
b1 b2 b3 b4
a1 　9 　 8　 7　 5
a2 　10 　6 　5 　4
a3 　1　 6　 3　 7
a4 　7 　4 　6 　3

補足

仰りたいことは分かります．
この場合ですと最小値を探索することは出来ませんね．
評価関数に関しては，No．4さんの仰るとおり言葉足らずでしたね．
「最小値が一つ」ではなく「極値が一つ」と書いたほうが良かったです．
また，極値の周辺も小さい値となるため，
今回の例のように”最小値１”の周りに大きな値が来ることはあまり無いと考えられます．
まあ絶対に無い訳ではないので，その様な場合は探索に失敗しますね．

この様な形となる評価関数は実験的に確認していることでしたが，
説明不足で申し訳ありません．

しかし，最小値を探索するには全探索をすれば良いですが，
その様な処理を行うのは実用的ではありませんよね（時間的にも）．
探索回数を減らすためにはある程度の局所解に陥るのも仕方がないのではと思います．

回答No.2

edomin7777

a1・b2のペアとa1・b3のペアはいつ比べる？

> (2)，(3)の様な処理を繰り返し行い，最小となるa・bの組を探索する．

ここから、どの順番で比べるのか読み取ることが出来ない。

必ず全てのペアの評価関数値を得なければならないのなら、素直にループで回して最小値を取り出した方が良い。

※評価関数がどのような関数なのかが記載されていないから。

補足

書くときに省略してしまって，分かりづらくなってしまいました．
申し訳ございません．

(1)a1・b1のペア（スタート地点），a2・b1のペア，a1・b2のペアでの値をそれぞれ算出し，小さい方を見つける．
（今回はa1・b2のペアの方が小さかったとします．）

(2)次にa2・b2のペアとa1・b3のペアでの値をそれぞれ算出し，
　a1・b2のペアと比較して小さいペアを保存する．
（今回はa2・b2のペアの方が小さかったとします．）

(3)次にa3・b2のペアとa2・b3のペアでの値をそれぞれ算出し，
　a2・b2のペアと比較して小さいペアを保存する．
（今回はa2・b3のペアの方が小さかったとします．）

(4)次にa3・b3のペアとa2・b4のペアでの値をそれぞれ算出し，
　a2・b3のペアと比較して小さいペアを保存する．

以上のように最小値を常に保存しながら，
かつ変数a,bは必ず＋１ずつ増加させるようにします．

やはり書いても分かりづらいですね．
変数の個数も６個位なため全探索（６×６＝３６通り）しても良いのですが，
基本的にa(b)2,3位の時に最小になるため演算を半分ほどに抑えられています．

回答No.1

Tacosan

名称うんぬんの前に, 完全なアルゴリズムになっていないのでは?

補足

完全ではないらどの様な時に破綻するのでしょうか？
できれば教えていただけないでしょうか．

伝え忘れたこととして
・評価関数は連続関数ではない（変数a,bが1刻みずつ変わる離散値である）
・最小値は一つのみであるため，評価関数は単峰性の形をしている．
　ただし，等方的な形をしていないため偏りのある形をしている．