LINUX.ORG.RU
решено Форум — Development  

[Алгоритмы][Транспортная задача] Ошибка в алгоритме

 


0

0

Решаю классическую транспортную задачу методом Форда-Фалкерсона:
1. Находим путь в остаточном графе(остаточный граф - граф по которому еще не ходили на прошлых итерациях).
2. Делаем его увечивающимся
3. Делаем так пока существуют пути

В литературе указывается что этот метод гарантированно найдет максимальный возможный поток, однако на этой сети : http://s51.radikal.ru/i132/1005/f8/831c107cf1bc.png такого не происходит, точнее может происходить, однако это сильно зависит от условий выбора пути, чего по идее не должно быть, и в исходном алгоритме по выбор конкретного пути ничего не упоминаются.

На графе все ребра с единичным весом.

8 - исток, 9 - сток

Как срабатывает:
1. Путь 8-6-3-9
2. Путь 8-0-7-9
3. Путь 8-2-1-9

Все, доступных путей не осталось, хотя поток не максимальный!

Максимальный поток получится на следующих путях:
1. 8-6-3-9
2. 8-0-7-9
3. 8-2-5-9
4. 8-4-1-9

Хотя во всей литературе указывается что метод Форда-Фалекрсона гаранированно ищет максимальный поток, этого не происходит. Это я туплю, или ошибка в алгоритме?

★
← QtCreator - Не появляется терминал в консольном приложении
Шифрование и расшифрование файлов в ядре →
Ответ на: комментарий от anonymous

увеличивающим(то есть вносящим вклад в общий поток)

recon88 ★
() автор топика

Я бы нашёл доказательство утверждения того, что метод Форда-Фалекрсона гаранированно ищет максимальный поток, и разобрал бы его применительно к указанному примеру.

Legioner ★★★★★
()

Это ты тупишь)

1) Транспортная задача и задача о максимальном потоке - не одно и тоже. Форд-Фалкерсон решает задачу о максимальном потоке.

Как срабатывает:
1. Путь 8-6-3-9
2. Путь 8-0-7-9
3. Путь 8-2-1-9

Есть еще 4ый путь: 8-4-1-2-5-9

white_pony
()
Ответ на: комментарий от white_pony

Да, ошибся на счет названия задачи : максимальный поток в транспортной сети.

Как вы получили дополнительный путь я не пойму : Ребро 2-1 не находится в остаточной сети(посколько мы за счет него уже увеличили поток), и в методе Форда-Фалекрсона оно не будет учитываться.

recon88 ★
() автор топика
Ответ на: комментарий от white_pony

если что, все ребра имеют единичный вес

recon88 ★
() автор топика
Ответ на: комментарий от Legioner

прочитал, доказательство основывается на утверждении наличия увеличивающего пути, а в данном графе его не остается из-за неправильного выбора первых трех путей. Нигде ничего не сказанно о порядке выбора путей - говорится что выбирается произвольный путь, вобще не пойму в чем дело.

recon88 ★
() автор топика
Ответ на: комментарий от recon88

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC...

В твоем случае, если добавляешь некий путь к потоку, то все ребра из этого пути условно говоря «разворачиваются». Так в 4ом пути появляется ребро 1-2.

Читай внимательно алгоритм.

white_pony
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← QtCreator - Не появляется терминал в консольном приложении
Development
Шифрование и расшифрование файлов в ядре →