求算法方案二维数组两点间最短路径

steven026

本帖最后由 steven026 于 2022-12-1 12:51 编辑

有一个大小为i×i地图以二维数组形式表示（4<i<20），

固定有1个起点、1个终点、Math.round(i*i/2)场战斗、i个宝箱、其余均为空路
起点以1表示、战斗以2表示，宝箱以3表示、终点以4表示、空路以0表示
起点固定位置为[Math.floor(i/2),i-1]，终点、战斗、宝箱随机分布在其余位置
每次可以向任意方向（上下左右）移动一步，空路不消耗体力，宝箱不消耗体力，战斗消耗1点体力
求起点至终点消耗体力最小方案
（在消耗体力相同情况下，空路需要尽可能少，宝箱可有可无，体力消耗优先级最高）

示例：

输入：

[
[2, 0, 0, 0, 2, 2],
[0, 0, 2, 0, 3, 2],
[0, 2, 4, 0, 2, 2],
[0, 0, 2, 2, 2, 3],
[2, 0, 0, 2, 3, 2],
[3, 2, 0, 1, 3, 2]
]

输出：
['左','上','左','上','左','上','上','右','上','右','右','下','下','左']

脚本体验师001

这一个标题就让人想起lua A*算法 寻路，不过真没深入过不太懂

steven026

脚本体验师001 发表于 2022-12-1 13:15
这一个标题就让人想起lua A*算法 寻路，不过真没深入过不太懂

GGNB 我去研究研究 似乎找到了新大陆

maxzhang

那自然是A-Start了

steven026

maxzhang 发表于 2022-12-1 15:23
那自然是A-Start了

大致了解了下A*算法
发现A*算法似乎不太适用于我的这种情况，需要做大改动……

A*算法默认就起点、终点、可通过的路、不可通过的路，不存在可通过但尽量避免通过的路，且注重最短路径，
这就导致了我无法简单地通过修改不可通过的路的代价权重来改进算法，因为改了权重就导致算法认为尽量避免通过的路是通路且较短，不会再绕路进行其他可能性计算

dannianya

实在不行就穷举吧

dannianya

你看看这个像不像你描述的

steven026

let m = [
    [2, 0, 0, 0, 2, 2],
    [0, 0, 2, 0, 3, 2],
    [0, 2, 4, 0, 2, 2],
    [0, 0, 2, 2, 2, 3],
    [2, 0, 0, 2, 3, 2],
    [3, 2, 0, 1, 3, 2]
];
let size = m.length;
//let start=[size-1,Math.floor(size/2)]
//预处理地图
let record = m.map((i, y) => i.map((m, x) => ({ x: x, y: y, value: m, cost: (m == 2) * 1, totalCost: (m == 2) * 1, parent: [] })));
let flat = record.flat();
//起点
let start = flat.find(i => i.value == 1);
//终点
let end = flat.find(i => i.value == 4);

//获取可通过的周围四个点 过滤：终点、超过边界点
function getChild({ x, y }) {
    return [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]].filter(([x, y]) => { return (x < size && y < size && x >= 0 && y >= 0 && !(x == end.x && y == end.y)) }).map(([X, Y]) => flat.find(({ x, y }) => x == X && y == Y))
}

//尝试通路
function applyChild(parent) {
    const child = getChild(parent)
    const newChild = child.filter(c => {
        const newCost = c.cost + parent.totalCost //目标消耗=子点消耗+父点总消耗
        if (c.parent.length == 0) {
            c.parent.push(parent)
            c.totalCost = newCost
        } else if (c.parent.find(i => i == parent)) {
            return false //终止走回路
        } else {
            if (c.totalCost == newCost) {
                c.parent.push(parent)
            } else if (c.totalCost > newCost) {
                c.totalCost = newCost
                c.parent = [parent]
            } else {
                return false //终止消耗过高
            }
        }
        return true
    })
    return newChild
}

let result = applyChild(start);

//循环遍历通路
while (result.length > 0) {
    result = result.map(c => applyChild(c)).flat()
}
//record.map(i=>i.map(i=>i.parent.length>0 && i))

//获取结果
getChild(end)

自己强行遍历了一个，结果不及预期，暂时没发现哪里写的有问题
预期结果是遍历完所有路径，终点右边的点totalCost应该为0，然后倒推parent路线
实际结果是终点右边的点totalCost为2

steven026

dannianya 发表于 2022-12-1 21:18
你看看这个像不像你描述的

有点像，能发下网址我去参考一下么

steven026

//尝试通路
function applyChild(parent) {
    const child = getChild(parent)
    const newChild = child.filter(c => {
        const newCost = c.cost + parent.totalCost
        if (c.parent.length == 0) {
            c.parent.push(parent)
            c.totalCost = newCost
        } else if (c.parent.find(i => i == parent) && newCost >= c.totalCost) {
            return false //终止走回路
        } else {
            if (c.totalCost == newCost) {
                c.parent.push(parent)
            } else if (c.totalCost > newCost) {
                c.totalCost = newCost
                c.parent = [parent]
            } else {
                return false //终止消耗过高
            }
        }
        return true
    })
    return newChild
}

//结果逆推顺序
function getRoute({ x, y, value, parent }, result) {
    parent = parent.filter(i => !result.find(n => n.x == i.x && n.y == i.y))//不走回路
    result.push({ x, y, value })
    if (!(start.x == x && start.y == y)) {
        parent.forEach(_parent => getRoute(_parent, [...result]))
    } else {
        routes.push(result)
    }
}

//输入数组
let m = [
    [2, 0, 0, 0, 2, 2],
    [0, 0, 2, 0, 3, 2],
    [0, 2, 4, 0, 2, 2],
    [0, 0, 2, 2, 2, 3],
    [2, 0, 0, 2, 3, 2],
    [3, 2, 0, 1, 3, 2]
];
let size = m.length;
let record = m.map((i, y) => i.map((m, x) => ({ x: x, y: y, value: m, cost: (m == 2) * 1, totalCost: 0, parent: [] })));
let flat = record.flat();
let start = flat.find(i => i.value == 1);
let end = flat.find(i => i.value == 4);

//获取可通过的周围四个点
function getChild({ x, y }) {
    return [[x + 1, y], [x - 1, y], [x, y + 1], [x, y - 1]].filter(([x, y]) => { return (x < size && y < size && x >= 0 && y >= 0 && !(x == end.x && y == end.y)) }).map(([X, Y]) => flat.find(({ x, y }) => x == X && y == Y))
}

let result = applyChild(start);
//循环遍历通路
while (result.length > 0) {
    result = result.map(c => applyChild(c)).flat()
}
//遍历结果
result = getChild(end)
let routes = []
result.forEach(i => { getRoute(i, []) })

//最终结果，[步数,战斗次数,宝箱数]
routes.map(i => [i.length, i.filter(i => i.value == 2).length, i.filter(i => i.value == 3).length])

最终还是一个人承担了所有😣