平成23年度

計画数学通論（木，後期）2011-12-28更新

◆ 2D Perfect Strip Packing問題に対して，H23年1月19日（木）の授業時間に下記の要領でコンテストと発表会を行う．

• 標準Cのソースファイルと発表用PDFファイル（一個ずつに限る）をUSBメモリまたはSDカードに入れて持参すること．
• 合計10問に対して，一問に付き30秒の制限時間で実行させる．長方形の数が1個～数百個，容器の幅が1～数百．実行可能解の存在する問題と存在しない問題が混在している．
• 入力は scanf() で読み込むこと．フォーマットは以下のサンプルを参照（#注の部分は入っていない）．

  5               #注：一行目は長方形の数
  10              #注：二行目は容器の幅
  1     5     8   #注：長方形1，幅，高さ
  2     2     5   #注：長方形2，幅，高さ
  3     2    15   #注：長方形3，幅，高さ
  4     8    12   #注：長方形4，幅，高さ
  5     3     8   #注：長方形5，幅，高さ
  	

• 出力は printf() で出力すること（エラーは fprintf(stderr, ...) で標準エラー出力に送る）．フォーマットは以下のサンプルを参照．

  5                              #注：長方形の数
  10     20                      #注：容器の幅，解の高さ（0＝解なし，-1＝時間内に分からなかった）
  1      0      0      5      8  #注：長方形1，左下角の横座標，縦座標，幅，高さ
  2      8      0      2      5  #注：長方形2，左下角の横座標，縦座標，幅，高さ
  3      8      5      2     15  #注：長方形3，左下角の横座標，縦座標，幅，高さ
  4      0      8      8     12  #注：長方形4，左下角の横座標，縦座標，幅，高さ
  5      5      0      3      8  #注：長方形5，左下角の横座標，縦座標，幅，高さ
  	

• あまり性能がよくないが，サンプルプログラムを示す．これをベースで作成してもらってOK．もちろん従う必要はない．より性能のよいアルゴリズムのために，分枝操作の工夫や限定操作の追加，階段法等を取り込んでみて下さい．
• 発表は，一人5分（質疑時間込）で自分のアイディア（アルゴリズム）を皆の前で説明すること．
• P1 = min{50, 正解数×6} + 発表点数（50点満点）のようにこのコンテストを採点する（100点満点）．

◆ 2月9日17時締切りでレポートを趙のオフィス（文学部東館459室）まで提出して下さい．問題の定義，コンテストと発表会で説明した自分のアルゴリズム，実験結果及び考察等について説明すること．4～8ページ．P2（100点満点）で採点する．

◆ 合計点数（趙の担当分を50点満点として）＝ (P1 + P2) / 4 とする．

Since 2006-08-07. Email: liang at i.kyoto-u.ac.jp