最新 | 最热门 | 最高评价

+4  八皇后问题算什么,来看看无穷皇后问题吧

Tag: 趣题 | 算法 | Brain Storm | 无穷
Matrix67 发于 2011年08月24日 03:49 | 点击: 2709 | 展开摘要
    当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题(eight queens puzzle)时,他恐怕怎么也想不到,100 多年以后,这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单:把八个皇后放在国际象棋棋盘上,使得这八个皇后互相之间不攻击(国际象棋棋盘是一个 8×8 的方阵,皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步)。虽然这个问题一共有 92 个解,但要想徒手找出一个解来也

查看全文: http://www.udpwork.com/item/5685.html

+3  Arrow不可能性定理:独裁是唯一完美的选举制度

Tag: 算法 | Brain Storm | 惊奇数学事实 | 证明 | 经济
Matrix67 发于 2011年04月10日 19:46 | 点击: 2528 | 展开摘要
    由于某些原因,最近在整理以前的日志。偶然翻到这篇日志时,顺便在 Wikipedia 复习了一下 Arrow 不可能性定理的证明,惊奇地发现这个定理的证明过程非常困难但又非常初等,是一个门槛很低、老少咸宜的思维游戏。虽然不少人都翻译过 Wikipedia 上的这段证明,但我也想自己写一个自己的理解,一来做个笔记,二来也锻炼一下自己的表达能力。

    Arrow 不可能性定理是一个与选举制

查看全文: http://www.udpwork.com/item/4769.html

+2  多模匹配算法与dictmatch实现

Tag: 数据结构与算法 | 多模匹配,算法,dictmatch
editor 发于 2011年10月10日 11:49 | 点击: 3399 | 展开摘要
多模式匹配在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树,AC算法,WM算法等等。我们将首先介绍这些常见算法。

1.hash

可以单字、双字、全字、首尾字hash。

优点:简单、通常有效

缺点:受最坏情况制约,空间消耗大,需要回朔。

2.Trie树

改进:进行

查看全文: http://www.udpwork.com/item/6036.html

+1  如此保证选举公正性能成吗?

Tag: 算法 | Brain Storm | 证明
Matrix67 发于 2011年11月23日 17:16 | 点击: 2058 | 展开摘要
    一个小镇上即将进行大选,候选人有 m ≥ 3 个,选民一共有 n 人。选举时,每个选民在选票上写下一个候选人的名字,然后由计算机根据某种选举机制算出大选的获胜者来。如果把 n 个选民的选票依次记为 x1, x2, ..., xn 的话,那么选举机制的算法其实就是一个映射到 {1, 2, ..., m} 的函数 f(x1, x2, ..., xn) 。

    为了保证选举程序的公平性,让

查看全文: http://www.udpwork.com/item/6368.html

+0  程序设计核心原则: 直观

Tag: IT技术和评论 | 算法
ideawu 发于 2021年08月07日 09:41 | 点击: 333 | 展开摘要
好的代码应该是直观的, 简单的. 直观就是"所思就所写", 想的是什么样就要把代码写成什么样子, 不要七拐八绕.

例如, 在做结构设计和流程设计时, 我们分析出某个功能流程应该这样做:

先做步骤1, 然后做步骤2.

什么是程序设计? 程序设计就是流程, 是串行化, 是先后顺序. 所以, 文档设计完毕之后, 必须写下这样的代码:

step1();
step2();

没错, 就是非常直观的两个函数调用语句, 一眼就能看出有先后顺序, 先 1 后 2. 但是, 初学者往往

查看全文: http://www.udpwork.com/item/18115.html

+0  浅析微软小冰算法和决策模型

Tag: 人工智能 | 小冰 | 微软小冰 | 情商模型 | 情绪模型 | 算法
Gauin 发于 2020年04月21日 22:06 | 点击: 267 | 展开摘要
文 李红涛

微软小冰,从2014年5月发布版本小冰一代,到2019年5月发布小冰七代;

概要:

1.小冰的训练数据,来源是全网数据

2.给用户打情绪标签

3.情绪数据来源:emoji数据表情

4.问答+情绪渲染 学习无情绪的表达 然后加上情绪的渲染

算法:

小冰的算法结构,信息输入、存储、分析、决策、输出等几个环节;

小冰的图片识别能力,是基于深度卷积神经网络(CNN)的计算机视觉算法系统,通过深度学习等机器学习算法,不断学习历史信息,建立相应数学模型。通过

查看全文: http://www.udpwork.com/item/18016.html

+0  Tag set 的数据结构优化

Tag: ECS | 算法
云风 发于 2021年07月27日 10:44 | 点击: 431 | 展开摘要
在最近实现的 ECS 库中,Tag 是一种非常重要的数据结构。它是一类特殊的 Component ,不携带数据,但会关联到同一 Entity ,最重要的用途是用于筛选。我在设计 Comonent 的数据结构时,采用了一种简单的数据结构 。它采用连续内存储存的数组,按 Entity id 有序排列。并在查询算法上做了一些优化,可以使得大部分查询时间小于 Log(N),接近常量时间。

但是,这样做的代价是插入和删除操作都是 O(n) 的。为了避免大量的插入删除操作堆积在一起时,

查看全文: http://www.udpwork.com/item/17989.html

+0  带猜测的二分查找算法

Tag: 算法
云风 发于 2021年06月11日 14:39 | 点击: 271 | 展开摘要
我想用 C 实现一个内存紧凑的 ECS 框架,希望数据结构足够的简单,且能管理海量的对象。所以我让每个 component 就是一个不包含任何引用的 struct ,并带有一个 32bit 的 id 。并把这样的一个数据结构放在一块连续内存中。

这个 id 没有对外暴露的 API (不是 entity id ),可以在运行过程中调整。如果两个不同类型的 component 有相同的 id ,即认为它们同属一个 entity 。id 的作用是管理 component 的生命期

查看全文: http://www.udpwork.com/item/17873.html

+0  分布式系统升级所遇到的问题

Tag: 分布式 | 算法
ideawu 发于 2021年05月28日 21:09 | 点击: 287 | 展开摘要
常规的单机软件升级, 一般认为是一个原子操作, 也就是说, 软件会在"瞬间"完成升级, 即使不能在"瞬间"完成升级, 也要中断服务, 等升级完成后再提供服务.

对于需要中断服务的情况, 在分布式系统中是不能接受的. 同时, 分布式系统的升级永远不可能在"瞬间"完成. 因此, 分布式系统升级会面临一个长时间的中间态, 新旧版本的软件同时运行, 这就涉及到兼容性问题.

假如, 新版本的软件的数据格式改变了, 那么, 新版本写入的数据就无法被旧版本识别, 旧版本就会报错. 因为

查看全文: http://www.udpwork.com/item/17872.html

+0  预运算地图寻路的一种方法

Tag: 算法
云风 发于 2021年01月05日 15:57 | 点击: 336 | 展开摘要
上次谈到服务器上寻路算法的优化。文末提到,其实,针对具体需求,我们实际上可以预运算所有的路径,把结果持久化在文件中,运行时用 O(1) 的时间就可以查询到任意路径。

对于半径为 N 的地图网格,选取任意两点作为起点和终点,一共有 N^4 数量级的路径,直接按起点和终点来缓存路径显然不现实。

但实际上,除非整张地图是个复杂的迷宫,大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上,整条路径和你从客厅出发是高度重叠的;仅有出家门前的那一小段略有

查看全文: http://www.udpwork.com/item/17517.html

+0  并发编程的核心技术 – 多版本(Multi Version)

Tag: C/C++语言编程 | Computer System | 分布式 | 数据库 | 算法
ideawu 发于 2021年04月17日 18:20 | 点击: 379 | 展开摘要
在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.

我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就

查看全文: http://www.udpwork.com/item/17461.html

+0  如何实现和优化 SVM(支持向量机)?

Tag: 人工智能 | AI | 算法
skywind 发于 2019年04月08日 14:50 | 点击: 333 | 展开摘要
学习 SVM 的最好方法是实现一个 SVM,可讲理论的很多,讲实现的太少了。

假设你已经读懂了 SVM 的原理,并了解公式怎么推导出来的,比如到这里:

SVM 的问题就变成:求解一系列满足约束的 alpha 值,使得上面那个函数可以取到最小值。然后记录下这些非零的 alpha 值和对应样本中的 x 值和 y 值,就完成学习了,然后预测的时候用:

上面的公式计算出 f(x) ,如果返回值 > 0 那么是 +1 类别,否则是 -1 类别,先把这一步怎么来的,为什么这么

查看全文: http://www.udpwork.com/item/17399.html
|<<<1234567>>>| 一共12页, 143条记录