Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.10.2010, 09:03
Новичок

Отправить личное сообщение для straus_kris_28 Посмотреть профиль Найти все сообщения от straus_kris_28
 
Регистрация: 18.10.2010
Сообщений: 6

Помогите, пожалуйста, с выбором алгоритма.
Есть граф G=<V,E>. Задана матрица весов ребер A. Задано некоторое множество вершин S in V графа G. Необходимо седать минимальный обход всех вершин множества S (не всех вершин графа G, а только заданных в множестве S). Веса неотрицательны.

Граф G содержит очень большое количество вершин и ребер.Алгоритм требователен ко времени выполнения.

благодарю за помощь
  #2  
Старый 18.10.2010, 09:32
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Заголовок темы должне быть осмысленным.
  #3  
Старый 18.10.2010, 09:45
гость

 
Сообщений: n/a

Сообщение от straus_kris_28 Посмотреть сообщение
Необходимо седать минимальный обход всех вершин множества S (не всех вершин графа G, а только заданных в множестве S).
Гамильтонов путь то есть найти? NP сложно.
  #4  
Старый 18.10.2010, 10:09
Новичок

Отправить личное сообщение для straus_kris_28 Посмотреть профиль Найти все сообщения от straus_kris_28
 
Регистрация: 18.10.2010
Сообщений: 6

Не совсем. Необходимо обойти все вершины множества S, но при этом возможен проход через вершину, не принадлежащую множеству S.
  #5  
Старый 18.10.2010, 10:17
гость

 
Сообщений: n/a

Сообщение от straus_kris_28 Посмотреть сообщение
Не совсем. Необходимо обойти все вершины множества S, но при этом возможен проход через вершину, не принадлежащую множеству S.
а какая разница. Строишь граф G' = <S, E'>, E'=S^2, в котором веса ребер в E' - это длины кратчайших путей в твоем исходном графе G. Очевидно что то, что ты ищешь - это просто гамильтоновый путь в нем. Потому если |S| большое, задача не решается.
  #6  
Старый 18.10.2010, 11:37
Новичок

Отправить личное сообщение для straus_kris_28 Посмотреть профиль Найти все сообщения от straus_kris_28
 
Регистрация: 18.10.2010
Сообщений: 6

спасибо огромное!
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сортировка выбором двумерного массива в C# Amel Сортировка и поиск 0 15.03.2010 20:19
Помогите пожалуйста найти ошибку в реализации классического генетического алгоритма. гость Искусственный интеллект, нейронные сети 1 26.02.2010 03:48
Помогите с расшифровкой неведанного мне алгоритма what? Математические алгоритмы 1 30.08.2009 12:52
Помогите анализировать алгоритма Олим Математические алгоритмы 4 20.04.2009 17:38
сортировка выбором!!!! помогите!!! Lusinka Сортировка и поиск 1 17.02.2009 06:43