Ryuhei Uehara 研究室

主宰者：Ryuhei Uehara
北陸先端科学技術大学院大学

AI 要約（直近 5 年の研究成果）

上田研究室では、パズルや折り紙といった身近な問題を計算機科学の視点から分析しています。折り紙の平面への展開図、パズルのピース配置、グラフ上の経路問題など、様々な離散的な対象を扱っており、これらの問題がコンピュータで効率的に解くことができるかどうかを理論的に調べています。特に、ある状態から別の状態への変換過程に注目し、最小何段階で実現できるかといった組合せ最適化の問題に取り組んでいます。 具体的には、折り紙では一次元の紙を折る際に生じる層の厚さ制約、多面体の展開図の重なり、及び複数の多面体間での共通の展開図の存在といった問題を扱っています。また、シルエットパズルやスライドパズルなどの古典的なパズルについて、ピースの回転や移動といった限られた操作のみで目標状態に到達できるかどうかを判定する問題の難しさも明らかにしています。さらに、グラフ上のトークン配置の再構成やネットワーク上の経路変換といった、より抽象的な組合せ問題も対象としています。 これらの研究は、パズルや折り紙という直感的な題材を通じて、計算の本質的な複雑性を理解することを目指しています。NP完全性の証明を行うことで、どのような問題が本質的に難しいのかを明らかにし、一方で特定の条件下では効率的なアルゴリズムが存在することも示しており、理論計算機科学の基礎的な知見を生み出しています。

※ AI（Claude）が、公開されている論文要旨から研究の問い・手法・主要な発見を事実情報として抽出・再構成して自動生成しています。誤りを含む可能性があるため、正確性は研究室公式情報でご確認ください。

外部リンク

関連研究室(8 件)

研究成果（30 件）

続きを表示（残り 20 件）

科研費（0 件）

まだデータがありません（KAKEN 取り込み後に表示）。

所属学会・役職（0 件）

まだデータがありません（学会データ連携後に表示）。