实践

由于要数学建模中需要解决一个三维装箱的问题，我经过搜寻选定了张德富教授等在计算机学报上发表的《求解三维装箱问题的混合模拟退火算法》这篇论文作为解决问题的理论基础。 该论文的摘要如下： 提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟 退火 算法 .三维装箱问题要求装载给定箱子集合的一个子 集到容器中 , 使得被装载 的箱子总体 积最大 .文中介绍 的 混合 模拟退火算法基于三个重要算法 :(1)复合块生成算法 , 与传统算法 不同的是文中提出的复合块 不只包含单 一 种类的箱子 , 而是可以在一定的限制条件下包含 任意种类的箱子 .(2)基础启发式算法 , 该算法 基于块装 载 , 可以 按 照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础, 将装载序列作为可行 放置 方案的编码 , 在编码空间中采用模拟退火算法进行搜 索以寻找问题的近似最 优解 .文 中采用 1 50 0 个弱异构 和 强异构的装箱问题数据对算法进行测试 .实验结 果表明 , 混合模拟退火算法的填充率超过了目前已知的 优秀算法 . DOI 号 :10.3724/ SP .J.1016 .2009.02147 本文算法实现其计算结果 该实现的核心函数 MATLAB 代码 function \[solution, newPlan, rate\] = container\_packeting(bcon, plan, blockTable, blockNeed) %UNTITLED2 根据大小容器的规格以及小容器的数量信息计算出打包的方案 % bigContainer 大容器的规格向量 \[L W H\] % smallContainers 小容器的规格矩阵\[L W H;\] % smallContainersNumber 小容器的数量向量 \[n\] solution = {}; newPlan = \[\]; searchDeep = 40960; clf; draw\_container(\[0,0,0\], bcon); % 剩余空间栈 lspace\_s = get\_stack(); % 空隙栈 iterval\_s = get\_stack(); itervalSpace\_s = get\_stack(); % 初始化剩余空间为大容器空间 lspace\_s = stack\_push(lspace\_s, get\_space(\[0,0,0\], bcon)); psCount = 0; while lspace\_s.count > 0 psCount = psCount + 1; % 从剩余空间栈中取得可用的剩余空间 lspace = stack\_top(lspace\_s); lspace\_s = stack\_pop(lspace\_s); lspace\_size = lspace.size; lspace\_base = lspace.base\_point; if\_input = 0; \[blockList, blockListNeed\] = get\_block\_list(blockTable, blockNeed, lspace\_size(1), lspace\_size(2), lspace\_size(3)); theBlockNeed = NaN; find\_idx = 1; if size(blockList, 1) == 0 find\_avaliable = 0; else find\_avaliable = 1; if plan(psCount) <= size(blockListNeed, 1) theBlockNeed = blockListNeed(plan(psCount),:); find\_idx = plan(psCount); else theBlockNeed = blockListNeed(size(blockListNeed, 1),:); find\_idx = size(blockListNeed, 1); end newPlan = \[newPlan, find\_idx\]; end %% locate container if find\_avaliable == 1 newLocatedBlock = {lspace\_base, blockList(find\_idx, :), theBlockNeed{1}, theBlockNeed{2}}; solution(size(solution, 1) + 1, :) = newLocatedBlock; spaceInfo = newLocatedBlock{4}; spaceLastInfo = spaceInfo(size(spaceInfo,1), :); locateInfo = newLocatedBlock{2}; hold on; draw\_container(lspace\_base, locateInfo(1:3)); itervalSpace\_s = stack\_push(itervalSpace\_s, (1-spaceLastInfo(1)) \* prod(locateInfo(1:3))); if\_input = 1; % 剩余空间计算 % H方向剩余空间 location = lspace\_base; location(2) = location(2) + locateInfo(2); iterval\_space = get\_space(location, \[locateInfo(1) , lspace\_size(2) - locateInfo(2), locateInfo(3)\]); lspace\_s = stack\_push(lspace\_s, iterval\_space); % L方向剩余空间 location = lspace\_base; location(1) = location(1) + locateInfo(1); left\_space = get\_space(location, \[lspace\_size(1) - locateInfo(1), lspace\_size(2), lspace\_size(3)\]); lspace\_s = stack\_push(lspace\_s, left\_space); % W方向剩余空间 location = lspace\_base; location(3) = location(3) + locateInfo(3); iterval\_space = get\_space(location, \[locateInfo(1) , lspace\_size(2), lspace\_size(3) - locateInfo(3)\]); lspace\_s = stack\_push(lspace\_s, iterval\_space); end if if\_input == 1 else % 压入空隙栈 iterval\_s = stack\_push(iterval\_s, lspace); % lspace\_s = stack\_push(lspace\_s, lspace); end end rate = space\_used\_rate(bcon, solution); end function rate = space\_used\_rate(container, solution) spaceHasTotal = 0.0; for i = 1:1:size(solution, 1) mergeMessage = solution{i, 4}; for k = 1:1:size(mergeMessage,1) spaceHasTotal = spaceHasTotal + prod(mergeMessage(k, 3:5)); end end rate = spaceHasTotal / prod(container); end 箱体产生函数 function \[blockTable, boxNeedTable\] = simple\_block\_generate\_indepent(container, box, num) simBlockCount = 0; simBlockTable = zeros(256, 8); for type = 1:1:size(box, 1) for nx = 1:1:num(type) for ny = 1:1:num(type)/nx for nz = 1:1:num(type)/ny/nx if box(type,3) \* nx < container(3) && box(type, 1) \* ny < container(1) && box(type, 2) \* nz < container(2) newSimBlock = \[box(type, :), nx, ny, nz, type, prod(box(type, :)) \* nx \* ny \* nz\]; simBlockTable(simBlockCount + 1, :) = newSimBlock; simBlockCount = simBlockCount + 1; end end end end end simBlockTable = simBlockTable(1:simBlockCount, :); simBlockTable = sortrows(simBlockTable, 8); simBlockTable = simBlockTable(:, 1:7); % 处理成启发式算法可以处理的格式 simBlockTable(:, 13) = ones(size(simBlockTable, 1), 1); simBlockTable(:, 11) = simBlockTable(:,4) .\* simBlockTable(:,3); simBlockTable(:, 12) = simBlockTable(:,5) .\* simBlockTable(:,1); % ly = ay simBlockTable(:, 8) = simBlockTable(:, 12); % lx = ax simBlockTable(:, 10) = simBlockTable(:, 11); % lz = lz0 \* nz simBlockTable(:, 9) = simBlockTable(:, 2) .\* simBlockTable(:, 6); boxNeedTable = cell(size(simBlockTable, 1), 2); for i = 1:1:size(simBlockTable, 1) boxNeedTable{i, 1} = zeros(1, size(box ,1)); boxNeedTable{i, 1}(simBlockTable(i, 7)) = simBlockTable(i, 4) \* simBlockTable(i, 5) \* simBlockTable(i, 6); boxNeedTable{i, 2} = \[simBlockTable(i, 7), 0, simBlockTable(i, 8:10)\]; end blockTable = simBlockTable(:, 8:13); blockTable(:,7) = blockTable(:, 1) .\* blockTable(:, 2) .\* blockTable(:, 3); \[blockTable, idx\] = sortrows(blockTable, \[ 7 \]); boxNeedTable = boxNeedTable(idx, :); end 箱体组合产生函数 function \[blockTable, boxNeedTable\] = complex\_block\_genrate(container, box, num, level) simBlockTable = simple\_block\_generate(container, box, num); simBlockTable(:, 13) = ones(size(simBlockTable, 1), 1); simBlockTable(:, 11) = simBlockTable(:,4) .\* simBlockTable(:,3); simBlockTable(:, 12) = simBlockTable(:,5) .\* simBlockTable(:,1); spaceUsedRateMin = 0.90; % ly = ay simBlockTable(:, 8) = simBlockTable(:, 12); % lx = ax simBlockTable(:, 10) = simBlockTable(:, 11); % lz = lz0 \* nz simBlockTable(:, 9) = simBlockTable(:, 2) .\* simBlockTable(:, 6); boxNeedTable = cell(size(simBlockTable, 1), 2); for i = 1:1:size(simBlockTable, 1) boxNeedTable{i, 1} = zeros(1, size(box ,1)); boxNeedTable{i, 1}(simBlockTable(i, 7)) = simBlockTable(i, 4) \* simBlockTable(i, 5) \* simBlockTable(i, 6); boxNeedTable{i, 2} = \[simBlockTable(i, 7), 0, simBlockTable(i, 8:10)\]; end blockTable = simBlockTable(:, 8:13); for level = 1:1:level newBlockTable = zeros(128,6); newBlockCount = 1; boxNeedCount = size(boxNeedTable, 1); for a = 1:1:size(blockTable,1) for b = a:1:size(blockTable, 1) if b == a continue; end if blockTable(a, 6) == blockTable(b, 6) % x 方向合并 if blockTable(a, 1) == blockTable(a, 5) && blockTable(a, 3) == blockTable(a, 4) && blockTable(a, 2) == blockTable(b, 2) tempBlockMerged = \[max(blockTable(a,1), blockTable(b,1)), max(blockTable(a,2), blockTable(b, 2)), blockTable(a,3) + blockTable(b,3), blockTable(a,4) + blockTable(b,4), min(blockTable(a,5), blockTable(b,5)), max(blockTable(a, 6), blockTable(b, 6)) + 1\]; rate = space\_used\_rate(tempBlockMerged(1:3), blockTable(a,1:3), blockTable(b,1:3)); if rate > spaceUsedRateMin newBlockTable(newBlockCount, :) = tempBlockMerged; boxNeedCount = boxNeedCount + 1; newBlockCount = newBlockCount + 1; boxNeedTable{boxNeedCount, 1} = boxNeedTable{a,1} + boxNeedTable{b,1}; boxNeedTable{boxNeedCount, 2} = \[boxNeedTable{a, 2}; rate, 1, blockTable(b, 1:3)\]; end end % y 方向合并 if blockTable(a, 5) == blockTable(a, 1) && blockTable(b, 5) == blockTable(b, 1) && blockTable(a, 2) == blockTable(b, 2) tempBlockMerged = \[blockTable(a,1) + blockTable(b,1), max(blockTable(a, 2), blockTable(b, 2)), max(blockTable(a, 3), blockTable(b, 3)), min(blockTable(a, 4), blockTable(b, 4)), blockTable(a, 5) + blockTable(b, 5), max(blockTable(a, 6), blockTable(b, 6)) + 1\]; rate = space\_used\_rate(tempBlockMerged(1:3), blockTable(a,1:3), blockTable(b,1:3)); if rate > spaceUsedRateMin newBlockTable(newBlockCount, :) = tempBlockMerged; newBlockCount = newBlockCount + 1; boxNeedCount = boxNeedCount + 1; boxNeedTable{boxNeedCount, 1} = boxNeedTable{a,1} + boxNeedTable{b,1}; boxNeedTable{boxNeedCount, 2} = \[boxNeedTable{a, 2}; rate, 2, blockTable(b, 1:3)\]; end end % z 方向合并 if blockTable(a,4) >= blockTable(b,3) && blockTable(a, 5) >= blockTable(b, 1) tempBlockMerged = \[max(blockTable(a,1), blockTable(b, 1)), blockTable(a, 2) + blockTable(b, 2), max(blockTable(a, 3), blockTable(b, 3)), blockTable(b, 4), blockTable(b, 5), max(blockTable(a, 6), blockTable(b, 6)) + 1\]; rate = space\_used\_rate(tempBlockMerged(1:3), blockTable(a,1:3), blockTable(b,1:3)); if rate > spaceUsedRateMin newBlockTable(newBlockCount, :) = tempBlockMerged; newBlockCount = newBlockCount + 1; boxNeedCount = boxNeedCount + 1; boxNeedTable{boxNeedCount, 1} = boxNeedTable{a,1} + boxNeedTable{b,1}; boxNeedTable{boxNeedCount, 2} = \[boxNeedTable{a, 2}; rate, 3, blockTable(b, 1:3)\]; end end end end end blockTable = cat(1, blockTable, newBlockTable(1:newBlockCount-1, :)); % 消除等价复杂块 blockTableTemp = blockTable(:, 1:5); \[~, ia\] = unique(blockTableTemp, 'stable', 'rows'); blockTable = blockTable(ia, :); boxNeedTable = boxNeedTable(ia, :); end blockTable(:,7) = blockTable(:, 1) .\* blockTable(:, 2) .\* blockTable(:, 3); \[blockTable, idx\] = sortrows(blockTable, \[ 7 \]); boxNeedTable = boxNeedTable(idx, :); end function \[rate\] = space\_used\_rate(container, box1, box2) rate = (prod(box1) + prod(box2)) /prod(container); end Main 函数 ts = 1; tf = 0.005; dt = 0.98; length = 50; maxSeq = 64; maxChoice = 1024; click = 1; tempRate = \[\]; tempRateX = \[\]; numList = \[64,64,64,64,64,64,64,128,128,128\]; container = StandardISOContainer; % \[blockTable, blockNeed\] = complex\_block\_genrate(StandardISOContainer, Packets, numList, 1); ps = ones(1, maxSeq); ps(1) = 1; \[solution, plan, rate\] = container\_packeting(container, ps, blockTable, blockNeed); best = plan; best\_rate = rate; best\_solution = solution; t = ts; while t > tf for i = 1:1:length k = randi(size(ps)); nps = ps; nps(k) = randi(maxChoice); \[solution, nplan, nrate\] = container\_packeting(container, nps, blockTable, blockNeed); % disp(\['TempPlan: ', mat2str(nplan)\]); % fprintf("TempRate: %f\\n",nrate); click = click + 1; if nrate > rate ps = nps; plan = nplan; rate = nrate; tempRateX = \[tempRateX, click\]; tempRate = \[tempRate, nrate\]; elseif rand(0, 1) > exp((nrate - rate) \* 10 / t) ps = nps; plan = nplan; rate = nrate; end if nrate > best\_rate best = nplan; best\_rate = nrate; best\_solution = solution; disp(\['BestPlan: ', mat2str(best)\]); fprintf("BestRate: %f\\n",best\_rate); end end t = (1 - t \* dt) \* t; end disp(\['BestPlan: ', mat2str(best)\]); fprintf("BestRate: %f\\n",best\_rate); figure(1) draw\_solution(container, best\_solution); figure(2) plot(tempRateX, tempRate); save Solution best\_solution best\_rate tempRateX tempRate

如果你建立了一个 Git 仓库，.gitignore 是你需要考虑的一个选项。 如果你想套用模板的话，推荐使用如下仓库地址中提供的模板： 进入仓库地址： https://github.com/github/gitignore 各种模板覆盖比较全，可以根据你的具体需求组合使用。

如果当导入外部的 SSH 公私密钥之时，可能需要在家目录下新建.ssh 文件夹并将公私密钥移动到该文件夹下。但如果没有将权限问题配置正确的话，会导致密钥无法使用的问题。 这里给出一组命令对分别配置文件夹、公私密钥的权限进行设置： % chmod 700 ~/.ssh % chmod 600 ~/.ssh/id\_rsa % chmod 600 ~/.ssh/id\_rsa.pub % chmod 600 ~/.ssh/authroized\_keys

MacOS 现在默认采用 Zsh，所以在用户家目录下寻找.zshrc 配置文件，如果没有则自行创建。 编辑.zshrc 文件，在最后加入下列代码 \# set proxy alias proxy='export all\_proxy=socks5://127.0.0.1:1234' alias unproxy='unset all\_proxy' 添加完毕后，保存，在终端输入以下命令 % source ～/.zshrc 完毕。 如果需要使用代理，则预先输入 proxy 命令。如果需要取消代理，则输入 unproxy 命令。 或者如果需要默认启用代理的话，在.zshrc 配置文件末尾添加 % export https\_proxy=http://127.0.0.1:7890 http\_proxy=http://127.0.0.1:7890 all\_proxy=socks5://127.0.0.1:7890 保存。 % source ～/.zshrc 完毕。

在 HyperV 下 Windows 系虚拟机默认就能够开启增强会话。在增强会话下可以方便地和宿主机共享剪切板与文件，并且在增强会话开启时也能够比较方便地调整分辨率。而 Ubuntu 等 Linux 系统下则默认为基本会话，分辨率的调整需要修改引导文件，而剪切板和宿主机是独立的非常不方便。 进过查找，找到了一种可以在 Ubuntu 20.04 下开启增强会话的方法，使用后有效，遂在此记录。 首先需要开启增强会话的话必须先在创建虚拟机的时候开启第二代虚拟机选项，在首次启动的时候关闭 Secure Boot。记得在安装 Ubuntu 的时候不要开启自动登录选项。 在终端下输入 % wget https://raw.githubusercontent.com/Hinara/linux-vm-tools/ubuntu20-04/ubuntu/20.04/install.sh % sudo chmod +x install.sh % sudo ./install.sh 在 Windows Power Shell 运行以下命令，然后重启。 \> Set-VM -VMName <your\_vm\_name> -EnhancedSessionTransportType HvSocket 重启后，就能看到链接虚拟机后会话已经为增强会话模式而后 Ubuntu 进入的 XRDP 登录页面，此时正常输入用户名密码即可。

安装 zsh 插件 zsh-autosuggestions 或者 zsh-syntax-highlighting 的时候，我们一般会遇到 oh-my-zsh plugin ‘xxx’ not found 的问题。现在，我们分析并解决 oh-my-zsh plugin ‘zsh-autosuggestions’ not found 与 plugin ‘zsh-syntax-highlighting’ not found 问题。 问题产生的原因是，没有把插件的代码仓库克隆到本地位置上，所以你想要的插件其实并没有被安装。 解决问题非常简单，只需要简单输入以下命令： $ git clone https://github.com/zsh-users/zsh-autosuggestions ~/.oh-my-zsh/custom/plugins/zsh-autosuggestions $ git clone https://github.com/zsh-users/zsh-syntax-highlighting.git ~/.oh-my-zsh/custom/plugins/zsh-syntax-highlighting $ source ~/.zshrc 然后，你可以重新打开 shell，可以发现问题已解决。你也可以用该方法解决其他插件的此类问题。

经过一段时间对于 Synology Drive 的版本控制功能的使用，总结出以下不建议使用版本控制的常见使用场景： Synology Drive 版本控制不适用于对音乐库与视频库的版本控制。这两种场景适合使用回收站机制来管理。因为音乐和视频库的容量变动幅度较大，在一段时间内进行大量的删除或者格式转换操作后，磁盘可用空间将迅速下降。不建议将音乐库与视频库加入到版本控制。 版本控制不适用于对于应用程序相关数据文件（例如 Docker 容器的映射目录下的相关文件）的备份，经过长期观察，版本控制对文件修改并不敏感。我往往发现经常变动的应用程序数据文件一直维持在较老的版本，并没有在应用程序对该文件作出修改后立即备份上一版本。建议使用 Cloud Sync 或者 Hyper Backup 对应用程序数据文件进行备份。 上述问题经过长期使用总结出，如果发现其他问题则会更新此文章。

介绍 手上有一张安装了 Openwrt 的 8G 的 TF 卡，根分区的容量已经不太能够满足我的使用需求了。所以开始着手扩大根分区的大小。根分区的所使用的的文件系统格式是 Ext4。首先，尝试使用 DiskGenius 等 Windows 下的工具进行扩容，很遗憾都不可以。于是准备使用 Gparted 进行扩容。由于该工具需要在 Linux 环境下运行，我不太想安装为此安装一个 Linux 发行版虚拟机所以使用 Gparted 的轻量 ISO 镜像配合 Virtual Box 虚拟机进行使用。 准备工作 首先下载安装 VritualBox 虚拟机和 VM VirtualBox Extension Pack。VirtualBox 并默认不支持 USB 外设操作，所以要安装而外后者来为 VirtualBox 添加 USB2.0、USB3.0 等外设支持。 VirtualBox 下载地址 VM VirtualBox Extension Pack 以上两者下载完后，先安装 VirtualBox。 然后安装 VM VirtualBox Extension Pack，具体在首选项界面扩展栏目中安装。 下载 GParted Live CD/USB/HD/PXE Bootable Image，下载链接。 步骤 创建虚拟机，分配单核、内存 512MB 即可，可以不创建虚拟硬盘。 在虚拟机设置界面中，在 USB 设备栏目中启用 USB 控制器，根据需要选择 USB2.0 或者 USB3.0。 在储存栏目光驱下，选择下载好的 ISO 镜像，启动虚拟机。 在第一个引导菜单中选择第一项。 而后，按步骤一次选择或者输入Dont touch keymap， 26（简体中文），0（启动 X Window 系统）。 然后就能够进入图形界面了，点击桌面上的 Gparted 工具镜像分区操作。 分区后，记得点击应用。 ...

YouCompleteMe 介绍 如果安装完YouCompleteMe并配置好后（本站有过程记录，点击这里查看），就可以使用单文件来检测代码提示效果了。但是，当 S&E 打开他的 C/C++工程时，却发现代码提示、跳转等功能不能正常使用。在查阅文档后，S&E 发现原来是 YouCompleteMe 相关的索引数据库没有建立，相关的编译选项并不正确，所以 YouCompleteMe 所使用的的 clangd 就不能将多个源文件联系起来。 建立 C/C++ VIM 代码提示索引的方法 如果是使用 CMake 建立工程，则可以在 CMakeList.txt 中加入 set( CMAKE\_EXPORT\_COMPILE\_COMMANDS ON ) 或者在命令行 cmake 后加上-DCMAKE_EXPORT_COMPILE_COMMANDS=ON也行 建立索引的原理 YouCompleteMe 读取由构建系统 CMake 生成的编译数据库（通常名字叫做 compile_commands.json），这样就可以完成对于工程文件的索引。而编译数据库包含项目中每个编译单元的编译器调用。YouCompleteMe 会寻找打开文件所在目录中的 compile_commands.json，如果没找到会递归地向上查找这个文件。如果在它找到.ycm_extra_conf.py 之前，找到了 compile_commands.json，那么它就会停止搜索，然后，让 clangd 处理接管并处理该文件中含有的标志。 在完成上述这些操作后，YouCompleteMe 的相关功能就可以正常使用了。

介绍 对于在 Vim 下的 C/C++程序编写，如果有代码提示插件会大大提高编写效率。大型 IDE 用的多了，刚回归 Vim 的 S&E 比较依赖这个。正好 YouCompleteMe 能够满足他的相关需求。索性把安装与配置的过程记录在这里，以供下次回忆使用。 除了 C/C++，YouCompleteMe 支持 Java、Go、C#、Objective-C、CUDA 等，可以说是比较强大了。但是话说，写 Java 为什么要用 Vim 呢？IDEA 貌似更好。 使用后发现这插件还支持代码跳转、引用查找、修改函数名和格式调整等操作，挺方便。 Giuhub 仓库地址：https://github.com/ycm-core/YouCompleteMe 前置条件 安装最新的 YouCompleteMe 插件需要满足一些条件 Vim 8.1 以上 并且启用了 Python3 扩展支持（本站有过程记录，点击这里查看） GCC 8 以上 或者 Clang 7 以上 Python3.6 以上编译的时候有–enable-shared 选项（一般包管理器安装都带有） 对于 Debian 10， 通过包管理器安装的 Gcc 版本为 8.3.0。 然后可以通过以下命令查看编译器版本 % cc -v 对于 python3 的版本，使用以下命令查看 % python3 --version 对于 Vim 版本，使用执行以下命令查看 % vim --version 检查完以上依赖后，也执行一下以下命令确认安装相关依赖 % sudo apt install build-essential cmake vim-nox python3-dev 安装 先确认用过了 Vim 插件管理器安装了 YouCompleteMe，推荐使用Vundle。 确认安装了 YouCompleteMe 后，进行下面的步骤 如果你想要安装所有的功能，包括 Java（JDK 8），Go、C#等代码提示功能，可以直接执行以下命令安装 ...