Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Информационные технологии
        поиск путей на графе
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Информационные технологии" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: paradise, KMA
  

mayor


Новичок

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

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

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

каким алгоритмом можено это решать?

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


(Сообщение отредактировал mayor 29 авг. 2009 17:16)

-----
na

Всего сообщений: 3 | Присоединился: август 2009 | Отправлено: 29 авг. 2009 16:49 | IP
Grumzik


Новичок

Не знаю точно,но вроде рекурсивно можно найти все пути 0->1,
состоящие из k шагов. Например если есть ребро
0->i, то  f(0,1,k) будет искаться через  f(i,1,k-1).
И на последнем шаге и будет видна возможность пройти
именно за k шагов. Одновременно надо считать и сумму рейтингов.

Всего сообщений: 1 | Присоединился: сентябрь 2009 | Отправлено: 1 сен. 2009 21:25 | IP
mayor


Новичок


Цитата: Grumzik написал 1 сен. 2009 21:25
Не знаю точно,но вроде рекурсивно можно найти все пути 0->1,
состоящие из k шагов. Например если есть ребро
0->i, то  f(0,1,k) будет искаться через  f(i,1,k-1).
И на последнем шаге и будет видна возможность пройти
именно за k шагов. Одновременно надо считать и сумму рейтингов.


все пути это 49**49 степени, данный метод если использовать поиск в ширину сдохнет на 8 уровне, поиск в глубину не вернется на 40 уровень

-----
na

Всего сообщений: 3 | Присоединился: август 2009 | Отправлено: 5 сен. 2009 6:49 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com