|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Нет наработок или кода, если нужно готовое решение - создайте тему в разделе Фриланс и оплатите работу. Название темы включает слова - "Помогите", "Нужна помощь", "Срочно", "Пожалуйста". Название темы слишком короткое или не отражает сути вашего вопроса. Тема исчерпала себя, помните, один вопрос - одна тема Прочитайте правила и заново правильно создайте тему. |
|
Опции темы | Поиск в этой теме |
19.10.2008, 22:27 | #1 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
применить Алгоритм Дейкстры для поиска кратчайшего пути в графе
исходные данные даны матрицей :
1 5 6 9 10 20 21 22 33 2 3 4 11 12 * * * * 3 1 5 19 20 25 * * * ****************** 40 26 27 29 31 37 * * * надо чтобы прокладывало маршрут(односторонний) из начальной точки(например 1) в конечную(например18) и его выводило (например 1-5-20-13-18), у каждой точки есть от 0 до 10 точек в которые можно из нее попасть но в одну сторону( из этих точек обратно нельзя) и условие что в цепочке не меньше 3х точек и не больше 5 я так понял надо применить Алгоритм Дейкстры для поиска кратчайшего пути в графе: for k:=1 to N do for i:=1 to N do for j:=1 to N do d[i,j]:=min(d[i,j], d[i,k]+d[k,j]); не совсем понимаю как увязать исходные данные с формулой да и как сделать односторонний маршрут я как понял графы у меня ориентированные...Помогите плиз=) |
20.10.2008, 22:53 | #2 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
тут помогают или нет?)
из точки 1 можно попасть в 5 ,6 9, 10,20,21,22,23 из 2 в 3,4,11 или 12 соответственно, и так далее это пояснение к исходникам уверен что задачка примитивна и решается на раз два помогите пожалуйста) Последний раз редактировалось Эдгар; 20.10.2008 в 23:49. |
20.10.2008, 23:04 | #3 |
Новичок
СтарожилДжуниор
Регистрация: 05.02.2008
Сообщений: 9,487
|
случается иногда
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете
|
21.10.2008, 05:26 | #4 |
Новичок
СтарожилДжуниор
Регистрация: 05.02.2008
Сообщений: 9,487
|
Уважаемый Эдгар, я не обнаружил точной постановки задачи в Вашем изложении, поэтому решал задачу поставленную самому себе по мотивам Вашей.
Итак, в моей задаче в качестве исходных взято 100 точек. В нижней таблице случайным образом написано из какой точки в какую есть путь. Предполагается, что из точки с меньшим порядковым номером можно попасть только в точку с большим номером. Количество тропинок из каждой точки равно 5 (можно до 10, нарисована сетка). Если в Вашей задаче число тропинок произвольное, необходимо написать реальные пути, а у тех точек, а где их мало - дополнить "фиктивными путями" до точки 100, которой нет на плане. Над кнопкой "старт" пишем номер начальной, конечной точки графа, и максимальное количество переходов. Жмем "старт". Видим последовательности переходов. Для поочередной визуализации графов достаточно написать номер графа под кнопкой "старт". Условное форматирование закрасит нужные ячейки. Задача решена алгоритмом Гончаренко. Данный алгоритм заключается в довольно примитивном переборе всех возможных вариантов. Собственно там 20 строк алгоритма, и 10 строк подготовки к расчетам.
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете
|
21.10.2008, 21:54 | #5 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
Супер!!! Это то что надо!!! Прога супер!!! только еще один маленький нюанс ... у меня точки это строки текстовые... можно точку 1 сопоставить с одним словом, 2- с другим и так далее? и результат что бы писало И словами...?=) ОГРОМНОЕ СПАСИБО!!!!
Последний раз редактировалось Эдгар; 21.10.2008 в 22:14. |
23.10.2008, 21:36 | #6 |
Новичок
СтарожилДжуниор
Регистрация: 05.02.2008
Сообщений: 9,487
|
Внимание:
- теперь вместо цифр можно использовать названия точек (любые строки) - для каждой точки может быть указано произвольное количество путей (связей с другими точками) - обрабатывается 100 строк с данными - рекурсивная процедура очень чувствительна к количеству обрабатываемых данных.
Программисты - это люди, решающие проблемы, о существовании которых Вы не подозревали, методами, которых Вы не понимаете
|
24.10.2008, 00:31 | #7 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
- теперь вместо цифр можно использовать названия точек (любые строки)
не понял как это сделать)))и хотелось бы иметь возможность увидеть результат в виде цепочки названий точек...(а может даже и задавать начальную и конечную точку по их названиям...) - рекурсивная процедура очень чувствительна к количеству обрабатываемых данных. не совсем понял о чем Вы излагаетесь=) Последний раз редактировалось Эдгар; 24.10.2008 в 00:38. |
24.10.2008, 10:28 | #8 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
часто происходит ошибка "28" и ссылается на эту строку
If Cells(RowP(TAr(s).t), TAr(s).l + 2) = "" Then Последний раз редактировалось Эдгар; 24.10.2008 в 10:42. |
24.10.2008, 10:49 | #9 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
- рекурсивная процедура очень чувствительна к количеству обрабатываемых данных.
кажись я понял что это значит=))) |
24.10.2008, 11:07 | #10 |
Пользователь
Регистрация: 12.09.2008
Сообщений: 16
|
это сообщение не смотреть=) (не знаю как удалить....)
Последний раз редактировалось Эдгар; 24.10.2008 в 11:19. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Флойда. Поиск Кратчайшего пути. | Shady | Помощь студентам | 5 | 06.10.2014 18:29 |
1) Поиск кратчайшего пути в графе методом полного перебора в ширину(очередь) | Serega123 | Помощь студентам | 3 | 30.10.2008 22:26 |
Алгоритм Дейкстры | Dimon88 | Помощь студентам | 2 | 03.11.2007 17:13 |