Форум: "Основная";
Текущий архив: 2002.03.04;
Скачать: [xml.tar.bz2];
ВнизАлгоритм, может кто-нибудь подобное решал... Найти похожие ветки
← →
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;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.004 c