\documentstyle[a4j,12pt]{jarticle}

\begin{document}

  \title{$BJY6/2q%l%8%e%a(B \\ -$B%"%W%j%1!<%7%g%s(B-}
  \author{$BJR6M9'MN(B}
  \date{\today}
 \maketitle

 \section {$B$O$8$a$K(B}
  $BJBNs=hM}$NBP>]$H$J$k$Y$-LdBj$O(B,$B?tB?$/5s$2$i$l$k$G$"$m$&(B.
$BB?$/$NJ,Ln$G%3%s%T%e!<%?$N=hM}$rI,MW$H$9$k$h$&$JKDBg$J7W;;$rI,MW$H$9$k(B
$BLdBj$,$"$k(B.$B$=$l$f$((B,$BJBNs=hM}$K$h$j8=B8$N%3%s%T%e!<%?$N@-G=$r8~>e$5$;$k(B
$B$3$H$,$G$-$J$$$+$H9M$($i$l$?(B. 
  
  $B$7$+$7$J$,$i(B,$B=hM}$NJ}<0$K$h$C$F$OIT8~$-$J$b$N$,$"$j(B,$B$5$i$K$OJBNs=hM}(B
$B$r$7$F$b$=$l$K1~$8$?@-G=$,8~>e$7$J$$$3$H$b$"$j$&$k$G$"$m$&(B. 
 
  $BJY6/$rDL$8$F(B,$B$=$l$i=tLdBj$rM}2r$7$F$$$1$k$h$&$KEXNO$7$?$$(B.

 \section{$B%?%s%Q%/<ANs$N%"%i%$%s%a%s%HLdBj(B}
   \subsection{$BLdBj$NDj<02=(B}

   $B%?%s%Q%/<A$r9=@.$9$k%"%_%N;@G[Ns$r2r@O$7(B,$B%?%s%Q%/<A$NN)BN9=B$$d5!G=$r(B
$B?dDj$9$k8&5f$,@9$s$K$J$5$l$F$$$k(B.$B6aG/$G$O(BDNA$BG[Ns$+$i%?%s%Q%/<A$N%"%_%N;@(B
$BG[Ns$,9bB.$+$DBgNL$K7hDj$5$l$k$h$&$K$J$j(B,$B$=$N7k2LF@$i$l$kKDBg$J%G!<%?$N(B
$B2r@O!&4IM}$N$?$a7W;;5!$K$h$kG[Ns2r@O$,I,?\$H$J$j$D$D$"$k(B. 

 $B%"%_%N;@G[Ns$N2r@O<jK!$NCf$K=EMW$J$b$N$N0l$D$KG[Ns4V$NN`;w@-$rD4$Y$kAjF1(B
$B@-2r@O$,$"$k(B.$B$3$N2r@OK!$N4pK\E*$JA`:n$O(B,$BJ#?t$N%"%_%N;@G[Ns$NN`;w$9$kItJ,(B
$B$rF1$8Ns$KB7$($FJB$Y9g$o$;$kA`:n$G$"$j(B,$B$3$l$r(B {\gt $B%"%i%$%s%a%s%H(B} $B$H$$$&(B.

 $B7W;;5!$G%"%i%$%s%a%s%H$r5a$a$kLdBj$O(BN$B<!85C5:w6u4V$N:GE,7PO)LdBj$KDj<02=(B
$B$G$-$k(B.$B$$$^Nc$H$7$F(B AHIE, ADHE $B$N#2K\$N%"%_%N;@G[Ns$r%"%i%$%s%a%s%H$9$k>l9g(B
$B$r9M$($k(B.
 
 $B$3$N$H$-(B,$B?^Cf$N4]$r%N!<%I(B,$BLp$r%"!<%/$H$7$F(B,$BLp$K$=$NN`;w@-$rI=$9%9%3%"!JN`;w@-(B
$B$,9b$$DxBg$-$$!K$rIU$1$k$H(B,$B=E$_$D$-M-8~%0%i%U$H$_$J$;$k!#(B

 $B0J>e$N$h$&$K$3$NLdBj6u4V$rDj5A$9$k$H(B,$B:GE,$J%"%i%$%s%a%s%H$r5a$a$kLdBj$O(B
$B$3$N%M%C%H%o!<%/>e$N:8>e$N%N!<%I$r=PH/E@$H$7(B,$B1&2<$N%N!<%I$r=*CeE@$H$7$?(B
$B:GBg7PO)LdBj$KBP1~$9$k(B.

   \subsection{$B%^%k%A%W%k%"%i%$%s%a%s%H$N<jK!(B}

   3$BK\0J>e$NG[Ns$N%"%i%$%s%a%s%H$rFC$K%^%k%A%W%k%"%i%$%s%a%s%H(B(Multiple 
Sequence Alignment)$B$H$$$&(B.n$BK\$N%^%k%A%W%k%"%i%$%s%a%s%H$b(B2$BK\$N;~$HF1MM(B
$B$K9M$($k$H(B,$B86M}E*$K$O(Bn$B<!85D66u4VCf$N:GE,7PO)LdBj$K5"Ce$9$k(B.$B$7$+$7$J$,$i(B
$B$3$NJ}K!$G$OKDBg$J7W;;;~4V$rI,MW$H$9$k$?$a8=<BE*$G$J$$(B.$B$=$l$f$($$$m$$$m$J(B
$BJ}K!$,Ds>'$5$l$F$$$k$,(B,$B$=$l$i$K$D$$$F$9$Y$F@bL@$9$k$3$H$OL\E*$G$J$$$+$i(B
$B@bL@$r3d0&$7$F$R$H$D$NJ}K!$K$D$$$F$N$_8@5Z$9$k(B. 
 \vskip 0.5 cm
{\gt $BH?I|2~A1K!(B} 

 $BH?I|2~A1K!$O(B1991$BG/$K(BBerger$B$H(BMunson$B$K$h$C$FDs>'$5$l$?<jK!$G$"$j(B,$B<!$N$h$&$J(B
$B=hM}$r9T$J$&(B \\
 1.$B=i4|G[Ns$r%i%s%@%`$K#2$D$N%0%k!<%W$KJ,3d$9$k(B. \\
 2.$BJ,3d$5$l$?%0%k!<%W4V$G(B {\gt $B%0%k!<%W4V%"%i%$%s%a%s%H(B} $B$r9T$J$&(B. \\
 3.$B$=$N7k2LF@$i$l$?%"%i%$%s%a%s%H$r<!$NH?I|$N=i4|G[Ns$H$9$k(B. \\
 4.$B$3$NA`:n$r%9%3%"$,<}B+$9$k$^$GH?I|$9$k(B. \\
 $B$3$NJ}K!$K$O4v$D$+$N7gE@$,$"$k(B. \\

 {\gt $B7gE@(B1:} $BMp?t$rMQ$$$FC`<!E*$K2~A1$7$F$$$/$?$a(B,$BF@$i$l$k%"%i%$%s%a%s%H$,(B
$BMp?t7ONs$KBg$-$/0MB8$7(B,$B<B9T$NEY$KF@$i$l$k2r$,JQ$o$C$F$7$^$&(B. 

 {\gt $B7gE@(B2:} $B$I$NJ,3d$rA*$s$@;~$G$b%9%3%"$,2~A1$5$l$k$o$1$G$b$J$/(B,1$BK\$H(Bn-1$BK\(B
$B$N$h$&$KJP$j$,$"$kJ,3d$7$?$H$-$K%9%3%"$,2~A1$5$l$k>l9g$,$*$*$$$3$H$,$"$k(B.
$B0lJ}G[Ns$NK\?t$,A}$($l$PJ,3d$N?t$,A}$($F(B,$B%9%3%"2~A1$K4sM?$7$J$$J,3d$rA*Br(B
$B$9$k3NN($,A}$7(B,$B7k2L$H$7$F<}B+;~4V$,A}$9(B. \\
$B$3$l$i7gE@$OJ,3dJ}K!$9$Y$F$KBP$7$FJBNs$K%0%k!<%W4V%"%i%$%s%a%s%H$r9T$J$$(B
$B$b$C$H$bNI$$=i4|%"%i%$%s%a%s%H$rA*Br$9$l$P2r7h$5$l$k(B.$B$5$i$KH?I|$N$?$S$KI,$:(B
$BI>2ACM$,JQ$o$k$?$a$K<}B+$,Aa$/$J$k(B.$B$^$?Mp?t$rMQ$$$F$$$J$$$?$a2r$,0BDj$K$J$k(B.
$B$3$l$r(B {\gt $BJBNsH?I|2~A1K!(B} $B$H$$$&(B.
  \vskip 0.5cm
{\gt $B8BDjJ,3dK!(B} 

  $B$9$Y$F2DG=$JJ,3dJ}K!$K$?$$$7$F=hM}$r9T$J$&$H$9$l$P(B,$BNs$r(Bn$BK\$H$9$k$H$-(B
$B$=$NJ,3dK!$O(B $2^{n-1}-1$ $BDL$j$"$k$+$iG[Ns$N?t$NA}2C$KBP$7$F;X?t%*!<%@$GA}2C$9$k(B
$B$3$H$OL@$i$+$G$"$k(B.$B$h$C$F07$($kK\?t$K@)8B$,$"$k(B.$B$=$3$G$3$N%0%k!<%WJ,3d$r(B
$B0lDj$NHO0O$K8BDj$9$k(B.$B$3$l$O@h=R$N$H$&$jJP$j$N$"$k%0%k!<%WJ,3d$,2~A1$K4sM?$9$k(B
$B>l9g$,B?$$$3$H$rMxMQ$7$?$b$N$G$"$k(B. \\

 \subsection{$BJBNsH?I|K!$N9bB.2=<jK!(B}

 $B$3$3$G$OJBNsH?I|2~A1K!$r$5$i$K9bB.2=$9$k<jK!$r=R$Y$k(B.

 \subsubsection{$BF0E*7W2hK!$NJBNs2=(B} 

 $B:G=i$NJ}K!$F$7$F(B,$B%0%k!<%W4V%"%i%$%s%a%s%H$r5a$a$k<jCJ$H$7$FF0E*7W2hK!(B
$B$,9M$($i$l$k(B.$BF0E*7W2hK!$H$O%"%i%$%s%a%s%H$N:](B,$B:GE,$J%Q%9$r7h$a$k$?$a$K(B
$B0JA0$N>pJs$r%a%b%j$J$I$K0l;~5-21$7(B,$B<B9T$N$?$S$K$=$l$r;2>H$7$FLdBj2r7h$r(B
$B9T$J$&<jK!$G$"$k(B.$B$3$N=hM}$rJ#?t$N%W%m%;%C%5$GJBNs<B9T$9$k$3$H$r9M$($k(B.
 
 \vskip 0.5 cm
 {\gt $BF0E*7W2hK!$K$h$k%"%i%$%s%a%s%H(B}

 {\gt $BF0E*7W2hK!(B}(Dynamic Programing$BK!(B,$B0J2<(BDP $B$HN,$9(B)$B$O(B,$B%"%k%4%j%:%`$N(B
$B3F%9%F%C%W$G7hDj$r9T$J$&FCD'$r;}$DLdBj$KBP$7$F(B,$BF0E*$K7hDj$r9T$J$&$b$N$G$"$k(B.
$B$I$&$7$FF0E*$K7hDj$9$k$+$H$$$&$H(B,$B7hDjE*$K9T$J$&>l9g$7$i$_DY$7$KC5:w$7(B,$B7k2L$H(B
$B$7$F7W;;NL$,GzH/E*$KA}Bg$7$F(B,$B2r$r5a$a$k$3$H$,8=<BE*$KIT2DG=$K$J$k$3$H$,$"$k(B.
$B$h$C$F$3$N7hDj$r(B,$B2r$,5a$^$k$G$"$m$&7hDj$r$*$3$J$$(B,$BM>J,$J<B9T$rM^@)$9$k(B.
$B$=$N7k2L$H$7$FLdBj$N%5%$%:(B $n$ $B$KBP$7$FB?9`<0;~4V$G2r$1$kLdBj$K$J$k(B.($BB?9`<0(B
$B5"Ce@-(B).  $B%"%i%$%s%a%s%HLdBj$O7k6I%M%C%H%o!<%/$N%9%3%":GBg7PO)LdBj$K5"Ce$9$k(B
$B$3$H$O=R$Y$?(B.

 DP$B$K$h$j(B2$B<!85%M%C%H%o!<%/$N:GE,7PO)$r5a$a$kJ}K!$O<!$N$H$&$j$K$J$k(B. \\
 \vskip 0.5 cm
 {\gt [$B%"%k%4%j%:%`(B]}

 1.$B8=:_$N%N!<%I$K;j$kD>A0$KDL2a$9$k2DG=@-$N$"$k%N!<%IA4$F$r9M$((B,$B3F!9$rDL2a(B
   $B$7$F$-$?>l9g$N:GE,%9%3%"$r7W;;$9$k(B.$B$9$J$o$A(B,$B%9%?!<%H%N!<%I$+$i$=$l$i3F(B
   $B%N!<%I$^$G$N:GC;7PO)$N%9%3%"$H(B,$B$=$3$+$iEv3:%N!<%I$X$N%"!<%/$N%9%3%"$r2C;;(B
   $B$9$k(B. 

 2.$B$=$NCf$+$i:GNI$N$b$N$rA*$S$@$7(B,$B$=$NCM$r8=:_$N%N!<%I$X$N:GC;7PO)$N%9%3%"(B
   $B$H$9$k(B.$BD>A0$K$I$N%N!<%I$+$iA*Br$7$?$+$H$$$&>pJs$bIU$12C$($k(B. 

 3.$B8=:_$N%N!<%I$,%4!<%k%N!<%I$G$J$1$l$P(B 1. $B$XLa$k(B. 

 4.$B%4!<%k%N!<%I$G$"$l$P(B,$B$=$3$+$i=g$K(B,$B$I$N%N!<%I$+$iA*Br$7$?$+$H$$$&>pJs$r(B
   $BC)$C$F$$$/$3$H$G:GC;7PO)$rF@$k(B. 

 \vskip 0.5cm
   $B$5$F(B,$B$3$N(BDP$B%"%k%4%j%:%`$OEv3:%N!<%I$N:8(B,$B>e(B,$B:8>e$N#3$D$N%N!<%I$,7W;;:Q$_(B
 $B$G$"$l$P7W;;$G$-$k(B.$B$h$C$F:8>e$+$i9TM%@h$G7W;;$9$l$P$h$$(B.$B$3$N$H$-(B,$BJBNs2=$r(B
 $B9T$J$&$?$a$K$O<!$N?^$N$h$&$JJ,3dJ}K!$,9M$($i$l$k(B.$B$^$?3FJ,3dJ}K!$KBP$7$F$D(B
 $B$.$N$h$&$KJ,N`$5$l$k(B.  \\

 {\gt $B%0%k!<%W(B1...(a)(b)(c)} $B$3$NJ,3dJ}K!$G$O(B,$B3F%W%m%;%C%5$OA0$N%W%m%;%C%5(B
 $B$,7W;;$,=*$k$^$G%G!<%?$,F@$i$l$:(B,$B<B9T$G$-$J$$(B.$B$h$C$FJBNs<B9T$9$k$K$OITE,(B
 $B$G$"$k(B. 

 {\gt $B%0%k!<%W(B2...(d)(e)(f)} $B%W%m%;%C%5(B $P_i$ $B$O0l9TJ,$N=hM}$r=*$($k$H(B,$B$=$N(B
  $B7k2L$r1&$I$J$j$N%W%m%;%C%5(B $P_{i+1}$ $B$KAw?.$9$k(B. $P_{i+1}$ $B$O$=$N%G!<%?(B
  $B$r<u?.$9$k$H(B,$B$=$N9T$N=hM}$,$G$-$k$N$G(B $P_i$ $B$N<!$N9T$H%*!<%P!<%i%C%W$7$F(B
  $B=hM}$r?J$a$k$3$H$,$G$-$k(B. \\
    $B$3$N$H$-J,3d$NBg$-$5$,>.$5$$$H(B,$B=hM}$h$j$bDL?.$N;~4V$,$+$+$j=hM};~4V$,(B
  $BM>J,$K$+$+$C$F$7$^$&62$l$,$"$k(B. 

 {\gt $B$=$NB>(B...(g)} DP$B$O%4!<%k%N!<%I$+$i;O$a$F$bF1$8$3$H$G$"$k(B.$B$h$C$F%9%?!<%H(B
 $B$H%4!<%k$NN>J}$+$iJBNs$KC5:w$7$F?^$N??Cf$N!}$G<($7$?%N!<%I$K$D$$$F3F%Q%9$r(B
 $B2C;;$7(B,$B:GE,$J$b$N$r:NMQ$9$k(B. \\

  $B$5$F(B,$BC`<!=hM}$HJBNs=hM}$H$N<B9T;~4V$NI>2A$G$"$k$,<!$N$h$&$K$J$k(B.

 \begin{tabular}{ll}
   $l$:$BG[NsD9(B         &  $t$:1$B%N!<%IEv$?$j$N=hM};~4V(B \\
   $p$:$BJBNs<BAuBf?t(B   &  $r$:$B<u?.%W%m%;%C%5$N%*!<%P%X%C%I(B \\
   $d$:$BDL?.;~4V(B       &  $s$:$BAw?.%W%m%;%C%5$N%*!<%P%X%C%I(B \\
 \end{tabular}

 $B$H$7(B,$T_1$ $B$rC`<!=hM}$r9T$J$C$?>l9g$NA4BN$N<B9T;~4V(B,$T_p$ $B$r(B $p$ $BBf$N(B
 $B%W%m%;%C%5$KJ,3d$7$FJBNs=hM}$r9T$J$C$?>l9g$N=hM};~4V$H$9$l$P(B 

 \begin{eqnarray*}
   T_1 &=& (1$B%N!<%IEv$?$j$N=hM};~4V(B) \times ($BA4%N!<%I?t(B) \\
       &=& tl^2  \\
   T_2 &=& ($B9T$N=hM};~4V(B + $BAw?.(B) \times (1$B$+$i(Bl-1$B9T(B) + (n$B9T$N=hM};~4V(B) +  \\
       & & ($BNs$N=hM};~4V(B + $BDL?.;~4V(B + $B<u?.(B) \times (p_2 $B$+$i(B p_p) \\
       &=& \left( \frac{tl}{p} + s \right) (l-1) + \frac{tl}{l} + \left( \frac{tl}{p} + d +r \right) (p-1) \\
 \end{eqnarray*}
  $B$h$C$F$=$NHf$O(B

 \begin{eqnarray*}
  \frac{T_p}{T_1} &=& \frac{(\frac{tl}{p} + s)(l-1) + \frac{tl}{l} + (\frac{tl}{p} + d +r)(p-1)}{tl^2} \\
                  &\to& \frac{1}{p} (l \to \infty) \\
 \end{eqnarray*}

 $B$H$J$j(B,$BG[Ns$ND9$5$,$"$kDxEY$*$*$-$$$H$-(B,$B$9$J$o$ALdBj$,$*$*$-$$$H$-$K$O(B
 $B%W%m%;%C%5Bf?t$KHfNc$7$?@-G=$,$G$k$3$H$,4|BT$5$l$k(B.

 \subsubsection{ $A^*$ $B%"%k%4%j%:%`$NE,MQ(B}
  $BBhFs$NJ}K!$H$7$F%0%k!<%W4V%"%i%$%s%a%s%H$rF0E*7W2hK!$N$h$&$JLUL\E*C5:w(B
 $B$G$O$J$/(B,$B$h$j2r$K6aIU$/$h$&$KC5:w$9$k%R%e!<%j%9%F%#%C%/C5:w$G$"$k(B $A^*$ 
  $B%"%k%4%j%:%`$r:NMQ$7$FL5BL$JC5:w6u4V$r:o8:$7$F9bB.2=$9$kJ}K!$,9M$($i$l$k(B.
  $A^*$ $B%"%k%4%j%:%`$O:G>.$J%N!<%IE83+$G2r$KE~C#$9$k$3$H$,>ZL@$5$l$F$$$k(B.

  \vskip 0.3cm
 {\gt $A^*$ $B$NI>2A4X?t(B} $B%R%e!<%j%9%F%#%C%/C5:w$r<B8=$9$k$?$a(B,$BE83+$9$k(B
  $B8uJd$N%N!<%I$+$i2r$,$"$k$H;W$o$l$k%N!<%I$r7hDj$9$k$?$a(B,$BI>2A4X?t$r(B
  $BF3F~$9$k(B. 
   
  \begin{eqnarray*}
    g(n) &:& $B=i4|@aE@$+$i@aE@(Bn$B$^$G$N%3%9%H(B \\
    h(n) &:& $B?dDj4X?t(B \\
    f(n) &=& g(n) + h(n) 
  \end{eqnarray*}

  $B$3$N?dDj4X?t$NCM$,>.$5$$@aE@$+$iE83+$,9T$J$o$l$k(B.
 
 \vskip 0.3cm
 {\gt [$B%"%k%4%j%:%`(B]}

  $s$:$B=i4|@aE@(B \\
  OPEN:$BL$E83+@\E@$N=89g(B \\
  CLOSED:$BE83+:Q$_$N@aE@$N=89g(B \\

  \begin{tabular}{lll}
   1. & &  $f(s)$ $B$r7W;;(B. \\
      & &  OPEN $\gets$ \{ s \} \\
      & &  CLOSE $\gets$ \{ \} \\
   2. & &  OPEN = \{ \} $B$J$iC5:w$O<:GT(B. \\
   3. & &  OPEN$B$N$J$+$+$i(B $f(n)$ $B$,:G>.$N@aE@(B $n$ $B$rA*Br(B. \\
      & &  OPEN $\gets$ OPEN - \{ $n$ \} \\
      & &  CLOSED $\gets$ CLOSED $\cup$ \{ $n$ \} \\
      & &  $n$ $B$,L\I8@aE@$J$iC5:w$O@.8y(B. \\
      & &  ($B2r$O@aE@(B $n$ $B$+$i(B $s$ $B$X$N%]%$%s%?$rC)$k$3$H$K$h$C$FF@$i$l$k(B.) \\
   4. & &  $n$ $B$rE83+(B. \\
      & &  $B3F(B $n'$ $\in$ $B$K$D$$$F0J2<$N=hM}$r9T$J$&(B. \\
      & (a) & $n' \notin$ OPEN $\cup$ CLOSED $B$N>l9g(B: \\
      & i.  & $n'$ $B$+$i(B $n$ $B$K%]%$%s%?$r$O$k(B. \\
      & ii. & $f(n')$ $B$r7W;;(B. OPEN $\gets$ OPEN $\cup$ \{ $n'$ \} \\
      & (b) & $n' \in $ OPEN $B$N>l9g(B: \\
      &     & $f(n')$ $B$r:F7W;;(B.$B?7$?$K7W;;$7$?(B $f(n')$ $B$NJ}$,>.$5$1$l$P(B,$B0J2<(B
              $B$r9T$J$&(B. \\
      & i.  & $n'$ $B$+$i(B $n$ $B$K%]%$%s%?$r$O$k(B. \\
      & (c) & $n' \in $ CLOSED $B$N>l9g(B: \\
      &     & $f(n')$ $B$r:F7W;;(B.$B?7$?$K7W;;$7$?(B $f(n')$ $B$NJ}$,>.$5$1$l$P(B,$B0J2<(B
              $B$r9T$J$&(B. \\
      & i.  & $n'$ $B$+$i(B $n$ $B$K%]%$%s%?$r$O$k(B. \\
      & ii. & OPEN $\gets$ OPEN $\cup$ \{ $n'$ \} \\
      & iii. & CLOSED $\gets$ CLOSED - \{ $n'$ \} \\   
 \end{tabular}

 \vskip 0.8cm
 {\gt $A^*$ $B$N@-<A(B} \\
  $B$3$3$G$O(B $A^*$ $B$N@-<A$r=R$Y$k(B.
 
 [$BE,3J@-(B(admissibility)]: \\
 $B?dDj4X?t(B $h$ $B$,E,3J(B,$B$9$J$o$A(B $\forall n \ ,h(n) \leq h^*(n)$ $B$G$"$l$P(B,
 $BL58B%0%i%U$NLdBj6u4V$K$*$$$F(B,$B=i4|@aE@$+$iL\I8@aE@$K;j$k7PO)$,B8:_$9$l$P(B
 $A^*$ $B$OI,$::GE,2r$r$_$D$1$k(B. \\
 \vskip 0.3cm
 {\gt $B>ZL@(B} \\
 $ g(x) > f^*(s) $ $B$J$kG$0U$N@aE@(B $x$ $B$,E83+$5$l$kA0$K(B,$BL\I8@aE@$KE~C#$9$k(B
 $B$3$H$r<($9(B. \\
 
 1. $ s = n_0,n_1,\cdots ,n_i,n_{i+1}, \cdots , n_k = t $ $B$rL\I8@aE@$K;j$k(B
    $B:GC;7PO)$H$7(B,$B4{$K(B $ n_0, \cdots , n_i $ $B$,E83+$5$l$F$$$k$H$9$k(B. \\
    $B2>Dj$NE,3J@-$h$j(B, $ h(n_{i+1}) \leq h^*(n_{i+1}) $ .$B$^$?(B, $ n_0,\cdots n_i$
    $B$,$9$Y$FE83+$5$l$F$$$k$N$G(B $g(n_{i+1}) = g^*(n_{i+1})$. $B=>$C$F(B, 

    \begin{eqnarray*}  
     f(n_{i+1}) &=& g(n_{i+1}) + h(n_{i+1}) \leq g^*(n_{i+1}) + h^*(n_{i+1}) \\
                &=& f^*(s) < g(x) \leq g(x) + h(x) = f(x) 
    \end{eqnarray*}

    $B$f$($K(B $n_{i+1}$ $B$,(B $x$ $B$h$j@h$KE83+$5$l$k(B. \\
 2. $B>e5-$r7+$jJV$7E,MQ$9$k$H(B,$B@aE@(B $x$ $B$rE83+$9$kA0$KL\I8@aE@(B $n_k$ $B$KE~C#(B
    $B$9$k(B. \ \ \ \  ($B>ZL@=*$j(B) \\

 \vskip 0.5cm  
 [$B?dDj4X?t$NC1D4@-(B(monotonicity)]: \\
  $B?dDj4X?t$,C1D4(B,$B$9$J$o$A=i4|@aE@$+$i$N7PO)$K1h$C$F?dDj4X?t$NCM$,7h$7$F(B
 $B8:>/$7$J$$$H$-(B, $A^*$ $B$K$h$k@aE@$NE83+$O(B,$B$=$N@aE@$K8~$1$F$N:GC;7PO)>e$G$N$_(B
 $B$*$3$J$o$l$k(B.$B$9$J$o$A(B CLOSED$B@aE@$O:FE83+$5$l$J$$(B.

  \vskip 0.5cm
  {\gt $B%/%k!<%W4V%"%i%$%s%a%s%H$X$N1~MQ(B} \\
 
  {\gt $BLdBj6u4V$NJQ49(B}
  DP$B$K$h$k2rK!$G$O(B,$B!V%9%3%"!W$rM?$((B,$B$=$N!V%9%3%":GBg7PO)!W$NLdBj$K5"Ce$5$;$?(B.
 $B$=$3$G(B $A^*$ $B$K$h$kC5:w$G$O(B,$B%"!<%/$K%3%9%H$,M?$($F$"$j(B,$B!V%3%9%H:G>.7PO)!W(B
 $BLdBj$K5"Ce$9$k$3$H$r<($9(B.

  $B$^$::G=i$K(B $A^*$ $B$NI>2A4X?t$OIi$K$J$i$J$$$?$a(B,$B8=%9%3%"(B $S$ $B$K2<BL$P$-(B $c$ $B$r(B
 $B$5$;(B $-S + c > 0$ $B$H$9$k$3$H$r;W$$$D$/$G$"$m$&!#$7$+$7$J$,$i(B,$B$3$NA}J,$O(B
 $B7PO)$K0MB8$7$F(B,$B$b$H$NC5:w6u4V$HEy2A$K$J$i$J$/$J$k(B.$B$h$C$F(B,$B%3%9%H$,$9$Y$F@5$K(B
 $B$J$k$h$&$KJQ49$9$k$3$H$r9M$($k(B. 

  $B$$$^%M%C%H%o!<%/$N3+;OE@$r(B $n(0,0)$ $B$H$7(B,$B%4!<%k%N!<%I$r(B $n(l,l)$ $B$H=q$/(B
 $B$3$H$H$9$k(B.$B$$$^<P$a$N%"!<%/$N?t$r(B $D$ $B$H$9$k$H(B, $n(i,j)$ $B$G$N%[%C%W?t$r(B
 $B0J2<$N$h$&$KDj5A$9$k(B.

  \begin{eqnarray*}
    H(i,j) = i + j - D 
  \end{eqnarray*}

 $B$3$l$K(B,$B<P$aJ}8~$N%"!<%/$r(B 2hop $B$H$9$k(B $n(i,j)$ $B$G$N:GE,7PO)$N%[%C%W?t$r(B
 $ H'(i,j)$ $B$O7PO)$K$h$i$:(B {\gt $B>o$K(B i+j $B$G0lDj$H$J$k(B.}$B$h$C$F(B 1hop $B$"$?$j(B
 $+c$ $B$N$+$5$"$2$9$l$O(B,$BC5:w6u4V$O$b$H$N$b$N$HEy2A$K$J$k(B.$B$3$l$rMxMQ$7$F(B
 $B<!$NJdBj$r>ZL@$9$k(B.$B$?$@$7(B,$BG$0U$N7PO)(B $P$ $B$N%9%3%"$r(B $Score(P)$ ,$BF1$87PO)(B
 $B$NEy2AJQ49$5$l$?LdBj6u4V$N%3%9%H$r(B $Cost(P)$ $B$H$9$k(B.

 \vskip 0.5cm
 {\gt $BJdBj(B}

 $B$b$H$NLdBj6u4V$K$*$1$kG$0U$N7PO)(B $P$ $B$N%9%3%"$r(B $Score(P)$, $BF1$87PO)$N(B
 $B?7$7$/@_Dj$5$l$?LdBj6u4V$N%3%9%H$r(B $Cost(P)$ $B$H$9$k(B.$B$"$k(B2$BE@4V$NG$0U$N(B
 2$B$D$N7PO)(B $P_1,P_2$ $B$K$D$$$F(B

 $$ Score(P_1)< Score(P_2) \Leftrightarrow Cost(P_1) > Cost(P_2) $$

 {\gt $B>ZL@(B} \\

 $B@h$[$I$NJ}K!$h$j(B
 \begin{eqnarray}
   Cost(P_1) &=& -Score(P_1) + H'(P_1) \times c  \\
   Cost(P_2) &=& -Score(P_2) + H'(P_2) \times c 
 \end{eqnarray}
  
 $B>e=R$N$h$&$K(B2$BE@4V$N7PO)$N(B hop$B?t$O7PO)$K$h$i$:0lDj$G$"$C$?$+$i(B

 $$ H'(P_1) = H'(P_2) $$
 (1)(2)$B<0$r:90z$-(B,$B>e<0$rBeF~$7$F(B \\
  
 \begin{eqnarray*}
 Cost(P_1) - Cost(P_2) &=& Score(P_2) - Score(P_1)  \\
 $B$f$($K(B & & \\
 Score(P_1) < Score(P_2) & \Leftrightarrow &  Cost(P_1) > Cost(P_2) \ \ \ \ 
     \ \ \ \ \ \ \ \ \ \  ($B>ZL@=*$j(B)     \\
 \end{eqnarray*} 

  \vskip 0.3cm
  {\gt $B%R%e!<%j%9%F%#%C%/4X?t$N@_Dj(B} \\

  $ A^*$ $B%"%k%4%j%:%`$O$=$N?dDj4X?t(B $h$ $B$r$I$&@_Dj$9$k$+$K$h$C$FBg$-$/0MB8(B
 $B$9$k(B.$B$9$J$o$A<B9T$KBP$7$F(B \\
  1. $B:GE,7PO)H/8+$NJ]>Z(B \\
  2. $B7PO)H/8+$K:]$7$F3HD%$5$l$k%N!<%I?t(B \\
  3. $h$ $B$N7W;;$KI,MW$J%3%9%H(B \\
  $B$G$"$k(B.$B$3$3$G$O(B

  $$ h^*(n) = \sum_{m=j+1}^l \min_{k \in \{ x | i+1 \leq x \leq l \} }
            C(m,k) + P' \times | i-j | \leq h(n) $$
  $ C_{i,j}:n(i-1,j-1)$B$H(Bn(i,j)$B$H$r7k$V%"!<%/$KM?$($i$l$?%3%9%H(B,P':
    $B%.%c%C%W%Y%J%k%F%#(B $  \\

 $B$H=R$Y$k$@$1$KN1$^$k(B.

 \subsection{$B@-G=I>2A$H9M;!(B}

  $BI=(B1$B$K%W%m%;%C%5?t$H=hM};~4V(B,$BB.EY8~>eHf(B,$B8zN($N4X78$r<($9(B.
 
 $B!|(B $BLdBj$,$*$*$-$/$J$k$[$I(B,$BJBNs=hM}$N8z2L$,$G$k(B

 \vskip 0.3 cm  
 {\gt [DP$B$NBf?t8z2L(B]} \\
  
 $B?^(B16$B$K(BDP$B$NJBNs2=$K$h$kB.EY8~>eHf$r<($9(B. \\

 $B!|(B $BJBNs$NBf?t8z2L$,Hf3SE*=P$F$$$k(B \\

    $BG[NsD9$,Bg$-$$$[$IN3EY$,Bg$-$/$J$k$?$a(B,$B$&$^$/%W%m%;%C%54VDL?.$K(B
  $B$h$k%l%$%F%s%7$,1#JC$5$l$F$$$k(B.$BJBNs2=$N<jK!$G$O(B DP $B$N$[$&$,8~$$$F$$$k(B
  $B%"%k%4%j%:%`$G$"$k$3$H$,$o$+$k(B.

 \vskip 0.3 cm
 {\gt [$A^*$ $B%"%k%4%j%:%`$NC5:w8zN((B] } \\
 
 $B?^(B17$B$O2#<4$OF@$i$l$?%"%i%$%s%a%s%H$N%+%i%`Ev$?$j$NJ?6Q%9%3%"$G$"$k(B.
 $B$3$NCM$,$*$*$-$$$[$IN`;w$7$F$$$k$3$H$rI=$9(B. \\

 $B!|(B $BN`;wEY$,9b$$$[$IC5:w6u4V$,:o8:$G$-(B,$B8z2LE*$G$"$k(B. \\
 
  $BHf3SE*(B,$BN`;wEY$,Dc$$G[Ns$G$b(B,$BA4BN$N#2#5!sDxEY$GC5:w$,2DG=$@$,(B,
  $B%G!<%?$K0MB8$9$k$3$H$OL@$i$+$G$"$k(B. 


 \section {$B$*$o$j$K(B}

  $BJBNs2=$N8z2L$,$"$k$N$O(B,$BH?I|K!$J$I$N$h$&$K(B,$B%G!<%?$NN.$l$,7h$^$C$F$$$k(B
$B%"%k%4%j%:%`$NJ}$,@-G=$,$G$d$9$$(B.$B$H$$$&$N$O(B,$B%W%m%;%C%54V$N%G!<%?$N<uEO$7(B
$B$K4X$9$kDL?.;~4V$,:o8:$5$l$k$+$i$G$"$k(B.$B$^$?(B,$B<B:]%W%m%;%C%5$r3d$jEv$F$k$H(B
$B$-J,3d$NJ}K!$,ITE,3J$G$"$l$O(B,$B$^$C$?$/JBNs=hM}$,$G$-$J$$$3$H$b$"$k(B. 

  $B0lJ}(B,$BLdBj<+BN$N@-<A$b9MN8$9$Y$-$G$"$k(B.$B>l9g$K$h$C$F$O(B,$BJBNs=hM}$7$J$/$F$b(B
$B%"%k%4%j%:%`$NJQ99$K$h$j=hM}B.EY$,8~>e$9$k>l9g$b$"$j$&$k$@$m$&(B.

 \section{$B;29MJ88%(B}
 
 [1] $B9SLZ(B \ $B;VHA(B $BJBNsH?I|2~A1K!$K$h$k%?%s%Q%/<AG[Ns$N%"%i%$%s%a%s%H(B 
    ($BF0E*7W2hK!$NJBNs2=$H(B $A^*$ $B%"%k%4%j%:%`$NE,MQ(B).$B5~ETBg3XB46HO@J8(B.
    1993.

 [2] A.Barr and E.A.Feigenbaum,$ The Handbook of Artifical Intelligence $,
    Willam Kaufmann,Inc,1981.

 [3] $BLn;{(B $BN4;V(B.$B3Z!9(B $\LaTeX$.$B6&N)=PHG3t<02q<R(B 

 \newpage
 
 \section {$B%"%W%j%1!<%7%g%s;qNA(B}

\end{document}










