Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
Архив форумов ЦИТФорума
Море(!) вопросов - Море(!) ответов
 
 FAQFAQ   ПоискПоиск   ПользователиПользователи   ГруппыГруппы   РегистрацияРегистрация 
 ПрофильПрофиль   Войти и проверить личные сообщенияВойти и проверить личные сообщения   ВходВход 
Как правильно задавать вопросы

Граф, как найти все неповторяющиеся маршруты

 
Перейти:  
Этот форум закрыт, вы не можете писать новые сообщения и редактировать старые.   Эта тема закрыта, вы не можете писать ответы и редактировать сообщения.    Список форумов Архив форумов ЦИТФорума -> Математика
Предыдущая тема :: Следующая тема  
Автор Сообщение
GY-GY



Зарегистрирован: 06.07.2007
Сообщения: 2

СообщениеДобавлено: Пт Июл 06 2007 15:41    Заголовок сообщения: Граф, как найти все неповторяющиеся маршруты Ответить с цитатой

Имеетя некий граф. Надо найти все возможные маршруты для попадания из одной произвольной вершины в другую, исключая закольцованные участки.
с алгоритмами нахождения кратчайшего пути(Дейкстры) - знаком, но мне нужны все варианты, исключая те, где одну вершину посешаем более 1 раза. Может есть решение и не надо изобретать велосипед?
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
slop



Зарегистрирован: 30.08.2007
Сообщения: 1

СообщениеДобавлено: Чт Авг 30 2007 12:36    Заголовок сообщения: Ответить с цитатой

Рекурсию сделать, где на каждом шаге делать ветвление по всем связям текущей вершины исключая уже посещенные вершины. Когда попадаем в результирующую вершину, то прерываем данную ветвь и добавляем трассу в результат. Только при большой размерности проблемы могут быть с реализацие самой рекурсии.

Posted with ForumPilot v1.1
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
GY-GY



Зарегистрирован: 06.07.2007
Сообщения: 2

СообщениеДобавлено: Ср Сен 05 2007 12:13    Заголовок сообщения: Ответить с цитатой

Цитата:
и добавляем трассу в результат

вот здесь-то и есть самое интересное. если решать тупо в лоб, то массив для для хранения промежуточных кусков трасс получается весьма внушительным.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Odomontois



Зарегистрирован: 30.10.2008
Сообщения: 5

СообщениеДобавлено: Чт Окт 30 2008 11:54    Заголовок сообщения: Ответить с цитатой

Вам нужны сами маршруты или их количество?
Хотя погодите,,, если рекурсивно - это поиск в глубину, вам не нужно никаких массивов - только одну единственную рассматриваемую трассу, если вам нужно их генерировать.
А если нужно не только генерировать, но и хранить, то меньшими объёмами не обойтись.
Вернуться к началу
Посмотреть профиль Отправить личное сообщение
Показать сообщения:   
Этот форум закрыт, вы не можете писать новые сообщения и редактировать старые.   Эта тема закрыта, вы не можете писать ответы и редактировать сообщения.    Список форумов Архив форумов ЦИТФорума -> Математика Часовой пояс: GMT + 3
Страница 1 из 1

 
Перейти:  
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах


Powered by phpBB © 2001, 2002 phpBB Group
Русская поддержка phpBB

 

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 6608306, ICQ 232284597
Пресс-релизы — pr@citforum.ru
Послать комментарий
Информация для авторов
This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2006 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...