著者

乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.46, no.2, pp.105-117, 2005-01-15

参考文献数

10

被引用文献数

1

---

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,LP ベースの分枝限定法によって解決した.これによって,19 万語程度の辞書から最長しりとりをXeon2.8GHz プロセッサのPC を使って1 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.This paper describes the definition of the longest Shiritori problem as a problem of network flow and the solution using the the integer problem. This formulation requires a large number of variables being of exponential order. To overcome the difficulty, we propose a solution based on the LP-based branch-and-bound method, which solves the relaxation problems repeatedly and enumerates all the solutions implicitly. This method is able to calculate the longest Shiritori sequences for 190 thousand words dictionary in a second in Xeon 2.8GHz PC. In this paper, we compare the performances for the heuristic local search and investigate the results for a variety of instances to explore characteristics of the longest Shiritori problem.

著者

乾 伸雄 品野 勇治 鴻池 祐輔 小谷 善行

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.46, no.SIG2(TOM11), pp.105-117, 2005-01-15

---

本論文では,最長しりとり問題をネットワークの問題としてモデル化し,整数計画問題として定式化を行う.この定式化では,変数の数が頂点数に対して,指数オーダで増加するため,事実上,整数計画問題として直接的に解くことは難しい.そのため,緩和問題を設定し,LP ベースの分枝限定法によって解決した.これによって,19 万語程度の辞書から最長しりとりをXeon2.8GHz プロセッサのPC を使って1 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.

著者

品野 勇治

出版者

公益社団法人日本オペレーションズ・リサーチ学会

雑誌

オペレーションズ・リサーチ (ISSN:00303674)

巻号頁・発行日

vol.59, no.5, pp.247-253, 2014-05

---

最適化研究におけるアプリケーション駆動研究サイクルを紹介する.アプリケーション駆動研究サイクルは,学術機関での研究と企業における研究成果の利用とのつながりを良くする点では優れている.一方で,ソフトウェア開発・維持に多大な労力を要するため,日本の大学や研究機関における実施には困難さが伴う.ZIBにおいてアプリケーション駆動研究サイクルが,比較的うまく機能している背景を説明する.また,日本においてアプリケーション駆動研究サイクルを活性化するための第一歩として,論文投稿時に,論文中の数値実験に利用した全データ提出の義務化を提案したい.

著者

乾 伸雄 品野 勇治 小谷 善行

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌数理モデル化と応用(TOM) (ISSN:18827780)

巻号頁・発行日

vol.46, no.17, pp.131-142, 2005-12-15

---

本論文では,先行研究の最長しりとり問題の一般化として,最長しりとり問題で単語の長さを考慮した文字数最大しりとり問題の厳密解法について述べ,その実験的評価を行う.文字数最大しりとり問題は,整数計画問題として記述した場合,単語の最大の長さをl としたとき,最長しりとり問題を記述するための変数のl 倍の変数が必要となり,現実的に解けるかどうかは未知である.l = 26 の既知の単語について,文字数最大しりとり問題は先行研究での最長しりとり問題に比べ,約41 倍の計算時間がかかることが分かった.さらに,これら2 つの問題の派生問題として,固定単語長文字数最大しりとり問題および固定文字数最長しりとり問題を取り上げる.これらの派生問題を用いて,広辞苑とICOT 形態素解析辞書について,最長しりとり問題の最適解と文字数最大しりとり問題の最適解の関係を分析した.This paper describes an exact algorithm of the maximum-shiritori-string-length shiritori problem (MS3 in short) which maximizes a shiritori-string length. This algorithm is obtained from a generalization of an exact algorithm of the longest shiritori problem (LS in short) proposed previously. We experimentally evaluate the algorithm and investigate the properties of the MS3 problem. Since the MS3 problem takes l times number of variables of the LS problem, where l is the maximum length of words, under the integer programming approach, it is unknown whether the problem instance can be solved or not. Our experimental results showed that 41 times calculation times of the LS problem is required to solve MS3 problem, when l = 26. In addition, two derived problem of these shiritori problems, called the fixedlength MS3 shiritori problem and the fixed-shiritori-string-length LS problem, are introduced. In this paper, we analyze the relations between the MS3 problem and the LS problem, using these derived problems.

著者

乾 伸雄 品野 勇治 小谷 善行

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS)

巻号頁・発行日

vol.2004, no.92(2004-MPS-051), pp.5-8, 2004-09-13

---

本論文では、しりとり全体に含まれる文字数を最長とする文字数最大しりとり問題をネットワークフロー問題としてモデル化し、LPベースの分枝限定法による解法および実験結果について述べる。単語数を最大にする最長しりとり問題に対して、問題を記述するための変数が最大単語長に比例して多くなる特徴を持つ。実験は実際の辞書に含まれる単語について行った。実験の結果、最長しりとり問題と同じく文字数最大しりとり問題は現実的な時間で解ける問題であることがわかった。

著者

中森眞理雄 金子敬一 並木美太郎 中條拓伯 品野勇治 小谷善行 辰己丈夫

雑誌

情報教育シンポジウム2004論文集

巻号頁・発行日

vol.2004, no.9, pp.175-176, 2004-08-28

---

東京農工大学工学部情報コミュニケーションエ学科では,平成18年度入学試験における個別学力検査(前期日程)に教科「情報」を出題する.そのための試行試験(第1回目)を7月31日に実施する.本報告では,「情報」出題と試行試験の目的,出題内容の方向性,広報活動と社会の反応について述べる.

著者

池田 諭 品野 勇治 中森 眞理雄

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.19, pp.17-20, 2002-03-04

---

与えられたグラフG=(V E)が連結か否かを判定することを考える.O(|V|+|E|)のメモリ領域を用いることが出来るならば,O(|V|+|E|)の手間で連結性が判定できることがR.E.Tarjanによって示されている.本論文の目的は,分散システム上で動作する連結性判定分散アルゴリズムを求めることである.本論文では,R.Aleliunas R.M.Karp R.J.Lipton L.Lovaaszおよび C.Rackoff による?RW を用いる手法を取り上げている.そして,簡単な前処理をすることが可能な状況ならば,O(|V|^2 ?log|V|)の手間でほぼ確実に無向グラフの連結性が判定出来ることを示した.また,有向グラフの場合もグラフの直径と次数の上界が分かっているならば同様にして多項式オーダーで判定できることを示した.We consider the reachability problem for directed and undirected graphs. Let G=(V,E) be a directed graph. In [1], R. E. Tarjan has showed the algorithm of O(|V|+|E|) sapce and time complexity. We show a probablistic distributed algorithm for this problem in space O(1) and time O(|V|^2 \log |V|). In this paper,\ we discuss a variant of the algorithm which based on random walk, due to R.Aleliunas, R.M.Karp, R.J.Lipton, L.Lovaasz, and C.Rackoff. We show an improvement of their algorithm from O(|V|^3 log |V|) to O(|V|^2 log |V|) in time helped with a simple preprocessing. In a directed graph,\ we also show their original algorithm run in time O(|V|^2log|V|),\ if the diameter and the degree of the graph is bounded.

著者

宮村(中村) 浩子 宮代隆平 七夕高也 品野勇治 斎藤 隆文

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.19, pp.45-48, 2007-03-03

参考文献数

8

---

大規模な階層データを,限られた空間内へ効率的に表現する適応的表示法を提案する.階層データは属性値をもつノードと親子関係を表わすリンクから構成されており,それぞれをプリミティブで表すことで構造を視覚的に捉えられる.しかし,大規模階層データを表示する際に,隣り合うノードやリンクが重なり合ってしまう問題がある.そこで本論文では,大規模階層データを木構造で表す際に,ノードの密集具合に応じて木の表現方法を選択する適応的表示を提案する.さらに本提案手法を大規模分枝限定木に適用し,その効果を検証する.We propose an adaptive visualization technique for a large-scale hierarchical dataset within limited display space. A hierarchical dataset has nodes and links that represent the parents/child relationship. These nodes and links are described using graphics primitives. When the number of these primitives is large, it is difficult to recognize the structure of the hierarchical data, because many primitives are overlapped within a limited region. In this context, we propose an adaptive visualization technique for hierarchical datasets. The proposed technique selects an appropriate graph style based on the density of the nodes. In addition, we demonstrate the effectiveness of the proposed method by applying it to the growing process of a large branch-and-bound tree

著者

斎藤 隆文 品野 勇治 金子 敬一 宮村 浩子

出版者

東京農工大学

雑誌

萌芽研究

巻号頁・発行日

2005

---

本研究は,離散構造データの幾何的配置変動が引き起こす複雑かつ大域的な位相構造変化について,理論的ならびに実験的に追究し,諸問題に共通するメカニズムを明らかにすることを目的としている.本年度は,階層的クラスタリングを対象とした安定性評価に関する検討と,CG,可視化,形状処理の各分野における関連課題の検討を行った.階層的クラスタリングの位相構造変化を見る新しい考え方である「仮想要素追加法」を初年度に考案した.当初はクラスタリングを行った結果の階層構造の各ノードに対してだけ,適用していたため,実際には近接した配置であっても,階層構造として離れた位置にあるクラスタ同士の安定性はわからなかった.本年度は,このような場合の安定度の算出方法と,その可視化方法について検討した.その結果,構造全体におけるクラスタ構造の安定性を可視化することに成功した.CG,可視化,形状処理の各分野において,種々の問題に取り組み,関連する課題を検討した.その過程において,人物の顔を撮影した動画像を,実時間でイラスト風に処理する手法や,固定カメラで撮影された長時間にわたる時系列画像をもとに,有効情報を可視化する手法などを提案,発表した.