powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритмическая задача на графах
17 сообщений из 17, страница 1 из 1
Алгоритмическая задача на графах
    #36649498
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дали мне такую задачу:
Для того чтобы получить диплом студенту необходимо обойти некоторое количество кабинетов. В каждом кабинете он находится определенное время (10 минут например). И в каждом кабинете его посылают в следующий. Найти максимальное время за которое студент поймет что его дурачат. Нам известны кабинеты и то, куда направят студента в каждом из них, но неизвестно куда зайдет студент в первый раз.

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

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

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

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

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

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

Если это лаба, то я в таких случаях просто подходил к преподу за пояснением. Бывает что методичка составлена криво и сам препод не может разобраться что надо собсно делать. В таких случаях он просто меняет задание на более простое.
...
Рейтинг: 0 / 0
Алгоритмическая задача на графах
    #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
Алгоритмическая задача на графах
    #36658544
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
softwarerzloy denТ.е. по сути надо найти максимальный цикл в графе
Это совершенно не так. Принципиальная ошибка.


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

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


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

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

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

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

ненулевые или нулевые?
...
Рейтинг: 0 / 0
Алгоритмическая задача на графах
    #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]