著者

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

出版者

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

雑誌

情報処理学会論文誌数理モデル化と応用(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 秒程度で作成することができた.また,本論文では,局所探索による解法と比較し,問題の困難さを実験的に調べた.さらに,様々なインスタンスにおける解を分析することで,最長しりとり問題の性質を調べた.

著者

石井 余史子 Bipin Indurkhya 野瀬 隆 乾 伸雄 小谷 善行 西村 恕彦

出版者

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

雑誌

情報処理学会研究報告コンピュータと教育(CE) (ISSN:09196072)

巻号頁・発行日

vol.1997, no.125, pp.31-38, 1997-12-19

参考文献数

5

被引用文献数

1

---

こどもが複数の絵からお話を作成できるように、絵を利用してこどもの作文作成を支援するシステム、STEP("Story TElling from Pictures") の改良を次の二点について行った。まず一つめは、こどもの日常生活場面の知識を調べるアンケートを行い、その結果から、こどもの日常生活を表現した絵を作成し、こどもの生活を反映するように、STEPの絵のデータベースの改良を行った。次に二つめとして、こどもがSTEPで遊べるように、お話作成支援の方法にジャンニ・ロダーリの提案する方法を利用した。改良後、作文の不得意な小学一年生の男女各一名にSTEPで遊んでもらった結果、こどもは複数の絵からひとつのお話を作ることができた。In this paper, we describe the modifications to our system, Story TElling from Pictures ("STEP") in which children practice their writing as a game. First, we changed pictures in STEP, from unfamiliar ones to the ones with which children are familiar. In order to do so, we asked 12 children to fill out a questionnaire, prepared pictures using the information from the questionnaire, and used these pictures in STEP. Then, we incorporated some techniques from Gianni Rodari's " The Grammar of Fantasy" into STEP to promote creative writinar in children. In our test, one girl and one bow (first graders) had fun making stories using STEP-we present that data here.

著者

五十嵐 力 中村 純平 乾 伸雄 小谷 善行

雑誌

第66回全国大会講演論文集

巻号頁・発行日

vol.2004, no.1, pp.219-220, 2004-03-09

著者

後藤 智章 柴原 一友 乾 伸雄 小谷 善行

雑誌

ゲームプログラミングワークショップ2003論文集

巻号頁・発行日

vol.2003, pp.25-32, 2003-11-07

---

将棋は状態空間が非常に大きく,解を求めることは不可能とされている.本研究では,盤を小さくした将棋の解を求め,ルールによる解と計算量に関して議論する.具体的には,端にだけ駒を置く配置の3×3と3×4の将棋の解を分析した.その結果,3×3は約98%,3×4は約56%の解を求めることができた.また,3×3は先手必勝と後手必勝が約2

著者

耿霽 池田 剛 乾 伸雄 小谷 善行

出版者

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

雑誌

情報処理学会研究報告音楽情報科学(MUS) (ISSN:09196072)

巻号頁・発行日

vol.2003, no.16, pp.31-36, 2003-02-21

被引用文献数

2

---

本研究の目的は、自然で多様な音符列を生成することである。そのために、音符の隣接情報と曲の構造に着目する。音符の隣接情報は音高と音価に分けて考える。音高は隣接情報によって構成されたマルコフ過程を使って生成する。音価はマルコフ過程で表現すると不自然な組み合わせが生成されるため、音価終了(開始)時間を隠れ状態とした隠れマルコフモデルを用いる。そして、マルコフモデルでは曲の構造を生成することができないという問題を解決するために、MFSと呼ぶ柔軟な曲構造を提案する。MFSに音符の隣接情報を適用することで自然な音符列を生成できることが実験結果からわかった。This research aims to generate natural and various sequences of notes for an automatic composition system. We focus on information between adjacent of notes and musical structure in this paper. Our system generates pitches and durations of notes independently. We assume that a sequence of pitches can be Markov process composed of adjacent pitch information and a sequence of durations can be Hidden Markov process such that note ending (starting) time is a hidden state to avoid generating unnatural sequences of durations. In addition, we propose a flexible musical structure, called MFS, to resolve a weakness of the (hidden) Markov model against the structural expression. Finally our system can generate a sequence of notes by adjacent information of notes with restrictions of MFS acquired from musical database. Preliminary experiments show that our method is effective for our aim.

著者

蛭田 健司 乾 伸雄 小谷 善行

雑誌

全国大会講演論文集

巻号頁・発行日

vol.54, pp.99-100, 1997-03-12

---

一般に詰め将棋のルーチンでは、王が詰んだ局面か、王手がかからなくなる局面まで先読みを進める。しかし、王手がかかっでいる局面において、王側が、適切な王手回避の着手を選ぶことによって次の王手がかからなくなるということを示すことができれば、その局面が不詰みであることがいえる。この場合そこで先読みを打ち切ることができるので、探索ノード数の減少が期待できる。本稿では、王手がかかっている局面において、次の一手によって王手がかからなくなるような着手 (一手逃れ) が存在するかどうかを、先読みをしないで判定する方法について考察する。

著者

乾 伸雄 品野 勇治 小谷 善行

出版者

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

雑誌

情報処理学会論文誌数理モデル化と応用(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.

著者

田中 盛一 藤井 勝之 徳田 浩 飯田 弘之 乾 伸雄 小谷 善行

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第50回, no.人工知能及び認知科学, pp.151-152, 1995-03-15

---

将棋において詰将棋の分野というのは大変重要な位置にある。詰将棋が将棋の勝ち負けを決する重要な要素に成りうるからである。そのため多くの将棋システムでは、まず詰将棋の探索を行ない、詰め手が存在しなければ通常の探索を行なうことが多い。しかし詰将棋探索ははとんどの場合不詰めを返してくるので、かなり時間の消費になる。詰将棋探索をまったくしないのはリスクが大きく、重要な場面で詰みが読めずに負けることになってしまう。そこで、本研究では詰みがあるかどうかを静的に判定する評価関数の実現を試みた。この評価関数は、ある将棋の局面を引数としてその情報から探索をせずに詰みがあるかどうかを数値で返す関数である。これは参考文献における一手詰めの計算の発展課題であるといえる。本稿で用いる用語を次のように定義する。王の退路 王手をかけられずに王が移動できる場所相手側の利きや、味方の駒、盤外、などによつて移動できない場所を8から引いた数である。したがって、0~8の整数値をとる。自勢力 先手の利きがあり、後手の利きがない場所

著者

乾 伸雄 品野 勇治 小谷 善行

雑誌

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

巻号頁・発行日

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

---

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

著者

平山 深華 荻澤 義昭 水野 貴文 乾 伸雄 小谷 善行 西村 恕彦

雑誌

全国大会講演論文集

巻号頁・発行日

vol.52, pp.5-6, 1996-03-06

---

人間と計算機の対話において、特に計算機が人間から知識の獲得を行う際、システムがどのような疑問文を発話するかは大きな問題である。話題となっている事柄に対するスクリプト的な知識をシステムが持っていれば、システムは適切な質問を発話できる。しかし、システムが持つことのできる知識には限界があり、ユーザーからのさまざまな入力に追従して、柔軟な発問をすることができない。一方、人間の対話を考えた場合、その連文関係においては、・相手の言葉の内容を受けてそれに対する問いがなされる"問答型"・相手の言葉とは無関係に、どんどん新しい話題に目先を変えていく"羅列型"の二種類に分けることができる。問答型は、"常に先行文や相手の言葉を手がかりに、次の文へと一つずつ移行していくので、論理的で生産的である。"という報告がある。本研究では、相手の文中の語に着目することで次の質問を出す、という観点から、動詞の意味に着目した。その分類によって文がどのような情報を持つことができ、どのような疑問表現を選択することができるか調査した。

著者

後藤 智章 乾 伸雄 小谷 善行

雑誌

ゲームプログラミングワークショップ2002論文集

巻号頁・発行日

vol.2002, no.17, pp.109-115, 2002-11-15

著者

西村 恕彦 乾 伸雄 野瀬 隆 小谷 善行

出版者

東京農工大学

雑誌

基盤研究(B)

巻号頁・発行日

1996

---

本研究は,利用者が自然言語対話を行いつつ,描画を行い,自動的に絵を含む知識を獲得する手法を開発し,創造性や表現力を育成するシステムの開発を目標としている.本年度は,絵を組み合わせ,利用者に提示し,創造性を養うシステムを開発し,実際に実験を行った.本研究では,特に子供が自発的に学習を行っていくようなシステムを目指している.そのため,飽きさせないような工夫が必要となる.そこで,本研究ではロダ-リの手法を採用した.これは,日常的な風景の中に意外なものを挿入することで,子供の創造性を引き出す方法である.絵の構成は自動的に作成することもできるが,子供が選択してもよい.絵の提示は4コマ漫画のような形で行われる.例えば,最初に教室の絵が提示され,次のその中に子供が入り,更に掃除器具が描かれたような絵が提示される.子供は,自分のストーリーを組み立て,コンピュータに言葉として入力する.システムは,絵と文の対応付けを行い,知識として獲得していく.実際に,小学校5年生程度の子供に対して実験を行ったところ,様々な物語を観察することができた.更に,替え歌作りのシステムを作成した.これは,子供が自由に既存の詞を変更していき,できあがったものをならすことができるシステムである.これについても,子供の実験を行ったところ,様々な詞を観察することができ,音としてならすことが創造性をかき立てることを観察することができた.従来はわれわれは自然言語だけを用いた教育システムを開発してきたが,絵や音楽を利用することによって,より豊かな子供の教育システムを提供することができ,その方法論を示すことができたと考えている.

著者

神藤 学 乾 伸雄 小谷 善行

雑誌

全国大会講演論文集

巻号頁・発行日

vol.52, pp.91-92, 1996-03-06

---

人は立体迷路を解いたり人に道を教えたりするときに「認知地図」[1]という知識を利用する。これは今スタート地点からどちらの方向に進んでいるか、どれくらいの距離にいるか、以前に通ったことのある道か、などのまとまった知識の総称である。本稿では人の認知地図を生成する過程でも特に重要視されると思われる「方向感覚」と「距離感覚」に着目し、様々な環境で実験を行うことによってこれらの感覚がどのように認知地図生成に影響を与えているかを調べることを目的としている。また、実験の環境には自然に基づいた仮想空間を使用した。自然迷路とはプリミティブがランダムに配置された、たとえば自然の洞窟のような迷路を指すもので、従来の迷路に比べれば比較的現実空間に近い仮想空間を作り出すことができ、現実空間での人の認知モデルをより深く追求する手がかりになると考えられる。