Предыдущая тема :: Следующая тема |
Автор |
Сообщение |
Soneg
Зарегистрирован: 04.03.2010 Сообщения: 8
|
Добавлено: Вт Апр 20, 2010 2:39 pm Заголовок сообщения: Поиск маршрута из точки А в точку В |
|
|
Хочу сделать программу, при помощи которой можно найти путь из точки А в точку В.
У меня имеется несколько слоев с автобусными маршрутами (линейные объекты), а также слой с автобусными остановками.
Программу я представляю так: открывается диалоговое окно "Введите точку А _____, Введите точку В _____". После нажатия кнопки ОК выделяются отрезки всех линий, соединяющих эти точки, а также выводится сообщение с номерами автобусных маршрутов, попавших в данную выборку.
Как это сделать - представления не имею. Пожалуйста, подтолкните на верный путь. Скажите, какие операторы можно использовать? |
|
Вернуться к началу |
|
|
Arhara
Зарегистрирован: 18.02.2009 Сообщения: 400 Откуда: Moscow, RF
|
Добавлено: Ср Апр 21, 2010 12:51 am Заголовок сообщения: |
|
|
ищите в интернете алгоритм дейстры. или просто поиск кратчайшего пути. тема многократно обсуждалась в интеренете. алгоритм хорошо прописан, в том числе и на различных диалектах Basic'a.
В общем виде, он требует задание матрицы смежности вершин отдельных отрезков.
Разбор существующих карт и картинок на такую матрицу смежности - задача по сложности превышает сам алгоритм. Кроме того есть еще ограничения на размер массива в MapBasic'е. Так что после создания списка смежности обработку проще проводить в стороннем языке программирования или внешней программе. |
|
Вернуться к началу |
|
|
FedorinoFF
Зарегистрирован: 01.02.2007 Сообщения: 272 Откуда: Санкт-Петербург
|
Добавлено: Ср Апр 21, 2010 4:10 pm Заголовок сообщения: |
|
|
Arhara писал(а): |
ищите в интернете алгоритм дейстры. или просто поиск кратчайшего пути. тема многократно обсуждалась в интеренете. алгоритм хорошо прописан, в том числе и на различных диалектах Basic'a.
В общем виде, он требует задание матрицы смежности вершин отдельных отрезков.
Разбор существующих карт и картинок на такую матрицу смежности - задача по сложности превышает сам алгоритм. Кроме того есть еще ограничения на размер массива в MapBasic'е. Так что после создания списка смежности обработку проще проводить в стороннем языке программирования или внешней программе. |
А зачем обязательно массивы, когда есть таблицы и SQL. Рамки ограничений существенно раздвигаются... |
|
Вернуться к началу |
|
|
Arhara
Зарегистрирован: 18.02.2009 Сообщения: 400 Откуда: Moscow, RF
|
Добавлено: Пт Апр 23, 2010 12:06 am Заголовок сообщения: |
|
|
Стандартные алгоритмы на графах используют матрицы смежности и рекурсию. Очень может быть, что существуют модификации для выбора из таблицы смежности вершин с использованием SQL.
Но разбор дорожной сети, если она не создавалась изначально как дорожный граф, требует достаточно сложных алгоритмов.
Рамки существенно раздвинуть нельзя, поскольку задача поиска кратчайшего пути есть задача высокой размерности - надо найти все цепочки из точки А в точку В, а потом выбрать из них самую короткую. |
|
Вернуться к началу |
|
|
FedorinoFF
Зарегистрирован: 01.02.2007 Сообщения: 272 Откуда: Санкт-Петербург
|
Добавлено: Пт Апр 23, 2010 9:03 am Заголовок сообщения: |
|
|
Имелись ввиду рамки, накладываемые ограничениями на размерность/размер массивов... ;-) |
|
Вернуться к началу |
|
|
|