Один из способов решения этой проблемы - смоделировать ее как задачу поиска в графе. Для каждого из различных транспортных средств v постройте график G v , узлами которого являются все дороги в сети с дугами между узлами, которые связаны транспортным средством v. Например, в вашем первом примере граф G A будет иметь пять узлов, из которых существует только соединение от узла 1 к узлу 2, тогда как граф G C будет иметь пять узлов с ребрами от 2 до 3, От 3 до 4 и от 4 до 2.
Теперь рассмотрим окончательный граф G, построенный следующим образом. G формируется путем взятия всех графиков G v для всех транспортных средств v (что означает наличие нескольких копий каждого узла в исходном графе) с последующим добавлением ребер между соответствующими узлами в разных графах, если Есть несколько различных транспортных средств, которые все достигают дороги. Например, в графе G для исходной задачи G будет содержать подграфы G A и G B , ..., G E . Поскольку дорога 1 обслуживается обоими транспортными средствами A и B, вы должны добавить ребро между узлами для дороги 1 на графиках G A и G B , а так как дорога 2 обслуживается на транспортных средствах A, B и C должны быть ребра, соединяющие все узлы дороги 2 для подграфов G A , G B и G C .
Вы заинтересованы в минимизации количества переводов, которое вам нужно сделать, и поэтому мы хотели бы установить некоторые затраты в этом графике, которые измеряют это. В частности, мы говорим, что любое ребро, полностью содержащееся в одном из подграфов G v , имеет нулевую стоимость, поскольку, когда вы находитесь на транспортном средстве данного типа, вам не нужно вносить какие-либо изменения для движения вокруг дорог автосервис. Однако мы назначаем цену в один для каждого из ребер, связывающих подграфы для разных транспортных средств, поскольку следование этому виду ребра будет означать, что вы меняете транспортное средство, которое используете. Если вы теперь проследите какой-либо путь на этом графике, общая стоимость этого пути будет количеством изменений транспортного средства, которые вы сделаете.
Чтобы завершить строительство, у нас должен быть какой-то способ найти стоимость от начальной дороги до места назначения. Для этого мы добавим два новых узла s и t к графику, представляющим начало и конец пути. Узлы s будут иметь ориентированные на ноль ребра к первой дороге каждого из подграфов, так как, когда вы начинаете движение, вы можете выбрать любой из транспортных средств в качестве первого шага. Аналогично, каждый узел подграфа для конечной дороги будет иметь нулевое преимущество до t, поскольку, как только вы прибудете на дорогу назначения, не имеет значения, на каком автомобиле вы находитесь.
В этой настройке любой путь от s до t имеет стоимость, равную общему количеству переводов, которые вам нужно сделать. Таким образом, поиск кратчайшего пути на этом графике от s до t дает вам как маршрут, так и стоимость этого пути. Вы можете решить это, используя алгоритм Дейкстры, например.
Время выполнения этого алгоритма не звездное, но оно все еще полиномиальное время. Предположим, что есть n дорог и m разных транспортных средств. Граф, который мы создадим, будет иметь m различных подграфов, каждый из которых предназначен для одного транспортного средства, и в худшем случае эти графики имеют O (n 2 ) ребер в них. Если мы затем свяжем вместе все соответствующие узлы этих подграфов, где вы можете изменить строки, то в худшем случае будет O ((mn) 2 ) таких ребер, поскольку существует m графов из n узлов что все может быть связано друг с другом. Таким образом, у нас есть граф с O (mn) узлами и O ((mn) 2 ) ребрами, поэтому мы можем запустить алгоритм Дейкстры в O ((mn) 2 + mn log mn ) время.
Основная идея, которую я считаю важной, чтобы избавиться от этой проблемы, заключается в том, что вы часто можете решить проблемы с нахождением путей в графах, на которые распространяются определенные ограничения, создав новый граф, сформированный из нескольких копий старого графа, а затем с хорошей функцией граничной стоимости для этого графика.
Надеюсь, это поможет!