“拼木头”算法挑战赛:禁忌搜索算法,用Javascript 跑

简介:

题目来源见文章《帮一个朋友征集算法代码,大家都来开动你的脑袋发挥你的智慧参与吧》,大家提出了很多算法,很多人说类似百钱买百鸡,这里要讨论一下,拼木头问题和百钱买百鸡问题是很不一样的

 

百钱买百鸡问题,每种鸡的数目没有限定,所以你可以用穷举法。

 

拼木头问题,每一种木头的数目一开始已经给出来了,这样,选用哪些种类的木头,最后会相互影响,如果你一开始总是选择最方便的数据来组合,很有可能陷入局部最优。

 

拼木头问题是一种典型的优化组合问题,应该用典型的优化算法来解决,例如:模拟退火、禁忌搜索、遗传算法等等。

 

下面的程序用禁忌搜索算法,每次得到的最终组合序列可能都不一样但是组合个数基本上总是最大(最优)的,不保证每次都是,但是能保证大概率得到最优解,这也是优化算法的一个特点。

 

原始数据选用了原文中的数据,您可以修改数据,验证算法是否正确

 

一般情况下程序一分钟左右即可发现最优解,到结束需要运行三分钟左右,运行期间浏览器响应可能会变慢一点,正常现象!

 

最终答案是可以得到 48 个21米的木头 ,但是组合方法则是数不胜数,可以看出,这里5米木头的数目决定了最终结果。

 

提示:必须在 Chrome 中跑,别的浏览器没有测试

种类 根数 长度
第一种
第二种
第三种
第四种
第五种
拼接长度


相关阅读:

《模拟退火算法应用于最优排列问题和最优组合问题 之 排列篇》

《“十滴水”游戏——求解算法挑战赛:模拟退火,用Javascript跑》 

//==========================================



本文转自左洸博客园博客,原文链接:http://www.cnblogs.com/myqiao/archive/2011/06/22/2087649.html,如需转载请自行联系原作者

目录
相关文章
|
3天前
|
算法 JavaScript 前端开发
在JavaScript中实现基本的碰撞检测算法,我们通常会用到矩形碰撞检测,也就是AABB(Axis-Aligned Bounding Box)碰撞检测
【6月更文挑战第16天】JavaScript中的基本碰撞检测涉及AABB(轴对齐边界框)方法,常用于2D游戏。`Rectangle`类定义了矩形的属性,并包含一个`collidesWith`方法,通过比较边界来检测碰撞。若两矩形无重叠部分,四个条件(关于边界相对位置)均需满足。此基础算法适用于简单场景,复杂情况可能需采用更高级的检测技术或物理引擎库。
34 6
|
1天前
|
存储 算法 Java
广度优先搜索(Breadth-First Search,BFS)是一种用于图的遍历或搜索的算法。
广度优先搜索(Breadth-First Search,BFS)是一种用于图的遍历或搜索的算法。
|
1天前
|
人工智能 算法 Java
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
|
4天前
|
算法 JavaScript 决策智能
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
|
5天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
5天前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
9天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
12天前
|
存储 算法
动态规划与搜索算法
动态规划与搜索算法
14 0
|
13天前
|
算法 Java Go
【经典算法】LeetCode 35. 搜索插入位置(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 35. 搜索插入位置(Java/C/Python3/Golang实现含注释说明,Easy)
8 0
|
13天前
|
算法 JavaScript 前端开发
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)
16 1

热门文章

最新文章