Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмическая задача на графах / 17 сообщений из 17, страница 1 из 1
26.05.2010, 11:23:45
    #36649498
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
Дали мне такую задачу:
Для того чтобы получить диплом студенту необходимо обойти некоторое количество кабинетов. В каждом кабинете он находится определенное время (10 минут например). И в каждом кабинете его посылают в следующий. Найти максимальное время за которое студент поймет что его дурачат. Нам известны кабинеты и то, куда направят студента в каждом из них, но неизвестно куда зайдет студент в первый раз.

Т.е. по сути надо найти максимальный цикл в графе
Я придумал 2 варианта решения, но есть странное ощущение что можно это сделать эффективнее
Вариант 1(менее эффективный):
Используем локальный массив пройденных элементов.
1. Берем первый элемент, добавляем его в этот массив.
2. Идем по ссылке из текущего элемента и проверяем-нет ли его в списке пройденных? Если есть, то выходим из проверки текущего элемента и сравниваем с максимальным количеством шагов
3. если нет, то берем элемент по ссылке из текущего и назад в пункт 2
Вариант 2:
Тут используется структура типа (текущая комната, ссылка на следующую, была ли посещена комната)
Проходим по пути из комнаты, отмечая их по пути. Как только находим уже пройденную комнату, очищаем пройденные точки тем же путем каким мы их отмечали.
Переходим к следующей комнате и повторяем процедуру.
...
Рейтинг: 0 / 0
26.05.2010, 11:41:02
    #36649594
krvsa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy denНайти максимальное время за которое студент поймет что его дурачат.
Что значит "дурачат"?

zloy denНам известны кабинеты и то, куда направят студента в каждом из них
Направить могут только в какой-то 1 кабинет? Или несколько "на выбор"?
...
Рейтинг: 0 / 0
26.05.2010, 11:47:14
    #36649636
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
"Дурачат"-одурачивают. Студента отправляют из кабинета в кабинет без конца. Он это понимает тогда, когда его отправляют в кабинет, в котором он уже был.

Отправить могут в один кабинет(естественно, заданный случайным образом в начале задачи)
...
Рейтинг: 0 / 0
26.05.2010, 12:53:03
    #36649962
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy denДали мне такую задачу:
Для того чтобы получить диплом студенту необходимо обойти некоторое количество кабинетов. В каждом кабинете он находится определенное время (10 минут например). И в каждом кабинете его посылают в следующий. Найти максимальное время за которое студент поймет что его дурачат. Нам известны кабинеты и то, куда направят студента в каждом из них, но неизвестно куда зайдет студент в первый раз.
ИМХО в задаче не хватает доп. условий. Или сама система кабинетов (орграф) изначально содержит безусловные петли. И система не имеет состояний (кроме положения студента). Тогда задача сводится к проверке куда попал студент в самый первый раз.
...
Рейтинг: 0 / 0
26.05.2010, 13:14:13
    #36650030
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
Вроде как да, по условию задачи есть петли. Т.е. дойдя до последнего кабинета мы обнаружим что нас вывело куда-то где мы уже были.

Изначально там было условие что есть К студентов и надо найти максимальное время когда они все определят что над ними издеваются. Куда попадает каждый студент в начале неизвестно. Я просто опустил это условие чтобы не загромождать.
Т.е. все же задача сводится к нахождению наибольшего цикла в графе.
...
Рейтинг: 0 / 0
28.05.2010, 17:49:29
    #36656098
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy denТ.е. по сути надо найти максимальный цикл в графе
Это совершенно не так. Принципиальная ошибка.

А алгоритм на глаз должен быть примерно следующий. Метим все вершины нулями, организовываем пустой стек вершин. Цикл: если стек непуст, берём вершину из стека, если пуст - любую нулевую. Смотрим, куда ведёт из неё путь. Если в ненулевую - метим текущую как "ненулевую плюс один" и идём на следующую итерацию. Если в нулевую - кладём текущую и целевую в стек и опять-таки идём на следующую итерацию. При этом запоминаем максимальную вершину. Когда ненулевые вершины кончатся - длиннейший путь найден.
...
Рейтинг: 0 / 0
28.05.2010, 18:33:35
    #36656176
Crazzy
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
Еще вариант:
допустим у графа n>2 вершин.
составляем для него матрицу смежности.
Затем в цикле k = 1, k<n, k++ n ищем матрицу достижимости за k шагов на основе предыдущей матрицы достижимости (за k-1 шагов) и матрицы смежности. Как только матрица достижимости на шаге k будет совпадать с матрицей достижимости на шаге k-1, возвращаем k в качестве результата.
...
Рейтинг: 0 / 0
28.05.2010, 21:21:40
    #36656346
Алгоритмическая задача на графах
Полагаю, братья, что это решается не на графе, а конечным автоматом. ИМХО, такая интерпретация проще и естественнее. Петли наверное возможны, но в каждом состоянии автомата можно иметь счетчик (студент на 10й раз поймет, что заблудился и умер от голода, аспирант поймет на 5й раз)
...
Рейтинг: 0 / 0
31.05.2010, 09:16:27
    #36658335
krvsa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy denЯ просто опустил это условие чтобы не загромождать.
В итоге просто запутал всех. Никогда не переделывай условие задачи, ибо напутаешь и будет не понятно какие исходные данные и каков собственно вопрос.

Есть шанс увидеть подленник задания?
...
Рейтинг: 0 / 0
31.05.2010, 10:01:52
    #36658399
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
Всё очень просто.

Если это лаба, то я в таких случаях просто подходил к преподу за пояснением. Бывает что методичка составлена криво и сам препод не может разобраться что надо собсно делать. В таких случаях он просто меняет задание на более простое.
...
Рейтинг: 0 / 0
31.05.2010, 10:13:55
    #36658419
krvsa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
Как вариант...

Код: 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.
START
	n
	s student= 5 
	s office= 10 
	s buf=$na(^CacheTemp($j,"START^tmp"))
	k @buf
	s rnd=$na(@buf@("Rnd"))
	s ofc=$na(@buf@("Office"))
	d INIT
	d SETOFFICE
	d LISTOFFICE
	s event=$na(@buf@("Event"))
	for i= 1 : 1 :student {
		d STUDENT
	}
	d MAXEVENT
	q
MAXEVENT ; Поиск максимального пути
	n i,max,st
	s max= 0 
	for i= 1 : 1 :student {
		s:@event@(i)>max max=@event@(i),st=i
	}
	w !
	w !,"Max event=",max
	w !,"Student=",st
	q
STUDENT ; События со студентом
	n of,j,dlm
	w !,"Student ",i,!
	s dlm=""
	s of=($r(office)\ 1 )+ 1 
GO ; метка повтора итерации
	if $d(@event@(i, 0 ,of)) {
		d RESULT
		q
	}
	s j=$i(@event@(i))
	s @event@(i, 0 ,of)=j
	s @event@(i, 1 ,j)=of
	w dlm,of
	s dlm=", "
	s of=@ofc@(of)
	g GO
	q
RESULT ; Подведение итогов по студенту
	w !
	if @event@(i)=office {
		w "Ok"
	} else {
		w "Break"
	}
	q
LISTOFFICE ; Вывод распределения кабинетов
	n i
	w !,"Office"
	for i= 1 : 1 :office {
		w !,i,"=",@ofc@(i)
	}
	q
SETOFFICE ; Распределить ссылки по кабинетам
	n i,max
	s max=office
	for i= 1 : 1 :office {
		d OFFICE
	}
	q
OFFICE ; Очередной кабинет
	n j,val
	s j=($r(max)\ 1 )+ 1 
	s @ofc@(i)=@rnd@(j)
	s @rnd@(j)=@rnd@(max)	
	s @rnd@(max)=@ofc@(i)
	s max=max- 1 
	q
INIT ; Подготовка переменных
	n i
	for i= 1 : 1 :office {
		s @rnd@(i)=i
	}
	q	

Результаты работы...

Код: 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.
ERR>d ^tmp
 
Office
 1 = 5 
 2 = 8 
 3 = 10 
 4 = 6 
 5 = 7 
 6 = 2 
 7 = 4 
 8 = 1 
 9 = 3 
 10 = 9 
Student  1 
 4 ,  6 ,  2 ,  8 ,  1 ,  5 ,  7 
Break
Student  2 
 3 ,  10 ,  9 
Break
Student  3 
 3 ,  10 ,  9 
Break
Student  4 
 5 ,  7 ,  4 ,  6 ,  2 ,  8 ,  1 
Break
Student  5 
 7 ,  4 ,  6 ,  2 ,  8 ,  1 ,  5 
Break
 
Max event= 7 
Student= 1 

Но бывает что и получается...

Код: 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.
ERR>d ^tmp
 
Office
 1 = 10 
 2 = 8 
 3 = 5 
 4 = 2 
 5 = 9 
 6 = 3 
 7 = 1 
 8 = 7 
 9 = 4 
 10 = 6 
Student  1 
 4 ,  2 ,  8 ,  7 ,  1 ,  10 ,  6 ,  3 ,  5 ,  9 
Ok
Student  2 
 9 ,  4 ,  2 ,  8 ,  7 ,  1 ,  10 ,  6 ,  3 ,  5 
Ok
Student  3 
 10 ,  6 ,  3 ,  5 ,  9 ,  4 ,  2 ,  8 ,  7 ,  1 
Ok
Student  4 
 9 ,  4 ,  2 ,  8 ,  7 ,  1 ,  10 ,  6 ,  3 ,  5 
Ok
Student  5 
 2 ,  8 ,  7 ,  1 ,  10 ,  6 ,  3 ,  5 ,  9 ,  4 
Ok
 
Max event= 10 
Student= 1 
...
Рейтинг: 0 / 0
31.05.2010, 11:16:02
    #36658544
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
softwarerzloy denТ.е. по сути надо найти максимальный цикл в графе
Это совершенно не так. Принципиальная ошибка.


Да, я неправильно выразился. При простейшем варианте
1->2
2->3
3->4
4->3
максимальный цикл будет из двух шагов(3->4->3), а путь максимальный путь будет из 4х (1->2-3->4->3)
...
Рейтинг: 0 / 0
31.05.2010, 11:18:54
    #36658557
krvsa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy denДа, я неправильно выразился.
Гони оригинальный текст задания.
...
Рейтинг: 0 / 0
31.05.2010, 11:38:37
    #36658618
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
softwarer

А алгоритм на глаз должен быть примерно следующий.


А этот прием как-то называется? Пытаюсь понять принцип работы
...
Рейтинг: 0 / 0
31.05.2010, 12:04:47
    #36658699
NotGonnaGetUs
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy den,

обход (поиск) в ширину.

http://en.wikipedia.org/wiki/Breadth-first_search
...
Рейтинг: 0 / 0
31.05.2010, 17:52:26
    #36659643
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
softwarerzloy denТ.е. по сути надо найти максимальный цикл в графе
Это совершенно не так. Принципиальная ошибка.

А алгоритм на глаз должен быть примерно следующий. Метим все вершины нулями, организовываем пустой стек вершин. Цикл: если стек непуст, берём вершину из стека, если пуст - любую нулевую. Смотрим, куда ведёт из неё путь. Если в ненулевую - метим текущую как "ненулевую плюс один" и идём на следующую итерацию. Если в нулевую - кладём текущую и целевую в стек и опять-таки идём на следующую итерацию. При этом запоминаем максимальную вершину. Когда ненулевые вершины кончатся - длиннейший путь найден.

ненулевые или нулевые?
...
Рейтинг: 0 / 0
01.06.2010, 08:11:19
    #36660395
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритмическая задача на графах
zloy denненулевые или нулевые?
Нулевые, конечно.

zloy denмаксимальный цикл будет из двух шагов(3->4->3), а путь максимальный путь будет из 4х
Важнее то, что максимальный путь совершенно не обязан включать в себя максимальный цикл.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмическая задача на графах / 17 сообщений из 17, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]