|
|
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
Дали мне такую задачу: Для того чтобы получить диплом студенту необходимо обойти некоторое количество кабинетов. В каждом кабинете он находится определенное время (10 минут например). И в каждом кабинете его посылают в следующий. Найти максимальное время за которое студент поймет что его дурачат. Нам известны кабинеты и то, куда направят студента в каждом из них, но неизвестно куда зайдет студент в первый раз. Т.е. по сути надо найти максимальный цикл в графе Я придумал 2 варианта решения, но есть странное ощущение что можно это сделать эффективнее Вариант 1(менее эффективный): Используем локальный массив пройденных элементов. 1. Берем первый элемент, добавляем его в этот массив. 2. Идем по ссылке из текущего элемента и проверяем-нет ли его в списке пройденных? Если есть, то выходим из проверки текущего элемента и сравниваем с максимальным количеством шагов 3. если нет, то берем элемент по ссылке из текущего и назад в пункт 2 Вариант 2: Тут используется структура типа (текущая комната, ссылка на следующую, была ли посещена комната) Проходим по пути из комнаты, отмечая их по пути. Как только находим уже пройденную комнату, очищаем пройденные точки тем же путем каким мы их отмечали. Переходим к следующей комнате и повторяем процедуру. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.05.2010, 11:23:45 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy denНайти максимальное время за которое студент поймет что его дурачат. Что значит "дурачат"? zloy denНам известны кабинеты и то, куда направят студента в каждом из них Направить могут только в какой-то 1 кабинет? Или несколько "на выбор"? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.05.2010, 11:41:02 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
"Дурачат"-одурачивают. Студента отправляют из кабинета в кабинет без конца. Он это понимает тогда, когда его отправляют в кабинет, в котором он уже был. Отправить могут в один кабинет(естественно, заданный случайным образом в начале задачи) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.05.2010, 11:47:14 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy denДали мне такую задачу: Для того чтобы получить диплом студенту необходимо обойти некоторое количество кабинетов. В каждом кабинете он находится определенное время (10 минут например). И в каждом кабинете его посылают в следующий. Найти максимальное время за которое студент поймет что его дурачат. Нам известны кабинеты и то, куда направят студента в каждом из них, но неизвестно куда зайдет студент в первый раз. ИМХО в задаче не хватает доп. условий. Или сама система кабинетов (орграф) изначально содержит безусловные петли. И система не имеет состояний (кроме положения студента). Тогда задача сводится к проверке куда попал студент в самый первый раз. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.05.2010, 12:53:03 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
Вроде как да, по условию задачи есть петли. Т.е. дойдя до последнего кабинета мы обнаружим что нас вывело куда-то где мы уже были. Изначально там было условие что есть К студентов и надо найти максимальное время когда они все определят что над ними издеваются. Куда попадает каждый студент в начале неизвестно. Я просто опустил это условие чтобы не загромождать. Т.е. все же задача сводится к нахождению наибольшего цикла в графе. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.05.2010, 13:14:13 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy denТ.е. по сути надо найти максимальный цикл в графе Это совершенно не так. Принципиальная ошибка. А алгоритм на глаз должен быть примерно следующий. Метим все вершины нулями, организовываем пустой стек вершин. Цикл: если стек непуст, берём вершину из стека, если пуст - любую нулевую. Смотрим, куда ведёт из неё путь. Если в ненулевую - метим текущую как "ненулевую плюс один" и идём на следующую итерацию. Если в нулевую - кладём текущую и целевую в стек и опять-таки идём на следующую итерацию. При этом запоминаем максимальную вершину. Когда ненулевые вершины кончатся - длиннейший путь найден. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.05.2010, 17:49:29 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
Еще вариант: допустим у графа n>2 вершин. составляем для него матрицу смежности. Затем в цикле k = 1, k<n, k++ n ищем матрицу достижимости за k шагов на основе предыдущей матрицы достижимости (за k-1 шагов) и матрицы смежности. Как только матрица достижимости на шаге k будет совпадать с матрицей достижимости на шаге k-1, возвращаем k в качестве результата. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.05.2010, 18:33:35 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
Полагаю, братья, что это решается не на графе, а конечным автоматом. ИМХО, такая интерпретация проще и естественнее. Петли наверное возможны, но в каждом состоянии автомата можно иметь счетчик (студент на 10й раз поймет, что заблудился и умер от голода, аспирант поймет на 5й раз) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.05.2010, 21:21:40 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy denЯ просто опустил это условие чтобы не загромождать. В итоге просто запутал всех. Никогда не переделывай условие задачи, ибо напутаешь и будет не понятно какие исходные данные и каков собственно вопрос. Есть шанс увидеть подленник задания? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 09:16:27 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
Всё очень просто. Если это лаба, то я в таких случаях просто подходил к преподу за пояснением. Бывает что методичка составлена криво и сам препод не может разобраться что надо собсно делать. В таких случаях он просто меняет задание на более простое. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 10:01:52 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
Как вариант... Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. Результаты работы... Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. Но бывает что и получается... Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 10:13:55 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
softwarerzloy denТ.е. по сути надо найти максимальный цикл в графе Это совершенно не так. Принципиальная ошибка. Да, я неправильно выразился. При простейшем варианте 1->2 2->3 3->4 4->3 максимальный цикл будет из двух шагов(3->4->3), а путь максимальный путь будет из 4х (1->2-3->4->3) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 11:16:02 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy denДа, я неправильно выразился. Гони оригинальный текст задания. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 11:18:54 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
softwarer А алгоритм на глаз должен быть примерно следующий. А этот прием как-то называется? Пытаюсь понять принцип работы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 11:38:37 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy den, обход (поиск) в ширину. http://en.wikipedia.org/wiki/Breadth-first_search ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 12:04:47 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
softwarerzloy denТ.е. по сути надо найти максимальный цикл в графе Это совершенно не так. Принципиальная ошибка. А алгоритм на глаз должен быть примерно следующий. Метим все вершины нулями, организовываем пустой стек вершин. Цикл: если стек непуст, берём вершину из стека, если пуст - любую нулевую. Смотрим, куда ведёт из неё путь. Если в ненулевую - метим текущую как "ненулевую плюс один" и идём на следующую итерацию. Если в нулевую - кладём текущую и целевую в стек и опять-таки идём на следующую итерацию. При этом запоминаем максимальную вершину. Когда ненулевые вершины кончатся - длиннейший путь найден. ненулевые или нулевые? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 31.05.2010, 17:52:26 |
|
||
|
Алгоритмическая задача на графах
|
|||
|---|---|---|---|
|
#18+
zloy denненулевые или нулевые? Нулевые, конечно. zloy denмаксимальный цикл будет из двух шагов(3->4->3), а путь максимальный путь будет из 4х Важнее то, что максимальный путь совершенно не обязан включать в себя максимальный цикл. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 01.06.2010, 08:11:19 |
|
||
|
|

start [/forum/topic.php?fid=16&msg=36650030&tid=1343648]: |
0ms |
get settings: |
7ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
190ms |
get topic data: |
15ms |
get forum data: |
4ms |
get page messages: |
79ms |
get tp. blocked users: |
1ms |
| others: | 200ms |
| total: | 517ms |

| 0 / 0 |
