2024年度 最適化特論1および2 レポート課題
- レポート課題に必要なファイル
(それをzipで固めたもの)
- 課題の詳細についてはこの中の readme.eng を読むこと.
- 注意事項:
- コンパイラーによってはfscanfを受け付けないものがあります．
gap.cの中の「#define FSCANF fscanf」を適宜変更してご利用ください．
- 疑似乱数を用いる場合は乱数の種をパラメータで与え，
何度走らせても同じ結果が出るようにすること．
たとえば種をtime()で与えてはならない(実行のたびに結果が変わり，
再現性がなくなってしまうので，実験用のプログラムではやっては
ならないことである)．
- プログラムの中のパラメータの値を，問題例ごとにチューニングして，
その値を使うことは許可しない．
そのようにパラメータを変えて実験することをコンペティションでは行わないし，
問題例のファイル名など，
問題例の本質と関係のない特定の属性から問題例を判断して
プログラム内で自動的にパラメータ設定を変えるのも許可しない．
つまり，パラメータチューニングのために用いた問題例と全く同じ問題例を入力すれば機能するが，
そうでない新たな問題例が入力されたら使えないような手段は許可しない．
一方，未知の問題例を入力してもうまく動作するように工夫されていれば，
問題例毎にパラメータが変わっても問題ない．
たとえば，問題例のコストや資源要求量などの値や，
それらの統計的データに基づいてパラメータ設定を変えるなど，
問題例のデータそのものを見てその傾向からパラメータ設定をプログラム内で自動的に変えるのは問題ない．
アルゴリズムの動作中に，探索の状況に応じてパラメータを適応的に変えるのも問題ない
(これはむしろ推奨したい方法の一つ)．
判断に迷う場合はあらかじめ相談すること．
- マルチスレッドを用いてはならない．
- 最適化特論1のレポート課題
- 提出するもの(以下の2つ):
- 一般化割当問題に対する近似解法のプログラムをc言語で作成し，
c言語のソースファイル
(複数のファイルに分けて書いた場合はソースファイル一式とmakefile)を提出せよ．
その際，上述のreadme.engの指示に従うこと（ただし，この指示は
最適化特論2の課題のコンペティションを想定して書かれており，
現時点では気にしなくていい点も含まれている）．
アルゴリズムは欲張り法などシンプルなもので良いが，課題用のファイルとして
与えている問題例の全てに対して実行可能解が得られるものであることが望ましい．
- 作成した近似解法のアイデアの概要を2ページ以内のレポートにまとめ，PDFで提出せよ．
- 提出方法: TACTのページの「課題」の欄より．
- 締切: TACTの「課題」欄にてお知らせします．
- 最適化特論2のレポート課題など
- 提出するもの(以下の2つ)と締切:
- 一般化割当問題に対する近似解法のプログラムをc言語で作成し提出せよ．
締切: TACTの「課題」欄にてお知らせします．
コンペティション用に，
最適化特論1の課題で提出したものよりも
良い解が得られるようなアルゴリズムを作ることを狙ってください．
- 作成した近似解法のアイデアの概要を説明するスライド
(7/28の講義の発表資料として作成したものでよい)
のPDFあるいはPowerPointファイルを提出せよ．
締切: TACTの「課題」欄にてお知らせします．
- 提出方法: TACTのページの「課題」の欄より．
プログラムとスライドで締切が異なるため，別の課題としています．
適切な方にご提出ください．
- 2024/7/25の講義の時間に，自分のアルゴリズムについて発表してください．
無作為に何名かに当てます．5分以内で説明できるよう，スライドを用意してください．
柳浦のホームページ