著者

高田 喜朗 五十嵐 達郎

雑誌

研究報告ゲーム情報学(GI) (ISSN:21888736)

巻号頁・発行日

vol.2016-GI-36, no.15, pp.1-8, 2016-07-29

---

立体ピクロスは,任天堂が販売するゲームソフトウェア中のパズルである.立方体を積み重ねた直方体が与えられ,ヒントを基に不要な立方体を消して隠された立体を見つけることがパズルの目的である.草野らは,このパズルの解の存在判定が NP 完全であること,また,高さが 1 に限定されかつセグメント情報がヒントとして与えられない場合には多項式時間可解であることを示した.しかし,高さが自由であることとセグメント情報が与えられることのどちらが NP 完全性に寄与しているかは不明であった.本研究ではこの問題について考察し,その結果,高さが 2 以上でセグメント情報が与えられない場合,及び,高さが 1 でセグメント情報が与えられる場合,どちらも NP 完全であることがわかった.

著者

高田 喜朗 辻野 嘉宏 都倉 信樹

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.38, no.2, pp.290-298, 1997-02-15

---

ヘルプシステムやWWW(World Wide Web)など 計算機アプリケーションのいくつかの分野でハイパーテキストを利用したシステムがよく見られるようになってきている.ここでは 大量の情報(文書)が個別に提供され それらをユーザが効率良くアクセスできるように検索のためのメニューとその間のリンクを構築する問題を考える.ユーザが効率良くアクセスするためには 操作の手間が平均的に小さいことが必要になる.また キーワードとそれからアクセスできるページの集合(カテゴリ)は意味的に対応づけられ ユーザが目的のページを検索するのに途中のメニューで迷わないようにしなければならない.本論文では 与えられたキーワードとカテゴリの関係を保つリンク構造すべての中から平均アクセス時間が最小なリンク構造を求める効率の良いアルゴリズムを示す.