文章目录

潘少的 BLOG

诗酒趁年华

分类: 算法 (6) 介绍、理解算法的文章

协同过滤Item-based算法实现电影推荐系统

摘要: 采用离线式计算推荐给每位用户的电影,采用Item-based算法并做了适当修改,
主要分两部分:

  1. 计算电影的相似度:利用调整的余弦相似度计算方法;
  2. 相似度加权求和:使用用户已打分的电影的分数进行加权求和,权值为用户未打分的各电影与打分的各电影的相似度,然后对所有相似度的和求平均。

系统详细设计

离线计算推荐电影模块

系统所用算法

本系统采用协同过滤(Collaborative Filtering)推荐算法。协同过滤推荐算法分为预测过程和推荐过程,其包括Item-based算法和User-based算法,但经查阅相关资料发现User-based算法存在两个问题:

  1. 数据的稀疏性:一个大型的电影推荐系统会有大量的电影信息,用户已打分的电影可能只占总量的很少一部分,不同用户之间电影打分的重叠性较低,导致算法无法找到一个兴趣用户;
  2. 算法的扩展性:最近邻算法的计算量会随着用户和电影信息数量的增加而增加,不适合信息量大的情况。所以本系统采用了Item-based协同过滤算法,并对其做了适当修改。

计算过程

数据库内部排序算法之两阶段多路归并排序算法实现

摘要: 两阶段归并排序算法是数据库查询的一个基础技术,在数据库应用中,常常采用“两阶段多路归并排序算法”来解决对海量数据的排序问题(这里的海量数据是指数据大小远远超过了数据库可用的主存的大小,无法将所有数据一次性的载入主存进行排序)。

前言

基于斯坦福大学的《数据库系统实现》,实现两阶段多路归并排序算法,通过merge-sort算法的实现,理解外存算法所基于的I/O模型与内存算法基于的RAM模型的区别;理解不同的磁盘访问优化方法是如何提高数据访问性能的。

首先生成一个具有10,000,000个记录的文本文件,其中每个记录由100个字节组成。实验只考虑记录的一个属性A,假定A为整数类型。记录在block上封装时,采用non-spanned方式,即块上小于一个记录的空间不使用。Block的大小可在自己的操作系统上查看,xp一般为4096 bytes。在内存分配50M字节的空间用于外部merge-sort。要求设计和实现程序完成下列功能:

  1. 生成文本文件,其中属性A的值随机产生。
  2. 对文本文件中的记录,按照属性A进行排序,其中在第二阶段的排序中每个子列表使用一

用Dijkstra算法求解无向图的最短路径

Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      

微软编程比赛里面的一道难度系数5%的编程题目如下:

image
image

Dijkstra算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用Dijkstra算法来解决这个问题。

image

ACM刷题之-内存分配(POJ-1193 )

摘要: 内存是计算机重要的资源之一,程序运行的过程中必须对内存进行分配。 经典的内存分配过程是这样进行的: 1. 内存以内存单元为基本单位,每个内存单元用一个固定的整数作为标识,称为地址。地址从0开始连续排列,地址相邻的内存单元被认为是逻辑上连续的。我们把从地址i开始的s个连续的内存单元称为首地址为i长度为s的地址片。 2. 运行过程中有若干进程需要占用内存,对于每个进程有一个申请时刻T,需要内存单元数M及运行时间P。在运行时间P内(即T时刻开始,T+P时刻结束),这M个被占用的内存单元不能再被其他进程使用。 3、假设在T时刻有一个进程申请M个单元,且运行时间为P,则: 1. 若T时刻...

算法分析:

  1. 维护一个进程的链表,每个节点存有进程开始时间t,进程运行时间p, 在内存中的首地址s,占用内存大小m,和下一节点指针。

  2. 维护一个队列,表示还没有空间运行的进程。

  3. 维护一个释放内存的最早时间nexttime,每读入一个新进程的时候,若进程开始时间不小于nexttime,表示有进程在这之前已结束(可能不止一个),将其从链表删除,并循环检测队首

世界名画陈列馆问题(回溯法)

算法问题描述:

世界名画陈列馆问题。世界名画陈列馆由m×n个排列成矩形阵列的陈列室组成。为了防止名画被盗,需要在陈列室中设置警卫机器人哨位。每个警卫机器人除了监视它所在的陈列室外,还可以监视与它所在的陈列室相邻的上、下、左、右4个陈列室。试设计一个安排警卫机器人哨位的算法,使得名画陈列馆中每一个陈列室都在警卫机器人的监视之下,且所用的警卫机器人数最少。

算法问题形式化表示

本问题的m*n的陈列室的解可表示如下图所示。其中1代表在该陈列室设置警卫机器人哨位,0表示未在该陈列室设置警卫机器人哨位。

问题描述

最为极端的情况是所有元素的值为1。那什么情况下是最优解呢?就是设置警卫机器人哨位数最少即为最优。因为每个矩阵中的值都可以为1或0,有m*n个元素,有 种可能满足约束条件的矩阵,要从 种可能中遍历找到满足约束条件的1的个数最小的矩阵。由此可见这是一个NP问题。这里的约束条件就是当某一个元素为1时,相邻的4个方向上的

ACM刷题之-POJ-1002(487-3279)

Description

Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino's by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. Yo