Есть населенные пункты(НП или точки), допустим штук двести. Есть несколько маршрутов движения транспорта, который соединяет все эти НП. Допустим будет железная дорога(Ж/Д), которая соединяет эти НП. Т.е. есть 20 поездов со своими маршрутами движения.
Задача состоит в том, как оформить базу движения Ж/Д, и как находить маршрут движения от точки А до точки В, через точку Б.

З.Ы.: не знаю понятно ли написал?

Задача на графах, сводится к поиску оптимального пути с ограничениями. Это к вопросу о том, как находить маршрут.
А что значит вопрос "как оформить базу движения" ?

Т.е. в каком виде это все хранить, чтобы применять поиск?
Там XML или обычный TXT, т.е. как хранить графы ( через какие точки проходит маршрут )?

bel_nikita

Цитата

как хранить графы ( через какие точки проходит маршрут )?

Для 200 точек лучше хранить готовые маршруты точка-точка, 20 тыс. маршрутов - дело плевое для любой БД. Из простейших - если жевать все это локально под Виндами - Аксессова база, в веб-варианте - мускул. Хотя можно и на DB2 заморочиться - но стОит ли того задача?
А также хранить таблицу элементарных участков и подпрограмму пересоздания таблицы готовых маршрутов - на случай изменения связей.

Это сообщение отредактировал(а) Akina - 29.10.2004, 08:44

Цитата

Т.е. в каком виде это все хранить, чтобы применять поиск? Там XML или обычный TXT, т.е. как хранить графы ( через какие точки проходит маршрут )?

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