回溯问题-can'I don’我不知道怎么做

Backtracking issue - can't figure out how to do this

本文关键字：我不知道 don -can 问题 回溯      更新时间：2023-09-26

我正在尝试制作一个小脚本（用于我正在设计的棋盘游戏：p），它取一个对象，其中包含英雄攻击伤害的1-4个随机对象和可能的目标，并通过计算每个可能的结果并权衡结果来计算英雄在攻击中的最佳移动。

这就是我的JavaScript对象的样子：

var usedAttacks = {
    1: {
      attack: 2,
      attackableMonsters: Array(0, 1, 2)
    },
    2: {
     attack: 1,
     attackableMonsters: Array(0,1,3)
    },
    3:{
     attack: 4,
     attackableMonsters: Array(1,2,3)
    }
}

usedAttacks中的键指向进行攻击的英雄id，attack是英雄可以造成的伤害，attackableMonsters数组是一个数组，包含英雄可以攻击的怪物的id。

我想做的是测试给定场景的每个结果，并在每个测试结束时返回一个power值，最后选择导致power弹药数最少的场景。

Hero 1 -> Monster 0, Hero 2 -> Monster 0, Hero 3 -> Monster 1 = Power 10
Hero 1 -> Monster 0, Hero 2 -> Monster 0, Hero 3 -> Monster 2 = Power 11
Hero 1 -> Monster 0, Hero 2 -> Monster 0, Hero 3 -> Monster 3 = Power 8
Hero 1 -> Monster 0, Hero 2 -> Monster 1, Hero 3 -> Monster 1 = Power 10
...

力量是根据英雄攻击阶段结束时仍然活着的怪物的攻击力计算的。

我觉得这个问题必须通过一些基本的回溯来解决，但我就是不知道如何用javascript开始解决它。我不需要一个完整的解决方案，如果有人能提供一些基本的指导，我可以开始开发我自己的解决方案。我将不胜感激！

可能是这样的东西：

我们需要一个数组，其中包含我们将使用索引访问的所有怪物id：

var monsters = [ /* all the monster IDs*/ ];

我们初始化一个target对象，其中包含英雄密钥和怪物值：

var target = {};
var numHeroes = 0;
for ( var i in usedAttacks )
    numHeroes++,
    target[i] = 0; // monsters array index.

并用第一个解决方案初始化最佳解决方案：

var minPower     = calcPower( target ),
    bestSolution = clone( target ); // store a copy, we don't want the solution changed.
function clone(obj) { return JSON.parse( JSON.stringify(obj) ); }

然后我们迭代所有怪物和英雄的组合：

for ( var k = 1; i < monsters.length * numHeroes; k++) {

我们增加怪物，类似于携带的增量：

    for ( var i in usedAttacks )                    // iterate hero IDs
        if ( target[i] + 1 >= monsters.length )
            target[i] = 0;                          // wrap around: carry (no break)
        else {
            target[i]++                             // no wrap:
            break;                                  //   abort.
        }

我们将与最佳解决方案进行比较，并可能进行更新：

    var p = calcPower( target );
    if ( p < minPower ) {
        minPower = p;
        bestSolution = clone( target );
    }
}
相关文章：