Q&A

講演のテーマ・内容に関するQ&A

各講演に関してお寄せいただいた質問に講演者が回答しております。
上の顔写真をクリックして切り替えてください。

どんなタイプの探索でもできますか？

一言で言うと、問題の種類によります。
ある地点から地点まで行く道を全部列挙する、非常に単純な例の話をしましたけれども、列挙する対象が変わると、管理する情報も変わります。そこはまさに工夫のしどころ、研究のしどころになっています。

最大化というのは途中のミッションをなるべく多くこなすタイプの探索ということでしょうか？

そう理解していただいても大丈夫です。ただ、なるべく多くミッションをこなすというと、やたら長いものになってきますので、例えば、経路長に上限があるという制約条件下で一番いいものを探索するということも可能です。

グラハム問題について、非常に大きなn次元のnという数字が出てきましたが、実際にはそれよりも小さいだろうという時に、それを列挙できますか？

原理的にはできるだろうと思います。原理的にというのは、n次元立方体を作ってそれに相当する構造を作ると、現実的な計算時間ではとても追いつかないでしょう。もちろんグラハム数そのものの表現は無理です。しかし、nがある程度小さいところでも相当の構造になりますが、それをどう整理するかは研究次第で、列挙手法プラス素晴らしい工夫により達成できるといいなあと思います。非常に面白いご提案だと思います。