一种智能终端完全图标排列方法及装置

技术领域

本发明涉及智能终端技术领域，特别涉及一种智能终端完全图标排列方 法及装置。

背景技术

在智能家居环境中，当人进入一个新的环境，会有各种需要用手机或 者智能终端去控制的设备，比如打印机，空调，电视，微波炉等智能家具， 但是设备在不同的环境中，个数类型也不一样，而且手机(有时候是平板之 类的智能终端)屏幕大小的也不一样，如何自适应的调整图标的大小和位 置，满足用户的个性化需求。因此建立如下模型的问题，假设有m种新的 设备图标被检测到(比如打印机，空调，电视等)，每一种图标(代表一种 设备比如打印机)有n中不同大小的类型可选择加载，每一种都有其相应的 用户的满意度估值。该问题是一种NP问题。

现有技术解决方法有一下几种：1)回溯法，回溯法，在包含问题的所 有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空 间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包 含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向 其祖先结点回溯。如果采用这个方法，是一个(n+1)叉树问题，随着n， m的递增算法的复杂度迅速增大。但是理论上该算法可以找到最优解，并且 一定能解决问题，对于M，n比较小的情况很容易解决。所以它不是一个通 用的解决算法。必须降低其时间复杂度。2)分治法，把问题划分为一个个 小问题，然后独立求解，最后不断地合并，最后形成最后的答案。对于此问 题解决方案行不通。3)贪心算法，该算法在选择局部最优来达到全局最优 的一个算法。而在此问题中貌似可以使用，因为在不考虑空间大小时候，选 择单位满意度最大的图标组成的显然是满意度最大。该算法很显然太过于简 单，而且也不能选择出来比较合适的图标，比如如果前面的图标太大，但是 他的宽度没有占满，而其他的又排列不下的情况，造成极大的浪费，如图 1。

发明内容

针对上述问题和不足，本发明提出了一种智能终端完全图标排列方法及 装置，该方法能够解决在智能家居环境下，各种大小与类型的图标的完全加 载问题。

为了实现上述目的，本发明采用如下技术方案予以实现：

一种智能终端完全图标排列方法，包括以下步骤：

智能终端扫描智能家居环境中的智能设备，获取所述设备的参数和智能 终端的屏幕大小，所述参数包括：设备数目、图标、图标大小和历史使用频 率；

设定或者计算设备的满意度值并在智能终端屏幕上预排列设备图标；

结合设备参数和智能终端的屏幕大小进行贪心运算，获取设备的加载序 列；

智能终端上根据设备的加载序列把设备图标排列在屏幕上，并且智能动 态加载设备图标。

作为本发明的进一步改进，所述预排列是将每一类不同大小的设备的图 标内部进行排序为矩阵行，不同类的设备图标按照单位面积满意度由高到低 排列形成矩阵列，这样就形成满意度矩阵a_mn。

作为本发明的进一步改进，所述贪心运算包括以下步骤：

1)智能终端屏幕矩阵a_mn中顺序选取第一列中x种图标，其中x<m，即 c₁₁,c₂₁,....c_x1，并且满足在大小为W×H的屏幕上排列，计算其初始满意 度m₀，初始满意度m₀等于初始X个图标的满意度之和，(关于满意度计算 公下面有)当x＝m则退出；其中a_mn表示第m种图标的第n种大小的类 型；

2)替换策略：在余下的m-x个图标中继续贪心策略，然后按照此贪心 算法选择第一个a_ij对应的图标大小S_ij满足以下条件的：

S_ij<(S_q1)，继续贪心策略选择S_tp，让S_ij+S_tp>S_q1，并且替换(改为C_q1， 其中1<q<x)为C_ij和C_tp之后，如果可以排列下，而且总的满意度有提高， 那么m₀更新成m₁；否则不替换，继续寻找，满足的则替换，循环次数加 1；其中i不等于t，并且i>x，t>x+1；总的循环次数q小于x；在替换时候 选择的S_ij,S_tp都在第X列以后，即要求i,t都大于X，也就是说在初始选的X 个图标后余下的列中选择，合适的进行替换。

3)如果循环次数小于x，那么返回步骤2)，继续执行，否则退出。

作为本发明的进一步改进，在选取满意度高的一组图标之后排列图标采 用的宽度优先策略。

作为本发明的进一步改进，所述满意度计算公式为：m＝b_ij×S_ij× 0.5+d_ij/(d_1j+d_2j+…+d_xj)×0.5；

其中，b_ij为某一种图标的单位面积满意度，S_ij为其面积，0.5是权重， d_ij是某一应用在某一短时间该应用的使用次数。

一种智能终端完全图标排列装置，包括：

获取单元，扫描智能家居环境中的智能设备，获取所述设备的参数和智 能终端的屏幕大小，所述参数包括：设备数目、图标、图标大小和历史使用 频率；

运算单元，设定或者计算设备的满意度值，结合设备参数和智能终端的 屏幕大小进行贪心运算，获取设备的加载序列；

排列单元，用于按照设备的满意度值在智能终端预排列设备图标；并根 据设备的加载序列智能动态加载设备图标；

获取单元、运算单元、排列单元依次电连接。

进一步，所述的运算单元按照以下方式运算：1)智能终端屏幕矩阵a_mn中顺序选取第一列中x种图标，其中x<m，即c₁₁,c₂₁,....c_x1，并且满足在 大小为W×H的屏幕上排列，计算其初始满意度m₀，当x＝m则退出；其中 a_mn表示第m种图标的第n种大小的类型；

2)替换策略：在余下的m-x个图标中继续贪心策略，然后按照此贪心 算法选择第一个a_ij对应的图标大小S_ij满足以下条件的：

S_ij<S_q1，继续贪心策略选择S_tp，让S_ij+S_tp>S_q1，并且替换C_q1为C_ij和C_tp之 后，如果可以排列下，而且总的满意度有提高，那么m₀更新成m₁；否则不 替换，继续寻找，满足的则替换，循环次数q加1；其中i不等于t，并且 i>x，t>x+1；总的循环次数q小于x；在替换时候选择的S_ij,S_tp都在第X列 以后，即要求i,t都大于X，也就是说在初始选的X个图标后余下的列中选 择，合适的进行替换。

3)如果循环次数小于x，那么返回步骤2)，继续执行，否则退出。

进一步，所述排列单元执行预排列是将每一类不同大小的设备的图标内 部进行排序，按照单位面积满意度由高到低排列。

进一步，所述排列单元在排列图标采用的宽度优先策略，每次运行进入 新环境进行运算，检测设备，动态加载设备，智能排列设备位置。

与现有技术相比，本发明具有以下有益的技术效果：

现有的一些解决所述NP问题的算法中，尝试了几大主要算法，并且发 现他们并不能解决该问题，或者说解决的不太好,因为这个问题的解的空间 最简单的情况n＝1,也是指数数量级。本发明的的排列方法对于现有技术的 问题提出了一个可行的算法，时间复杂度为多项式复杂度，在可控制范围 内。在贪心算法的基础上，总是寻找最大满意度的图标，同时提出了一些优 化改进使用替换策略，让算法的时间复杂度没有明显的上升情况下，避免了 贪心算法容易局部收敛的缺点。所以该算法既拥有贪心算法的优点，又有效 地防止了局部收敛的发生。完全图标的选择与排列问题的在不同的数据复杂 度时候多对应的解决方法。并且方法简单快捷，图标排列合理，用户实用性 增强。

进一步，算法的平均时间复杂度为小于x三次方。把解得空间由 下降到多项式的维度。

进一步，循环次数小于x，主要原因是替换次数更好等于x，缩小了解 空间。

本发明的装置，都是结合智能软件自带成型实现，不增加额外成本，显 示排布合理，增加了用户体验度和美观性。

附图说明

图1为图标排列不下的情况的示意图；

图2是本发明方法逻辑流程图；

图3是本发明贪心运算算法的流程图；

图4是本发明具体实施例的流程图；

图5是电脑模拟了一个手机屏幕上的排列结果图。

具体实施方式

现有技术的问题如下矩阵：

其中第一行表示第一种图标的不同大小，总共m行表示有m种图标，每一 种图标(比如第一种也就是第一行)有n种类型的图标，因此a_mn表示第m 种图标的第n种类型。

然而每一种图标中的每一个类型的图标有一个对应的满意度值(在这里 仅仅写出其对应的单位大小满意度矩阵方便后面使用)，矩阵如下：

b_ij，表示第i种图标的第j个类型的单位满意度大小。那么问题是在屏幕大 小为W×H的屏幕上寻找一组图标(每一种要么选一个，要么不选)，使得 屏幕图标的满意度之和最大，也就是让表达式：

$\underset{i=1}{\overset{m}{\Sigma }}{b}_{\mathrm{ij}}*X_{\mathrm{ij}}$

取最大值，注意X_ij取值(0或者1)表示第i种图标是否被选择，如果被选 中取值为1，否则为0。

1-3表示每一个图标的大小矩阵。

问题分析：算法分析，首先想到该问题是一种NP问题，下面予以说明 该问题的答案的可能性：

如果结果中有1种图标可以中可能的，(因为选取一种图标之后然 后再从改中图标中选择一种类型的大小图标。)

如果结果中有2种图标时候，结果可能组合有

$n^2*C_m^2;$

如果结果中有3种图标时候，结果的可能组合

$n^3*C_m^3.$

…

如果结果中有m种图标，结果可能组合有

$n^m*C_m^m;$

那么总共的答案的组合可能数目为

$(n*C_m^1+n^2*C_m^2.....+n^m*C_m^m)$

在这里做一种最简单的情况：仅仅零n＝1，那么上面式子变为

$(C_m^1+C_m^2.....+C_m^m)=2^m-1$

假设每一种可能的解结果做一对比，假设该用时间为单位1，那么总的 时间为2^m-1，即指数数量级的大小，随着m的增大算法时间复杂度迅速增 大。因此该算法是NP难问题。而对于NP难问题至今没有找到一个比较直 接的方式穷举法去解决它。

因此解决方法初步如下：

因此本发明提出了以下的算法解决方案：

如图2、图3所示，一种智能终端完全图标排列方法，包括以下步骤：

S100：智能终端扫描智能家居环境中的智能设备，获取所述设备的参 数和智能终端的屏幕大小，所述参数包括：设备数目、图标、图标大小和历 史使用频率；

S200：设定或者计算设备的满意度值并在智能终端屏幕上预排列设备 图标；

S300：结合设备参数和智能终端的屏幕大小进行贪心运算，获取设备 的加载序列；

S400：智能终端上根据设备的加载序列把设备图标排列在屏幕上，并 且智能动态加载设备图标。

所述预排列是将每一类不同大小的设备的图标内部进行排序为矩阵行， 不同类的设备图标按照单位面积满意度由高到低排列形成矩阵列，这样就形 成满意度矩阵a_mn。在选取满意度高的一组图标之后排列图标采用的宽度优 先策略。

所述贪心运算包括以下步骤：

1)智能终端屏幕矩阵a_mn中顺序选取第一列中x种图标，其中x<m，即 c₁₁,c₂₁,....c_x1，并且满足在大小为W×H的屏幕上排列，计算其初始满意 度m₀，当x＝m则退出；其中a_mn表示第m种图标的第n种大小的类型；

2)替换策略：在余下的m-x个图标中继续贪心策略，然后按照此贪心 算法选择第一个a_ij对应的图标大小S_ij满足以下条件的：

S_ij<S_q1，继续贪心策略选择S_tp，让S_ij+S_tp>S_q1，并且替换C_q1为C_ij和C_tp之 后，如果可以排列下，而且总的满意度有提高，那么m₀更新成m₁；否则不 替换，继续寻找，满足的则替换，循环次数加1；其中i不等于t，并且 i>x，t>x+1；总的循环次数1<q<x；在替换时候选择的S_ij,S_tp都在第X列以 后，即要求i,t都大于X，也就是说在初始选的X个图标后余下的列中选 择，合适的进行替换。

3)如果循环次数小于x，那么返回步骤2)，继续执行，否则退出。

这里示例性的实例进行说明，算法流程表示在图片中，如图4所示，首 先使用手机扫描环境中的设备，比如空调，打印机，加湿器，电视等。

在这个些设备中他们的满意度值与历史使用频率成正比，加上设备预先 有一个满意度，两个值以一定的权值相加就是基本满意度，具体到图标大小 再与图标的面积成正比。在这里设定：满意度量化为数字分别为1.5，1.8， 0.9，2.0(之所以是小数，因为使用频率和本身满意度权值相加所得)。图标 的大小选择为：边长为(0.5-3cm)之间的小正方形，每一个的大小不同的 图标最终满意度为面积和满意度的乘积。

屏幕的大小是4.0寸，固定81.28mm×60.96mm。

预处理之后把参数传给算法模块，然后进行贪心运算，结果算法的目的 让屏幕的满意度之和最大，结果使用排序模块进行排序，最后动态加载在手 机屏幕上图5是用电脑模拟了一个手机屏幕上的排列结果。

可以看出，按照宽度有限的规则，基本上达到了目的，两个大点的是 3×3的分别是电视和打印机，其余的两个是空调和加湿器的图标，验证符 合。

需要说明的是在满意度计算：m＝b_ij×S_ij×0.5+d_ij/(d_1j+d_2j+…+d_xj)×0.5

其中，b_ij，某一种图标的单位满意度，S_ij为其面积，0.5是权重，这第 一部分是图标的满意度，第二项是历史满意度由使用次数决定，d_ij是某一应 用在某一短时间该应用的使用次数，那么该图标的使用次数除以所有应用的 总的使用次数再乘以权重0.5就是历史满意度.在下一段时间计算中，就以这 些满意度的和为第一项，只需要算第二项简单加和即可。

以上所述，仅是本发明的较佳实施例，并非对本发明作任何限制，凡是 根据本发明技术实质对以上实施例所作的任何简单修改、变更以及等效结构 变化，均仍属于本发明技术方案的保护范围内。