少ないメモリで動作するアルゴリズム

的 な 時 間 が か か っ て しま う。 そ れ で は 計 算 に 時 間 が か か

り過 ぎ 実 用 的 と は 言 え な い 。 そ こ で 、 通 る 場 所 を 決 め 打

ち す る 際 、 点 を 決 め 打 つ の で は な く 、 範 囲 を 指 定 して そ

TetsuoAsano,TaisukeIzumi,MasashiKiyomi,Matsuo

の 範 囲 内 を 通 る と い う よ うに 決 め 打 ち を す る ア ル ゴ リズ

Konagaya,HirotakaOno,YotaOtachi,PascalSchweitzer,

ム を 開 発 し た 。計 算 が 煩 雑 に な る の で 詳 細 は 参 考 文 献[7]

JunTarui,RyuheiUehara'

に 譲 る が 、開 発 した や り方 で は 計 算 時 間 を0(n3)時

Depth-FirstSearchUsingO(n)Bits.ISAAC2014'553-

間 に抑

564

え な が ら ・ 使 用 す る メ モ リ の 量 を ・(n(logn)152Vl

ogn)一

・(n)ビ ッ

White,S.L.Salzberg:Alignmentofwholegenomes.

トに 抑 え る こ と に 成 功 して い る 。

6.未

A.L.Delcher,S.Kasif,R.D.Fleischmann,J.Peterson,0.

解決な問題

NucleicAcidsResearch.27(ll):pp.2369-2376(1999)

JohnHammersley:Afewseedlingsofresearch.Proc.

SixthBerkeleySymp.Math.Statist.andProbability.1:pp.

345-394(1972)

グ ラフ とそ の 中 の1つ の 頂 点 が 与 え られ た と き、 与 え

られ た 頂 点 か らそ の グ ラ フ を深 さ優 先 探 索 す る こ とを考

D.S.Hirschberg:"Alinearspacealgorithmforcomputing

maximalcommonsubsequences".Communicationsofthe

ω(η)ビッ トの メ モ リを使 用 す る。

ACM.18(6):341-343(1975)

え る。 よ く知 られ た 深 さ優 先 探 索 の アル ゴ リズ ム で は

我 々 は 深 さ優 先 探 索 を行 っ た と き に訪 れ る順 で 頂 点 を

多 項 式 時 間 で 出 力 す るn+0(logn)ビ

J.Hunt,T.Szymanski:"Afastalgorithmfbrcomputing

longestcommonsubsequences",Communicationsofthe

ッ トの ア ル ゴ リズ ム

ACM,20(5):350-353(1977)

を 開 発 した[1]。 しか し、o(n)ビ ッ トの メ モ リで 動 作 す る

多 項 式 時 間 ア ル ゴ リズ ム が 存 在 す るか ど うか は 未 解 決 で

一27一

成 践 大 学 理 工 学 研 究 報 告

MasashiKiyomi,HirotakaOno,YbtaOtachi,Pascal

Schweitzer,JunTarui!Space-Ef5cientAlgorithms

fbrLongestIncreasingSubsequence.Theory

Comput.Syst.64(3):522-541(2020)

MasashiKiyomi,TakashiHoriyama,YotaOtachi.●

Longestcommonsubsequenceinsublinearspace.In￡

Process.Lett.168.'106084(2021)

DavidMaier:TheComplexityofSomeProblemson

SubsequencesandSupersequences.J.ACM.ACMPress.

25(2):322-336(1978)

C.L.Mallows:Patiencesorting.Bull.Inst.Math.Appl.9:

216-224(1973)

一28一

Vol.58No.2(2021。12)

...