問題
方針
最短の経路はすぐわかります。結局、下にN回、右にM回移動することになります。
最短経路は結局、AとBを結ぶ四角形の中の道を、常識的（上に行ったり、右に行ったりしない）に結ぶ線の組み合わせの数ということになります。
この問題では、組み合わせの問題と考えた方が簡単に解を求められますが、ここでは動的計画法の問題として考えます。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。(Wikipedia)
下図のような３点 (i, j), (i, j - 1), (i - 1, j) を考えた場合
- (i, j - 1) から(i, j)
- (i - 1, j) から(i, j)
へ移動する方法は一つしかないため
- (i, j - 1)へ最短経路で到達する経路の数をP(i, j - 1)
- (i - 1, j) へ最短経路で到達する経路の数をP(i - 1, j)
とした場合、(i, j)へ最短経路で到達する経路の数P(i, j)は
a) 0 < i <= m, 0 < j <= nの場合
P(i, j) = P(i, j - 1) + P(i - 1, j)
b) i = 0またはj = 0の場合
P(i, j) = 1
ということになります。
これをコードに落とすと、以下のようになります
これをコードに落とすと、以下のようになります
コード
swift3
//
// ShortestPathMatrix.swift
// ShortestPathCounting
//
// Created by 山崎真一郎 on 2017/02/04.
// Copyright © 2017 山崎真一郎. All rights reserved.
//
import Foundation
class ShortestPathMatrix
{
// 各ポイントへの最短経路数を
// m_cNum * m_rNumの２次元配列と考える
var m_elements: [[Int]] = []
var m_cNum = 0
var m_rNum = 0
// 初期化処理
init(rNum:Int, cNum:Int)
{
m_cNum = cNum
m_rNum = rNum
let row = Array(repeating: -1, count: m_cNum)
m_elements = Array(repeating: row, count: m_rNum)
}
// 各ポイントの計算処理
func calculate()
{
for row in 0...(m_rNum - 1)
{
for col in 0...(m_cNum - 1)
{
if (col == 0 || row == 0)
{
m_elements[row][col] = 1
}
else
{
m_elements[row][col] =
m_elements[row][col - 1] +
m_elements[row - 1][col]
m_elements[row - 1][col]
}
}
}
}
func printMatrix()
{
print(m_elements)
}
}
var matrix = ShortestPathMatrix(rNum: 4, cNum: 5)
matrix.calculate()
matrix.printMatrix()
実行結果
[[1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6], [1, 3, 6, 10, 15, 21], [1, 4, 10, 20, 35, 56], [1, 5, 15, 35, 70, 126]]
マトリックス上に結果を書くと、以下のようになります。
