Pull to refresh

Comments 11

UFO just landed and posted this here

А в демо-базе все равно только самолеты.

UFO just landed and posted this here

А в демо-базе все равно только самолеты.

просьба еще explain (analyze, buffers) показывать,

и что если вместо
Представление «пути» в виде массива помогает во многих случаях

использовать для этой цели тип данных ltree.
может это жесткач будет но что если зная что у нас не может быть level больше 6, предварительно сделать таблицу(матвьюху) со всеми вариантами полученных «путей» для каждого узла в формате ltree + gin индекс на это поле
и тогда все запросы сведутся к поиску веток по индексу, а выше разобранный запрос использовать для заполнения ltree-)

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


Насчет ltree + gin gist — почему бы и нет, если перелеты статические, а искать надо часто. И к тому же как-нибудь хитро, типа «из A в B через C», потому что иначе достаточно обычного индекса.

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

Точно не минимальное? Нужно найти все варианты пути без циклов и выбрать из них самый длинный и так для каждой пары аэропортов?

Если говорить формально, то так: найти минимальное число N такое, что из произвольного аэропорта A можно добраться в произвольный аэропорт B, используя меньшее либо равное N число пересадок.


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

Возможно ли решить 1 задачу не перебравы все варианты?

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

Sign up to leave a comment.