設計技法「全探索」を学ぶ

最近はアルゴリズムを勉強している。

なかなか頭に入ってこないので、アウトプットをして整理する。

なお、今回は設計技法「全探索」の話。

アルゴリズムを設計するうえで重要な基礎となるのが「全探索」。

「全探索」とは何か？ => 解きたい問題に対して、考えられる可能性をすべて調べ上げることによって解決する手法。

高速なアルゴリズムを設計したい場合であっても、まず最初に力任せの全探索手法を考えることが有効な場合もあるらしい。

なぜなら、「全探索」をすれば遅くてもすべてを調べ上げることによって、問題を解決することができるから。

線形探索法（計算量：O(N))

N個の整数 a0,a1,..., aN-1 と整数vが与えられる。ai = V となるデータが存在するかどうかを判定してください。

これも解くと以下のようになる。

func main() {
    fmt.Println("N個の整数 a0,a1,..., aN-1 と整数vが与えられる。ai = V となるデータが存在するかどうかを判定してください。")

    var N int
    fmt.Print("N:")
    _, n_err := fmt.Scan(&N)
    if n_err != nil {
        fmt.Println("input error.")
        return
    }

    a := make([]int, N, N)
    for i := 0; i < N; i++ {
        fmt.Printf("a[%d]:", i)
        _, err := fmt.Scan(&a[i])
        if err != nil {
            fmt.Println("input error.")
            return
        }
    }

    var V int
    fmt.Print("V:")
    _, v_err := fmt.Scan(&V)
    if v_err != nil {
        fmt.Println("input error.")
        return
    }

    exist := false
    for _, v := range a {
        if v == V {
            exist = true
            break
        }
    }

    fmt.Println(exist)
}

全探索は応用範囲が広く、全探索する = すべての値を参照するという特徴から以下のようなすべての値を参照しないとわからないようなものを見つけることに向いている。

見つけたい値の添字の取得
最小値・最大値の取得

次は応用問題で、与えられたデータの中から最適なペアを探す問題を解いてみる。

N個の整数a0,a1....aN-1とN個の整数b0,b1...bN-1が与えられる。
2組の正数列からそれぞれ1個ずつ整数を選んで和を取ります。その和として考えられる値のうち、整数K以上の範囲内で最小値を求めてください。

package main

import (
    "fmt"
    "math"
)

func main() {
    fmt.Println("N個の整数a0,a1....aN-1とN個の整数b0,b1...bN-1が与えられる。\n2組の正数列からそれぞれ1個ずつ整数を選んで和を取ります。その和として考えられる値のうち、整数K以上の範囲内で最小値を求めてください。")

    var N int
    fmt.Print("N:")
    _, n_err := fmt.Scan(&N)
    if n_err != nil {
        fmt.Println("input error.")
        return
    }

    a := make([]int, N, N)
    for i := 0; i < N; i++ {
        fmt.Printf("a[%d]:", i)
        _, a_err := fmt.Scan(&a[i])
        if a_err != nil {
            fmt.Println("input error.")
            return
        }
    }

    b := make([]int, N, N)
    for i := 0; i < N; i++ {
        fmt.Printf("b[%d]:", i)
        _, b_err := fmt.Scan(&b[i])
        if b_err != nil {
            fmt.Println("input error.")
            return
        }
    }

    var K int
    fmt.Print("K:")
    _, k_err := fmt.Scan(&K)
    if k_err != nil {
        fmt.Println("input error.")
        return
    }

    pair_min_value := math.MaxInt64
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            sum := a[i] + b[j]
            if sum <= K {
                continue
            }
            if sum < pair_min_value {
                pair_min_value = sum
            }
        }
    }

    fmt.Println(pair_min_value)
}