next up previous
Next: 実施形態

2001年度 数理情報学科 特別研究1

テーマ 物理のりでの組合せ最適化2

担当教員 樋口三郎 ( 定員 9 名) 3


この特別研究では, 物理的なセンスと計算機で, 情報科学の問題を扱います. 特に, 組合せ最適化に重点を置きたいと思います.

組合せ最適化の問題とは, たとえば,

\fbox{
\begin{minipage}[t]{6cm}
沈没する船にのっているたくさんの骨董品(価格と重...
...脇發, どういう組合せをとれば, いちばん
価格の合計が高くなるか?
\end{minipage}}
というような, 離散的な問題です. 簡単な解法はありません. 骨董品の種類が多いと, 最適な選び方を見つけるのには 非常に長い時間が必要になってしまいます. こんな問題もあります.
\fbox{
\begin{minipage}[t]{6cm}
一方通行と両方通行の道の混じった町内を, 郵便配...
...\begin{center}\includegraphics[scale=0.5]{cpm.eps}
\end{center}\end{minipage}}

これらのタイプの問題の最適解を高速に見つけることは大切です. また, 最適解の個数を求めたり, 問題の難しさの起源を探ったりすることにも興味があります. これらのことに, たとえば次のような物理的アプローチを行います.

モンテカルロ法
絶対零度で問題の最適解が求まるような物理系を作り, 温度を下げていくシミュレーションを行う.
並列計算
複数の CPU に効率よく仕事を分担させ, 高速化を図る.
くりこみ群の方法
異なるスケールの情報をむすびつける.
平均場理論
問題の集団を考え, 最適値の期待値などを求める.
その他
これらの組み合わせ
上の説明に match していないテーマでも 希望があればできるだけ対応したいと思います. 相談しましょう.





saburo higuchi 2000年11月29日