Комментарии 76
Это очень круто. К сожалению графы и поиски оптимального [чего-либо] это слабое место многих программистов, а ведь это основа основ.
Да, помню контесты по 5 часов…
Жаль сейчас в другой сфере.
Жаль сейчас в другой сфере.
>Под катом очень-очень много текста
Ну зачем же так людей пугать? :)
Ну зачем же так людей пугать? :)
НЛО прилетело и опубликовало эту надпись здесь
Транспортные задачи не только один из моих курсовиков, но и диплом — через неделю защищать.
По сабжу — реально много текста, не стал читать. Но на графах не представлял эту задачу, только табличный метод. Хотя согласен, многие из них на графе проще решать.
По сабжу — реально много текста, не стал читать. Но на графах не представлял эту задачу, только табличный метод. Хотя согласен, многие из них на графе проще решать.
Курсач? Диплом? У меня транспортная задача (равно как и все алгоритмы поиска по графам, задача комивояжера, симплекс-метод) были простыми лабами на 1-2 пары. Что там писать на курсач или диплом? Реализация от силы 300-400 строк занимает.
Кстати, думаю большинство кому нужно знают, но для меня когда-то очень полезным открытием оказалась книга Роберта Седжвика — Фундаментальные алгоритмы на С++, а конкретно в данном случае ее пятая часть посвященная графам.
Может кому еще поможет в их изучении
Может кому еще поможет в их изучении
направленные/ненаправленные графы
вроде графы называются ориентированные/неориентированные?
вроде графы называются ориентированные/неориентированные?
А я вот веду разработку решения задачи о укладке плоского графа, если есть интерес, давайте кооперироваться.
на эту тему могу посоветовать статью Efficient Planarity Testing portal.acm.org/citation.cfm?id=321852 (если нет доступа, могу послать pdf), этот же алгоритм значительно подробнее описан в книге «Комбинаторные алгоритмы. Теория и практика» авторы Э. Рейнгольд, Ю. Нивергельт и Н. Део, издательство «МИР» 1980
Оо, спасибо! А то в университете этот предмет как-то не особо посещал, нужно совершенствоваться, спасибо!
Преподаю студентам дискретную математику, как вы получили такие классные иллюстрации? это какая-то обучающая программа или вы «ручками», спасибо
Очень просто MS Visio + «ручки»…
Уж очень хотелось сделать что-нибудь полезное. Потребовалась неделя!
А Вам огромное спасибо! за то что прочитали, очень рассчитываю что кто-нибудь из Ваших студентов заинтересуется ACM ICPC =)
Уж очень хотелось сделать что-нибудь полезное. Потребовалась неделя!
А Вам огромное спасибо! за то что прочитали, очень рассчитываю что кто-нибудь из Ваших студентов заинтересуется ACM ICPC =)
Когда-то для них написал несколько апплетов на Java, демонстрирующих разные алгоритмы на графах, вот здесь посмотрите (не пугайтесь это чешский :), но теперь понимаю КАК можно было все оформить :)
Региональный ACM у нас проводится, да не хватает чехам русской/советской школы )
Региональный ACM у нас проводится, да не хватает чехам русской/советской школы )
Чертовски много текста, но спасибо. Впреть буду знать где искать информацию по теме, а то в универе благополучно прогулял все лекции по Методам оптимизации… (чем, впрочем, отнють не горжусь).
И да, отличные иллюстрации с графами! Сразу видно, душу вложили…
И да, отличные иллюстрации с графами! Сразу видно, душу вложили…
Очень неплохо. Материал нескольких лекций, дом. заданий и одной из шести практик за семестр по основам информатики — в одной статье.
мы в универе проходили форда-фалкерсона (предмет «Сети ЭВМ...»)… ох как я его люто бешено ненавидел, но когда разобрался и понял — стал боготворить. текста не на самом деле не много, кода больше :)
Большой плюс за великолепное оформление!
Просто образцовый пост!
Просто образцовый пост!
Я заставлю себя это прочитать и понять! :)
Попробуйте лучше симплекс-метод — более универсальный алгоритм и подходит не только для транспортной задачи. У меня лет 8 назад был заказ — оптимизировать производство мороженого: смысл в том что в готовом мороженом должно содержаться определенное кол-во различных веществ таких, как сухой молочный остаток, жир, влага и сахар и еще кажись что то. И есть набор сырья, содержащий эти вещества в разных пропорциях, а так же имеющиеся на складе в разных кол-вах и имеющих разную себестоимость. Например, можно положить сгущенку, немного воды и немного масла, а можно сухое молоко, сахар, воды и много масла. Так вот при помощи симплекс метода — задача была решена. Каждый день выдавалась оптимальная рецептура, да и выдается до сих пор
НЛО прилетело и опубликовало эту надпись здесь
Неправильно тебе известно — симплекс метод тоже можно отнести к дискретной математике (хотя предмет назывался «Начало анализа») — а она большинство задач решает перебором (примеры в топике это доказывают). Смысл различных методов решения различных задач в дискретной математике достичь решения за как можно меньшее кол-во переборов
НЛО прилетело и опубликовало эту надпись здесь
Насколько я помню, симплекс-метод больше заточен под поиск екстремума линейных(квадратичный — нелинейных) функций от многих переменных при ограничениях на фазовое пространство. ИМХО, теория графов служит немного другим целям. Хотя все, естественно, зависит от формализации поставленной задачи.
У Вас странное представление о теории сложности, Вы путаетесь в терминологии.
Вкратце, симплекс-метод (в среднем) работает за полиномиальное время, так же и память. Есть, впрочем, другие методы линейной оптимизации, которые работают строго за полиномиальное время, но они сильно сложнее в понимании/реализации.
Вкратце, симплекс-метод (в среднем) работает за полиномиальное время, так же и память. Есть, впрочем, другие методы линейной оптимизации, которые работают строго за полиномиальное время, но они сильно сложнее в понимании/реализации.
Насколько я понял условие задачи. Я бы счел ее «Задачей о назначениях» и решал бы ее «Венгерским алгоритмом». Вы натолкнули меня на мысль! Попробую описать Венгерку в картинках в след. статье! Спасибо! =)
Кстати, было бы просто здорово! Так и не сумел разобраться в настолько, чтобы писать ее просто и по памяти, надеюсь, с вашим прекрасным изложением это удастся.=) Между прочим, а не подскажете ли литературу, в которой можно поразбирать задачу о назначениях и примеры порешать, для experience?
Ну, венгерский алгоритм основан на симплекс-методе, потому и часто (на практике) так же и интерпретируется.
А вы, кстати, никогда не пробовали решения подобных задач доверить генетическим алгоритмам?
А вы, кстати, никогда не пробовали решения подобных задач доверить генетическим алгоритмам?
У вас недостаточно заряда для голосования
У вас недостаточно заряда для голосования — у меня то же самое. А ты бы проголосовал за.
У нас на первом курсе в качестве курсового проекта была примерно такая же задача :)
Просто великолепная статья, как и в плане описания, так и в плане оформления, можно смело копи+паст и сдавать )
Просто великолепная статья, как и в плане описания, так и в плане оформления, можно смело копи+паст и сдавать )
Хорошая статья спасибо!
Получится значительно меньше кода, если не искать сначала максимальный поток, и потом понижать его стоимость, а каждый раз искать наиболее легкий путь в остаточной сети. Этот способ поддерживает инвариант, что на каждом шаге текущий поток самый дешевый из потоков такой же величины.
Вот еще несколько наблюдений:
видимо, у вас перепутаны комментарии в коде около функций bf() и bfs();
похоже, что ваш код неправильно работает в орграфах со встречными дугами;
вы N увеличили вначале, чтобы не писать "<="?.. очень странный ход, лучше перейти к 0-индексации.
Вот еще несколько наблюдений:
видимо, у вас перепутаны комментарии в коде около функций bf() и bfs();
похоже, что ваш код неправильно работает в орграфах со встречными дугами;
вы N увеличили вначале, чтобы не писать "<="?.. очень странный ход, лучше перейти к 0-индексации.
Добавил в избранное. Ибо пары по теме прогулял но информация очень интересна, а времени сейчас нет т.к. диплом на носу.
Возможно напишу что-то ужасное, но когда у нас был целый семестр дискретной оптимизации, мы решали и эту и еще ряд других задач на графах, используя модифицированную структуру вирта.
Поищите в сети, дядя Вирт ее специально для графовых задач придумал. Только изначально она была у него так себе, а потом ее модифицировали.
Точно не помню, как она описывалась, но, по-моему, там был список всех вершин, и в каждой ячейке списка хранился список смежных для текущей вершин. Обходы по этому списку, создание матриц и алгоритмы писались на ура. Главное было в самом начале грамотно спроектировать классы, которые описывали бы структуру вирта.
Поищите в сети, дядя Вирт ее специально для графовых задач придумал. Только изначально она была у него так себе, а потом ее модифицировали.
Точно не помню, как она описывалась, но, по-моему, там был список всех вершин, и в каждой ячейке списка хранился список смежных для текущей вершин. Обходы по этому списку, создание матриц и алгоритмы писались на ура. Главное было в самом начале грамотно спроектировать классы, которые описывали бы структуру вирта.
По вашему описанию, это просто списки смежности.
Вот, нашел, чуть вниз промотайте и увидите структуру Вирта. Там над ней как раз граф нарисован из 5-ти врешин, который она представляет: Модифицированные структуры Вирта
Хех, вспомнил прошлую сессию — как раз экзамен по сетевой экономике :)
Хм… После трех лет занятия олимпиадами могу написать Форда-Фалкерсона за двадцать минут, даже если разбудят посреди ночи пистолетным выстрелом.
П.С. Извините за занудство, но Форд-Фалкерсон — это не алгоритм, а метод. А вот Беллман-Форд уже его реализация в виде алгоритма.
П.С. Извините за занудство, но Форд-Фалкерсон — это не алгоритм, а метод. А вот Беллман-Форд уже его реализация в виде алгоритма.
Не совсем понятно, к чему вы это… Много людей умеют реализовывать метод Форда-Фалкерсона. Это вовсе не означает, что его не нужно никому объяснять.
Вообще, в статье действительно как-то многовато слова «алгоритм», но все же автор указал, что показывает реализацию Эдмондса-Карпа. А вот с Беллманом-Фордом, наверное, очепятались — это вообще несколько другое.
Вообще, в статье действительно как-то многовато слова «алгоритм», но все же автор указал, что показывает реализацию Эдмондса-Карпа. А вот с Беллманом-Фордом, наверное, очепятались — это вообще несколько другое.
Где ж вы раньше были, а то я вспоминал ТИЛС из универа, когда карту дорог строил, ох и намучался :)
Можно небольшое разъяснение?
«Алгоритм поиска в ширину (breadth first search), BFS»
на первом рисунке на последнем шаге мы смотрим из 4й вершины на 7ю и 8ю, и там даже два квадратика «в конце итерации» 7 и 8. Так почему на втором рисунке восьмёрка красная? Мы же не можем в восьмерку попасть из семерки или шестерки, мы там были уже после четверки…
а в остальном вроде всё доступно написано, спасибо за статью!
«Алгоритм поиска в ширину (breadth first search), BFS»
на первом рисунке на последнем шаге мы смотрим из 4й вершины на 7ю и 8ю, и там даже два квадратика «в конце итерации» 7 и 8. Так почему на втором рисунке восьмёрка красная? Мы же не можем в восьмерку попасть из семерки или шестерки, мы там были уже после четверки…
а в остальном вроде всё доступно написано, спасибо за статью!
вот на транспортную задачу я убила весь прошлый день и ночь. захожу с утра (наконец-то выспавшись) на хабр — и тут опять это! >_<
а по теме — отличная статья!
а по теме — отличная статья!
Было бы интересно увидеть статьи про симплекс-метод и венгерский алгоритм. И, наверно, напрасно вы используете матрицы смежности — они не сильно нагляднее, но чаще медленнее (на разреженных графах).
Вот побольше бы таких статей, может в конце концов и прав будет Дон Тэпскотт насчет того, что университеты в том виде, что они сейчас — отомрут.
уф… аж ностальгия по институтским временам! «Задача коммивояжера» Спасибо огромное!
Отлично, спасибо
хорошая, годная статья.
Под катом увидел немного не то, что ожидал. Дело в том, что в классическом понимании «транспортная задача» линейного программирования решается составлением матрицы перевозок, а не через графы.
А вот это 5 баллов. Это вам не описание транспортной задачи в два клика в Excel )
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Максимальный поток минимальной стоимости