Python-сообщество

Может кто поможет идеей? суть такова: Есть модель

class Point(models.Model):
   sosedi = models.ManyToManyField('self')

Если предположить, что растояние между соседями = 1, то суть задачи в написании метода определения растояния между точками...

def Rasstoyanie(start, stop):
    start = Point.object.get(...)
    stop = Point.object.get(...)
    # do something
    return [...]

на выходе нужно получить список возможных маршрутов между этими точками... Есть какие идеи?

Идея поиска маршрутов вообще такова:
1. Сначала строится граф “транспортной” сети.
2. Так как задача на поиск минимальных расстояний не стоит, то просто моделлируете маршруты обычным перебором (перебираете по-очереди узлы).
3. Формируете множество маршрутов и отбираете из них те, которые подходят по определенным критериям.

Будут вопросы - пишите.

Отредактировано 4kpt_II (Дек. 17, 2013 15:14:20)

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

ну по графам пройдись, алгоритм Дейкстры и всё такое
думаю спец либы для графов это умеют из коробки

Отредактировано slav0nic (Дек. 17, 2013 21:59:57)

вот как раз этим и занимаюсь.... читаю про графы и алгоритм Дейкстры

Если нужно построить все множество маршрутов без повторений узлов, то алгоритм Дейкстры здесь не нужен. Я написал выше. Тут можно просто по исходным данным получить матрицу инцидентности, а уже по ней методом обычного перебора с фиксацией вершин найти все варианты маршрутов из определенных точек. Нужно еще фильтровать и отсеивать одинаковые маршруты.

P.S. Алгоритм Дейкстры служит для поиска кратчайших расстояний, а ни как не для построения маршрутов. На самом деле для построения разных видов маршрутов существуют совершенно разные методы. Все зависит от типа маршрута, функции цели и начальных условий…

Отредактировано 4kpt_II (Дек. 17, 2013 23:16:46)

Всем спасибо… проблема решена.

Мне кажется ты не правильно хранишь данные. Надо использовать встроенные средства БД

Singularity
Мне кажется ты не правильно хранишь данные. Надо использовать встроенные средства БД

Вполне возможно… Будь добр - пни в нужном направлении