Алгоритм, может кто-нибудь подобное решал...

← →
Cossys (2002-02-11 18:14) [0]

Господа, прошу помочь с решением задачи. Есть транспортная сеть (не путать с транспортной задачей) - ориентированный граф, заданный матрицами смежности В (еще ее называют матрицей инцендентности) и матрицей весов ребер U.
У кого-нибудь есть алгоритмы (или методы решений)???

Всех заранее благодарю за помощь

← →
Ura (2002-02-11 18:44) [1]

Ты лучше напиши как называеться задача...

← →
Builder (2002-02-11 21:19) [2]

А что найти-то нужно? :)

← →
Cossys (2002-02-12 10:34) [3]

to Ura

Это задача из теории графов.

to Builder

В общем задача следующая. Есть матрица В с m солбцами (в столбцах отражаются дуги) и n строками (в строках отображаются вершины графа). Самый простенький пример (х1 - начало, х3 -конец):
x2 x3
0-----0
|\ |
| \ |
| \ |
| \ |
0-----0
x1 x4

Для такого графа матрица В записывается (1 - начало дуги, -1 - конец, 0 - не соприкосаются):
1 2 3 4 5
- - - - -
1| 1 0 1 0 0
В= 2|-1 1 0 0 1
3| 0-1 0-1 0
4| 0 0-1 1-1

Фактически, матрица В - закодированая структура орграфа. Если задана матрица U={u1,...,u5} - весы дуг (другими словами - стоимость перевозки от, допустим, х1 до х2). МАТРИЦЫ ЕСТЬ... ЧТО ДЕЛАТЬ ДАЛЬШЕ??? Очевидно, как-то эти матрицы надо перемножить.

Нужны Ваши знания

← →
Cossys (2002-02-12 11:07) [4]

Господа, ну же!

← →
Ura (2002-02-12 11:53) [5]

> Cossys ©
Не торопи. Бодун... По моему эту задачу можно решить просто проходом от начальной точки до конечной. В конце сравниваешь все варианты пути, которыми прошел и находишь минимальный. Это если задача ТАКАЯ ПРОСТАЯ.
НО ЕСЛИ ТАКИХ ПЕРЕВОЗОК БОЛЬШЕ И ОНИ ЕЩЕ ВЛИЯЮТ НА ПРЕДЫДУЩИЕ ТО НАДО ДУМАТЬ... Скажи словами задачу, простыми... А графы это или еще что мы сами решим...
Теперь серьездно.
Есть транспортная сеть(почему она направленная? в обратную сторону нельзя ехать?). Нужно оптимизировать перемешения груза?
Сколько грузов одновременно перемешать? Фактор времени есть или только стоимость? Путь перемещения имеет ограничения на колличество грузов в нем? (Сегодня не помогу, но завтра...)

← →
Cossys (2002-02-12 12:17) [6]

to Ura

Задача не простая, вершин может быть хоть 100... и получается так, что необходимо произвести перевозку ТОЛЬКО из начального пункта ТЛЬКО в конечный. Все остальные пункты - промежуточные.

Дело в том, что приведенные выше матрицы я могу реально представить в виде масивов (как их преобразовать в маршруты - я без понятия). Однако догадываюсь, что матричный метод решения тут присутствует.

По условиям:
1. В обратную сторону ехать нельзя;
2. Сколько перевозится груза - все равно, платится одинаково;
3. Фактор времени не учитывается;

← →
Cossys (2002-02-12 12:22) [7]

Чуть не забыл... необходимо минимизировать сумарные затраты.

← →
Cossys (2002-02-12 16:12) [8]

...

← →
Ura (2002-02-12 16:57) [9]

Только пришел из налоговой. Не суетись...
Задачу можно решить так с первого взгляда и без матриц... Извини.
1. TList - объекты остановок (О). ID + Название
2. TList - связи объектов (Св). ID_Poditel + ID_Zavisimi + Стоимость
Цель найти все пути от О1 до О3.
1. Находим связи O1 - все заисимые от нее... И создаем сразу столько же путей (П). К примеру у нас О1-О2 и О1-О4 = 2 пути.
Путь это TList - остановка1+ остнановка 2 + остановка...+ сумма стоимости
2. Берем наши пути (сейчас это 2 штуки) и смотрим их последний элемент. В нашем случае О2 и О4. О2 соединен с О3 и О4. О4 - соединен с О3. (Связь О4-О2 или О2-О4 должна быть направленной, Я выбрал О2-О4) Следовательно создаем. Пути О1-О2-О3 и путь О1-О2-О4, путь О1-О4 просто наращиваем до О1-О4-О3. И так обходим пути пока они не замкнуться на граничных остановках (что следует указать в свойстве остановки) или не попадут в конечнуюю точку...
3. У тебя есть массив путей - следует пройтись по списку связей и найти их стоимость, если ты сразу не считал... И выбрать наименьший...

← →
Cossys (2002-02-12 18:45) [10]

to Ura

Ok, спасибо, попробую

← →
Ura (2002-02-13 12:21) [11]

Смотрел умные книги. Есть такая задача. Толко там ненаправленный граф. И цель перемещать товары с промежуточными остановками и оптимизировать перевозки. НО МАТРИЦЫ ТЫ РИСОВАЛ ДЛЯ ИМЕННО ДЛЯ НЕГО...
Или ты опишешь задачу или ... ничего. ;-))
То что я написал, это часть задачи сетевого планирования, нахождение минимального и максимального времени выполнения работ ;-).
ЧАЮ, ТРАВКИ, ИСХОДНЫЙ КОД?

Алгоритм, может кто-нибудь подобное решал... Найти похожие ветки