Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/17: Рейтинг темы: голосов - 17, средняя оценка - 4.76
mayor
0 / 0 / 0
Регистрация: 29.08.2009
Сообщений: 3
1

поиск путей на графе

29.08.2009, 13:55. Просмотров 3125. Ответов 11
Метки нет (Все метки)

поиск путей на графе

дан ориентированый граф из 2-50 вершин, где каждому существующему ребру соотвествует рейтинг +-R, ребер соединающих вершину саму с собой не существует, нужно за кратное K число переходов, но не большее чем К*МAX, проити из вершины 0 в вершину 1, так чтобы сумма рейтингов переходов была максимальной и выдать полученный рейтинг

если невозможно за кратное К и меньше К*МАX число переходов, пройти из 0 вершины в 1, выдать ответ невозможно

каким алгоритмом можено это решать?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2009, 13:55
Ответы с готовыми решениями:

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых...

Поиск нескольких кратчайших путей в графе
Добрый день всем! Такая казалось бы тривиальная задача для гуру программистов,...

Поиск всех путей в графе, сумма значений которых меньше установленного числа
Здравствуйте. Есть граф, в вершинах которого числовые значения. Нужно найти...

Экономное представление путей в графе
Есть приведенное бинарное дерево (изоморфные подграфы сливаются, в узла может...

Поиск в ширину в графе
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и...

11
odip
Эксперт С++
7164 / 3222 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
29.08.2009, 16:11 2
О! Клевая задача!
Обычным алгоритмом - перебор всех путей в глубину и ширину с возвратами.
Есть конечно ряд отличий.
1) Нужно считать сумму рейтингов для строящегося пути.
Считать можно сумму при шаге вперед.
2) Учитывать следует только те пути, где число переходов кратно K.
3) При попытке построить переход с номером (K*MAX+1) следует делать шаг назад.
4) Искать следует не путь максимальной длины, а каждый путь максимального рейтинга - то есть учитывать и пути не самые длинные.

Учитывая задачу можно взять 50 как заданную переменную.
И так же начальную и конечную вершины брать любые, а не 0 и 1.
0
_mayor
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
29.08.2009, 17:06 3
Цитата Сообщение от odip Посмотреть сообщение
О! Клевая задача!
Обычным алгоритмом - перебор всех путей в глубину и ширину с возвратами.
Есть конечно ряд отличий.
1) Нужно считать сумму рейтингов для строящегося пути.
Считать можно сумму при шаге вперед.
2) Учитывать следует только те пути, где число переходов кратно K.
3) При попытке построить переход с номером (K*MAX+1) следует делать шаг назад.
4) Искать следует не путь максимальной длины, а каждый путь максимального рейтинга - то есть учитывать и пути не самые длинные.

Учитывая задачу можно взять 50 как заданную переменную.
И так же начальную и конечную вершины брать любые, а не 0 и 1.
на графе с 2к ребер
поиск в глубину сдохнет не вернувшись к корню
поиск в ширину не обойдет и 8 вершин

хм, похоже я что-то упустил в условии:

пусть k*max будет ограничено 10**9
время выполнения ограничено 1 сек

еще варианты алгоритмов?
0
odip
Эксперт С++
7164 / 3222 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
29.08.2009, 17:14 4
Какой 10**9 ? У тебя же всего 50 вершин !
При построении пути одна и та же вершина может посещаться один раз или многократно ?
0
_mayor
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
29.08.2009, 18:01 5
Цитата Сообщение от odip Посмотреть сообщение
Какой 10**9 ? У тебя же всего 50 вершин !
При построении пути одна и та же вершина может посещаться один раз или многократно ?
еще раз все по порядку:

- 50 вершин при условии, что любая из вершин не связана ребром сама с собой, могут образовывать до 2401 ребра включительно

- в условии нигде не сказано, что граф является деревом - поэтому в графе по умолчанию полно циклов

- каждая вершина может посещатся сколько угодно раз, лиш бы число переходов по окончанию алгоритма было кратно К и не больше К*MAX

- 10**9 это примерно 32 битный инт который передается фукнции поиска

тут походу потребуется какой-то навороченный алгоритм дейкстры с поддрежкой отрицательных ребер
0
odip
Эксперт С++
7164 / 3222 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
29.08.2009, 18:18 6
- в условии нигде не сказано, что граф является деревом - поэтому в графе по умолчанию полно циклов
Это понятно.
- каждая вершина может посещатся сколько угодно раз
А вот это надо было сразу говорить !

Добавлено через 6 минут
Я думаю так - максимальный рейтинг можно достичь если найти цикл, где путь по циклу дает максимальное число +R. Далее по этому циклу промотать столько ходов, сколько позволяет K*MAX.
При этом еще нужно чтобы этот цикл лежат на пути от вершины 0 до вершины 1.
Если K*MAX<=50, то можно не мучиться и сделать обычный перебор в глубину и ширину.
0
XuTPbIu_MuHTAu
Эксперт С++
2237 / 752 / 25
Регистрация: 27.05.2008
Сообщений: 1,498
31.08.2009, 14:38 7
Алгоритм дейкстры
0
_mayor
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
31.08.2009, 16:36 8
Цитата Сообщение от XuTPbIu_MuHTAu Посмотреть сообщение
этот не поможет, нужен какой-то навороченнее
0
Monte-Cristo
2796 / 1385 / 107
Регистрация: 07.03.2009
Сообщений: 4,446
31.08.2009, 16:56 9
_mayor, это алгоритм. Сама идея. Немного его видоизменить (изменить условия) и получится твой вариант.
0
_mayor
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
31.08.2009, 18:39 10
Цитата Сообщение от Monte-Cristo Посмотреть сообщение
_mayor, это алгоритм. Сама идея. Немного его видоизменить (изменить условия) и получится твой вариант.
условия пусть остаются иначе это будет другая задача

ссылку на алгоритм дейкстры я и сам знаю, проблемма в том, как ее изменять и ваще ее ли изменять?
0
odip
Эксперт С++
7164 / 3222 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
31.08.2009, 21:31 11
Там есть ссылка на алгоритм Дейкстры, модифицированный для отрицательных весов.
0
_mayor
1 / 1 / 1
Регистрация: 29.08.2009
Сообщений: 63
01.09.2009, 16:15 12
Цитата Сообщение от odip Посмотреть сообщение
Там есть ссылка на алгоритм Дейкстры, модифицированный для отрицательных весов.
похоже статью значитально переписали, с моего последнего посещения

допустим если разбить задачу на 3 состовляющих:

1 нахождение кратного пути

2 нахождение минимального кратного пути, когда нету походящих положительных циклов

3 нахождение максимального цикла, а так же входа выхода в него - на условии сохранения кратности пути

2 имхо подойдет дейкстра с потенциалами

только как можно прикрутить кратность к поиску?

Добавлено через 4 минуты
почему-то у меня возникло чувство, что Алгоритм Флойда — Уоршелла больше к этой задаче подойдет ...
0
01.09.2009, 16:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.09.2009, 16:15

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя...

Поиск критических элементов в графе
Критической вершиной в графе называется вершина, удаление которой приводит к...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru