步伐员的算法趣题Q14: 国名接龙

乱世烽火

目录

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全解


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！