最もエネルギー効率のよいルート選択

6 つのポイントがあり，あるポイントから別のポイントへ移動するために必要なエネルギーが energy.matrix で記述されている。1 番目のポイントから 2 番目のポイントに移動するためには，energy.matrix[1, 2] = 7 必要というようなこと。

1 番目のポイントからスタートして，全てのポイントを回った後，最後に 1 番目のポイントに帰る。どのようなルートをとれば，最小エネルギーで回れるか。

解答例

n = 6
energy.matrix <- matrix(c(
0,7,12,8,11,7,
3,0,10,7,13,2,
4,8,0,9,12,3,
6,6,9,0,10,7,
7,7,11,10,0,5,
9,7,8,9,10,0),
ncol=n, byrow=TRUE)
library(e1071)
route = permutations(n)
route = route[route[,1] == 1,] # 1 番目からスタートするルートのみ
total.energy = apply(route, 1, function(r) sum(energy.matrix[cbind(r, c(r[-1], 1))]))
where = which.min(total.energy)
route[where,]
total.energy[where]

実行例

> route[where,] # ルート
[1] 1 4 5 2 6 3

> total.energy[where] # そのときのエネルギー
[1] 39
    
> sum(total.energy == 39) # 最小値をとるルートはいくつあるか確認
[1] 1

> table(total.energy) # 必要エネルギーの分布
total.energy
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 59
 1  1  3  5  8 10  8 13 15 11 12 10  9  3  5  2  2  1  1