为了回答知乎问题 将中国城市名首尾相连,最多能连几个? 写的代码,可以找出多个最长相连的结果,也可以指定必须包含的城市。结果会进行可视化。
理论上替换输入文件,可以计算其他接龙的结果,不过受限于使用方法,计算大规模问题时效率很低(如成语接龙这种,可能性太多)。以及,非城市的状态下,可视化部分不可用。
运行main.py
即可,需指定文件名、最大迭代次数、以及必须包含城市(没有则为空)
- PuLP~=2.6.0
- pandas~=1.5.2
- pyecharts~=1.9.1
构建一个图,每个节点是一个城市,首尾名字相同的城市之间连一条边,接龙问题转换成找图上的一个最长路问题,用整数规划方法建模求解,并且支持找出前K个最好解。