Dijkstra's Algorithm

Diesell

Троглодит
#1
расскажите про сабж, естественно кто знает, пользовался, сталкивался и тп. Подсмотревшие в гугле и решившие поумничать автаматически идут нах, это понятно?
 

Diesell

Троглодит
#3
PinkFloyd грамматей?? *
_________________________________________-
* Не навижу недалеких (если ты недалекий, то читай глупых) людей...
* Специально для PinkFloyd: в 25 уже не сдают ничего, уже самт все занают :-))))
* В такой серьезной теме как: ..:: www.phorum.armavir.ru ::.. Welcome! » Computer science » Программирование » Флейм ???
 

Aliens

Известный деятель города
#4
diesell
если в 25 всё уже сами знают, то зачем спрашивают?

И поясни что тебе надо, что там у тебя за графы/лабиринты?

Мне лично, - больше нравится волновой алгоритм поиска кратчайшего пути, пользовался, и сам писал на делфе. Он понятен до очевидности и реализуется легко.
 

Diesell

Троглодит
#5
Nic есть задача которую уже довольно долгое время не могут решить, она связанна с вышеназванным алкоритмом, если интересно могу сюда положить условия. может совместными усиляими ума дадим?
 

Aliens

Известный деятель города
#6
Давай конечно условия.
Но я не понимаю, как это "задача связанная с алгоритмом" - это видимо что-то схаластическое. Поскольку алгоритм существует уже для решения прикладной задачи.
 

Diesell

Троглодит
#8
Hазрела у меня следущая задачка...

Hа входе есть разнообразные пути следования по вершинам графа в виде
a->b
a->b->c
d->e->f
и так далее.
количество этих путей (маршрутов) жестко фиксировано и сами они жестко
определены.
По условиям задачи, следует компактизировать этот ориентированный граф
(т.е. выполнить декомпозицию всех этих путей прохода вида a->b, d->e->f.. итд)
в виде нескольких ориентированных, но _уже_взвешенных_ графов, чтобы потом
суметь _однозначно_ восстановить какой-то из изначальных путей алгоритмом
Дейкстры. Дело в том что Дейкстра будет работать на одном из маленьких графов
быстрее. Предлагается ввести список соответсвия, в каком из получившихся графов
искать Дейкстрой путь. (Таких графов для данного пути может быть не один).

То есть понимаете что получается.
Все сложные пути вида a->b->c->d->e->f мы декомпозируем в несколько небольших
более простых графов, и восстанавливаем исходный путь поиском при помощи
Дейкстры (для этого нужно расставить в графах веса). Причем важное условие.
Hужно восстанавливать не все _возможные_ пути и подпути, нет. Hужно
восстанавливать пути as is, также как они были на входе. Что было, то
восстановилось Дейкстрой. Укзали в табличку "найди путь между d и f, ищи в
графе X" - Дейкстра поискал и восстановил путь d->e->f, так как в данном графе
веса расставлены именно так, что находится именно такой путь. Это очень важно
уметь вычленить все изначальные пути что были на входе. Выжным дополнительным
условием составления алгоритма является минимизация (оптимизация) кол-ва графов
на выходе.

Хотелось бы услышать, что делать. Или названия алгоритмов, "попробуй это"
keywords, советы итд.
 

Aliens

Известный деятель города
#9
:D сам придумал задачу?

насколько я понял условие, имеется соответствеие один к многим. И соответствено из конечного результата получить исходные данные не получиться.

задача не разрешима , и дело тут не в алгоритме Дейкстра.

Может я что-то не понял? Или вы изложимли условия не точно!?
 

Diesell

Троглодит
#10
уточняю
Конечно задача не из стандартных(придумал сам)

Есть некие статистические данные, скажем поездки по направлениям , каждая поездка имеет несколько разных путей, например:
Из вершины «А» в вершину «В» я могу попасть по следующим путям:
«A» ’ «B»
«A» ’ «F» ’ «B»
Из вершины «А» в вершину «F» я могу попасть по следующим путям
«A» ’ «F»
«A» ’ «E» ’ «F»
И так далее. Между двумя вершинами будут существовать 3-4 пути. Максимум (но могут быть и исключения.). Очень часто будет существовать только один путь.
Так вот их надо хранить как направленный граф со взвешенными дугами, зачем (надо так, обсуждению не подлежит). Граф и веса должны быть такими что бы я сказал алгоритму дейкстры найди в нем путь из А в F, и он выдал A-E-F, а ни какой либо другой. Очевидно что если у направления будет более одного возможного пути то размещать их надо в разных графах.

Теперь что я думаю по решению: возможно ли построить алгоритм как бы обратный Дейкстре?
Например я даю ему на вход путь, а он формирует граф, даю следующий путь он добавляет в граф его + соответственно меняет все веса в графе чтобы путь сохранился как минимальный (ну что бы его потом однозначно извлечь), а если это не возможно он говорит об этом и ничего не делает.
Вот такой мне бы хотелось найти алгоритм или помощь в его построении.
 

Aliens

Известный деятель города
#11
Теперь что я думаю по решению: возможно ли построить алгоритм как бы обратный Дейкстре? Например я даю ему на вход путь, а он формирует граф, даю следующий путь он добавляет в граф его + соответственно меняет все веса в графе чтобы путь сохранился как минимальный (ну что бы его потом однозначно извлечь), а если это не возможно он говорит об этом и ничего не делает. Вот такой мне бы хотелось найти алгоритм или помощь в его построении.
да , но затыкаться этот алгоритм будет очень быстро...
 

Diesell

Троглодит
#12
В смысле затыкаться? Поясни. И вообще реально ли его сделать?
С чего так сказать начать? А может как-то по другому? Перерыл инет - нет таких алгоритмов! Или задача такая не тривиальная или я незнаю уже что делать, повторюсь задача висит уже месяцев 8 минимум. На этом форуме я разместил ее так сказать с минимальной надеждой что найдется гений способный ее решить.
 

Aliens

Известный деятель города
#13
Затыкаться, в смысле:
он будет корректировать весовые числа, и добавлять новые узлы при необходимости.
Но уже после добавления 2-3 путей, он не сможет добавить- больше ни одного пути не потеряв - "забыв" один из добавленных путей. Так будет происходить при вводе альтернативного пути, например
из путей а-б-с, а-д-с, а-в-с ....он вспомнит только один... если хранить это в одном графе...

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

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

Aliens

Известный деятель города
#14
все это похоже на затею:
- изобрести свой архиватор ...т.е. алгоритм сжатия...