Предыстория проблемы

Я работаю над проблемой, когда, используя алгоритм поиска A*, мне нужно найти самый быстрый маршрут между двумя узлами на графике с учетом конкретной функции затрат. Вот обзор функции затрат:

Посылка находит самый быстрый маршрут, в ожидании, для определенного водителя доставки. Всякий раз, когда этот водитель едет по дороге с ограничением скорости >= 50 миль в час, есть вероятность, что посылка выпадет из их грузовика и будет уничтожена. Следовательно, эта ошибка добавит дополнительные 2*(t_road t_trip) часы к их поездке, где t_trip время, необходимое для того, чтобы добраться от стартового города до начала дороги, и t_road время, необходимое для прохождения отрезка дороги.

Для дороги длиной l в мили вероятность p возникновения этой ошибки равна tanh(l/1000) , если ограничение скорости >= 50 миль в час и 0 в противном случае. Это означает, что, в ожидании, потребуется t_road p * 2(t_road t_trip) несколько часов, чтобы проехать по этой дороге.

Итак, я построил свой график, где каждый город в данном наборе данных является узлом, а каждая дорога, соединяющая два города, является ребром. Каждое ребро имеет словарь весов, определенных как: {'distance':int, 'speed':int, 'time':float}

Обзор проблемы

Итак, я пытаюсь выяснить, где в моем алгоритме поиска A* я ошибаюсь, потому что, когда я пытаюсь рассчитать функцию стоимости пакета, есть некоторые крайние случаи (см. Пример ниже), когда моя функция затрат работает неправильно.

Моя попытка(ы)

Вот метод, который я написал для расчета стоимости упаковки:

 def delivery_calculation(path, G):
    result = 0

    for i in range(0, len(path)-1):
        edge = G.get_edge(path[i], path[i 1])

        if not edge:
            continue
        if edge[1]['speed'] >= 50:
            prob = math.tanh(edge[1]['distance']/1000)
        else:
            prob = 0

        t_road = edge[1]['time']
        t_trip = total_metric(path[0:i 1], G, 'time')
        result  = t_road   (prob*(2*(t_road t_trip)))

    return result
 

where path is a list of nodes, G is a graph, and get_edge() returns an edge and its weight between two nodes. It should be noted that the graph is undirected.

So within my A*, when I check all adjacent nodes and look to add them to the fringe (implemented as a priority queue), I calculate what the package cost would be for a given adjacent node. This, to me, seems like correct logic, but I could be wrong. Here is the code for that:

 for move in G.get_adjacent(curr_node):

    neighbor = move[0]
    weight = move[1]
    path = [neighbor]
    node = curr_node

    while node is not None:
        path.append(node)
        node = tracked_nodes[node]
    path.reverse()
            
    ncost = float(delivery_calculation(path, G))
 

where get_adjacent() gets all nodes that are adjacent to a given node.

So ncost is then used for the priority metric within my priority queue. My thinking behind that is if I want the fastest route, the smallest package cost should lead me there.

Results

So, the problem here is that for some searches, other cost functions turn up faster routes for package costs than the package cost function itself. An example:

I want to find the fastest route between Bloomington, Indiana, and Chicago, Illinois based on time

 Total hours: 3.900 (cost function)
Total hours for package delivery: 4.725
 

Я хочу найти самый быстрый маршрут между Блумингтоном, штат Индиана, и Чикаго, штат Иллинойс, исходя из времени доставки

 Total hours: 4.115
Total hours for package delivery: 4.736 (cost function)
 

Я потратил часы, просматривая свой код и пытаясь переработать логику, но я не могу понять, почему это произошло. Возможно, как работает тип float и значения округления? Это один из немногих крайних случаев, которые я нашел (еще один-от Блумингтона, штат Индиана, до Буффало, штат Нью-Йорк). Рабочий пример будет выглядеть так:

Я хочу найти самый быстрый маршрут между Денвером, штат Колорадо, и Милуоки, штат Висконсин, по времени

 Total hours: 16.387 (cost function)
Total hours for package delivery: 33.704
 

Я хочу найти самый быстрый маршрут между Денвером, штат Колорадо, и Милуоки, штат Висконсин, исходя из времени доставки

 Total hours: 21.513
Total hours for package delivery: 23.037 (cost function)
 

Есть какие-нибудь идеи? Я совершенно застрял. Заранее благодарю вас, и я ценю, что вы нашли время прочитать весь этот пост.