Я имею дело с алгоритмической проблемой. У меня есть известный алгоритм графа с одним центральным узлом. Цель состоит в том, чтобы доставлять товары с этого центрального узла на некоторые другие, определенные узлы двумя транспортерами. Каждый транспортер может нести макс. одна единица товара в то время, так что после каждого посещения узла они возвращаются к центральному узлу для следующего. Я должен рассчитать самое короткое время, чтобы это сделать.КОРОТКИЙ срок поставки 2 транспортерами
Мой подход состоял в том, чтобы использовать dijkstra algorithm для центрального узла, чтобы найти кратчайшие пути ко всем остальным узлам, учитывая разные расстояния между узлами. Затем для всех узлов, куда должны перемещаться транспортеры (иногда даже более одного раза к конкретному узлу), я удваивал значения из-за расстояния назад и вперед. Я разделил значения на две группы с суммой как можно ближе друг к другу, потому что есть два транспортера и напечатан больше.
Решение, однако, кажется, не идеально. Мне нужно другое дело, чтобы в нее вступить. Если первый транспортер знает, что он заканчивает работу, скажем, 8 единиц раньше, он может когда-нибудь во время доставки подготовить хорошее для второго транспортера по дороге, так что ему не нужно заходить на него до центрального узла, но бит меньше. Тогда их общее время будет равным, но с учетом как более короткого. Это, к сожалению, не всегда возможно (например, только одна доставка на один узел и т. Д.). Мне нужно добавить этот аспект в мою программу.
У вас есть полный пример, где этот маневр необходим для достижения оптимального времени? –
Я подумал об этом простом [пример] (https://drive.google.com/open?id=0BybjAhGDTdlMQXZoYU9XcjRSR00). Представьте себе, что им нужно доставить три товара из центрального 1 в узлы 2,3,3. Их время, основанное на моем решении, будет 16,12. В лучшем решении первый переносит пункт 5 единиц в направлении 3-го узла, позволяет ему вернуться в центр и обрабатывать узел 2. Вторая сначала обрабатывает узел 3, а затем завершает задачу другого узла 3. Времена обоих равны 14. Вопрос заключается в том, как определить, что эта оптимизация возможна для данного известного графика применительно ко всем возможным случаям. – ludgo
Нужно ли двум транспортерам вернуться к центральному узлу в самом конце? Если нет, вы можете сэкономить время, заставив их подавать отдаленные узлы в последний раз. –