Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2002.03.04;
Скачать: CL | DM;

Вниз

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

 
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]

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



Страницы: 1 вся ветка

Текущий архив: 2002.03.04;
Скачать: CL | DM;

Наверх




Память: 0.49 MB
Время: 0.015 c
7-9310
Leviathan
2001-11-26 17:17
2002.03.04
Два вопроса... :)


1-9147
Poirot
2002-02-17 05:42
2002.03.04
Как сделать форму прозроачной - Alpha например на 70%


14-9279
phantom2040
2002-01-17 10:28
2002.03.04
Установка Delphi 6


1-9119
AleksK
2002-02-16 15:28
2002.03.04
MDIChildren Form in DLL


1-9233
staratel
2002-02-13 15:29
2002.03.04
web