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

@mayor · Регистрация: 29.08.2009

Студворк — интернет-сервис помощи студентам

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

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

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

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

@odip · 29.08.2009, 16:11

О! Клевая задача!
Обычным алгоритмом - перебор всех путей в глубину и ширину с возвратами.
Есть конечно ряд отличий.
1) Нужно считать сумму рейтингов для строящегося пути.
Считать можно сумму при шаге вперед.
2) Учитывать следует только те пути, где число переходов кратно K.
3) При попытке построить переход с номером (K*MAX+1) следует делать шаг назад.
4) Искать следует не путь максимальной длины, а каждый путь максимального рейтинга - то есть учитывать и пути не самые длинные.

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

@_mayor · 29.08.2009, 17:06

Сообщение от odip

О! Клевая задача!
Обычным алгоритмом - перебор всех путей в глубину и ширину с возвратами.
Есть конечно ряд отличий.
1) Нужно считать сумму рейтингов для строящегося пути.
Считать можно сумму при шаге вперед.
2) Учитывать следует только те пути, где число переходов кратно K.
3) При попытке построить переход с номером (K*MAX+1) следует делать шаг назад.
4) Искать следует не путь максимальной длины, а каждый путь максимального рейтинга - то есть учитывать и пути не самые длинные.

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

на графе с 2к ребер
поиск в глубину сдохнет не вернувшись к корню
поиск в ширину не обойдет и 8 вершин

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

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

еще варианты алгоритмов?

@odip · 29.08.2009, 17:14

Какой 10**9 ? У тебя же всего 50 вершин !
При построении пути одна и та же вершина может посещаться один раз или многократно ?

@_mayor · 29.08.2009, 18:01

Сообщение от odip

Какой 10**9 ? У тебя же всего 50 вершин !
При построении пути одна и та же вершина может посещаться один раз или многократно ?

еще раз все по порядку:

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

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

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

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

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

@odip · 29.08.2009, 18:18

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

Это понятно.

- каждая вершина может посещатся сколько угодно раз

А вот это надо было сразу говорить !

Добавлено через 6 минут
Я думаю так - максимальный рейтинг можно достичь если найти цикл, где путь по циклу дает максимальное число +R. Далее по этому циклу промотать столько ходов, сколько позволяет K*MAX.
При этом еще нужно чтобы этот цикл лежат на пути от вершины 0 до вершины 1.
Если K*MAX<=50, то можно не мучиться и сделать обычный перебор в глубину и ширину.

@XuTPbIu_MuHTAu · 31.08.2009, 14:38

Алгоритм дейкстры

@_mayor · 31.08.2009, 16:36

Сообщение от XuTPbIu_MuHTAu

Алгоритм дейкстры

этот не поможет, нужен какой-то навороченнее

@Monte-Cristo · 31.08.2009, 16:56

_mayor, это алгоритм. Сама идея. Немного его видоизменить (изменить условия) и получится твой вариант.

@_mayor · 31.08.2009, 18:39

Сообщение от Monte-Cristo

_mayor, это алгоритм. Сама идея. Немного его видоизменить (изменить условия) и получится твой вариант.

условия пусть остаются

иначе это будет другая задача

ссылку на алгоритм дейкстры я и сам знаю, проблемма в том, как ее изменять и ваще ее ли изменять?

@odip · 31.08.2009, 21:31

Там есть ссылка на алгоритм Дейкстры, модифицированный для отрицательных весов.

@_mayor · 01.09.2009, 16:15

Сообщение от odip

Там есть ссылка на алгоритм Дейкстры, модифицированный для отрицательных весов.

похоже статью значитально переписали, с моего последнего посещения

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

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

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

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

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

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

Добавлено через 4 минуты
почему-то у меня возникло чувство, что Алгоритм Флойда — Уоршелла больше к этой задаче подойдет ...

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@mayor 0 / 0 / 0 Регистрация: 29.08.2009 Сообщений: 3

	поиск путей на графе 29.08.2009, 13:55. Показов 4345. Ответов 11 Метки нет (Все метки) поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру соотвествует рейтинг +-R, ребер соединающих вершину саму с собой не существует, нужно за кратное K число переходов, но не большее чем КМAX, проити из вершины 0 в вершину 1, так чтобы сумма рейтингов переходов была максимальной и выдать полученный рейтинг если невозможно за кратное К и меньше КМАX число переходов, пройти из 0 вершины в 1, выдать ответ невозможно каким алгоритмом можено это решать? 0

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

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	29.08.2009, 17:14
	Какой 10**9 ? У тебя же всего 50 вершин ! При построении пути одна и та же вершина может посещаться один раз или многократно ? 0

@XuTPbIu_MuHTAu 2256 / 771 / 25 Регистрация: 27.05.2008 Сообщений: 1,496
	31.08.2009, 14:38
	Алгоритм дейкстры 0

@Monte-Cristo 2816 / 1408 / 107 Регистрация: 07.03.2009 Сообщений: 4,446
	31.08.2009, 16:56
	_mayor, это алгоритм. Сама идея. Немного его видоизменить (изменить условия) и получится твой вариант. 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	31.08.2009, 21:31
	Там есть ссылка на алгоритм Дейкстры, модифицированный для отрицательных весов. 0