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

Бодрого времени суток!
Ищу алгарим для решения моей задачки, хоть на 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. Для наглядности прикрепил картинку =)
906804a5c01c469c97016b431ec4a6de.jpg
  • Вопрос задан
  • 514 просмотров
Решения вопроса 2
@MarkusD
все время мелю чепуху :)
Уж не карту ли для EVE Online ты решил своими руками сделать? Все предпосылки, включая картинку, говорят об этом. :)

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

Поиск маршрута делается один раз для самого безопасного маршрута и еще один раз для самого короткого.
В первом случае весовым коэффициентом узла будет сек-уровень звезды. Эвристика - средний сек-уровень на число прыжков до цели.
Во втором случае весом будет уже число самих прыжков, а эвристику надо будет считать из числа прыжков до цели.
Ответ написан
@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);
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы