Нахождение самого длинного неповторяющегося пути через соединенные узлы

Question

Я работаю над этим пару дней безуспешно. По сути, у меня есть куча узлов, расположенных в 2D матрице. Каждый узел имеет четыре соседа, за исключением узлов по сторонам и углам матрицы, которые имеют 3 и 2 соседа соответственно. Представьте себе кучу квадратных карт, разложенных бок о бок в прямоугольной области - проект фактически имитирует своего рода карточную / настольную игру.

Каждый узел может или не может быть связан с узлами вокруг него. У каждого узла есть функция (get_connections ()), которая немедленно возвращает узлы вокруг него, к которому он подключен (поэтому возвращается от 0 до 4 узлов). Каждый узел также имеет свойство «index», которое содержит его положение на матрице платы (например, «1, 4» -> строка 1, столбец 4). То, что я пытаюсь сделать, - это найти самый длинный неповторяющийся путь из соединенных узлов, заданный конкретным «начальным» узлом.

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

(источник: requiredgames.com )

(источник: requiredgames.com )

На обоих изображениях выделенные красные карточки предположительно являются самым длинным путем из соединенных карточек, содержащих самую верхнюю левую карточку. Однако на обоих изображениях видно, что пара карт, которые должны быть на пути, были опущены (Румыния и Мальдова на первом изображении, Греция и Турция на втором)

Вот рекурсивная функция, которую я сейчас использую, чтобы найти самый длинный путь, учитывая начальный узел / карту:

def get_longest_trip(self, board, processed_connections = list(), 
                     processed_countries = list()):
    #Append this country to the processed countries list,
    #so we don't re-double over it
    processed_countries.append(self)
    possible_trips = dict()
    if self.get_connections(board):
        for i, card in enumerate(self.get_connections(board)):
            if card not in processed_countries:
                processed_connections.append((self, card))
                possible_trips[i] = card.get_longest_trip(board, 
                                                          processed_connections, 
                                                          processed_countries)
        if possible_trips:       
            longest_trip = []
            for i, trip in possible_trips.iteritems(): 
                trip_length = len(trip)
                if trip_length > len(longest_trip):
                    longest_trip = trip
            longest_trip.append(self)         
            return longest_trip
        else:
            print
            card_list = []
            card_list.append(self)
            return card_list
    else:
        #If no connections from start_card, just return the start card 
        #as the longest trip
        card_list = []
        card_list.append(board.start_card)
        return card_list

Проблема здесь связана со списком processing_countries: если вы посмотрите на мой первый скриншот, вы увидите, что произошло то, что, когда Украина обошла, она посмотрела на два возможных варианта для самого длинного пути (Мальдова-Румыния или Турция, Болгария), увидели, что они оба равны, и выбрали одного без разбора. Теперь, когда Венгрия приходит в себя, она не может пытаться проложить путь через Румынию (где на самом деле будет самый длинный путь), потому что Румыния была добавлена ​​Украиной в список обработанных стран.

Любая помощь в этом чрезвычайно приветствуется. Если вы найдете мне решение этой проблемы, рекурсивное или нет, я с радостью пожертвую вам $$.

Я загрузил полный исходный код (требуется Python 2.6, Pygame 1.9) в:

http://www.necessarygames.com/junk/planes_trains.zip

Соответствующий код находится в файле src / main.py, который настроен на запуск.

Answer 1

Вы знаете, что проблема самого длинного пути в графе с циклами является NP-трудной?

Answer 2

... Румыния была добавлена ​​Украиной в список обработанных стран.

Используйте отдельные списки processing_countries для каждого пути графа.Говорят, один пример кода стоит тысячи слов, поэтому я немного изменил ваш код (без проверки):

def get_longest_trip(self, board, processed_countries = list()):
    # see https://stackoverflow.com/questions/576988/python-specific-antipatterns-and-bad-practices/577198#577198
    processed_countries = list(processed_countries)
    processed_countries.append(self)

    longest_trip = list()
    if self.get_connections(board):
        possible_trips = list()
        for card in self.get_connections(board):
            if card not in processed_countries:
                possible_trips.append(card.get_longest_trip(board, 
                                                            processed_countries))
        if possible_trips:
            longest_trip = max(possible_trips, key=len)
            longest_trip.append(self)

    if not longest_trip:
        longest_trip.append(self)
    return longest_trip

Не имеет значения:

Traceback (most recent call last):
  File "main.py", line 1171, in <module>
    main()
  File "main.py", line 1162, in main
    interface = Interface(continent, screen, ev_manager)    
  File "main.py", line 72, in __init__
    self.deck = Deck(ev_manager, continent)
  File "main.py", line 125, in __init__
    self.rebuild(continent)  
  File "main.py", line 148, in rebuild
    self.stack.append(CountryCard(country, self.ev_manager))
  File "main.py", line 1093, in __init__
    Card.__init__(self, COUNTRY, country.name, country.image, country.color, ev_manager)  
  File "main.py", line 693, in __init__
    self.set_text(text)
  File "main.py", line 721, in set_text
    self.rendered_text = self.render_text_rec(text)  
  File "main.py", line 817, in render_text_rec
    return render_textrect(text, self.font, text_rect, self.text_color, self.text_bgcolor, 1)       
  File "/home/vasi/Desktop/Planes and Trains/src/textrect.py", line 47, in render_textrect
    raise TextRectException, "The word " + word + " is too long to fit in the rect passed."
textrect.TextRectException: The word Montenegro is too long to fit in the rect passed.

Существует 16 различных bak файлы в вашем исходном пакете.Шестнадцать.Sixteeeen.Подумайте об этом и начните использовать контроль версий.

Answer 3

Метод грубой силы:

1. Создать первый список глубины подключения. Список магазинов L и его длина T.

2. Для каждого соединения этого списка:

   • Push Whole Diagram
   • Удалить соединение.
   • Создание первого связанного списка глубины.
   • Если список длиннее, чем T: установите T на длину, а список на L, затем рекурсивный вызов 2.
   • Pop Whole Diagram.
   • Возвращение

Это должно создать решение стиля заливки всех возможных способов соединения этих узлов.