分割統治 Divide and Conquer : PHPで実装

Tweet

Pocket

分割統治は元の問題を分割していき分割された問題の解を統合して最終的な解を求めます。

アルゴリズムクイックリファレンス 第2版で掲載されているサンプルをPHPで実装した例です。

関数の呼び出しは丸付き数字の順で呼び出されます。木構造では深さ探索と同じように一筆書きで呼び出しをなぞれます。

<?php
/*
 * 分割統治 Divide and Conquer
 * 
 * アルゴリズムクイックブック p48
 */
class DAC
{
    /**
     * @param integer[] $a
     * @return integer
     */
    public function getMax(array $a)
    {
        return $this->calc($a, 0, count($a));
    }

    /**
     * @param integer[] $a
     * @param integer   $left
     * @param integer   $right
     * @return integer
     */
    private function calc($a, $left, $right)
    {
        if (( $right - $left ) == 1) {
            return $a[$left];
        }
        $mid  = (int) floor(( $left + $right ) / 2);
        $max1 = $this->calc($a, $left, $mid);
        $max2 = $this->calc($a, $mid, $right);

        return ( $max1 > $max2 ) ? $max1 : $max2;
    }
}
$a   = [4, 3, 1, 2];
$o = new DAC();
$max = $o->getMax($a);
echo $max;  // 4