Tag: 蛮力

解决填字游戏

我有一个填字游戏和一个可以用来解决它的单词列表（单词可以放置多次或甚至不放一次 ）。 对于给定的填字游戏和单词列表，始终存在解决方案。 我搜索了如何解决这个问题的线索，发现它是NP-Complete。 我的最大填字游戏大小是250乘250，列表的最大长度（可以用来解决它的单词数量）是200.我的目标是通过powershell/回溯来解决这个大小的填字游戏，这应该是可能的几秒钟（这是我的粗略估计，如果我错了，请纠正我）。 例： 可用于解决填字游戏的给定单词列表： 能够 音乐 金枪鱼 嗨 给定的空填字游戏（X是无法填写的字段，需要填充空字段）： 解决方案： 现在我的方法是将填字游戏表示为二维数组并搜索空格（填字游戏上的2次迭代）。 然后我根据它们的长度将单词与空格匹配，然后我尝试所有单词组合来清空具有相同长度的空格。 这种方法变得非常混乱非常快，我迷失了试图实现这一点，是否有更优雅的解决方案？

模拟退火TSP

我正在寻找在Java中实现模拟退火算法以找到旅行商问题的最佳路线，到目前为止，我已经实施了暴力，并且正在寻找修改该代码以便使用模拟退火。 显然，蛮力和模拟退火是非常不同的，并且使用非常不同的function。 我知道模拟退火使用一个称为温度的变量，然后在算法运行时冷却; 温度从高处开始逐渐冷却。 虽然温度很高，但算法更可能选择比当前更差的解决方案，从而消除了类似爬山算法中的局部最大值。 由于它冷却，算法更不可能接受更糟糕的解决方案，因此它可以专注于特定区域，并且可以快速找到最佳路径。 我相信我理解算法是如何工作的，但是我把它放到Java中有困难，我有2个类; 一个名为City的城市， getDistance包含计算每个城市细节的方法，如getIndex ， getDistance等。算法类从输入文件读取并将其存储在数组中（ int [][] ） 下面的代码是蛮力的算法，这是我想要修改以进行模拟退火的算法，如果有人可以帮助我这样做，我会非常欣赏它。 public static void doBF() { int random1 = generateRand(); if (towns2.size() > random1) { Town town = towns2.get(random1); visitedTowns[i] = town; towns2.remove(town); i++; if (lastTown != 1000) { journey += town.getDistance(lastTown); } lastTown = town.getIndex(); } else { doBF(); } […]