Python规划旅行的独特路径

Question

我要写一个函数，把给定的 国家名称和n（所需步骤数）为您提供了一组国家 我可以从指定的国家开始跨越n个国家。在

请注意：

• 零步走，你就不能离开出发国
• 在一个步骤中，你只能在边境国家
• 这条路必须是最小的，例如从意大利到比利时，你可以穿过瑞士 德国或只有法国是第二个选择
• 你不能穿越一个国家两次或更多次或返回，例如，意大利→瑞士→意大利 或者意大利→瑞士→法国错了。在

这是我的地图：

neighborhood = {
'albania': ['greece', 'macedonia', 'serbia', 'montenegro'],
'andorra': ['spain', 'france'],
'austria': ['liechtenstein', 'switzerland', 'italy',
'czech republic', 'germany', 'slovakia',
'hungary', 'slovenia'],
'belarus': ['russia', 'lithuania', 'latvia', 'poland',
'ukraine'],
'belgium': ['luxembourg', 'germany', 'france', 'netherlands'],
'bosnia and herzegovina': ['montenegro', 'serbia', 'croatia'],
'bulgaria': ['romania', 'serbia', 'macedonia', 'greece'],
'croatia': ['bosnia and herzegovina', 'serbia', 'hungary',
'slovenia'],
'czech republic': ['slovakia', 'austria', 'germany', 'poland'],
'denmark': ['germany'],
'estonia': ['russia', 'latvia'],
'finland': ['sweden', 'russia', 'norway'],
'france': ['spain', 'andorra', 'monaco', 'luxembourg',
'belgium', 'germany', 'switzerland', 'italy'],
'germany': ['denmark', 'luxembourg', 'belgium', 'france',
'netherlands', 'poland', 'czech republic',
'austria', 'switzerland'],
'greece': ['bulgaria', 'macedonia', 'albania'],
'hungary': ['romania', 'ukraine', 'slovakia', 'austria',
'slovenia', 'croatia', 'serbia'],
'iceland': [],
'ireland': ['united kingdom'],
'italy': ['france', 'switzerland', 'austria', 'slovenia',
'san marino', 'vatican city'],
'latvia': ['russia', 'estonia', 'lithuania', 'belarus'],
'liechtenstein': ['austria', 'switzerland'],
'lithuania': ['russia', 'latvia', 'belarus', 'poland'],
'luxembourg': ['belgium', 'germany', 'france'],
'macedonia': ['bulgaria', 'serbia', 'albania', 'greece'],
'malta': [],
'moldova': ['ukraine', 'romania'],
'monaco': ['france'],
'montenegro': ['albania', 'serbia', 'bosnia and herzegovina'],
'netherlands': ['germany', 'belgium'],
'norway': ['sweden', 'finland', 'russia'],
'poland': ['russia', 'lithuania', 'belarus', 'ukraine',
'slovakia', 'czech republic', 'germany'],
'portugal': ['spain'],
'romania': ['ukraine', 'moldova', 'bulgaria', 'serbia',
'hungary'],
'russia': ['norway', 'finland', 'estonia', 'latvia',
'lithuania', 'belarus', 'ukraine', 'poland'],
'san marino': ['italy'],
'serbia': ['bosnia and herzegovina', 'hungary', 'croatia',
'montenegro', 'albania', 'macedonia', 'bulgaria',
'romania'],
'slovakia': ['hungary', 'austria', 'czech republic', 'poland',
'ukraine'],
'slovenia': ['italy', 'austria', 'hungary', 'croatia'],
'spain': ['portugal', 'andorra', 'france'],
'sweden': ['norway', 'finland'],
'switzerland': ['germany', 'france', 'liechtenstein', 'austria',
'italy'],
'ukraine': ['russia', 'belarus', 'poland', 'moldova',
'slovakia', 'hungary', 'romania'],
'united kingdom': ['ireland'],
'vatican city': ['italy']
}

试验主要是：

^{pr2}$

以及执行：

^{3}$

有人有什么建议吗？在

我试着写：

def crossing(naz,step):
 vicini = border(naz)
 for i in range(step):
    next(vicini)
 return next(vicini)

def border(naz):
    vicini = set([naz])
    yield vicini
    yield neighborhood[naz]

Answer 1

这是图论上的任务，这个问题在“Python算法：掌握Python语言中的基本算法”一书中解决了。在

Answer 2

根据我的判断，基本算法：

有三个数组：currently_at，going_to，和{}。对于每个步骤：添加到going_to中没有been_to的所有唯一邻居。然后将currently_at替换为going_to，将它们添加到been_to，并清空{}。在