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

Здравствуйте.

Уважаемые специалисты, прошу помощи для выбора направлении решения.
Дано:
————————-
50 42 80 <- ID 1
————————-
45 60 80 <- ID 2
————————-
50 60 60 <- ID 3
————————
Грубо говоря - Есть три дороги с тремя разными отрезками пути, по которым можно двигаться с разной сторостью.
После любого отрезка пути можно переместиться на другую дорогу.
Требуется перебрать все возможные варианты перемещения и выбрать наиболее быстрый путь.
Записи по каждому ID находятся в базе (Django)
То есть варианты движения
ID1(1)-ID1(2)-ID1(3)
ID1(1)-ID2(2)-ID1(3)
ID1(1)-ID2(2)-ID2(3) и так далее.
С 1 на 3 дорогу тоже можно перемещаться(условно они расположены одна над другой).
Если кто сталкивался с подобной задачей- прошу совета, каким образом эффективно организовать перебор наборов вариантов в данной матрице значений.

Заранее благодарю за ответы.

Похоже все сводится к поиску кратчайшего пути на графе? Какой размер данных? ИМХО, лучше всего все данные в память. Если такие расчеты все время, то в отдельный процесс.

В память- устроит, размер данных небольшой- максимум 10-15 записей “каждой дороги”, количество узлов- в обычном случае- от 3 до 10. Теоретически может быть и 20-30, но в редких случаях. Рассчет не постоянный, потребовалось- просчитали.
Если не тяжело, подскажите пожалуйста, как это правильно реализовать.
Вопросы- какой правильный массив для хранения этих данных сформировать(какая структура), как построить все возможные варианты “путей”, в каком виде хранить их в памяти с результатами просчета, чтобы сравнив итоговые значения можно было бы указать верный путь.
И, прошу прощения, совсем забыл уточнить- возможны условия на узле, что-то вроде “на второй узел ID2 нельзя переехать, если предыдущая дорога была ID1”.
Откровенно говоря, полный ноль в высшей математике, незнаю даже откуда подступиться.

Ну в таком случае, наверное, проще всего будет взять готовую библиотеку, вот эту, например. Каждых участок становится ребром графа, скорость на участке - весом ребра, а точки начала, конца и перехода между дорогами - вершинами. Потом воспользоваться pygraph.algorithms.minmax.shortest_path, описание этого метода можно почитать здесь

ну какой граф ) Тут же короткий путь будет равен последовательности из минимумов каждого столбца(отрезка)

Отредактировано sergeek (Ноя. 5, 2013 07:28:34)