Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Решение графовой задачи: какой алгоритм выбрать?

Автор: Flier 12.4.2008, 22:13

Помогите пож. разобраться с одной "несложной" задачей.
Условие строится на прктическом примере.

Есть курьерская служба, состоящая из M курьеров и N заказчиков.
Заказчики и курьеры нах. в вершинах неориетированного графа. Известно время на переход из i-ой в j-ую вершину. Приоритетным является заказчик, который "заказывает товар большей стоимости".
При выходе из начальной вершины каждый курьер обладает товаром для удовлетворения всех заказов.
Так вот... Надо организовать работу курьеров так, чтобы прибыль от проданных товароров, была максимальна. Причем, время ограничено (не все заказчики могут быть удовлетворены в доставке).
Трабл:
Всего не один курьер, а несколько, притом в разных вершинах графа.

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

Если можно, то дайте, пож. линки на ресурсы по решению подобных задач.
Заранее спасибо.

Автор: Flier 13.4.2008, 11:55

Задачу можно переформулировать по другому:
Есть неориентированный взвешенный граф. Каждой вершине приписана определенная эффективность.

Так вот.. надо найти M путей (всего M курьеров, т.е. путь для каждого) длина, которых не превышает S (ограниченность времени доставки), причем суммарная эффективность этих путей (сумма эффективностей вершин, через которые проходят пути) должна быть максимальной.

Может у кого-нибуть есть мысли?

Автор: maxdiver 13.4.2008, 19:59

Flier

Цитата

Так вот.. надо найти M путей (всего M курьеров, т.е. путь для каждого) длина, которых не превышает S (ограниченность времени доставки), причем суммарная эффективность этих путей (сумма эффективностей вершин, через которые проходят пути) должна быть максимальной.

Видимо не совсем так. Если я правильно понял, то, во-первых, каждого заказчика нужно "удовлетворить" один раз, т.е. либо каждую вершину можно проходить только один раз, либо повторное прохождение вершины всегда даёт нулевую эффективность. Во-вторых, приоритетом обладают заказчики с большей эффективностью, т.е. из всех ответов нужно выбрать такой, который удовлетворяет самого дорогого заказчика (если такой, конечно, есть), затем из всех оставшихся ответов выбрать тот, который удовлетворяет второго по выгоде заказчика, и т.д.
Я правильно понимаю?

Автор: Flier 13.4.2008, 22:50

Цитата(maxdiver @ 13.4.2008, 19:59)

Flier

Цитата

Все именно так, как вы сказали.
И еще: посетив одного заказчика, курьер может двигаться дальше для обслуживания оставшихся клиентов.

Задача для одного курьера решается довольно просто с использованием алгоритма поика пути максимаьной эффективности.

Вот он:

Код


Пусть задана сеть, в которой для каждой дуги (i;j) определены два числа (Эij; Sij), ин-
терпретируемые как эффект при осуществлении соответствующей операции – Эij и затраты на эту операцию – Sij. Эффективность K(X)
пути X определяется как отношение его эффекта Э(X) = сумма(Эij) к
затратам S(X) = =сумаа(Sij) , то есть K(X) = Э(X)/S(X). Задача заключа-
ется в поиске пути X* максимальной эффективности: K(X) стремится к max.
Если решение K* = K(X*) этой задачи известно, то по определению K* выполнено:
(8) Э(X) – K* S(X)<=0
Следовательно, задача свелась к поиску минимального значе-
ния K*, для которого имеет место (8).
Другими словами, необходимо найти минимальное K*, такое, что все пути (длина которых
определяется как Lij(K*) = Эij – K*Sij) в сети имеют неположительную длину (неравенство (8) должно выполняться, в том числе, и
для пути максимальной длины).

Тут все довольно просто: находим пути, длина которых не превышает S (по условию задачи)
и применяем вышеописанный алгоритм.

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

Как это все связать, я не представляю.
Неужели простой перебор?!