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

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

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

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

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

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

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

Flier

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

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

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

Вот он:


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

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

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


Это сообщение отредактировал(а) Flier - 13.4.2008, 22:52