探索の本体

以下の関数search-nodeが探索の本体である.

;;; 引数:
;;; DEPTH: 探索地点の深さ
;;; TAKEN: これまでに選択されたスタック領域(の番号)のリスト
;;; MIN-E: TAKENによって得られたエネルギー
;;; MAX-E: 今後探索を続けていって得られる最大のエネルギーの評価値
;;; MAX-P-DEPTH: 並列に再帰呼び出しをする深さ
;;;
;;; 大域変数:
;;; *ISLETS*:          isletを格納する配列
;;; *N-ISLETS*:        isletの数(=探索木の深さ)
;;; *STACK-REGIONS*:   スタック領域を格納する配列
;;;
;;; *BEST-ANSWER*:      これまでに見つかった最大のエネルギー値
;;; *ABORT-THRESHOLD*:  これ以下の解は捨てる(= *BEST-ANSWER* - 一定値)
;;; *SIGNAL-THRESHOLD*: これ以上の解は探索の途中でも他プロセッサに報告
;;;                       (= *BEST-ANSWER* + 一定値)
;;; 

 1 (defun search-node (depth taken min-e max-e max-p-depth)
 2   (declare (fixnum depth) ((list fixnum) taken) (real min-e max-e)
 3            (fixnum max-p-depth) (reply-type unit))
 4   (cond ((< max-e *abort-threshold*) 
 5          ;; ある値以下であれば枝苅り.
 6          unit)
 7         ((= depth *n-islets*)
 8          ;; 葉に到達. もしこれまでの解を更新したなら他のプロセッサに
 9          ;; 解を報告
10          (when (< *best-answer* min-e) (past (signal-new-answer min-e)))
11          ;; 見つかった解を保存
12          (found-answer taken min-e))
13         (true
14          ;; 現時点で非常に良い値が得られている場合, 他のプロセッサに報告
15          (when (< *signal-threshold* min-e) (past (signal-new-answer min-e)))
16          (let* ((ideal-e (ideal-energy depth))
17                 ;; IDEAL-E = この段で得られる最大のエネルギー
18                 (rs '()))
19            (declare ((list (future unit)) rs))
20            (dolist (s (vref *islets* depth))
21              ;; DEPTH段目のisletに属する各スタック領域Sについて,
22              (when (geometically-compatible-all-p s taken)
23                ;; もし, SがTAKEN中の全てのスタック領域と共存可能ならば,
24                ;; SEARCH-NODEを再帰呼びだし
25                (match (vref *stack-regions* s)
26                  ((stack-datum e _ _ _ _)
27                   ;; 再帰FUTURE呼びだし
28                   ;; :on により呼び出すプロセッサ指定. DEPTHが小さい時は,
29                   ;; ランダムにプロセッサを選ぶ. 大きい時は, ローカル
30                   (let* ((x (future
31                              (search-node (+ depth 1) (cons s taken)
32                                           (+ min-e e) (- max-e (- ideal-e e))
33                                           max-p-depth)
34                              :on (if (< depth max-p-depth) (random-pe) *pe*))))
35                     ;; 並列に呼びだした時は, reply boxを, RSに貯める. 
36                     ;; ローカルに呼び出した時は, 直ちにTOUCHする.
37                     (if (< depth max-p-depth) (push x rs) (touch x)))))))
38            ;; このisletからどのスタック領域も選ばない場合の(逐次)再帰呼びだし
39            (search-node (+ depth 1) taken min-e (- max-e ideal-e) max-p-depth)
40            ;; 全ての再帰呼び出しの返事待ち
41            (dolist (x rs) (touch x))))))

各引数の意味は以下の通 り. 括弧内は型を表す.

depth(整数):

探索地点の深さを示す整数. 探索木の根において0で, 再帰呼出時に1増える.

taken(整数のリスト):

今までに選択されたスタック領域の番号のリ スト.

min-e (浮動小数点数):

このノードの下の探索木で得られる最小のエ ネルギー. すなわち, taken中のスタック領域のエネルギーの和.

max-e (浮動小数点数):

このノードの下の探索木で得られる最大のエ ネルギーの評価値. 探索木の根においては, 全てのisletから最大のエネルギー を持つスタック領域をとったものと仮定して計算しておき, 探索が進むごとに 実際に得られたエネルギーと, 各段での最大のエネルギーとの差を減じていく.

max-p-depth (整数):

他のプロセッサに対してfuture呼びだしをする 段数. Depthがこの値以上の場合, それ以下の処理はローカルに, かつ逐次に 行なう.

また以下の大域変数がある. ABCL/fにおいては大域変数はプロセッサごとに 別の値をとり得る. 一貫性の保証は一切行なわれない.

*islets* (整数のリストの配列), *n-islets* (整数):

incompabile isletsを格納する配列およびその大きさ. 各要素は整数のリストで, 一つの isletに属するスタック領域の番号のリスト. 初期化時に全プロセッサで同じ 値に束縛され, 更新されない.

*stack-regions* (スタック領域データの配列):

スタック領域の番号 でindexingされ, 各要素はスタック領域を記述するデータである. 初期化時に 全プロセッサで同じ値に束縛され, 更新されない.

*best-answer*, *abort-threshold*, *signal-threshold* (各浮動小 数点数)

それぞれ, これまでに見つかった解の最大値, 枝苅りのための閾値 (max-eがこの値以下だったら探索を打ち切る), 探索途中でも解を更新 するかを決める閾値(min-eがこの値以上になれば, 探索途中においても その値を全プロセッサの*best-answser*などを更新するためにブロード キャストする).