您当前的位置：首页 > 学习 > 阅览室

程序员的算法趣题Q14: 国名接龙

时间：12-26来源：作者：点击数：

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))