Графы

[STeM]

Здравствуйте, дорогие форумчане!
Мне дали диплом с темой: определения оптимального маршрута до другого мобильного объекта, передающего свои координаты в рамках системы, с учетом его движения и/или конечной точки его маршрута. Т.е. после каждого перехода объекта в новую вершину мы получаем новые координаты. И надо спрогнозировать куда пойдет объект дальше и перехватить его. Мне сказали что прогнозировать можно с помощью метода наименьших квадратов. Но пока я к сожалению не могу понять как. Если бы вы мне подсказали, был бы очень признателен.

[Utkin]

Не знаю, чем обычный алгоритм Дейкстры не нравиться? Сдвинулся объект на другую позицию - перечитал оптимальный маршрут заново и все проблемы. Конечно для большого количества точек накладно, зато дешево и сердито.

[STeM]

а разве мы его так когда нить поймаем? Не будем ли мы за ним по пятам ходить?

[Utkin]

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

[STeM]

ну единственное что можно добавить граф ориентированный и взвешенный

[Utkin]

Объект имеет право возвращаться на прежние точки?

[STeM]

ну если только есть обратная дуга, а она может быть

[Utkin]

Если известно откуда и куда движется объект, а также точка откуда надо его ловить, то все можно решить с помощью алгоритма Дейкстры (че-то я кажись уже писал про это). Я ведь могу получить кратчайшие маршруты до каждой точки (и из каждой точки). Мне надо будет провести анализ кратчайших расстояний до х (куда идет объект) и до y (где сейчас находиться объект) с точки z (где мы сейчас находимся). Там же я смогу увидеть и кратчайшие маршруты.

[raxp]

...а не послать-ли нам TC на статью в журнале

[STeM]

А откуда мы знаем куда движется объект?