找回密码
 新注册用户
搜索
查看: 6992|回复: 11

[新项目] [BOINC] [数学,算法类] TSP

[复制链接]
发表于 2007-10-25 20:59:42 | 显示全部楼层 |阅读模式
http://bob.myisland.as/tsp/

旅行商问题。

正准备注册帐号,发现帐号已存在,看来那个boinc wide account/team creation功能是生效了,不足之处是没有自动发信到注册邮箱,告诉个account key之类的。

欢迎加入Team China:
http://bob.myisland.as/tsp/team_display.php?teamid=61

评分

参与人数 1基本分 +30 维基拼图 +2 收起 理由
霊烏路 空 + 30 + 2

查看全部评分

回复

使用道具 举报

发表于 2007-10-26 00:02:45 | 显示全部楼层
我不太明白,但是这个问题还有什么可算的?改进算法么?现有算法还不好么?
回复

使用道具 举报

发表于 2007-10-26 00:03:43 | 显示全部楼层
我觉得这个项目的建立者对旅行推销商问题研究可能也不算很深入~~~观察一段时间再说~~~
回复

使用道具 举报

发表于 2007-10-26 00:06:52 | 显示全部楼层

回复 #2 feynord 的帖子

旅行推销商是NP完全问题~~~现在还没有找到好的算法~~~在这里“好的算法”意思是时间复杂度是多项式的~~~
现在也有不少关于这个问题的算法~~~当然有好有坏~~~除了简单的穷举以外还有遗传算法和模拟退火法等等~~~这个项目现在似乎正在测试遗传算法~~~还有就是正在在穷举方面想办法~~~当然这方面恐怕只能用来验证结果了~~~

评分

参与人数 1基本分 +20 维基拼图 +10 收起 理由
霊烏路 空 + 20 + 10

查看全部评分

回复

使用道具 举报

发表于 2007-10-26 14:58:05 | 显示全部楼层

回复 #4 fwjmath 的帖子

恩,所以我就搞不懂了,难道GA或者SA还是在一直推出新版本么?
当然好像GA还发展出了LGA,GALS等等。。。
因为我不是学数学的,所以也就知道算法名字了
回复

使用道具 举报

头像被屏蔽
发表于 2007-10-26 16:06:59 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

发表于 2007-10-26 18:16:31 | 显示全部楼层

回复 #5 feynord 的帖子

算法框架虽然相同~~~但是放进去的模型不同的话对得到的结果也是有影响的~~~所以不一定是算法推出新版本~~~更有可能是新的模型~~~
回复

使用道具 举报

发表于 2007-10-26 22:41:53 | 显示全部楼层

回复 #7 fwjmath 的帖子

有点懂了
回复

使用道具 举报

 楼主| 发表于 2007-11-17 08:21:12 | 显示全部楼层

2007-11-16

Ok there are still no workunits and I'm sorry for that, but the good news is today I have all to myself, and the 2.08 app for linux and windows will be up shortly. Next I'll finish fixing the work generator and then the project in my eyes will be out of beta.

很抱歉仍然没有新任务可下载,但好消息是2.08版的计算程序(linux和windows版本)很快就会发布。接下来,我将修复任务包生成器,然后在我看来项目就算是正式运行了:)

评分

参与人数 1基本分 +10 维基拼图 +5 收起 理由
霊烏路 空 + 10 + 5

查看全部评分

回复

使用道具 举报

 楼主| 发表于 2007-11-18 12:01:15 | 显示全部楼层

2007-11-17

The goal of getting out of beta is off to a slow started but a good one. The automatic work generator is going strong and the workunit signature problem is a thing of the past. The addition of the workunit status slowed down the app a little, but version 2.09 (due out later today) should fix that. New mac apps, and win 64 apps will follow soon.

结束beta阶段还需要一些时间。任务包生成器已经搞定,不会现有下载后验证出错的情况了。新增的任务包状态会让计算慢一点,但今天晚此时间将发布的2.09将修复这个问题。MAC以及64位Windows平台的计算程序将会随后发布。

评分

参与人数 1基本分 +16 维基拼图 +8 收起 理由
霊烏路 空 + 16 + 8

查看全部评分

回复

使用道具 举报

 楼主| 发表于 2007-11-22 10:13:31 | 显示全部楼层
2007-11-20

The issue of credits is not an easy one to address. It reminds of the mac vs. pc, or best linux distro discussions. People fall into one of three categories a) fixed, b) flop based, c) I don't do it for the credits. The only algorithm running now is the brute force method. Each workunit consists of a fixed number of possible paths to evaluate, and it almost entirely integer based math. Given these conditions fixed credits seem the most fair. I'm still working on how much each credit will be worth, right now the average for the current app version (2.10) is around 20, I'm goign to wait for a larger sample size from more platforms before I make a final decision. The next algorithm to come out will be the genetic algorithm. This will require a considerable amount of floating point operations and a fair number of calculations will be based on conditional probabilities (i.e. there is no way to know how many flpops a WU will take). Once the new GA app is up, TSP users will have the option of running both, or the one with the credit granting scheme they like best. This is about the best I can do.

积分方案还有待确定,候选的有:固定积分,基于计算量,维持现状。现在的任务包可以采取固定积分的办法,但还需要进一步观察以最终确定给分的方法。待引入遗传算法后,计算量更是没法估计了,到时候两种任务包都有,大家可以看看更喜欢哪种积分算法。

2007-11-21

Bug fix, errrrr I mean upgrade coming soon. I was getting some strange results from my validator. After a little digging I found a small (and by small I mean huge) error in my code. Its fixed now and beging tested. Look for the 2.11 version of tsp soon. For those worried about credits, I disabled the strick error checking that was causeing most (ok all) results to become invalid so you will be getting credit in the same manner you were before the bug was found. Once I have tested the patch and the various platforms updated I turn the strict error checking back on again. Good thing we are not out of beta yet.

在程序中发现了一个小问题,可能导致结果验证失败,很快2.11版本将修复这个问题,大家不用担心积分的问题。

评分

参与人数 1基本分 +20 维基拼图 +10 收起 理由
霊烏路 空 + 20 + 10

查看全部评分

回复

使用道具 举报

 楼主| 发表于 2008-3-19 12:03:24 | 显示全部楼层
2008-03-18
LOL the best laid plans of mice and men.... I thought people would be happy to know they could get a optimized app for the BF, and get a killer rac. I thought it would be good to reward people for taking advantage of the open source nature of the TSP project. I was very happy that someone took the time to make the updates I never got around to doing, as well as the things I had not thought of doing.

What do I get in return? Someone suggesting Im lazy and a poor coder, as well as other crunchers being accused of cheating. At least one user has gone so far as to drop TSP altogether over this. I understand that it is the view expressed by one person here but the TSP does not live in a vacuum no matter how much I would like it to, and there are others that feel the same way. I have often been tempted to just grant 1,000,000 credits per workunit just to devalue the credit system altogether, and hope all the discussion about credits goes away. This would obviously be unfair to other projects.

I don't like dealing with credits, and the BF app is all but useless on its own. It's only useful as a second step in a larger algorithm.

So where do I go from here? Well I'm not doing anything for the rest of this week. The ACO is ready, but I need to put some more thought into the experimental design, and workunit generation. I also have to fix GA. The people that worked hard on fixing the BF should reap some reward. Come Monday, I'll turn off the BF work generator and make a decision on the future of the BF.

貌似是因为项目的计算程序是开源的,然后有人把程序优化之后,得分效率提高非常多,引发了一些相关的讨论。。。

评分

参与人数 1基本分 +10 维基拼图 +5 收起 理由
霊烏路 空 + 10 + 5

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 新注册用户

本版积分规则

论坛官方淘宝店开业啦~

Archiver|手机版|小黑屋|中国分布式计算总站 ( 沪ICP备05042587号 )

GMT+8, 2024-3-29 18:03

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表