引越学

諸々の事情によって居住地を変更するということは昔から行われてきていることではあるが、都市化によって何倍にも増えたことが知られている。特に核家族化が進んだ昨今では、結婚や子供の自立などによって引越が行われることが多い。また一人暮らしであれば比較的気兼ね無しに引越が可能なためますます引越が増えている。
さて、引越に基づくいくつかの問題として取り上げられることが多いのは、やはりその引越という作業にかかる労力であろう。この労力は、長い間ずっと元の家にある物の数をnとした時に線形に増加するということが信じられてきた。しかしながら、近年それでは収まらない可能性が示唆され始め、専門家の間では一般の問題はNP完全であるという説も現れてきている。
古典引越学における主張は以下のようなものである。
元の家の中にあるものをオブジェクトとしてみなし、この中から必要なものだけを新居に移すという作業をコンピュータープログラミングとして見た場合、これはガベージコレクションに相当する。すなわちそれが現在参照されうるオブジェクトであれば新居に移し、そうでなければガベージコレクションの対象とする。このガベージコレクションのアルゴリズム自体は、最大でもO(n)で抑えられるので、線形時間で終了となる。
しかしながら、現実の問題としてO(n)で終了しないケースが存在する。これはなぜだろうか。それは現実のものをオブジェクトと対比して考えた場合、例えばガベージコレクションを行うために幅優先探索を行う可能性があるが、幅優先探索用のキューを実装するのにはそれなりのスペースが必要である。すなわち、コンピュータープログラミングではある程度のメモリが前提とされているのに対し(もちろん必要なメモリがどの程度かを見積もることは重要である)、現実ではメモリほど豊富な容量は見込めないということ、また必要なものにチェックを入れていく作業を物自体にするわけにはいかず(物を傷つける可能性があるため)、すでに必要であると結論されたものを間違えて再検討してしまう可能性がある。これが頻発すると、O(n)どころではなく爆発的に作業時間が増加してしまう。これをmoving explosion(引越爆発)と呼ぶ。
また、検討するべきもののリストアップ自体が最初から困難である場合もある。例えば衣類に埋もれて書籍が発見されたりする。このように、他の物に埋もれている物のことをburied object(埋没物質)、またはhidden object(隠された物質)と呼び、例えば埋没していた本であればa buried bookと呼ぶことがある。
このような様々な要因により引き起こされるmoving explosionだが、実例は多くは無くそのためまだまだ研究が進んでいるとは言えない。専門家の間では「all objects can be thrown away(全て捨てればよい)」「owning is forever(所有権は永遠=何も捨てずに持っていく)」という解決策を提示されることがあるが、様々な面で効率的とは呼べず、一刻も早い新たなるアルゴリズムの確立が求められている。