Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
幅優先ビームサーチがこれで合ってるのか分からないけど説明読んだだけのイメージで実装してみた
// 結論(出力結果)
// Rank 1: Sum: 486, HELMS-05(54)
// BODIES-05(50)
// FOLDS-01(141)
// HANDS-04(120)
// LEGS-04(121)
// Rank 2: Sum: 484, HELMS-05(54)
// BODIES-05(50)
// FOLDS-05(139)
// HANDS-04(120)
// LEGS-04(121)
// Rank 3: Sum: 482, HELMS-01(50)
// BODIES-05(50)
// FOLDS-01(141)
// HANDS-04(120)
// LEGS-04(121)
// Rank 4: Sum: 482, HELMS-05(54)
// BODIES-05(50)
// FOLDS-01(141)
// HANDS-04(120)
// LEGS-02(117)
// Rank 5: Sum: 480, HELMS-05(54)
// BODIES-05(50)
// FOLDS-05(139)
// HANDS-04(120)
// LEGS-02(117)
// 5種類の防具をそれぞれ1つずつ身につけられる
// 愚直に探索すると5の5乗で3125通りの解がある
// 最も防御力が高くなる組み合わせを上位5通り求める
var HELMS = [{
name: 'HELMS-01',
defense: 50,
}, {
name: 'HELMS-02',
defense: 1,
}, {
name: 'HELMS-03',
defense: 30,
}, {
name: 'HELMS-04',
defense: 25,
}, {
name: 'HELMS-05',
defense: 54,
}];
var BODIES = [{
name: 'BODIES-01',
defense: 10,
}, {
name: 'BODIES-02',
defense: 20,
}, {
name: 'BODIES-03',
defense: 30,
}, {
name: 'BODIES-04',
defense: 40,
}, {
name: 'BODIES-05',
defense: 50,
}];
var FOLDS = [{
name: 'FOLDS-01',
defense: 141,
}, {
name: 'FOLDS-02',
defense: 60,
}, {
name: 'FOLDS-03',
defense: 64,
}, {
name: 'FOLDS-04',
defense: 59,
}, {
name: 'FOLDS-05',
defense: 139,
}];
var HANDS = [{
name: 'HANDS-01',
defense: 102,
}, {
name: 'HANDS-02',
defense: 69,
}, {
name: 'HANDS-03',
defense: 61,
}, {
name: 'HANDS-04',
defense: 120,
}, {
name: 'HANDS-05',
defense: 88,
}];
var LEGS = [{
name: 'LEGS-01',
defense: 41,
}, {
name: 'LEGS-02',
defense: 117,
}, {
name: 'LEGS-03',
defense: 109,
}, {
name: 'LEGS-04',
defense: 121,
}, {
name: 'LEGS-05',
defense: 89,
}];
var SEARCH_ORDER = [
HELMS,
BODIES,
FOLDS,
HANDS,
LEGS,
];
var BEAM_WIDTH = 5;
var beams = [];
// 評価関数
// 防御力の和を返す
function score(beam) {
return beam.reduce(function(memo, gear) {
return memo + gear.defense;
}, 0);
}
// 出力用
function stringify(beam) {
return beam.map(function(gear) {
return gear.name + '(' + gear.defense + ')';
}).join("\n");
}
SEARCH_ORDER.forEach(function(gears, i) {
var results = [];
// 結果を詰める
if(i === 0) {
results = gears.map(function(gear) {
return [gear];
});
} else {
beams.forEach(function(beam) {
gears.forEach(function(gear) {
// 枝刈りポイント: 評価が下がる場合。今回の場合負の数がないので不要、TODO
results.push(beam.concat([gear]));
});
});
}
// ソートする
results.sort(function(beamA, beamB) {
return (score(beamB) - score(beamA));
});
// ビーム幅で切り落とす
beams = results.slice(0, BEAM_WIDTH);
});
// 出力
beams.forEach(function(beam, i) {
console.log('Rank ' + (i+1) + ': Sum: ' + score(beam) + ', ' + stringify(beam));
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment