文書整形問題(pretty printing)に対する動的計画法のプログラム 問題 入力: 英文，1行の文字数（の範囲），余分なスペースに対するコスト関数． 出力: 与えられた英文の単語と単語の間にスペースを挿入し，改行位置を調整することで 右揃えに整形するとき，余分なスペースに対するコストの合計を最小にする整形法． つまり，できるだけきれいな（大きなスペースをあけないような）整形法を求める 問題．コスト関数はいろいろ考えられる． 注意: 実行結果は等幅フォントで見てください．そうでないと右揃えになりません． 入力例 ---------------------------------------------------------------------- Metaheuristic algorithms are widely recognized as one of the most practical approaches for combinatorial optimization problems. Among representative metaheuristics are genetic algorithm, simulated annealing, tabu search and so on. In this paper, we explain essential ideas used in such metaheuristic algorithms within a generalized framework of local search. We then conduct numerical experiment of metaheuristic algorithms using rather simple implementations, to observe general tendencies of their performance. From these results, we propose a few recommendations about the use of metaheuristics as simple optimization tools. We also mention some advanced techniques to enhance the ability of metaheuristics. Finally, we summarize some theoretical results on metaheuristic algorithms. 1行の文字数: 75 余分スペースのコスト: 単語のあとに余分なスペースが k 個入ったとき，k の 5乗 のコストが加算される．（スペース一つは余分ではないので k = 0 と数える．） 出力例 ---------------------------------------------------------------------- Metaheuristic algorithms are widely recognized as one of the most practical approaches for combinatorial optimization problems. Among representative metaheuristics are genetic algorithm, simulated annealing, tabu search and so on. In this paper, we explain essential ideas used in such metaheuristic algorithms within a generalized framework of local search. We then conduct numerical experiment of metaheuristic algorithms using rather simple implementations, to observe general tendencies of their performance. From these results, we propose a few recommendations about the use of metaheuristics as simple optimization tools. We also mention some advanced techniques to enhance the ability of metaheuristics. Finally, we summarize some theoretical results on metaheuristic algorithms. 合計コスト: 28 ----------------------------------------------------------------------------- 動的計画法の考え方については，dp_jp.pdf (またはdp_eng.pdf)を見てください． 利用法 コンパイルは make と入力してください．あるいは， gcc -Wall -O2 -o typeset typeset.c -lm のようにしてください．（必要ファイル: typeset.c, cpu_time.c, makefile.） 標準入力から英文テキストを入力．出力は標準出力へ．1行の文字数の範囲はパラメー タとして入力できる．段落が複数ある場合，段落間は１つ以上の空行で区切ってくださ い．英文が sample.txt というファイル名の場合のコマンド入力例: cat sample.txt | ./typeset パラメータを変更する場合: cat sample.txt | ./typeset （パラメータ名） （パラメータ値）... cat sample.txt | ./typeset lmin 65 cat sample.txt | ./typeset lmin 60 lmax 70 outlvl 1 パラメータの説明 パラメタ名 デフォルト値 意味 lmax 80 1行中文字数の最大値（lmin未満ならlminに修正される） lmin 70 1行中文字数の最小値（単語文字数の最小値以下なら単語 文字数の最小値に設定される） ind1 0 最初の段落の行頭のインデント（スペースの数） ind2 0 2段落目以降の行頭のインデント lines 1 段落間の空行数 ctype 2 コストのタイプ（以下の exp はパラメータ） 1: 1行中の空行数の exp 乗．右揃の整形でなく，改行位置 のみを調整する． 2: 単語のあとに余分なスペースが k 個入ったとき，k の exp 乗のコストが加算される（1スペースはk=0）． exp 5 コストの指数（exponent） pslide 1 plide = 1 -> 行末に '.' か ',' が来たとき，もともと とそれらがなかったものとしてコストを計算． (available only if ctype=2) plide = 0 ならばこのような例外処理を行わない． outlvl 0 出力のレベル 0: 整形した文書のみ 1: 採用された1行中文字数（text width），最適コスト， および計算時間を併せて出力 2: さらに各1行中文字数に対する最適コストも併せて出力 pslide = 1 は，個人的には，ピリオドとコンマはテキスト幅から1文字右にはみ出して レイアウトするほうがきれいに感じたため採用．これらは小さいので，行末に来ると， そこがへこんで見える．ただし，これはフォントによると思うので，好まない人は pslide = 0 として下さい． emacs 上での利用: emacsをご利用の方はご存じと思いますが，emacs で region を指定し(C-spcでマークした ところからカーソルまで)，region内の文字列に対して typeset を利用することもできま す．「M-| (あるいは M-x shell-command-on-region)」として typeset [option(s)]と してください． 解説[1]をご参照ください． バグなど，気付いた点は柳浦（yagiura "at" nagoya-u.jp）までご連絡いただけると 幸いです． 参考文献 [1] 黒木裕介，組版におけるオペレーションズ・リサーチ， 　　オペレーションズ・リサーチ, Vol. 60, No. 9, 2015, pp. 536-542.