Здравсвуйте!
Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути? Имеется ввиду путь на графе из узла А в узел В не содержащий циклов и обладающей наибольшей стоимостью... Или какую эвристику можно применить для поиска подобного пути на большом графе (порядка N=100000 узлов, каждый узел связан с 1-4 другими, вес каждого ребра — целое число от 1 до 4 с обратным распределением (т.е. 70% ребер имеют вес 1, 20% — 2, 7% — 3, 3% — 4))??? Необходимо попадание в 10% самых длинных путей.
Заранее благодарен.
P.S. Желательно, чтобы вычислительная сложность алгоритма не превышала O(N^2)

Здравствуйте, FlameHeap, Вы писали:

FH>Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути?

Посмотри поиск критического пути на сетевом графике

Здравствуйте, FlameHeap, Вы писали:

FH>Здравсвуйте!
FH>Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути? Имеется ввиду путь на графе из узла А в узел В не содержащий циклов и обладающей наибольшей стоимостью... Или какую эвристику можно применить для поиска подобного пути на большом графе (порядка N=100000 узлов, каждый узел связан с 1-4 другими, вес каждого ребра — целое число от 1 до 4 с обратным распределением (т.е. 70% ребер имеют вес 1, 20% — 2, 7% — 3, 3% — 4))??? Необходимо попадание в 10% самых длинных путей.
FH>Заранее благодарен.
FH>P.S. Желательно, чтобы вычислительная сложность алгоритма не превышала O(N^2)

А мож попробовать все тот же родной и близкий сердцу А*, предварительно сделав веса ребер и возвращаемое значение эвристической функции отрицательными?

Здравствуйте, Aquary, Вы писали:

FH>>Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути?

A>Посмотри поиск критического пути на сетевом графике

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

Здравствуйте, FlameHeap, Вы писали:

А замена весов на отрицательные и поиск наименьшего решения приводит к полному перебору графа, что опять таки неприемлемо...

Что значит к "полному перебору" ?!

Здравствуйте, FlameHeap, Вы писали:

FH>Здравсвуйте!
FH>Везде всегда очень подробно рассматриаются алгоритмы нахождения самых коротких и "дешевых" путей... А есть ли какие-нибудь алгоритмы нахождения самого длинного пути? Имеется ввиду путь на графе из узла А в узел В не содержащий циклов и обладающей наибольшей стоимостью... Или какую эвристику можно применить для поиска подобного пути на большом графе (порядка N=100000 узлов, каждый узел связан с 1-4 другими, вес каждого ребра — целое число от 1 до 4 с обратным распределением (т.е. 70% ребер имеют вес 1, 20% — 2, 7% — 3, 3% — 4))??? Необходимо попадание в 10% самых длинных путей.
FH>Заранее благодарен.
FH>P.S. Желательно, чтобы вычислительная сложность алгоритма не превышала O(N^2)

Идея такая:

Максимальный путь без циклов можно построить, если пройти через все точки. => Необходимо решить ЗКВ для вспомогательной задачи, у которого вес ребер вычисляем так: вспом_вес = (5 — фактический_вес).
ЗКВ — NP полна => придется решить приближенно.
Попробуй использовать жадный алгоритм соединения вершин: соединяем с минимальным вспом_вес или максимальным фактический_вес. Думаю, О(..) получишь, и в требуемые 10% попадешь.

Здравствуйте Ilnar, Вы писали:

I>Максимальный путь без циклов можно построить, если пройти через все точки.
хочу заметить что через некоторые точки нужно пройти более одно раза:

  3       4
   o--------o
    \     /
 1    \2/5
 o-----o-------o 6
      /8\     /
    /     \ /
  9o       o 7

сабж... ногами чур не пинать... спать надо чаще..

Здравствуйте, _MarlboroMan_, Вы писали:

M>Здравствуйте Ilnar, Вы писали:

I>>Максимальный путь без циклов можно построить, если пройти через все точки.
M>хочу заметить что через некоторые точки нужно пройти более одно раза:

M>

M>  3       4
M>   o--------o
M>    \     /
M> 1    \2/5
M> o-----o-------o 6
M>      /8\     /
M>    /     \ /
M>  9o       o 7

M>

Тут ты прав и не прав.
Необходимо составить маршрут через все пункты предполагая, что между всеми пунктами есть ребра.
Если тебе не известна длина ребер, пользуешся алгоритмом Флойда-Уоршелла.
Потом с помощью алгоритма Дейкстры составляешь реальные маршруты ребер (т.е. как пройти).

Замечание: Из множества пунктов предварительно "убрать" точку назначения и ребра, связанные с ней, и для нее решать модифицированную задачу КВ, если это возможно.