Форум программистов, компьютерный форум CyberForum.ru

Графы. Нужно составить алгоритм - C++

Восстановить пароль Регистрация
 
Gennadiusisus
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 8
22.09.2013, 07:50     Графы. Нужно составить алгоритм #1
Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.
Заранее спасибо =)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
22.09.2013, 10:17     Графы. Нужно составить алгоритм #2
Цитата Сообщение от Gennadiusisus Посмотреть сообщение
Помогите алгоритмизировать задачу! Нужно написать программу способную определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.
Заранее спасибо =)
Попробуйте использовать алгоритм поиска в ширину, сначала из вершины А, а потом из вершины С. Если алгоритм находит путь из вершины А в вершину С и из вершины С в вершину В, значит существует путь из А в В проходящий через С.
Gennadiusisus
0 / 0 / 0
Регистрация: 26.12.2012
Сообщений: 8
23.09.2013, 16:13  [ТС]     Графы. Нужно составить алгоритм #3
Цитата Сообщение от D3fend0r Посмотреть сообщение
Попробуйте использовать алгоритм поиска в ширину, сначала из вершины А, а потом из вершины С. Если алгоритм находит путь из вершины А в вершину С и из вершины С в вершину В, значит существует путь из А в В проходящий через С.
Думал об этом, но этот алгоритм не может учесть то, что из "А" в "С" можно прийти разными путями и возможно пройдя по одному пути, мы не сможем прийти в "В"...не совсем универсально получается..=(
D3fend0r
17 / 17 / 1
Регистрация: 14.09.2013
Сообщений: 37
24.09.2013, 01:46     Графы. Нужно составить алгоритм #4
Цитата Сообщение от Gennadiusisus Посмотреть сообщение
Думал об этом, но этот алгоритм не может учесть то, что из "А" в "С" можно прийти разными путями и возможно пройдя по одному пути, мы не сможем прийти в "В"...не совсем универсально получается..=(
Да , не учел этого. Может быть тогда найти путь из А в С, пометить ребра через которые прошли и для этого пути проверить все возможные пути из С в В не проходящие через помеченные ребра. Если не найдем путь перейдем к следующему варианту пути из А в С и опять проверим если путь из С в В. Продолжаем пока не найдем путь удовлетворяющий условию или не проверим все варианты. Алгоритм по времени получается очень затратным, возможно можно ускорить его работу, скажем сохранять вершины или ребра которые не приведут к нужной вершине.
Yandex
Объявления
24.09.2013, 01:46     Графы. Нужно составить алгоритм
Ответ Создать тему
Опции темы

Текущее время: 09:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru