|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
21.05.2010, 21:23 | #1 |
Регистрация: 15.03.2010
Сообщений: 6
|
графы - Все возможные пути
привет всем)))!!!
я студент 2 курса изучаю с++))), вот дошёл до графов))))!! пока у меня очень плохо получается с ними(((((!!! Препод дал задачку: Лабиринт задается матрицей сложности N*N.где С(i,j)=1,если узел i связан с узлом j посредством дороги.Часть узлов назначается входами.часть выходами.Входы и выходы задаются последовательностями узлов X(1),...,X(p) и Y(1),..,Y(k) соответственно. Найти максимальное число людей которых можно провести от входов до выходов т о чтобы: 1-их пути не пересекались по дорогам.но могут пересекаться по узлам 2-их пути не пересекались по узлам объясните пожалуйста с чего начать хотя бы!!! и если можете киньте пожалуста код, я буду разбираться в нём))!!! а то никак я его не понимаю(((!!! |
21.05.2010, 22:06 | #2 |
Форумчанин
Регистрация: 04.05.2010
Сообщений: 495
|
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948 |
22.05.2010, 03:04 | #3 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Классическая задача на DFS (поиск в глубину). Называется "лабиринт с личными дверями"
Основная стратегия человека в лабиринте - двигаться безотрывно держась левой рукой за стенку лабиринта. Находясь в очередной позиции лабиринта он должен помнить как он сюда пришел ( слева, справа, сверху, снизу). И выбирать правильно следующее направление движения Если в позицию попали сверху, то наилучшим направлением будет налево затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев. В стеке храним координаты текущей позиции и направление, по которому пришли в эту позицию.
O(n)
|
22.05.2010, 03:06 | #4 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Z1000000, там по ссылке для взвешенных графов, да еще и с возможными отрицательными весами. Штука полезная - но слишком "тяжеловесная" для данной задачи.
O(n)
|
23.05.2010, 21:04 | #5 |
Форумчанин
Регистрация: 04.05.2010
Сообщений: 495
|
Что это за задача? Гугл о ней не слышал. Можно ссылку?
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948 |
23.05.2010, 21:08 | #6 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Ну, условие у нее такое как в первом посте. А вот о том, насколько она классическая, вопрос спорный, наверное. В книгах по олимпиадам для школьников публиковалась.
O(n)
|
23.05.2010, 21:21 | #7 |
Форумчанин
Регистрация: 04.05.2010
Сообщений: 495
|
А решается в лоб?
Полный обход в глубину для всех входящих дверей? И последующий просмотр всех найденных путей, и выбрасывание - не удовлетворяющих условиям.
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948 |
23.05.2010, 21:24 | #8 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Нашли 1 путь (кратчайший). Пометили. Потом ищем следующий (не пересекающийся с первым. Помечаем. И так далее.
O(n)
|
23.05.2010, 21:44 | #9 |
Форумчанин
Регистрация: 04.05.2010
Сообщений: 495
|
Непонятно, почему 1 путь - кратчайший.
Твой алгоритм ( пост 3) находит первым не обязательно кратчайший путь.
Нажми на весы, поставь +
Для благодарностей : WebMoney WMR R252732729948 |
23.05.2010, 23:58 | #10 |
Пользователь
Регистрация: 23.07.2009
Сообщений: 66
|
Да. Про "кратчайший" я сдуру написал.
O(n)
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Даны цифры от 1 до 38 нужно составить все возможные комбинации из 6 чисел без повторений. | gector | Фриланс | 14 | 01.04.2013 20:20 |
поиск кратчайшего пути проходящий через ВСЕ города C++ | vo_sa | Общие вопросы C/C++ | 2 | 02.06.2009 21:21 |
Все возможные слагаемые | anGeee | Паскаль, Turbo Pascal, PascalABC.NET | 4 | 04.12.2008 20:22 |
Delphi, рекурсия, как сделать все возможные N-ки чисел (сколько столбцов такая N-ка,в данном случае 3)? | domik | Помощь студентам | 5 | 26.09.2007 16:43 |