[велосипедизм] графы, наименьшая стоимость пути

>Фишка в том, что рассматривать критерии нужно все вместе, но только один из них доминирует.

Доминирует - это как? Если он просто важнее других = сделать x = f(...) с учетом "коэффициента важности" критериев, т.е. главный сделать более значимым. Комплексный критерий в общем.

Дадададад.

Единственное, к чему я пришел на данную минуту — на каждую приоритетность f(t, p, c) должна быть своя.

Мне главное даже не это. А то, чтобы избежать сортировок и поиска при вычислении этого коэффициента оптимума. Он должен работать как хеш-функция, возвращая какое-то число, уникальное для любого набора (t, p, c), но это число должно отражать прямую либо обратную зависимость от желанности результата.

Мне кажется, что такая задача уже была решена, вот интересно только — как.

> Доминирует - это как?

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

тебе нужна функция сравнения.
Каждому ребру сопостален список 3х значений [time, price, changes]. 
Приоритет задается порядком следования в списке.
Для двух ребер A и B нужна функция 
f(A, B), которая возвращает их соотношение вида (больше | меньше | равно)

f a b = case dropWhile (==EQ) $ zipWith compare a b of
             [] -> EQ
             (x:_) -> x

ну а потом любой известный алгоритм с этой функцией в качестве функции сравнения.

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

Спасибо

если я правильно понял задачу, то теоритически её можно разрулить dimensional деревьями. Например kd-tree. И, как написали выше, приоритет одного из ключей суть f(x).

http://en.wikipedia.org/wiki/Kd-tree
http://www.cs.sunysb.edu/~algorith/implement/KDTREE/implement.shtml

> выразить в виде одной величины x = f(time, price, changes)

ну возьми трехмерный вектор (time, price, changes) -- вот тебе и будет такая величина.

правда отношение порядка в пространстве этих векторов определить каким-либо естественным способом нельзя

так что например алгоритм нахождения кратчайшего пути применить не получится

> остальные величины при прочих равных всегда располагаются от лучшей к худшей

а, ну если так, то как раз отношение порядка определить можно

а именно, сравнивать векторы покоординатно -- т.е.
{ (x, y) < (x', y') } <=> { (x < x' ) or ( x == x' and y < y') }.

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

Хм, а это уже более-менее идея, берем оси (расстояние, цена, время) и имеем сравнимые между собой величины на каждой оси, для приоритетности достаточно сравнить в нужном порядке.

Тут немного лучше есть вариант -- вектор А хуже набора векторов В,С,... если он лежит внутри их линейной оболочки :-) не знаю, можно ли к этому приспособить алгоритм Дейкстры.

// www_linux_org_ru

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

> Тут немного лучше есть вариант -- вектор А хуже набора векторов В,С,... если он лежит внутри их линейной оболочки

Не понял. Как теперь предлагается сравнивать два вектора? В общем случае два (и даже три) вектора будут линейно независимы.

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

* граф состоит из станций метро (или какой там транспорт?), и каждому ребру присваивается векторный вес (время, стоимость, количество пересадок). Чтобы учесть пересадки и стоимость проезда, видимо надо вводить отдельное ребро для каждой пересадки (с весом например (0,0,1)), и отдельное ребро для действий типа "вход в метро" или "пересечение границы тарифных зон" (с весом (цена, 0, 0)).

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

нет, искать и сравнивать нужно одновременно, причем поик должен идти в первую очередь по маршрутам с минимальной длиной, см. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Всё тот же обратный волновой алгоритм.

>рассматривать критерии нужно все вместе, но только один из них доминирует

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

нормализуй троицу