講演名 | 2023-11-16 組合せ最適化問題の画像表現による解法 石山 遼(九大), 白川 嵩大(九大), 内田 誠一(九大), 松尾 信之介(九大), |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 組合せ最適化問題とは定められた制約下で評価値が最良となる組合せ方法を選択する問題である.本稿ではその一例として,グラフ理論における組合せ最適化問題である巡回セールスマン問題を取り上げる.これは,複数の都市をそれぞれ1回通過する最短閉路を求める問題である.換言すれば,全都市を頂点とする完全グラフのうち,最短閉路に対応する部分グラフを求める問題となる.本研究では,この完全グラフに対応する距離行列から,部分グラフを表現する隣接行列への変換を,一種の画像変換問題として捉え,それを機械学習の枠組みで実現する.すなわち,要素が2次元的に配列される行列を,その要素の値を画素値とする画像と見なす.この発想に基づき,巡回セールスマン問題のようなグラフ最適化問題を画像変換問題として扱うこととする.グラフベースのニューラルネットワーク(GNN)との比較実験を行い,画像解析による有効性を実証した.さらに,画像に対して特有の前所理を組込むことにより,精度が向上することを確認した. |
抄録(英) | |
キーワード(和) | 組合せ最適化 / 巡回セールスマン問題 / 近似解法 / 深層学習 / 画像処理 |
キーワード(英) | |
資料番号 | PRMU2023-15 |
発行日 | 2023-11-09 (PRMU) |
研究会情報 | |
研究会 | PRMU / IPSJ-CVIM / IPSJ-DCC / IPSJ-CGVI |
---|---|
開催期間 | 2023/11/16(から2日開催) |
開催地(和) | 鳥取県立生涯学習センター(県民ふれあい会館) |
開催地(英) | |
テーマ(和) | 人を表現・理解するためのCG/DCC/CV/PR技術 |
テーマ(英) | |
委員長氏名(和) | 柏野 邦夫(NTT) |
委員長氏名(英) | Kunio Kashio(NTT) |
副委員長氏名(和) | 舩冨 卓哉(奈良先端大) / 入江 豪(東京理科大) |
副委員長氏名(英) | Takuya Funatomi(NAIST) / Go Irie(Tokyo Univ. of Science) |
幹事氏名(和) | 井上 中順(東工大) / 川西 康友(理研) |
幹事氏名(英) | Nakamasa Inoue(Tokyo Inst. of Tech.) / Yasutomo Kawanishi(Riken) |
幹事補佐氏名(和) | 下西 慶(京大) / 原 健翔(産総研) |
幹事補佐氏名(英) | Kei Shimonishi(Kyoto Univ.) / Kensho Hara(AIST) |
講演論文情報詳細 | |
申込み研究会 | Technical Committee on Pattern Recognition and Media Understanding / Special Interest Group on Computer Vision and Image Media / Special Interest Group on Digital Contents Creation / Special Interest Group on Computer Graphics and Visual Informatics |
---|---|
本文の言語 | JPN |
タイトル(和) | 組合せ最適化問題の画像表現による解法 |
サブタイトル(和) | |
タイトル(英) | combinatorial optimization |
サブタイトル(和) | |
キーワード(1)(和/英) | 組合せ最適化 |
キーワード(2)(和/英) | 巡回セールスマン問題 |
キーワード(3)(和/英) | 近似解法 |
キーワード(4)(和/英) | 深層学習 |
キーワード(5)(和/英) | 画像処理 |
第 1 著者 氏名(和/英) | 石山 遼 / Ryo Ishiyama |
第 1 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 2 著者 氏名(和/英) | 白川 嵩大 / Takahiro Shirakawa |
第 2 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 3 著者 氏名(和/英) | 内田 誠一 / Seiichi Uchida |
第 3 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
第 4 著者 氏名(和/英) | 松尾 信之介 / Shinnosuke Matsuo |
第 4 著者 所属(和/英) | 九州大学(略称:九大) Kyushu University(略称:Kyushu Univ.) |
発表年月日 | 2023-11-16 |
資料番号 | PRMU2023-15 |
巻番号(vol) | vol.123 |
号番号(no) | PRMU-266 |
ページ範囲 | pp.1-5(PRMU), |
ページ数 | 5 |
発行日 | 2023-11-09 (PRMU) |