1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
||||||
1 | ||||||
Кратчайший путь в графе(Рекурсия)29.04.2013, 10:38. Показов 9887. Ответов 23
Метки нет (Все метки)
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без рекурсии. Помогите изменить прогу под исполььзование рекурсии
input.txt 0 500 3 500 500 500 0 9 500 4 3 9 0 3 8 500 500 3 0 2 500 4 8 2 0 500-прямой дороги нет
0
|
29.04.2013, 10:38 | |
Ответы с готовыми решениями:
23
Кратчайший путь в графе. Найдите кратчайший путь в графе Как найти НЕ Кратчайший путь в графе ? Кратчайший путь коня с++ |
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
29.04.2013, 14:56 | 2 |
алгоритм Флойда с рекурсией...?)
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
||||||
29.04.2013, 15:56 | 3 | |||||
LEBRON32RUS, Классический алгоритм Флойда-Уоршелла пишется в 3-х циклах
0
|
212 / 214 / 44
Регистрация: 20.12.2011
Сообщений: 635
|
|
29.04.2013, 16:05 | 4 |
у ТС вопрос был не в нахождении кратчайшего пути(он его уже нашёл этим алгоритмом), а в том, что ему необходимо использовать рекурсию для нахождения этого пути.
смотрите в сторону обхода графа в глубину или ширину
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
29.04.2013, 16:12 | 5 |
Fler, через dfs(Обход в глубину) никогда не стоит искать кратчайшее расстояние! Подчёркиваю.
bfs(обход в глубину) в классической реализации -- очередь с циклом. Но обычный цикл всегда можно переделать в рекурсию, что ухудшит производительность.
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 16:21 [ТС] | 6 |
ну может кто нибудь сможет показать эту функцию рекурсивную(пожалуйста)
Добавлено через 1 минуту Нет не алгоритм флойда с рекурсией а новый метод какой нибудь.подразумевающий использование рекурсии и решающий мою задачу
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
29.04.2013, 16:30 | 7 |
LEBRON32RUS, http://habrahabr.ru/post/162915/ вот алгоритм поиска кратчайшего пути JPS очень шустро работает. Там рекурсивная функция прыжка. Но он не ко всем графам применим, а если точнее, то очень не ко многим. Например, к прямоугольным лабиринтам
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 17:42 [ТС] | 8 |
что то совсем туго я понимаю то что там разбирается.
вот условие задачи.мало ли может я с этими графами совсем нетуда пошел может и по другому эта задача решается Дана матрица размером NxN с расстояниями между городами при наличии прямой дороги между ними. По вертикали содержаться города откуда выезжаем, по горизонтали – куда. На пересечении - расстояние по прямой дороге. Если прямой дороги нет, в соответствующем элементе матрицы записывается число “-1”. Найти кратчайшее расстояние между городами i и j даже если между ними нет прямой дороги. Препод сказал функция должна принимать саму матрицу .пройденное расстояние .количество сделанных шагов и текущую координату(город)
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
29.04.2013, 17:49 | 9 |
вы так и не прояснили: вам нужно узнать расстояние между какими-то двумя конкретными городами или для всех пар?
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 17:50 [ТС] | 10 |
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
29.04.2013, 17:51 | 11 |
начнем тогда с того, что алгоритм Флойда-Уоршелла к этой задаче применять нерационально.
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 17:52 [ТС] | 12 |
да это я уже понял...я сначала находил для всех а потом уже в зависимости какой путь интересен пользователю выдавал результат.
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
29.04.2013, 17:54 | 13 |
LEBRON32RUS,
Ужас, если рекурсия будет принимать каждый раз матрицу(не по ссылке), то у вас будет Memory limit, т.к. очень много займёт памяти. Наверное вам без рекурсии надо. Позвольте мне угодать, вы хотите сделать функцию кратчайшего расстояния между двумя вершинами, в аргументы которой будет подаваться матрица смежности графа.
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
29.04.2013, 17:54 | 14 |
тогда напишите Дейкстру, сравните время работы с рекурсией и без и задайте преподавателю вопрос, который витает в воздухе...)
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 17:56 [ТС] | 15 |
Я говорил преподу что рекурсией нерационально а он уперся и говорит. "Задание на рекурсию"
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
29.04.2013, 17:58 | 16 |
да понятно, извините за болтовню.
Дейкстру писать умеете?
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 18:01 [ТС] | 17 |
0
|
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
|
|
29.04.2013, 18:01 | 18 |
LEBRON32RUS, да, переделайте же вы цикл в рекурсию, омфг...
0
|
194 / 174 / 30
Регистрация: 10.07.2012
Сообщений: 800
|
|
29.04.2013, 18:02 | 19 |
там ее нет, потому что она неэффективна. там есть цикл. а в информатике есть теорема о взаимозаменяемости цикла и рекурсии. изучайте.
0
|
1 / 1 / 0
Регистрация: 06.11.2012
Сообщений: 90
|
|
29.04.2013, 18:05 [ТС] | 20 |
0
|
29.04.2013, 18:05 | |
29.04.2013, 18:05 | |
Помогаю со студенческими работами здесь
20
Найти кратчайший путь Графы кратчайший путь ! Как найти кратчайший путь? Найти кратчайший путь из вершины u в вершину v Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |