Поиск пути с обязательными точками

Question

[CrazyAngel]

Подскажите, пожалуйста, что искать.

Есть точки на карте, а так же путь для объекта, но этот путь написан не полностью.
тоесть есть путь: точка 1; точка 2; точка 4; точка 6;
Но что бы пройти путь, мне надо сделать такой путь: точка 1; точка 2; точка 58; точка 4; точка 17; точка 6;

Comments

[sizenko]

Георгий для начала свяжитесь со мной (Сизенко Дмитрий) и давайте доделаем работу. Советую выйти на связь и ответить на сообщения в ВК, скайпе или почте

[sizenko]

Ну и соответственно если сегодня выйдете на связь - мы нашу проблему сможем урегулировать мирно.

[sizenko]

Георгий, пожалуйста, ответьте на почту

Answer 1

[mayorovp]

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

А вот решение второй задачи уже зависит от того, что такое «карта», каковы критерии оптимальности, и т. п.

Comments

[CrazyAngel]

Нет, как раз и нужно ограничение на обязательные точки.

[mayorovp]

Хорошо, объясню очевидную мне вещь.

Если нам надо найти путь, проходящий между точками 1, 2, 3 и 4 — то достаточно найти путь от 1 к 2, от 2 к 3, от 3 к 4 — и сложить их вместе.
Таким образом, задача о пути с обязательными точками сводится к задаче без них.

А вот решение второй задачи уже зависит от того, что такое «карта», каковы критерии оптимальности, и т. п.

Answer 2

[barker]

Если надо прикинуть алгоритм, то недостаточно информации. Как недостающие точки описаны? Как я понимаю, есть путь, но его надо дополнить точками? Тогда какие критерии включения недостающих точек в каждый отрезок пути? Итд.

Comments

[CrazyAngel]

могу описать в любом вине, по сути это просто координаты. «Тогда какие критерии включения недостающих точек в каждый отрезок пути?» — просто нельзя посетить точку, без посещения неназванной точки

Answer 3

[Sergey Lerg]

Последовательный поиск пути от точки к точке, используя алгоритм «A*»?

http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 4

[T-D-K]

Если точки нельзя посещать несколько раз, то вот. Пускай точки что уже известны лежат в массиве points. Тогда по волновому или A* находим все кратчайшие расстояния от points[i] до points[i+1] и заносим в массив paths[i,j], где j — j-й путь от points[i] до points[i+1]. Дальше перебором (или тоже можно пути на графе из путей рассмотреть) пытаемся построить общий путь из всех paths, такой чтобы ни в одну точку не заходили дважды. Т.е. если по-тупому: берём paths[1,1] и перебираем все paths[2,1] и т.д.
Если точки можно посещать несколько раз, то как сказали выше: последовательный поиск пути от точки к точке.

Answer 5

[sizenko]

Георгий всё просто - свяжитесь со мной (Сизенко Дмитрий) и давайте доделаем работу. Советую выйти на связь и ответить на сообщения в ВК, скайпе или почте

Answer 6

[sizenko]

Георгий, свяжитесь со мной срочно, ни к чему хорошему молчание ваше не приведет.