MacGK7JXnu.png
在数学城市的街道遵循一个整数坐标的方形网格。任何两点之间的距离都是通过计算它们在坐标上的水平和垂直差异来实现的。
住在(3,4)的Thiago现在非常需要咖啡。在他的附近，有三家咖啡馆：在(-4,3)，(-4,3)，(-1,-1)，(-1,-1)和(2,-4)。(2,-4).
蒂亚戈应该去哪里才能尽快得到他的咖啡？
def distEqual(home,location): #coordinate
short = float('inf')
x,y = home
for i,j in location:
s = x-i + y-j
if s < short:
tag = (i,j)
short = s
return tag
location = [(-4,3),(-1,-1),(2,-4)]
home = (3,4)
print(distEqual(home,location))
(-4, 3)
接下来你标记周围 n 分钟可以到达的区域
借助turtle标记分布
step1 坐标轴
def xy():
t.pensize(5)
t.color("black")
t.goto(-300,0)
t.pendown()
t.forward(600)
t.penup()
t.goto(0,300)
t.pendown()
t.right(90)
t.forward(600)
#t.done()
step2
# upgrade coffeeshop
# every shop target users not exceed distance 5 min,
# so that how many cross cover
#coordinate X,Y
import turtle as t
def capicity(time,zero):
x,y = zero
loc = []
for x in range(-time+x,x+time+1):
#print(x)
loc.extend([(x,time-abs(x)),(x,abs(x)-time)])
return set(loc) #len(set(loc)),
time = 5
zero = (-1,0)
print(capicity(time,zero))
获取 n 个单位的距离坐标后
pos = capicity(time,zero)
ratio=40
xy()
for xy in pos:
x, y = xy
t.dot(10,'green')
t.penup()
t.goto(x * ratio, y * ratio)
t.pendown()
t.dot(10, 'red')
t.done()
汉密尔顿和欧拉之旅
谈到图论，图上的路径计算是不可避免的。今天，让我们来学习一下文献中经常遇到的哈密尔顿轮和欧拉轮。
Hamilton ve Euler Turu.png
汉密尔顿之旅
哈密尔顿路径是决定有向图或无向图中是否存在哈密尔顿路径或哈密尔顿回路的问题。在哈密尔顿图的情况下，一个游程必须只遍历图中的所有顶点一次，才能完成。如果这条路径被完成为封闭的，它就被称为哈密尔顿图。
Hamilton ve Euler Turu2.gif
在汉密尔顿路径中，这是NP-不完全问题之一，所有的边可能是封闭的，也可能不是。然而，边缘永远不应该被重复。
汉密尔顿路径和循环
威廉-罗文-汉密尔顿爵士是一位爱尔兰数学家，也是二项式微积分的发明者--他用二项式微积分来研究十二面体上每一个顶点都精确访问一次的闭边路径（也叫汉密尔顿路径！）。虽然在一篇文章中甚至不可能触及icosian微积分，但让我们试着在图形--不一定是十二面体--的更一般的背景下理解汉密尔顿路径和循环。
Sir William Rowan Hamilton.gif
威廉-罗文-汉密尔顿爵士
在我们上一篇关于柯尼斯堡七桥的文章中，我们遇到了图中行走的定义--即一连串交替的顶点和边。特别是，路径是一个所有顶点和边都不同的行走。在此基础上，汉密尔顿路径是指图中每一个顶点都精确访问一次的路径。
Hamiltonian Paths and Cycles.png
在上图中，4->3->1->6是一条路径，因为它是由不同的顶点和边组成。我们也能找到哈密尔顿路径吗？是的！我们可以找到汉密尔顿路径。
2->6->5->1->3->4就是其中之一!
Herschel’s Graph.png
赫歇尔的图形
一个包含哈密尔顿路径的图被称为可追踪图。以英国天文学家亚历山大-斯图尔特-赫歇尔命名的赫歇尔图是可追踪的。寻找哈密尔顿路径已被作为一项练习留给读者。
当然，我们可以将哈密尔顿路径的概念扩展到循环上--一个对每个顶点都精确访问一次的循环被称为哈密尔顿循环，而包含这样一个循环的图被称为哈密尔顿图。
Herschel’s Graph1.png
十二面体中的汉密尔顿循环
投影到二维的十二面体
任何哈密尔顿循环都可以通过移除其一条边而转化为哈密尔顿路径，但哈密尔顿路径只有在其端点相邻时才能扩展为哈密尔顿循环。
Orthogonal projections of platonic solids.png
有趣的是，所有柏拉图实体（只有五个）的图形都是哈密顿式的--十二面体（在旁边显示）就是其中之一。作为一个有趣的练习，请尝试在其他四个柏拉图中找到哈密顿循环!
Petersen Graph.png
柏拉图实体的正交投影
哈密顿路径在棋盘游戏理论中也经常出现，比如说国际象棋。如果你把8x8棋盘上的每个方块都模拟成图形的一个顶点，并考虑为一个马找到一个移动序列，使马正好访问每个方块（顶点）一次，你会得到什么？这就是骑士游问题!
Petersen Graph.png
8x8棋盘上的开放式骑士巡视问题
最后，这里有一个发人深省的问题--证明（当然是数学上的）彼得森图没有哈密尔顿循环。事实上，值得一提的是，彼得森图是低米尔顿图，也就是说，从其中删除任何一个顶点都会使其成为哈密尔顿的。
彼得森图
阅读更多
- 哈密顿循环的充分条件研究（罗斯-胡尔曼大学本科数学杂志）
- 汉密尔顿路径和循环的NP完备性
- 骑士的旅行问题
- 骑士游和Zeta函数
网友评论