Как сделать поиск элементов массива по цепочке (поиск оптимального пути)?

Question

[FreeZa]

Бодрого времени суток!
Ищу алгарим для решения моей задачки, хоть на php хоть на js, это не суть важно.
Дан массив:

[0, "name", x, y, z, 10, [1,2]],
[1, "name", x, y, z, 10, [0,3]],
[2, "name", x, y, z, 5, [0,3,4]],
[3, "name", x, y, z, 10, [2,1,4]],
[4, "name", x, y, z, 10, [3,2]],
[5, "name", x, y, z, 10, [4]]

по сути, каждый элемент массива это точка в пространстве которая соединена с другими такими же точками, точки с которыми она соединяется хранится во вложенном массиве.
Разумеется точки не связаны все друг с другом напрямую. то есть от точки 0 до точки 5 можно попасть только через соседние точки, причем можно попасть разными путями, например:

1) 0->2->3->4->5
2) 0->1->3->4->5
3) 0->2->4->5

3 путь самый коротки по колличеству звеньев, это одна из целей алгоритма найти короткий путь, но это еще не все)

у каждой точки есть значение безопасности, например у точки 0 значение равно 10 (безопасно),
а у точки 2, уровень безопасности ниже 6, то есть не безопасно.

на выходе работы алгоритма должно выходить 2 набора точек в нашем случае:

2) 0->1->3->4->5  // самый короткий из безопасных путей
3) 0->2->4->5       // самый короткий путь

Собственно посоветуйте оптимальное решение на ваш взгляд для данной задачки.
PS. массив состоит более чем из 1000 элементов
PPS. Заранее большое человеческое спасибо! =)
PPPS. Для наглядности прикрепил картинку =)

Comments

[D']

Прокладка маршрута по карте евы?) Зачем, если не секрет? Чем встроенный планировщик не устраивает?

Answer 1

[Евгений Шатунов]

Уж не карту ли для EVE Online ты решил своими руками сделать? Все предпосылки, включая картинку, говорят об этом. :)

Любой алгоритм поиска пути тебе в помощь. Смотри в сторону A*, его реализация существует, наверное, даже на бреинфаке, поэтому код попросту неуместен.

Поиск маршрута делается один раз для самого безопасного маршрута и еще один раз для самого короткого.
В первом случае весовым коэффициентом узла будет сек-уровень звезды. Эвристика - средний сек-уровень на число прыжков до цели.
Во втором случае весом будет уже число самих прыжков, а эвристику надо будет считать из числа прыжков до цели.

Comments

[FreeZa]

Да именно ее) в 2012 сохранил себе их визуализацию на three.js, вот решил свою сделать, с некоторыми улучшениями)

Answer 2

[enixpp]

function findRoute(routeMap, from, to, secureLevel) {
    let route;
    while (!Array.isArray(route = tryFindRoute(routeMap, from, to, secureLevel))) {
        let invalidRoute, invalidRouteIndex;

        invalidRoute = routeMap[route][6]
            .sort((a, b) => a - b)
            .reverse()
            .find(e => e > from && e > route);
        invalidRouteIndex = routeMap[route][6].indexOf(invalidRoute);

        routeMap[route][6].splice(invalidRouteIndex, 1);
    }

    return route
}

function tryFindRoute(routeMap, from, to, secureLevel) {
    let route = [from], routePoint;

    for (let i = 0, len = routeMap.length; i < len; i++) {
        let el = routeMap[i];
        if (route[route.length - 1] > el[0]){
            continue
        }

        routePoint = el[6]
            .sort((a, b) => a - b)
            .reverse()
            .find(e => e > from && e > i);
       
        if (el[0] !== to) {
            if (!routePoint || el[5] < secureLevel) {
                route = route[Math.max(0, route.length - 2)];
                break
            }
            route.push(routePoint)
        }
    }

    return route;
}

let x, y, z;
let routeMap = [
    [0, "name", x, y, z, 10, [1, 2]],
    [1, "name", x, y, z, 10, [0, 3]],
    [2, "name", x, y, z, 5, [0, 3, 4]],
    [3, "name", x, y, z, 10, [2, 1, 4]],
    [4, "name", x, y, z, 10, [3, 2, 5]],
    [5, "name", x, y, z, 10, [4]]
];

let shortRoute = findRoute(routeMap, 0, 5, 0);
let inSecureshortRoute = findRoute(routeMap, 0, 5, 10);

console.log('самый короткий из безопасных путей', inSecureshortRoute);
console.log('самый короткий путь', shortRoute);