| 題名 | 単色ドミノ構成問題の解法について |
| 著者 | *三鴨 礼二郎, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院 工学研究科 情報認識論研究室) |
| Page | pp. 159 - 160 |
| Keyword | ドミノ構成問題, NP完全 |
| Abstract | ドミノ構成問題とはm×nの長方形空間に，2×1のドミノを長方形の縦辺と横辺に与えられたドミノ数に従い，はめ込んでいく問題である．投影データから元の図形を再構成する問題の一種であり，画像認識やデータ圧縮などを初めとする計算機の分野で多くの応用がある．これまでの研究では，問題を難しくしてNP完全性を示すアプローチと，問題を易しくして，多項式時間で解くアプローチがあった．いままでは前者のアプローチから3または2色のドミノを用いた場合のNP完全性が示されている． しかし，単色ドミノについては未解決のままで，条件付で解くアプローチがいくつか示されている．本研究ではさらにそれを進めた． |
| 題名 | Web ページ動的リンクのペトリネットモデル |
| 著者 | *小林 哲也 (広島大学大学院工学研究科), 山内 雅弘 (近畿大学工学部電子情報工学科), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | pp. 161 - 162 |
| Keyword | ペトリネット, Web |
| Abstract | 一般的な Web ページ上のページ遷移は，そのページ内に移動先の URL が固定的に記述されている．よって，URL やサイト内のディレクトリ構成が変更されただけで，多量のリンクの書き換えが必要となる．また，動的コンテンツと呼ばれる，ページの遷移やページ内容が動的に変化するコンテンツも存在する．これは一般的に CGI 等のスクリプト内に遷移規則を記述することになり，容易に仕様変更等ができないといった問題もある．本研究では効率的で高い汎用性を有するペトリネットを用いた Web ページの動的リンクのモデル化を主題とし，まず，ペトリネットを用いて Web ページの動的リンクのモデル化を行い，ページ間リンク記述言語として CGI を用いて実装した．次に，有用性を示すために Web コンテンツをサンプルとして作成した． |
| 題名 | VNS組換え改良によるグラフ点彩色問題解法の性能強化 |
| 著者 | *岡田 慎司 (広島大学工学部), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | pp. 163 - 164 |
| Keyword | 点彩色, VNS, グラフ |
| Abstract | グラフの点彩色とは，与えられたグラフGにおいて隣接頂点(1本の辺で結ばれている頂点)は異なる色となるように，すべての頂点に色を塗ることである．彩色に必要な最小の色数を最小色数と呼び，Gで表す．k-点彩色とは、k色以下の点彩色のことである． 点彩色問題は最小色数G及びそのときの点彩色を求める問題であり，一般にNP困難であることが知られている.本稿では，近似解放の一つであるVNSを改良して性能をあげることを目標とした． |
| 題名 | 最小重み点被覆問題に対する近似解法の計算機実験による性能比較 |
| 著者 | *國近 拓也 (広島大学工学部), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | pp. 165 - 166 |
| Keyword | グラフ, 点被覆, 近似解法 |
| Abstract | 本稿では，各頂点vが非負整数の点重みw(v)を持つグラフG=(V,E)における最小重み点被覆問題を扱う．グラフの点被覆とは，頂点集合であり，任意の辺の両端点のうち少なくとも一方を含むものである．点被覆の重みは，点被覆に含まれる各頂点の重み総和である．グラフの最小重み点被覆問題は，非負整数の点重みを持つ無向グラフが与えられたとき，重み最小となる点被覆を求める問題である．本稿では，5つの既存近似解法について，計算機実験により性能を評価する． |
| 題名 | タブーサーチを用いた小選挙区区割画定問題の一解法 |
| 著者 | *岩崎 雄介 (岡山県立大学大学院), 金川 明弘, 山内 仁 (岡山県立大学), 小野 勉 (両備システムソリューションズ) |
| Page | p. 167 |
| Keyword | タブーサーチ, 小選挙区 |
| Abstract | 日本の衆議院議員選挙のうち，小選挙区制において，今日でも一票の格差が2倍を越えていることが問題視されている．これを解消する選挙区割りをおこなう．すなわち小選挙区区割画定問題についての研究が進められてきた．我々も重み付きボロノイ領域を用いた解法を示してきたが，局所解からの抜け出しに困難である問題点が見受けられた．そこで，この点に強いとされているタブーサーチを用いた解法を提案し，検証実験の結果，各都道府県多くの選挙区で一票の格差の改善が見られた． |
| 題名 | 並列シミュレーティッドアニーリング法による配線問題の計算 |
| 著者 | *中川 歩, 趙 悦 (広島国際学院大学 工学研究科) |
| Page | p. 168 |
| Keyword | SA, 並列計算, 配線問題, PCクラスタ |
| Abstract | 組み合わせ最適化問題には、NP−完全問題のような問題が多くある。ゆえに、厳密解を求めることが工学的な意味で不可能となることも多い。したがって、そのような問題に対して厳密な最適解を求めず、短時間で比較的よい準最適解を求めるほうが意味がある。準最適解を求める工学的な手法にシミュレーティッドアニーリング法（SA法）が提案されている。SA法は逐次改善法に比べ、常によい結果を得られるが、計算時間が非常に長いという欠点を持つ。そこで並列計算を行うことで計算時間の短縮ができる分散シミュレーティッドアニーリング（DSA法）が考えられた。本稿ではDSA法を配線問題に適応させ、その有効性を実験で実証した。 |