подсчёт расстояния из пункта А в Б

[berkut]

подсчёт расстояния из пункта А в Б

Подскажите, как в принципе реализовать подсчёт расстояний из пункта а в пункт б, например как на autotransinfo.ru.

 

[neko]

тебе теорему пифагора рассказать или задачу коммивояжера?

 

[Кром]

>подсчёт расстояния из пункта А в Б

Когда пойдешь в школу, там научат.

 

[berkut]

спасибо за содержательный ответ. если у кого-то ещё окажутся соображения, буду очень признателен за их изложение
autotransinfo.ru/tc.php

 

[Кром]

Да, соображение окажутся. И первое соображение такое: к php это не имеет никакого отношения.
Так что начни, для начала с эти ссылок:
http://gsu.unibel.by/dla/library/graph/part1_5.htm
http://www.zatvor.ru/u/conf?a=s&u=logistic&aa=&w=389
http://www.tisbi.ru/resources/lib/graph/Teor1.htm
http://algolist.manual.ru/games/wavealg.php
Дальше, думаю, понятно, в каком направлении копать.

 

[nagash]

мне кажется нужно начать с изучения математики.

 

[berkut]

это всё занимательно, но где взять исходные данные для вычислений? и как они могут выглядеть? древовидный список, с "корнем" в виде какого-то определённого города, все дочерние узлы - города с прямым дорожным сообщением?

                                   \     /
                                    \   /
                           - - -  чапаевск
                                    |   |
                                   1|  2|
                                    |   |
                              новокуйбышевск
                                 |     /
                                1|   2/
                                 |   /
                                 самара  - - - тольятти
                                    |
                                    |

 

[Cid]

Такие задачи решаются либо эмпирически, с учетом стандартных маршрутов, привязанных к определенным трассам (что скорее всего имеет место на autotransinfo.ru - и то это не их собственная разработка, в чем легко убедиться посмотрев на страницу, выводимую после сабмита), либо с помощью геоинформационных систем со слоем, отражающим пути сообщения (векторизованные трассы/дороги) - тогда можно более-менее точно вычислить расстояние между любыми точками. В свободном доступе интересующих тебя данных нет.

 

[Lithium366]

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

 

[Cid]

Lithium366

балин, ну сделай базу где будут расстояния от каждого населенного пункта до соседних.

Сделай. Заодно на диплом потянет.

 

[Кром]

Где данные брать сам думай. Ищи в сети какие нибудь каталоги, списки дорог с расстояниями и т.д.

А структура будет выглядить наверное в виде двух таблиц.
table_city
ID
CITY_NAME

table_road
CITY_ID
ROAD_ID - ID соседнего города
DISTANCE - расстояние до соседнего города
другие поля...

Связь table_city.ID - table_road.ROAD_ID

Ну а дальше уже думаешь над алгоритмом.

-~{}~ 21.12.04 00:57:

>Заодно на диплом потянет.

Очень в этом сомневаюсь.

 

[Lithium366]

Cid

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

 

[Cid]

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

Проблема только в том, откуда взять данные

 

[Lithium366]

Cid

Мне показалось что именно это я и предложил.

 

[sergadm]

дискретная математика или теория оптимизации-транспортная задача либо теория графов (в любой технической библиотеке)+ карта автодорог продаются на компактов как данные выцепить из их базы твои проблемы

 

[SiMM]

Автор оригинала: Cid
Проблема только в том, откуда взять данные

От нас то ты чего хочешь? Это форум по PHP, а не геодезический центр.

 

[Cid]

SiMM

От нас то ты чего хочешь? Это форум по PHP, а не геодезический центр.

Хмм.. от вас ничего - я не автор топика

 

[SiMM]

Cid, прамахнулся (надо было цитировать пост от 21.12.04 01:29)

 

[azamat]

>Заодно на диплом потянет.
Очень в этом сомневаюсь.

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

 

[Кром]

>задача сразу переходит в другой разряд сложности.

То что задача нетривиальная, я не спорю.