Где используется этот алгоритм?

Question

[OwerFan]

Где применяется задача о назначениях с использованием методов теории графов в практике? или это еще одна теория, которая просто есть

Answer 1

[Антон Федорян]

Слабо вики почитать?

Предположим, что таксомоторная компания имеет три свободные машины (исполнители), и три заказчика (работы), желающих получить такси как можно быстрее. Фирма заботится о времени доставки такси к заказчику, так что для каждой машины стоимость определяется временем, с какой машина доберётся до места ожидания, определённого заказчиком. Решением задачи о назначениях будет распределение машин по заказчикам такое, что суммарная стоимость (суммарное время ожидания) минимальна.

Задачу о назначениях можно сделать более гибкой. В вышеприведенном примере могут оказаться не три, а четыре свободных такси, но заказчика по-прежнему три. Можно назначить четвёртого фиктивного заказчика с нулевой стоимостью, распределение же машины на фиктивного заказчика означает — «ничего не делай».

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

Comments

[OwerFan]

Херня, в какой компании такси это ваще используется? ты о чем?

[hint000]

OwerFan,

в какой компании такси это ваще используется?

Во всех, кроме агрегаторов типа Яндекса. Да и в агрегаторах в принципе тоже, только в сильно изменённой форме.

Херня

ну так она не предназначена, чтобы ей думать, используй по назначению.

[OwerFan]

hint000, откуда такая уверенность?(Там же работает программа какая машина ближе и свободная та и приедет)

[hint000]

OwerFan,

какая машина ближе

В этом и смысл алгоритма, о котором ты спрашиваешь. "Ближе" - это не всегда тупо расстояние между точками А и Б. Потому что такси - не вертолёт, по прямой не летает, приходится ехать по дорогам, а прямой дороги может не быть. А ещё на дорогах могут быть пробки, так что объехать по длинной дороге может быть в несколько раз быстрее, чем стоять в пробке на короткой дороге. Всё это и приходится учитывать в алгоритме.

[OwerFan]

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

[hint000]

OwerFan, Алгоритмы не только в программах реализуются. Может слышал про такую профессию - диспетчер. Сидит тётенька на телефоне, а на мониторе у неё карта и в реальном времени показано, где какая машина находится. Если тётенька давно работает, то весь этот алгоритм у неё в голове на интуитивно-эвристическом уровне работает, почти мгновенно и почти без ошибок. Программа тут работала бы хуже, чем живой человек. Но алгоритм по сути тот же самый.

Или ты своим воображением решил убедить что это действительно используется?

:) Задавай ещё вопросы