Насколько трудное данное тестовое задание и что полистать чтобы его решить?

Всем привет! есть тестовое(одно из), время: до 1 февраля...
Что посоветуете полистать, почитать, посмотреть чтобы подойти к реализации данного алгоритма?
Транспортный путь
У вас есть карта звёздного неба. На ней указано название каждой звезды, а также расстояние от неё до других звёзд в световых секундах. Реализуйте функцию solution, которая должна принимать три аргумента: объект, в котором ключами являются названия звёзд, а значениями — расстояния до звёзд (в космосе одностороннее движение), а также названия начальной и конечной точки пути — start и finish соответственно. Функция должна возвращать кратчайшее расстояние от звезды start до звезды finish и путь, по которому нужно пройти.
Сигнатура функции:
const solution = function(graph, start, finish)  {
    // Ваше решение
}

Пример входных данных:
const graph = {
  start: { A: 50, B: 20 },
  A: { C: 40, D: 20 },
  B: { A: 90, D: 90 },
  C: { D: 160, finish: 50 },
  D: { finish: 20 },
  finish: {}
};
const start = 'start';
const finish = 'finish';

Пример выходных данных:
{
    distance: 90,
    path: ['start', 'A', 'D', 'finish']
}

решение поместить сюда:
const solution = function(graph, start, finish)  {
    // Ваше решение
}
  • Вопрос задан
  • 3187 просмотров
Решения вопроса 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
@grinat
Можешь тут глянуть реализацию https://github.com/qiao/PathFinding.js только там для поиска пути в лабиринте, но алгоритмы те же.
А задание отстойное, мне ни раз не приходилось на проде это делать. С задачей комивояджера только сталкивался, но там не было смысла трахаться с ней, с данными для нее и т.п., потому что есть osrm.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@ebroker
Самый тривиальный способ через обход графа в ширину. Гугли bfs
Ответ написан
virtual_hack2root
@virtual_hack2root
.NET Core, JS, DevOps
Это одно из тех заданий, где следует проявить фантазию, и нестандартный подход, а не умение гуглить решение.

4d. фантазия на тему звезд.

Во первых, это 3d. Во вторых, звезды движутся. Предположим, у звезд есть координаты, вектора скорости и кроме этого - релятивиское смещение, из-за ограничения скорости света, некоторые звезды могут к тому же двигаться со скоростями, близкими скорости света. Это потрясающая задача, а вы ее сводите к проблеме коммивояжера и backpack problem.

Я бы считал что задача релятевисткая, динамическая, так как расстояния между звездами - миллионы сетовых лет, а космический корабль не может превысить скорость света при передвижении, то есть по сути, это задача которую невозожно решить точно, в отличие от любой задачи на земле, с конечными нерелятевисткими скоростями,

Я так же допустил бы, что время разгона до крейсерской корости и торможения несущественны, при подлете к звезде и удалении от звезды, так так эти рассояния измеряются световыми годами, то есть на 5-8 порядков меньше расстояний между звездами, кроме того, в звездных сисемах есть кластеры и пустоты, что облегчает задачу, как таковую.

Можно рассмотреть 4 способа решения задач: генетические алгоритмы, нейронные сети, машинное обучение, и стандартный поход - приближенное решение задач с краевыми условиями.

Можно для простоты вообще отказаться от скоростей у звезд, и считать что коммивояжер перемещается с помощью телепортации, то есть зафиксировать время t0. Тогда я бы применил метод Монте-Карло, к примеру, так как никто не гарантирует, что задача будет на малом количестве звезд и из не будут триллионы, либо использовал какое-то условие, которо бы решало, как мы будем решать задачу, приближенно, либо точно.

В любом случае, можно поиграть с 3d, попробовать использовать алгоритмы отсечения который разщработал Кармак в Quake, либо как-то еще выделиться и показать нестандартность мышления, в том числе, попробовать деревья бинарного поиска, самобалансирующие RB-деревья, и так далее.
Ответ написан
Ваш ответ на вопрос

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

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