著者

上土井 陽子 若林 真一 吉田 典可

出版者

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

雑誌

情報処理学会研究報告. AL, アルゴリズム研究会報告 (ISSN:09196072)

巻号頁・発行日

vol.48, pp.17-22, 1995-11-17

参考文献数

5

---

グラフの最小コストk分割問題は枝に正の重みを持つ無向グラフG=(V,E)の節点集合Vを互いに非連結なk個の節点集合に分割する最小コスト分割を求める問題である.この問題は巡回セールスマン問題やVLSI設計で用いられるクラスタリング問題等の組合せ問題の定式化において用いられる重要な組合せ問題の一つである.Goldschmidtらはグラフの最小コストk分割問題に対し,n=|V|とするとき,O(n^<k^2>の計算時間のアルゴリズムを提案している.本稿では最小コストk分割問題に対する多項式計算時間のアルゴリズムを提案する.提案アルゴリズムでは最大流-最小コストカットアルゴリズムをO(n^<k-1>)回適用する.

著者

齋藤 忠志 大谷 純 上土井 陽子 吉田 典可

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.99, no.724, pp.25-32, 2000-03-22

被引用文献数

2

---

オンラインに逐次発生するジョブをネットワーク上のどの資源に割り当てると効率良い処理が行えるかを考える負荷分散問題であるオンラインスケジューリング問題について考察する。Aspnesらにより8-competitive ratioをもつオンラインアルゴリズムSLOWFITが提案されている。理論的にはSLOWFITは効率の良い手法であるが、実験的には貪欲法GREEDYが良質な解を得ている。本稿ではSLOWFITに導入されているステージの概念とダブリング・トリックに注目して、新しい2つのオンラインスケジューリングアルゴリズムを提案する。シミュレーション実験により、提案手法の有効性を検証する。

著者

位藤 邦生 吉田 典可 小林 芳規

出版者

広島大学

雑誌

一般研究(B)

巻号頁・発行日

1993

---

本研究は角筆文献の発見者でありその後の角筆文献研究を領導してきた小林芳規を研究分担者に迎えて、角筆文献をさらに発掘し、従来の語学的見地からのみでなく、広く文化史資料として角筆文献を活用せんとする試みであった。さらに角筆文献によって得られる情報(文字情報および絵画情報)を画像処理によってコンピュータに入力し、それらの情報を国内外の研究者に提供する方法の研究を同時に行ってきた。位藤邦生は山口県宇部市厚東にある恒石八幡宮蔵『角筆下絵八幡大菩薩御縁起』に注目し、これを三原市御調八幡宮蔵『角筆下絵八幡大菩薩御縁起』と比較することによって両本の関係や中世において寺社縁起の類がどのようにド伝播したかの研究を進めた。小林芳規は二年間にわたって全国各地の図書館や文庫に赴き、多くの角筆文献を発見調査した。これまでの全発見点数は平成7年3月現在で1,485点にのぼっている。そうした発見の文献の中には、大英博物館蔵の敦煌文献中にあった角筆文献があり、日本における角筆文献の淵源としての中国大陸での角筆使用の実態を探ることが今後の重要な研究課題となった。また高野長英が獄中で書いた角筆による手紙が解読され、脱獄の半年前から長英が脱獄の意思を持っていたことが判明した。広島大学が新たに購入した角筆文献の中には千利休の聚落屋敷の絵図等があり、これには角筆で方眼が描かれている。角筆文献の大半は漢籍であるが、山林の境界線を角筆で描いたものなど、さまざまな分野の文献が発見され、文化史的見地からの研究は今後ますます重要になることが予想される。文字だけでなくこうした絵画・地図資料等をコンピュータに入れて提供する方法の検討も今後併せて行われなければならない。

著者

吉田 典可 相原 玲二 前田 香織

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. IN, 情報ネットワーク

巻号頁・発行日

vol.95, no.391, pp.49-54, 1995-11-27

参考文献数

12

被引用文献数

1

---

中国地域におけるインターネットへの取り組みについて経過と現状を報告するとともに今後の展望について述べる.最初に中国地域における広域学術・研究ネットワーク(JUNET, JAIN, WIDE, SINET)の変遷について述べる.次に地域ネットワークの誕生の経緯,現状を報告し,特に最近の活動報告として広島における被爆50周年平和記念式典のインターネット上のMboneと呼ばれる仮想的な国際実験ネットワーク上での中継実験に関する報告,高速通信回線を利用したマルチメディア実験などの現状を述べる.最後に,地域における自治体のインターネットへの取り組みや商用プロバイダの現状について述べ,今後の地域でのインターネットへの取り組みに関する必要なことをまとめる.

著者

中村 朋健 上土井 陽子 若林 真一 吉田 典可

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.103, no.468, pp.31-37, 2003-11-18

---

近年,巨大なデータベースが世界中の至るところで作成され,そこから役立つ情報を抽出するデータマイニング技術が実用に供されるようになった.規則性の見え難いデータベースからデータベースの性質を見つけ出す場合に,類似したデータ要素を集めるクラスタリングは有効である.特に,大規模な高次元データベースからの知識抽出において,実時間性や即時応答性が要求される分野ではメモリ使用量が少なく高速なクラスタリングが要求される.本稿では,実社会データを想定した高次元かつ疎なデータ空間を対象に,処理時間とデータ要素数が線形関係であるクラスタリング手法を提案する.また,数次元の入力データに対して提案手法を適用し,与えた評価基準により提案手法を評価する.提案手法では入力のデータ空間を階層的に不均一なサイズのセルに区切り,パラメータにより密と判断された隣接したセルを結合させることで,類似したデータ要素を集めるアルゴリズムである.

著者

細谷 好志 若林 真一 小出 哲士 吉田 典可

雑誌

全国大会講演論文集

巻号頁・発行日

vol.47, pp.89-90, 1993-09-27

---

ネットワーク管理における重要な問題の1つに最短経路木更新問題がある.特に各通信リンクの負荷晴報をコストと考えた場合に最短経路木更新問題を解くことは,メッセージを送る経路を決定する際に混雑した経路を避けるという意味で有用である.オンラインシステムではネットワークのトポロジが頻繁に変化するため,その都度最短経跨を更新する必要がある.動的ネットワークにおける最短経路木更新問題はこれまでにも多くの研究がなされてきた.特に,アルゴリズムの実行中でもトポロジの変化を許す場合,いつかはネットワークのトポロジ変化が安定するという仮定のもとでいくつかのアルゴリズムが提案されている.一般にメッセージ複雑度と空間計算量はトレードオフの関係にあり,さらにメッセージに持たせる情報を少なくすれば,一時的に経路木中にサイクルが生じるなどして各プロセスが正しい情報を保持するまでに時間がかかったり,ネットワークが非連結になった場合に正しい更新が保証されない.文献では,静的ネットワークのアルゴリズムを動的ネットワークに適用する手法として,トポロジの変化ごとにアルゴリズムをリセットして再起動させているが,その手法だとそれまでに集められた情報が無駄になってしまう.本稿では,少ない局所情報及びメッセージ情報によって,分散最短経路木更新問題を効率良く解くイベントドリプンアルゴリズムを提案する.