-
【基础方法】Traveling Salesman Problem 问题和解决办法
TSP问题其实之前就学过，但是之前介绍的是递归贪心和动规的方法，这次看论文，看到了2-opt算法和蚁群算法，做一个简单的介绍。 TSP问题简单介绍 TSP（Traveling Salesman Problem），即旅行商问题或货郎担问题。假设有一个商人，需要去$n$个城市进行售卖，要求每个城市去且仅去一次，城市与城市之间的距离为确定值，最后返回出发城市，目标是求得一条最优路线，使得商人所走的路程最短。 这一个NP-hard问题，即在确定多项式时间内无法求解的问题。从图论的角度来看，这…
-
【基础方法】Trie Tree（字典树）
之前有看到过这个概念，但是没有认真了解过，这次刷hihoCoder的题目看到了这个。 Trie Tree，也就是常说的字典树。它利用了空间换时间的思想，用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，提高查询效率。它是一种多叉树的结构，对它来说，每一个结点由值域和链域两部分组成，值域保存这个结点对应的字符数和以到这个结点的所有的字符组成的字符串为前缀的字符串个数，链域则是指向该结点后继的结点。树的形式极大地减少了比较的次数，便于查找。 对于一个结点来说，链域的存储方…