Всем доброго времени суток.

Описываю вопрос.

Пусть декартовыми координатами задано множество вершин V. Для каждой пары вершин (v1, v2) из V определно некоторое число
p(v1,v2) — поток от v1 к v2.
Если очень сложно, то p(v1,v2) можно считать равным p(v2,v1). Необходимо построить следующие связи между этими вершинам (читай — граф), где стоимость связи пропорциноальна её длине и её пропускной способности, так, чтобы удовлетворить все потоки с минимальной суммарной суммой стоимостью связей.

Короче — упрощённое проектирование топологии сети, НО по-моему и здесь точного решения за нефакториальное время нет. Пока есть идеи тока танцевать от полного графа алгоритмом Примы или Краскала (Крускала, кого как учили . Но и там куча неясностей. Буду рад любым советам, ссылкам на материалы, и, самое главное, алгоритмам

Заранее спасибо.

Пояснения.
1) Считается, что "поток удовлетворён" если из вершины v1 в вершину v2 можно указать такой путь, где минимальная пропускная способность по всем связям больше или равна p(v1,v2). ИЛИ(!это сложнее, наверное, так что пока отложим!), Что если все вершины генерят заданные потоки, то наша сеть с этим справляется.

2) Для упрощения связи тоже (как и потоки от вершин p(v1,v2)=p(v2,v1) )можно считать двусторонними — то есть пропускная способность в одну сторону равна пропускной способности в другую сторону.

3) Стоимость связи (допустим) вычисляется по ф-ле $$$=k1*length + k2*width; Где length — длина связи, width — её пропускная способность. Коэффициенты считаем данными.

Здравствуйте, Rulikkk, Вы писали:

R>Всем доброго времени суток.

R>Описываю вопрос.

R>Пусть декартовыми координатами задано множество вершин V. Для каждой пары вершин (v1, v2) из V определно некоторое число
R>p(v1,v2) — поток от v1 к v2.
R>Если очень сложно, то p(v1,v2) можно считать равным p(v2,v1). Необходимо построить следующие связи между этими вершинам (читай — граф), где стоимость связи пропорциноальна её длине и её пропускной способности, так, чтобы удовлетворить все потоки с минимальной суммарной суммой стоимостью связей.

R>Короче — упрощённое проектирование топологии сети, НО по-моему и здесь точного решения за нефакториальное время нет. Пока есть идеи тока танцевать от полного графа алгоритмом Примы или Краскала (Крускала, кого как учили . Но и там куча неясностей. Буду рад любым советам, ссылкам на материалы, и, самое главное, алгоритмам

R>Заранее спасибо.

R>Пояснения.
R>1) Считается, что "поток удовлетворён" если из вершины v1 в вершину v2 можно указать такой путь, где минимальная пропускная способность по всем связям больше или равна p(v1,v2). ИЛИ(!это сложнее, наверное, так что пока отложим!), Что если все вершины генерят заданные потоки, то наша сеть с этим справляется.

R>2) Для упрощения связи тоже (как и потоки от вершин p(v1,v2)=p(v2,v1) )можно считать двусторонними — то есть пропускная способность в одну сторону равна пропускной способности в другую сторону.

R>3) Стоимость связи (допустим) вычисляется по ф-ле $$$=k1*length + k2*width; Где length — длина связи, width — её пропускная способность. Коэффициенты считаем данными.

Ну так а чем все же не устраивают алгоритмы построения минимального остовного дерева? Есди у тебя задан поток между любыми двумя вершинами, то у тебя действительно полный граф. Только маленькое уточнение — если граф полный, то Прим значительно лучше Краскала, т.к. его сложность — O(n^2), а Краскала — O(mlogn), где m — число ребер. В случае полного графа, нетрудно посчитать, что m = C(n,2) = O(n^2)

Здравствуйте, kl, Вы писали:

kl>Ну так а чем все же не устраивают алгоритмы построения минимального остовного дерева? Есди у тебя задан поток между любыми двумя вершинами, то у тебя действительно полный граф. Только маленькое уточнение — если граф полный, то Прим значительно лучше Краскала, т.к. его сложность — O(n^2), а Краскала — O(mlogn), где m — число ребер. В случае полного графа, нетрудно посчитать, что m = C(n,2) = O(n^2)

Да, в данной формулировке задача решается именно так, однако, на практике, как я понял вчера формула $$$=k1*length + k2 * width на самом деле неверна. Ведь чем "шире" провод — тем дороже КАЖДЫЙ ЕГО МЕТР, следовательно — $$$=length * width;

Здесь необходимо учесть, что width — мы выбираем сами. Может оказаться так, что между (v1,v2) надо выбрать width(v1,v2)>p(v1,v2) чтобы, например, удовлетворить оптимальнее связь между v4,v5 которая проходит по пути v4-v1-v2-v5... Как это обсчитать я не в курсе.

К 7ому апреля постараюсь представить что-нить рабочее, если кому интересно

Здравствуйте, Rulikkk, Вы писали:


R>Да, в данной формулировке задача решается именно так, однако, на практике, как я понял вчера формула $$$=k1*length + k2 * width на самом деле неверна. Ведь чем "шире" провод — тем дороже КАЖДЫЙ ЕГО МЕТР, следовательно — $$$=length * width;

R>Здесь необходимо учесть, что width — мы выбираем сами. Может оказаться так, что между (v1,v2) надо выбрать width(v1,v2)>p(v1,v2) чтобы, например, удовлетворить оптимальнее связь между v4,v5 которая проходит по пути v4-v1-v2-v5... Как это обсчитать я не в курсе.

R>К 7ому апреля постараюсь представить что-нить рабочее, если кому интересно

Аа, я кажись тебя понял. Да, простой Прим нам тут не поможет, т.к. при добавлении новой вершины в дерево (скажем — v), может существовать такая вершина u, что где-то на пути от u к v есть ребро с потоком менее чем p(u,v).
Гхм, ну что тут скажешь... может есть стандартный алгоритм, ктр решает подобное. У меня только мысль пересчитывать пути от v до всех вершин в дереве при добавлении каждой новой вершины. В этом случае мы имеем следующее:
1. Если Дийкстра (O(n^2)) говорит нам, что все пути удовлетворяют условию — min(v1,v2) >= p(u,v), для минимального пути u->v — то мы втупую добавляем v и скачем дальше.
2. Если это не так — то начинается самое интересное. мы запоминаем число p, — сумма всех приращений, которые надо сделать в текущем дереве, чтобы добавить v. v пока не добавляем, а оставляем в очереди. Естественно ребра, которые надо наращивать мы тоже запоминаем.
3. Переходим к следующей вершине после v по степени близости к дереву. Считаем его расстояние до дерева + точно так же суммарное приращение ширин ребер (если необходимо). Если сумма получается меньше, чем у v — добавляем эту вершину, а не v.
4. Вместо пункта 3, можно еще посмотреть а нельзя ли v присоединить не к ближайшей вершине в дереве, а к следующей по удаленности.
Выглядит в общем не очень быстро — грубый анализ дает нам O(сумма степеней вершин * n^2). Что как известно в случае полного графа даст в итоге O(n^3). Но есть пара возможностей для оптимизации. Например если в начале пункта 3, мы понимаем, что разность расстояний до дерева между v и новой вершиной больше суммы приращений, посчитанной на шаге 2 — мы просто добавляем v и продолжаем растить дерево. Плюс, если эта новая вершина собирается приращаться к той же точке в дереве, что и шагом ранее v — ее можно сразу отвергать (ибо минимального суммарного веса уже никак не получится). Т.е. average complexity может будет и не такой плохой.
Ну а если где прогнал — не пинай сильно, это всего лишь мои unstructured thoughts

Здравствуйте, kl, Вы писали:

Дружище! Мне нравится ход твоих мыслей. Тока я предлагаю по пункту (3) перебирать тупо все вершины. И среди них искать вершину с минимальным p. И ещё ты не правильно указал сложность Дейкстры — ведь мы будем запускть его столько раз, сколько у нас вершин в уже построенной сетке. Но меня всё же берут сомнения что этот алгоритм (жадный вроде, да?) будет получать хоть иногда то, что надо... Ну да ладно, мне в общем-то не так уж нужен точный ответ, хватит и приближённого. Визуализацию, структуры данных и всё, в общем, кроме самого алгоритма написал уже... Через полтора часа надеюсь накидать тупого Кра(у)скала и понтоваться

kl>Аа, я кажись тебя понял. Да, простой Прим нам тут не поможет, т.к. при добавлении новой вершины в дерево (скажем — v), может существовать такая вершина u, что где-то на пути от u к v есть ребро с потоком менее чем p(u,v).
kl>Гхм, ну что тут скажешь... может есть стандартный алгоритм, ктр решает подобное. У меня только мысль пересчитывать пути от v до всех вершин в дереве при добавлении каждой новой вершины. В этом случае мы имеем следующее:
kl>1. Если Дийкстра (O(n^2)) говорит нам, что все пути удовлетворяют условию — min(v1,v2) >= p(u,v), для минимального пути u->v — то мы втупую добавляем v и скачем дальше.
kl>2. Если это не так — то начинается самое интересное. мы запоминаем число p, — сумма всех приращений, которые надо сделать в текущем дереве, чтобы добавить v. v пока не добавляем, а оставляем в очереди. Естественно ребра, которые надо наращивать мы тоже запоминаем.
kl>3. Переходим к следующей вершине после v по степени близости к дереву. Считаем его расстояние до дерева + точно так же суммарное приращение ширин ребер (если необходимо). Если сумма получается меньше, чем у v — добавляем эту вершину, а не v.
kl>4. Вместо пункта 3, можно еще посмотреть а нельзя ли v присоединить не к ближайшей вершине в дереве, а к следующей по удаленности.
kl>Выглядит в общем не очень быстро — грубый анализ дает нам O(сумма степеней вершин * n^2). Что как известно в случае полного графа даст в итоге O(n^3). Но есть пара возможностей для оптимизации. Например если в начале пункта 3, мы понимаем, что разность расстояний до дерева между v и новой вершиной больше суммы приращений, посчитанной на шаге 2 — мы просто добавляем v и продолжаем растить дерево. Плюс, если эта новая вершина собирается приращаться к той же точке в дереве, что и шагом ранее v — ее можно сразу отвергать (ибо минимального суммарного веса уже никак не получится). Т.е. average complexity может будет и не такой плохой.
kl>Ну а если где прогнал — не пинай сильно, это всего лишь мои unstructured thoughts