Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 02.11.2010, 22:48
Новичок

Отправить личное сообщение для AndreyA Посмотреть профиль Найти все сообщения от AndreyA
 
Регистрация: 02.11.2010
Сообщений: 5

Поиск алгоритма
Наверно вопрос в эту тему. Если не в эту, то прошу прощения я новичок.
Так вот задача кажется простой, но не могу найти существующий алгоритм. НАПРИМЕР я проектирую транспортную сеть (граф) в которой имеется несколько входов (1...N) и выходы (N), транзитные узлы (N), конфигурация сети может быть какая угодна (тупиковая, кольцевая, смешанная), количество дуг и узлов не ограничено. Имеются числовые данные характеризующие объем выхода (к примеру количество машин, которое должно выйти из этого узла), заданы длины всех дуг. Моя задача определить какое количество машин мне нужно запустить во входы (т.е. определить в какой вход и сколько), чтобы из заданных выходов вышло заданное число машин. Граф изначально не ориентирован следовательно его надо ориентировать и определить пропускную способность каждой дуги так, чтобы обеспечить заданный выход в заданных узлах.
Если у кого есть какие мысли по поводу решения такой задачи помогите пожалуйста.
Все алгоритмы которые я встречал предполагают либо изначально ориентированный граф, либо каждой дуге назначена пропускная способность!
  #2  
Старый 03.11.2010, 02:57
гость

 
Сообщений: n/a

Я не вижу никакой разницы между тем что вы описали (по модулю замечаний ниже) и обычной транспортной задаче.

Цитата:
Граф изначально не ориентирован
следовательно его надо ориентировать
дублируешь каждое ребро в обе стороны и гонишь поток. он сам без тебя сориентируется. (нет смысла гнать поток по одной трубе в обе стороны - одна сторона же там просто вычтется)

Цитата:
и определить пропускную способность каждой дуги так, чтобы обеспечить заданный выход в заданных узлах.
А вы не перепутали понятие "величина потока" и "пропускная способность"? По моему вы тут хотите определить величину потока - ее определяет алгоритм для решения транспортной задачи. А пропускные способности, раз вы их не знаете, и никаких ограничений не накладываете, стало быть у вас бесконечные.
  #3  
Старый 03.11.2010, 10:02
Новичок

Отправить личное сообщение для AndreyA Посмотреть профиль Найти все сообщения от AndreyA
 
Регистрация: 02.11.2010
Сообщений: 5

на пропускные способности есть ограничения мин и макс. Наверно все таки не перепутал. Мне надо доставить заданное число автомобилей в заданные узлы каждый узел может принять свое количество авто. Выпускать авто я могу из разных узлов (которые я задаю) и здесь то же есть ограничение задано максимально возможное число авто которые могут выйти из узла. Ширина дороги мне неизвестна (только мин и макс) и моя задача определить ширину дороги и направления движения.
  #4  
Старый 03.11.2010, 10:04
Новичок

Отправить личное сообщение для AndreyA Посмотреть профиль Найти все сообщения от AndreyA
 
Регистрация: 02.11.2010
Сообщений: 5

ну и соответственно надо подобрать величину потока.
Я так понимаю надо одновременно определять эти два параметра, чтобы выполнить все заданные ограничения
  #5  
Старый 03.11.2010, 10:54
гость

 
Сообщений: n/a

Ну что значит "мин"? В этом же нет никакого физического смысла. Зачем вам требовать чтобы на какой-то дороге было всегда скажем 10
машин/секунду?

Транспортную задачу конечно вы можете модифицировать и решать с учетом ограничений "мин" в том смысле, чтобы потребовать, чтобы поток не был меньше "мин". Только результат вам не понравится. Это не поток будет, а циркуляция. Т.е. алгоритм можно намеренно создавать циклы в графе, чтобы "накрутить" величины потока в ребрках, а вовсе не гнать поток из истока в сток.

Может вы хотите на самом деле найти поток, а потом положить, как вы говорите, "ширину дороги" равную max(величина потока, "ограничение мин" на дороге)?

А ваше ограничение "макс" собственно и есть пропускная способность по определению.
  #6  
Старый 03.11.2010, 11:00
гость

 
Сообщений: n/a

Цитата:
заданные узлы каждый узел может принять свое количество авто.
Т.е помимо ограничений на ребрах, есть еще дополнительные ограничения на вершинах? Т.е. не больше к примеру X машин/сек через каждую вершину?

Не совсем стандартная постановка, но решается тоже элементарно. Делим каждую вершину на две. "вход" и "выход", соединяешь "вход" однонаправленным ребром с "выход" нужной тебе пропускной способности и все. От пропускных ограничений на вершинах ты избавился.
  #7  
Старый 03.11.2010, 11:06
Новичок

Отправить личное сообщение для AndreyA Посмотреть профиль Найти все сообщения от AndreyA
 
Регистрация: 02.11.2010
Сообщений: 5

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

Последний раз редактировалось AndreyA, 03.11.2010 в 11:49.
  #8  
Старый 03.11.2010, 12:00
гость

 
Сообщений: n/a

Хорошо. Итак, вы хотите найти циркуляцию минимальной стоимости в неориентированном графе с нижними (и верхними, но это не так важно) ограничениями на пропускные способности ребер, так?

Не могу сходу сказать как это решается. То что есть и нижние ограничения и граф неориентированный сильно все усложняет. Возможно исследовательская задача. По английски это будет min-cost circulation in undirected graphs with lower bounds. Попробуйте что-то в этом духе погуглить.
  #9  
Старый 03.11.2010, 12:07
гость

 
Сообщений: n/a

Вот тут http://books.google.com/books?id=kMC...Blower&f=false пишут NP-полная, тут - http://www.sciencedirect.com/science...searc htype=a - что есть полиномиальный алгоритм.... х/з... надо доставать оригинальные статьи и разбираться.
  #10  
Старый 03.11.2010, 12:50
Новичок

Отправить личное сообщение для AndreyA Посмотреть профиль Найти все сообщения от AndreyA
 
Регистрация: 02.11.2010
Сообщений: 5

спасибо посмотрю.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализация алгоритма Ху (Hu) RARIA Графы 2 25.12.2009 00:47
алгоритма Грэхема ciaonataha Вычислительная геометрия 1 06.07.2009 22:19
поиск алгоритма RUmkO Реализация, исходники, языки 8 05.03.2009 18:33
Поиск эффективного алгоритма вращения Vacuum Обработка изображений, звук, графика 1 15.10.2008 06:44
поиск алгоритма оп распознаванию изображения, мктод мозайки antoshka1303 Математические алгоритмы (другое) 0 21.04.2008 02:20