08-习题

9.5　习题

1．用第4章的图框架为旅行商问题的朴素解法重新编写代码。

2．通过实现第5章介绍的遗传算法来求解旅行商问题。请从本章的佛蒙特州5个城市的简单数据集开始。你能让遗传算法在短时间内达到最优解吗？然后再尝试加入更多的城市。遗传算法还能撑得住吗？你可以在互联网上搜一下，找到专为旅行商问题制作的大型数据集。请为检验解法的效率开发一个测试框架。

3．在电话号码助记符程序中采用字典，使其仅返回包含字典内单词的字母排列。

[1]　为了编写此解决方案，我研究了好几份资料，其中最权威的是Robert Sedgewick的《算法（第2版）》（第596页）。我查阅过Rosetta Code网站上求解0/1背包问题的几个示例，特别是其中的Python动态规划解决方案，本函数在很大程度上移自那里，而那也是来自本书的Swift版。它从Python到Swift，然后又回到Python。

[2]　参见Robert Sedgewick的Permutation Generation Methods（普林斯顿大学）。