mayor
Новичок
|
    
поиск путей на графе
дан ориентированый граф из 2-50 вершин, где каждому существующему ребру соотвествует рейтинг +-R, ребер соединающих вершину саму с собой не существует, нужно за кратное K число переходов, но не большее чем К*МAX, проити из вершины 0 в вершину 1, так чтобы сумма рейтингов переходов была максимальной и выдать полученный рейтинг
если невозможно за кратное К и меньше К*МАX число переходов, пройти из 0 вершины в 1, выдать ответ невозможно
каким алгоритмом можено это решать?
зы ограничение по k*max 10**9, по времени выполнения 1 секунда
(Сообщение отредактировал mayor 29 авг. 2009 17:16)
|
Всего сообщений: 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 уровень
|
Всего сообщений: 3 | Присоединился: август 2009 | Отправлено: 5 сен. 2009 6:49 | IP
|
|
|
Форум
поиск путей на графе
