Дейкстры найти кратчайший путь удовлетворения заданных ограничений


Вопрос возник из Hackerrank.

Предположим, что есть 1 to N магазины в городе, которые соединены двунаправленный дорогах, связанных с путешествиями раз. Каждый магазин продает некоторые виды рыб (0 <= type_of_fish_store_i < K), в общей K видов рыб продают в городе. Кошка начинается в магазине 1и путешествуя по пути покупает рыб в каждый магазин по пути.

Вычислить минимальное время, за которое удовлетворяет ограничениям

  • кошка должна закончиться в определенный магазин X
  • кот должен заканчиваться определенным видам рыб в корзину

Примечание: в магазин, в том числе конечного пункта назначения можно посетить более чем один раз

Магазин и видов рыбы продажа в магазине ({shop:fish_type}):

{1: {1}, 2: {2}, 3: {3}, 4: {4}, 5: {5}}

Матрица смежности с ячейками, наполненный затрат времени (имеется в виду cost_matrix):

[[0, 10, 10, 0, 0],
 [10, 0, 0, 10, 0],
 [10, 0, 0, 0, 10],
 [0, 10, 0, 0, 10], 
 [0, 0, 10, 10, 0]]

Подход я реализовал:

def dijkstra(cost_matrix, start, wanted, end):
    """

    :param cost_matrix: adjacency matrix filled with time costs
    :param start: the store where the cat starts at
    :param wanted: types of fishes the cat wants at the end of journey
    :param end: the store where the cat ends at
    :return: 
    """
    fish_basket = shop_and_fish[start]
    accum = 0
    h =[]
    visited = [start]

    while not (wanted.issubset(fish_basket) and start == end):
        for i, dist in enumerate(cost_matrix[start - 1]):
            if dist > 0:
                    heapq.heappush(h, [ accum + dist, i + 1, fish_basket | shop_and_fish[i + 1], visited + [i + 1]])
        # print("heap: ", h)
        accum, start, fish_basket, visited = heapq.heappop(h)
    print("Total time: ", accum, ", End store:", start, ", Fish types collected: ", fish_basket, ", Path: ", visited)
    return accum

Выполнить:

dijkstra(cost_matrix, 1, {1,2,3,4,5}, 5)
# this is saying the final accepted state is the cat 
# at 5th store with {1,2,3,4,5} types of fishes in hand

Возвращает

50
# Total time:  50 , End store: 5 , Fish types collected:  {1, 2, 3, 4, 5} , Path:  [1, 2, 4, 5, 3, 5]

Проблема

Эффективность. Расширяя ненужных узлов, таких как [1,2,1,2,1,2]в некоторых других случаях [1,2,3,4,3,2,1,2,3,4..]может, некоторые другие непредвиденные моделей. Любые мысли о том, как их устранить? Я пробовал палиндром, но это, кажется, добавить много сложностей, так как он рассматривает каждую тропинку и каждый подпуть пути. Кроме того, если вы определили какие-либо другие улучшения, не стесняйтесь добавить ответ.



Комментарии