深さ優先探索アルゴリズムを実装 部分和問題を解く

2018-12-25
javascript%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0atcoder
    

目次

深さ優先探索について

深さ優先探索(depth-first search)は探索手法の一つです。 DFS、バックトラック法とも呼ばれます。 探索する木の1番目のノードから、「目的のノードに着く」もしくは「子のないノードに着く」まで、縦に伸びる探索です。 性質上、再帰関数を使うと簡単に実装できるそうです。

状態遷移の様子

https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

より

部分和問題を解いてみる

部分和問題

https://ja.wikipedia.org/wiki/%E9%83%A8%E5%88%86%E5%92%8C%E5%95%8F%E9%A1%8C

ここから問題を借りてきます。

問題

{1,3,7,10,13} の部分和で、和が 21 になるものは存在するか?

※ 21 = 1 + 7 + 13 となるので存在します。

サンプルコード

main()

function main(arg) {
    const k = 21
    const a = [1,3,7,10,13]

    function dfs(i, sum) {
        if (i === a.length) {
            return sum === k
        }

        if (dfs(i + 1, sum)) {
            return true
        }

        if (dfs(i + 1, sum + a[i])) {
            return true
        }

        return false
    }

    if (dfs(0, 0)) {
        console.log("Yes")
    } else{
        console.log("No")
    }
}

Yesと出力されます。

const k = 19
const a = [2,4,6,8,10]

とした時は「No」と出力されました。

デバッグ

関数dfsにデバッグを入れて動きをみてみました。

main()

function main(arg) {
    const k = 21
    const a = [1,3,7,10,13]

    function dfs(i, sum) {
        console.log([i, sum])
        if (i === a.length) {
            return sum === k
        }

        if (dfs(i + 1, sum)) {
            console.log(`dfs(${i}, ${sum})`)
            return true
        }

        if (dfs(i + 1, sum + a[i])) {
            console.log(`dfs(${i} + 1, ${sum} + a[i])`)
            return true
        }

        return false
    }

    if (dfs(0, 0)) {
        console.log("Yes")
    } else{
        console.log("No")
    }
}

以下のように出力されました。

0,0
1,0
2,0
3,0
4,0
5,0
5,13
4,10
5,10
5,23
3,7
4,7
5,7
5,20
4,17
5,17
5,30
2,3
3,3
4,3
5,3
5,16
4,13
5,13
5,26
3,10
4,10
5,10
5,23
4,20
5,20
5,33
1,1
2,1
3,1
4,1
5,1
5,14
4,11
5,11
5,24
3,8
4,8
5,8
5,21
dfs(4 + 1, 8 + a[i])
dfs(3, 8)
dfs(2 + 1, 1 + a[i])
dfs(1, 1)
dfs(0 + 1, 0 + a[i])
Yes

例題: AtCoder ABC015 C

https://atcoder.jp/contests/abc015/tasks/abc015_3

解説

ソースコード

"use strict"
function main(arg) {
    let tmp = arg.trim().split("\n").map(e => e.split(" ").map(Number))
    let [N,K] = tmp.shift()
    let data = tmp.slice()
    function dfs(i, sum) {
        if (i + 1 === data.length) {
            return sum === 0
        }
        for (let j = 0; j < K; j++) {
            let t = dfs(i+1, data[i+1][j] ^ sum)
            if (t) {
                return true
            }
        }
        return false
    }
    for (let i = 0; i < K; i++) {
        let ans = dfs(0, data[0][i])
        if (ans) {
            console.log('Found')
            return
        }
    }
    console.log('Nothing')
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

おまけ : 2進数を利用して

こんな方法でも実装できました。

main()

function main(arg) {
    const k = 21
    const a = [1,3,7,10,13]

    var ans = false

    for (var i = 0; i < 32; i++) {
        //2進数作成
        var bin = i.toString(2)
        for (var j = bin.length; j < a.length; j++) {
            bin += "0"
        }
        bin = bin.split("").map(e => Number(e))
        var sum = 0
        for (var j = 0; j < bin.length; j++) {
            if (bin[j] === 1) {
                sum += a[j]
            }
        }
        if (sum === k) {
            ans = true
            break
        }
    }

    if (ans) {
        console.log("Yes")
    } else {
        console.log("No")
    }
}
    

関連記事

Node.js で作成した REST API を Docker化
Node.jsでREST APIを作成 コンテナ化 コンテナ化定義 コンテナ化作業 参考 Node.js で作成した REST API を Docker化した際のメモです。 Node.jsでREST APIを作成 まずはNode.js…

JavaScriptで優先度付きキューを実装する
優先度付きキューについて ソース 参考 JavaScriptで優先度付きキュー (プライオリティキュー) を実装する 優先度付きキューについて 具体的には次のような機能があります。 キューに対して要素を優先度付きで追加 (push…

next_permutationをJSで実装する
ソース 使い方 参考 C++で提供されている順列を生成する next_permutation のJS実装です。 ソース 順列が存在する場合はtrueを返し、そうでなければfalse…

応用情報技術者試験の合格体験記
受験時のステータス 受験結果 対策 スケジュール 午前問題 午後問題 参考書等 令和…

[JS]ラジアンから度数に度数からラジアンに変換する
コード 度数からラジアンへ ラジアンから度数へ サンプル ラジアンから度数に度数からラジアンに変換する際のスニペット。 コード 度数からラジアンへ ラジアンから度数へ サンプル

JS/TSのclassでclass名を取得する
コード JS/TSのconstructorを利用して自分自身のクラス名を取得する際のメモ。 コード このコードの結果は次のようになります。

JSで32ビット符号付き整数に対してのビット演算でハマった
具体例 参考にしたサイト JSでサブネットマスクの計算を行おうとしたとき、ビット演算でハマりました。その時のメモです。 JSでサブネットマスクの計算 JSでビット演算子を利用する場合 3…

JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
IPアドレスが指定した範囲内にあるかどうか判定 参考にしたサイト JSでIPアドレス(IPv4)が指定したサブネットの範囲に含まれるか判定するロジックを作った時の記録です。 IPアドレスが指定した範囲内にあるかどうか判定 処理としては、IP…

プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
はじめに 誤差の種類 丸め誤差 打ち切り誤差 桁落ち 情報落ち 桁溢れ誤差 参考にしたサイト コンピュータで出てくる誤差はいくつかありますが、 それらをコードに落として整理しました。 はじめに 例えば の計算の答えは 0.6666666666…

JSでサブネットマスクの計算
JSによるサブネットマスク関連の計算 IPv4アドレス文字列をNumber型に変換する CIDR と サブネットの相互変換 ネットワークアドレス と ブロードキャストアドレス クラス 改めて計算方法を整理する 参考にさせていただいたサイト JSでIPv…

最新の投稿

Node.js で作成した REST API を Docker化
Node.jsでREST APIを作成 コンテナ化 コンテナ化定義 コンテナ化作業 参考 Node.js で作成した REST API を Docker化した際のメモです。 Node.jsでREST APIを作成 まずはNode.js…

JavaScriptで優先度付きキューを実装する
優先度付きキューについて ソース 参考 JavaScriptで優先度付きキュー (プライオリティキュー) を実装する 優先度付きキューについて 具体的には次のような機能があります。 キューに対して要素を優先度付きで追加 (push…

AWS Amplify で コンテナベースのデプロイを行い REST API を構築
検証した環境 やってみる 初期準備 パイプラインを確認 終了処理 参考 AWS Amplify で コンテナベースのデプロイを行い REST API を構築した際のメモです。 検証した環境 amplify 5.1.…

Pythonでソケット通信を実装しメッセージの送受信を行う
ソース server.py client.py 動かしてみる 参考 Pythonでソケット通信を実現する方法です。 ソース server.py サーバ側のソースです。 client.py…

next_permutationをJSで実装する
ソース 使い方 参考 C++で提供されている順列を生成する next_permutation のJS実装です。 ソース 順列が存在する場合はtrueを返し、そうでなければfalse…

応用情報技術者試験の合格体験記
受験時のステータス 受験結果 対策 スケジュール 午前問題 午後問題 参考書等 令和…

[JS]ラジアンから度数に度数からラジアンに変換する
コード 度数からラジアンへ ラジアンから度数へ サンプル ラジアンから度数に度数からラジアンに変換する際のスニペット。 コード 度数からラジアンへ ラジアンから度数へ サンプル

CentOS8 に Python + OpenCV をインストール
インストール テスト CentOS8 で標準で提供されているパッケージで Python + OpenCV 環境を構築する方法です。 検証した環境は CentOS8.3 (Docker) です。 インストール まず opencv…

[Perl] CentOS8 に plenv をインストール
インストール Step1 事前準備 Step2 PATHを通す (README通りにインストール) Step2 PATHを通す ($HOME以外にplenvをインストール) Step3 Perlインストール Step4 cpanmインストール CentOS…

JS/TSのclassでclass名を取得する
コード JS/TSのconstructorを利用して自分自身のクラス名を取得する際のメモ。 コード このコードの結果は次のようになります。

Tags

Dates

s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV
© 2021   404 motivation not found