Страница 1 из 1
Поиск кратчайшего пути
Добавлено: 14 фев 2010, 13:27
Asphyxis
Добрый день.
Получил задачу: создание утилиты для mapinfo, написать утилиту поиска кратчайшего маршрута на mapbasic.
Маршрут должен быть "привязан" к существующим дорогам (отрисованы линиями).
Подскажите пожалуйста как это реализовать? или что почитать?
Спасибо.
Re: Поиск кратчайшего пути
Добавлено: 15 фев 2010, 01:38
Boris
Если вы знаете самим используемым продуктам, то в Гугле наберите "алгоритм поиска кратчайшего пути на Basic" или "Алгоритм Дейкстры".
Во всем мире это нехилая коммерческая задача. Требующая и неплохих компьютерных ресурсов. Задачи оптимизации разреженных графов, то же требуют не слабой изворотливости. А так же кропотливого создания и актуализации исходных данных - ребер в правильном порядке, а не "как отрисовалось, так и хорошо", обязательных вершин в местах ветвления дорог и т.п.
Re: Поиск кратчайшего пути
Добавлено: 15 фев 2010, 01:45
bim2010
Re: Поиск кратчайшего пути
Добавлено: 17 фев 2010, 12:23
Asphyxis
спасибо! очень полезные ссылки
а существуют ли в природе исходники этого Route_Walker?
обидно что утилита скомпилирована
Re: Поиск кратчайшего пути
Добавлено: 19 фев 2010, 22:39
bim2010
Re: Поиск кратчайшего пути
Добавлено: 21 фев 2010, 08:23
bim2010
Масса ссылок
http://masters.donntu.edu.ua/2006/ggeo/ ... /index.htm
Ряд решений
http://www.digimap.com/pdf/ChronoVia%20 ... ochure.pdf
http://www.theexmiles.com/routeoptimiza ... fopro.html
http://www.routeware.dk/download.php
http://www.ifp.uni-stuttgart.de/lehre/s ... eutle.html
http://www.paper.edu.cn/en/paper.php?se ... 200806-590
Масса решений на других языках (см предыдущие ссылки)
http://www.gis-mapinfo.cn/post/22093.html
Может пора уже перевести на Mapbasic и выложить?
Вот частично:
http://ciren.vn/forums/archive/index.php/t-816.html
http://www.gisdevelopment.net/applicati ... yt0003.htm
Нужно больше информации по задаче:
1. Обязательно ли это делать на MB и MI?
2. Данные в какой проекции (географическая / не географическая)?
3. Реализация транспортного графа, слоя домов. Проще выложить кусок Ваших данных. чтоб не гадать ...
4. Задача учебная (диплом/курсяк) или real ? Какие еще условия и ограничения Вы собираетесь учитывать?
Re: Поиск кратчайшего пути
Добавлено: 23 фев 2010, 22:03
Asphyxis
За ссылки спасибо)
1. да
2. географическая
3. слой домов задан точками (в таблице название и координата широты и долготы), дороги отдельным слоем (заданы полилиниями)
4. задача реальная, сначала надо реализовать простейший случай без всяких ограничений (ну естественно, что путь должен быть привязан к дорогам), остальное я думаю дело техники...
Re: Поиск кратчайшего пути
Добавлено: 01 мар 2010, 23:29
Asphyxis
появился вопрос в ходе решения задачи
нужно считать в массив координаты всех узлов всех полилиний (находящихся в таблице)
почему то в массив заносится лишь координаты одной точки для каждой полилинии...
надо как-то все узлы считать для каждой полилинии...
Код: Выделить всё
For j1=1 To ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS)
For i1=1 To ObjectInfo (road.obj, OBJ_INFO_NPOLYGONS+j1)
node_pol(j1).x1=ObjectNodeX(road.obj, j1, i1)
node_pol(j1).y1=ObjectNodeY(road.obj, j1, i1)
cur_size = UBound(node_pol)
ReDim node_pol(cur_size + 1)
Next
Next
подскажите что в коде поправить?
Re: Поиск кратчайшего пути
Добавлено: 02 мар 2010, 05:48
Boris
ReDim node_pol(cur_size + 1)
зачем столько раз память перераспределять? нельзя заранее посчитать размерность?
здесь и ошибка - нарастающий индекс пишется в номер сегмента полигона.
Re: Поиск кратчайшего пути
Добавлено: 02 мар 2010, 10:37
Asphyxis
Boris писал(а):ReDim node_pol(cur_size + 1)
зачем столько раз память перераспределять? нельзя заранее посчитать размерность?
здесь и ошибка - нарастающий индекс пишется в номер сегмента полигона.
в том и дело что нельзя...
но ведь код вида (при заданной размерности):
Код: Выделить всё
For j1=1 To ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS)
For i1=1 To ObjectInfo (road.obj, OBJ_INFO_NPOLYGONS+j1)
node_pol(j1).x1=ObjectNodeX(road.obj, j1, i1)
node_pol(j1).y1=ObjectNodeY(road.obj, j1, i1)
Next
Next
выдаёт такой же массив, как в предыдущей реализации... т.е. по всем узлам не пробегает...
или я недопонял )
поправьте пожалуйста в коде, если я не прав
Re: Поиск кратчайшего пути
Добавлено: 02 мар 2010, 15:23
Boris
Код: Выделить всё
dim arr_Size as Integer,N as Integer,M as Integer
arr_Size=0
N=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS)
For j1=1 To N
M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1)
For i1=1 To M
arr_Size = arr_Size + 1
Next
Next
ReDim node_pol(arr_Size) '' память перераспределяется только 1 раз
cur_size = 0 '' массивы в MapBasic'е начинаются только с 1-цы
For j1=1 To N
M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1)
For i1=1 To M
cur_size = cur_size + 1 '' массивы в MapBasic'е начинаются только с 1-цы
node_pol(cur_size).x1=ObjectNodeX(road.obj, j1, i1)
node_pol(cur_size).y1=ObjectNodeY(road.obj, j1, i1)
Next
Next
Re: Поиск кратчайшего пути
Добавлено: 02 мар 2010, 18:12
Asphyxis
ругается на ObjectNodeX(road.obj, j1, i1) , пишет, что аргумент 3 вышел за заданные пределы...
Re: Поиск кратчайшего пути
Добавлено: 03 мар 2010, 10:01
reasonat
M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1) - в обоих случаях
Re: Поиск кратчайшего пути
Добавлено: 04 мар 2010, 05:25
Boris
reasonat писал(а):M=ObjectInfo(road.obj, OBJ_INFO_NPOLYGONS+j1) - в обоих случаях
Спасибо. Код - поправил.