前言

最近有一部番很火(其实冷门的很),那就是《理科生坠入情网,故尝试证明。》,在里面提到了一个很有趣的问题,巡回推销路线问题,又称旅行商问题,借此介绍一下这个十分著名的TSP问题。

正文

NP类与P类问题

在这之前,我们需要了解一下什么是NP类问题,什么是P类问题。
因为篇幅问题,我们这里只给出它粗略的定义,严格定义将另分一文介绍。
P类问题就是可以在多项式时间内解决的问题,NP类问题不一定可以在多项式时间内解决,但是可以在多项式时间内验证答案的准确性。

NP-hard

这是一类特殊的问题,所有的NP类问题都可以花费多项式时间归约到的问题,但它很难解决。

NP-complete

我们称呼NP-complete为NP完全或者NP完备,它是目前最不可能被归约为P类问题的一类问题,一个问题是NP完全的前提是,它是个NP类问题,同样也是NP-hard问题.

哈密顿回路

给定一个无向图G=(V,E),由指定的起点前往指定的终点,途中经过所有其他节点且只经过一次,构成的图被称为哈密顿通路,而闭合的哈密顿通路就是哈密顿回路
一道题难倒百万人?一笔画问题与哈密顿问题该怎么解?

Traveling Salesman Problem

了解上述前提,我们就可以正式了解Traveling Salesman Problem了,给定一个无向连通图G=(V,E),其每一边(u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈密顿回路,这个问题就是著名TSP问题
TSP问题是NP完备的,因此它目前不存在任何准确解的多项式时间解法。目前只能使用近似算法对其进行求解(近似解)。常见的解法包括:人工智能模拟退火算法遗传算法蚁群算法
你觉得我会详细在这里教这个问题的近似算法是怎么写的吗。。怎么可能,我自己都只会用SA去解这个问题,没那个资格教的哦...