目錄

1. 問題描述

2. 解題分析--深度優先搜索

3. 代碼

3.1 運行結果

4. 后記

1. 問題描述

FIFA世界杯對足球愛好者而言是四年一次的盛事，下面我們拿2014年世界杯參賽國的國名做個詞語接龍游戲，不過，這里用的不是中文，而是英文字母（忽略大小寫），2014年FIFA世界杯的32個參賽國參見代碼中的國名串列，

舉個例子，如果像下面這樣，那么連續 3 個國名之后接龍就結束了（因為以上國名串列中沒有英文名稱以 D 開頭的國家），

“Japan” →“Netherlands” →“Switzerland”

問題：假設每個國名只能使用一次，求能連得最長的順序，以及相應的國名個數，

2. 解題分析--深度優先搜索

本題可以用深度優先搜索演算法來解決，

針對某個國家開始的情況，以深度搜索的方式搜索每一條可行的接龍路徑，按照每條接龍路徑一直搜索到底（直到當前接龍路徑的最后一個國家再也找不到下一個可以接上的國家了），此時將當前接龍的長度與保存的最大長度的接龍（在實作中可以作為全域變數）進行比較并根據比較結果相應更新，

沿每條路徑深度搜索時，用visited和unvisited分別管理已經搜索過的國家和尚未搜索過的國家，進一步的exploration僅從unvisited中選取下一個探索物件，因此省掉了“是否已被訪問過”的檢查判斷，另一方面，visited是按照訪問順序存入被訪問物件，所以其中存盤的就是當前搜索的接龍順序，visited和unvisited都需要以堆疊的方式進行管理，因此如果用遞回呼叫的方式實作的話，將它們作為遞回函式的介面引數傳遞即可；如果用回圈方式實作的話，則需要注意顯式的入堆疊和出堆疊管理，

注意：本題是要求接龍中同一國名只能使用一次，這意味著路徑不能形成loop，正因為這個，才可以以上述的visited、unvisited的方式進行分割以實作節點（每個國名就是一個節點）不重復訪問的管理，在有些問題中，允許節點在路徑上重復出現，但是不允許edge重復，則需要另外的防止重復訪問的管理機制，

此外，最長接龍搜索的結果依賴于從哪個國家開始，因此需要在針對以某個國家為起點的深度優先搜索的基礎上再追加一層外層回圈，遍歷國家名字串列中的每一個國家作為起始國家分別進行接龍搜索，

3. 代碼

# -*- coding: utf-8 -*-
"""
Created on Mon Sep  6 08:17:34 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque
# import itertools as it

country_list = ["Brazil", "Croatia", "Mexico",
                "Cameroon", "Spain", "Netherlands",
                "Chile", "Australia", "Colombia",
                "Greece", "Cote d'Ivoire", "Japan",
                "Uruguay", "Costa Rica", "England",
                "Italy", "Switzerland", "Ecuador",
                "France", "Honduras", "Argentina",
                "Bosnia and Herzegovina", "Iran", "Nigeria",
                "Germany", "Portugal", "Ghana",
                "USA", "Belgium", "Algeria",
                "Russia", "Korea Republic" ]
 
longest_jielong = []
 
def jielong_explore(visited, unvisited):
    """
    Parameters
    ----------
    visited   : list of conuntry names already visited
    unvisited : list of conuntry names not yet visited        
    Returns   : None
    """
    
    isNxtFound = False
    if len(unvisited) != 0: # There are countries not yet visited, continue the exploration.
        for index, c in enumerate(unvisited):
            if c[0] == visited[-1][-1]:
                jielong_explore(visited + [c], unvisited[:index] + unvisited[index + 1:])
                # jielong_explore(visited.append(c), unvisited[:index] + unvisited[index + 1:])
                isNxtFound = True
                
    # If there is no next country found, then the current jielong path is finished,
    # Compare the length of the current jielong with the recorded longgest jielong and update accordingly.
    if not isNxtFound or len(unvisited) == 0:
        global longest_jielong
        if len(longest_jielong) < len(visited):
            longest_jielong = visited
    
# Convert all country names to upper case for the convenience of processing.
for k in range(len(country_list)):
    country_list[k] = country_list[k].upper()

# Start from each country for a new jielong game
tStart = time.time()
for i, country in enumerate(country_list):
    jielong_explore([country], country_list[:i]+country_list[i+1:])
tCost  = time.time() - tStart

print("The max length of JieLong = {0}\n{1}\ntCost={2:6.3f}(sec)".format(len(longest_jielong), longest_jielong,tCost))

3.1 運行結果

The max length of JieLong = 8
['KOREA REPUBLIC', 'CAMEROON', 'NETHERLANDS', 'SPAIN', 'NIGERIA', 'AUSTRALIA', 'ARGENTINA', 'ALGERIA']
tCost= 0.002(sec)

4. 后記

最長接龍問題，可以聯想到最長路徑搜索問題，因此可以想到應該也可以用廣度優先搜索（BFS）的方式來實作，但是BFS雖然能夠找出最長路徑，因為不是沿著路徑進行搜索，所以不能像DFS那樣天然地記錄搜索路徑，在找到最長路徑后，如何恢復出來對應的路徑是一個問題，值得繼續思考，

上一篇：Q13: 滿足字母算式的解法

下一篇：Q15: 走樓梯

本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解