Basic Greedy Поиск в Python

def basic_greedy(): 

    start = 1 
    mindist = d_dict[(1,2)] 
    m = 0 

    while len(tour)!=size: 
     tour.append(start) 
     for k in range(len(cities)): 
      if cities[k] not in tour: 
       if d_dict[(start,cities[k])]<mindist: 
        mindist = d_dict[(start,cities[k])] 
        m = k 
     start = cities[m] 

    return tour

Это мой код для базового жадного поиска в Python. начать это начало город, тур список, который должен содержать города, чтобы они посетили, города список, содержащий все города от 1 до размера (1,2,3,4 ... ..12..размер), где размер - это число городов. d_dict - словарь, содержащий расстояния между всеми возможными парами городов. mindist и м лишь временные переменные, отслеживающие ближайших соседей и т.д.Basic Greedy Поиск в Python

Я ожидаю, что код начинается с города 1, перейти к ближайшему соседу, а затем в ближайший до каждого города покрыта раз. Я ожидаю, что выход этого кода будет чем-то вроде строк [1,5,3,8,4,6,2,7] для городов с 1 по 8 (некоторая комбинация посещений всех городов ровно один раз), но Я получаю [1,7,7,7,7,7,7,7]. Что не так?

источник

2017-01-19 singhuist

Включается ли d_dict расстояния между городами и сам по себе? Похоже, вы можете оказаться в бесконечной строке 7, потому что 7 ближе всего к себе. Также вы, вероятно, захотите сбросить умника до начала следующего цикла; что произойдет, если я поеду city1 в city2 и это 1 единица расстояния, а затем, чтобы добраться откуда-нибудь из города2, будет> 1 единица расстояния. –

@AlbertRothman Только что сработал умник: D Я только что включил mindist = 99 в начале. Отдых такой, какой есть. Спасибо огромное! – singhuist

рад, что сработал. Чтобы сделать его еще лучше, вы можете искать словарь и находить наибольшее расстояние, а затем добавлять его к нему и использовать его как умника в начале каждого цикла; таким образом, ваше большое расстояние не жестко закодировано (так что вы можете добавить города, которые находятся дальше 99 и до сих пор получают решение). –

Вопросы: В общем случае проблема не определена. Код завершен. Однако позвольте мне предоставить некоторые основные указатели. Надеюсь, поможет. Здесь идет речь ...

Вам необходимо выйти из цикла for-loop, как только город будет найден и добавлен (похоже, что это чехол, проверьте, перепроверьте внимательно).
Код не заполнен. Например: (a) Как вы получаете доступ к списку тура? (b) размер не определен
Удостоверьтесь, что вы не пересматриваете или не добавляете города, которые уже были посещены в списке тура (похоже, это случай, проверка, повторная проверка).
Рекомендуется использовать методы графа/узла для реализации такого жадного поиска.

источник

2017-01-19 18:57:21 Ehsan

Я обеспечил 2,3 - я не упомянул весь исходный код, так как это было бы слишком долго! :) – singhuist

Это не отвечает на вопрос и будет лучше работать как комментарий .... –

def basic_greedy(): 
    # greedy search algorithm 
    d_dict = {1: [(1, 2), (2, 15), (3, 30)], 2: [(1, 30), (7, 10)]} # dict of lists of tuples such that nodei : [ (neighbourj, distancej), .... ] 
    currentCity = 1 
    tour = [] # list of covered nodes 
    tour.append(currentCity) 
    distanceTravelled = 0 # distance travelled in tour 
    while len(set([neighbourCity for (neighbourCity, distance) in d_dict.get(currentCity, [])]).difference(set(tour))) > 0: # set(currentCityNeighbours) - set(visitedNodes) 
     # way 1 starts 
     minDistanceNeighbour = None 
     minDistance = None 
     for eachNeighbour, eachNeighbourdDistance in d_dict[currentCity]: 
      if eachNeighbour != currentCity and eachNeighbour not in tour: 
       if minDistance is not None: 
        if minDistance > eachNeighbourdDistance: 
         minDistance = eachNeighbourdDistance 
         minDistanceNeighbour = eachNeighbour 
       else: 
        minDistance = eachNeighbourdDistance 
        minDistanceNeighbour = eachNeighbour 
     nearestNeigbhourCity = (minDistanceNeighbour, minDistance) 
     # way 1 ends 
     # way 2 starts 
     # nearestNeigbhourCity = min(d_dict[currentCity], key=lambda someList: someList[1] if someList[0] not in tour else 1000000000) # else part returns some very large number 
     # way 2 ends 
     tour.append(nearestNeigbhourCity[0]) 
     currentCity = nearestNeigbhourCity[0] 
     distanceTravelled += nearestNeigbhourCity[1] 
    print(tour) 
    print(distanceTravelled)

Это то, что вы просили? Возможно, я изменил структуру dist dict и некоторые другие переменные, но это не влияет на логику логического подхода, надеюсь, что это сработает для вас ... Отредактировал свой ответ, так как в первый раз я нашел nearestNeighbourCity среди все соседи currentCity но теперь я нахожу nearestNeighbourCity среди всех непосещенных соседей текущего города, и я сделал это, используя 2 способа way 1 и way 2

источник

2017-01-19 20:21:56 tkhurana96

Basic Greedy Поиск в Python

ответ

Смежные вопросы