仓库管理员的最优入库方案问题

mathe

现在我们同样以m=13,n=8作为例子来手工计算。为了描述方便，还需要定义几个术语。
边的子孙树—— 边的白端子树和黑端子树中不含根结点者，即边的子端子树。也称为边的子端的子孙树。
边的白/黑端子树谱表T=（边的权重 r，白/黑端子树所含黑点数 B，白/黑端树所含白点数 W），简称为边谱。
为了区别白端和黑端，在黑端谱表中 r 取负值。所以黑白谱表中的参数统一成立关系式 r=8W-13B.
   
好了，下面可以开始计算了。

1、先计算出所有可能的谱，通过解不等式-8≤r=8W-13B≤8, 0<W<13, 0≤B≤8可得。

1. {r,w,b}/.Solve[8 >= r==8w - 13 b >= -8 && 0 <w<13 && 0<= b <=8, {r, b,   w}, Integers]
   
2. out[1]={{-8, 8, 12}, {-7, 3, 4}, {-6, 6, 9}, {-5, 1, 1}, {-4, 4, 6}, {-3, 7, 11}, {-2, 2, 3}, {-1, 5, 8},
   
3. {1, 3, 5}, {2, 6, 10}, {3, 1, 2}, {4, 4, 7}, {5, 7, 12}, {6, 2, 4}, {7, 5, 9}, {8, 0, 1}}

复制代码

其中B+W较小的谱容易确定对应边的层级：
一级边，叶柄，权重为8, T=(8,0,1)，相应的黑端谱 (-8, 8, 12)必含根结点，舍去。
二级边，子端权汇13，所以只够长出 1 条一级边，r=13-8=5, T=(-5,1,1)，相应的白端谱 (
三级边，子端权汇8, 也只够长出 1 条二级边，r=8-5=3, T=(3,1,2）
四级边，子端权汇13, 设可长出 a 条 一级边， b条三阶边，则T=(8a+3b-13, b+1, a+2b)
    a=1时，b=1, 有 T=(-2, 2, 3)
    a=0时，b=2, 则 T=(-7, 3, 4)
                 b=3, 则 T=(-4, 4, 6)
                 b=4, 则 T=(-1, 5, 8)
    得四级边4种. 显然，树至少包括 4 个层级的边，所以一、二、三级边的B+W较大端的子树必含有根结点，对应的谱(-8, 8, 12), (-3, 7, 11), (5, 7,12)舍弃。
(-2, 2, 3)为四级边，对应的 白端(2, 6, 10）和通过一个白点对接的 (-6, 6, 9)都不是四级边，两者都必含根结点，舍去。

2、如果四级边是顶级边的话
假定从根结点 (白点，权汇为8) 伸出二级边和各种四级边的数目分别为`\{x_1, x_2, x_3, x_4, x_5\}=:X`，
通过统计根结点各边参数可以得到 3 个方程（由于存在赋权公式，只有两个独立方程）,为了简化公式输入写成矩阵形式：
\[\begin{pmatrix}5&2&7&4&1\\1&2&3&4&5\\1&3&4&6&8\end{pmatrix}\cdot X^\tau=\begin{pmatrix}8\\8\\12\end{pmatrix}\]容易解得上述方程仅有以下 5 解
     (0,0,0,2,0),  (0,0,1,0,1), (0,2,0,1,0),  (0,4,0,0,0)， (1,1,0,0,1)

mathe

2、如果五级边为顶级边
       将上楼方程中的等号全都变成 < 符号 ,解不等式。由于至少有 2 条顶级边，而一个顶级边至少生出一条四级边，所以不等式至少可以加强为
\[\left\{\begin{split}5x_1+2x_2+7x_3+4x_4+x_5&=8-r\le7\\x_1+2x_2+3x_3+4x_4+5x_5&=B\le5\\x_1+3x_2+4x_3+6x_4+8x_5&=W-1\le8\end{split}\right.\]这个不等式共有以下6个解：
(r, B, W):{x1,x2,x3,x4,x5}
(1, 3, 5): {0, 0, 1, 0, 0}, {1, 1, 0, 0, 0}
(4, 4, 7): {0, 0, 0, 1, 0}, {0, 2, 0, 0, 0},
(6, 2, 4): {0, 1, 0, 0, 0}
(7, 5, 9): {0, 0, 0, 0, 1}
这就得到了4型、6种顶级的五级边（同型可以互相转换）。
      假定根结点 (黑点，权汇13) 伸出的各种一、三、五级边的数目分别为`\{x_1,x_2,x_3,x_4,x_5,x_6\}=:X`, 仿上得到 3 个方程,
\[\begin{pmatrix}8&3&1&4&6&7\\0&1&3&4&2&5\\1&2&5&7&4&9\end{pmatrix}\cdot X^{\tau}=\begin{pmatrix}13\\7\\13\end{pmatrix}\]这个不定方程共有以下6个解：
{0, 0, 0, 0, 1, 1},  (唯一解）
{0, 0, 1, 0, 2, 0}, （有2个同型解）
{0, 1, 0, 1, 1, 0}, （有2个同型解）
{0, 2, 1, 0, 1, 0}, （有2个同型解）
{1, 0, 1, 1, 0, 0}, （有4个同型解）
{1, 1, 2, 0, 0, 0},  ( 有3个同型解)

3、六级以上的边为顶级边
    到五级边时，我们发现所有的子孙树谱都已经用到了，所以其中必有一些谱具有层级更高的异构子树。
我们已得到了所有的可用谱表达的解，但是其中有些谱解对应了多种结构的树。

mathe

现在有可以改进的方法。
i)列出下面方程的所有非负整数解
$n-m<1*x_1+2*x_2+...+m*x_m<=n$
ii)列出下面方程的所有非负整数解
$0<1*y_1+2*y_2+...+(m-1)*y_{m-1}<m$
iii)对于所有整数k,$0<=k<=m$,求出整数$u_k,v_k$使得$u_k*m-v_k*n=k$而且$0<=u_k<n,0<=v_k<m$，记为四元组$(1,k,u_k,v_k)$
  对于所有整数k,$0<=k<m$,求出整数$s_k,t_k$使得$s_k*n-t_k*m=k$而且$0<=s_k<m,0<=t_k<n$,记为四元组$(0,k,s_k,t_k)$
并且将上面的所有四元组根据后面两个元素进行任意偏续排序，也就是如果$(a_1,b_1,c_1,d_1)$和$(a_2,b_2,c_2,d_2)$中，如果$c_1<=c_2,d_1<=d_2$而且至少一个等号不成立，那么$(a_1,b_1,c_1,d_1)$排在前面。第一个四元组必然为$(1,m,1,0)$
然后对于每个四元组我们需要计算一个计数C(a,b,c,d)，首先对于第一个四元组$C(1,m,1,0)=1$,其余初始化为0
然后对于每个四元组$(a,b,c,d)$按顺序计算
如果a=0,对于i)中，所以结果为$n-b$的解$(x_1,x_2,...,x_m)$，计算$C(1,1,*,*)^{x_1}*C(1,2,*,*)^{x_2}*...*C(1,m,*,*)^{x_m}$,并且对所有这些结果累加，赋予C(a,b,c,d)
同样对于a=1,对于ii)中，所有结果$m-b$的解作类似计算得出C(a,b,c,d)
最后，我们需要计算C(0,0,n,m)和C(1,0,m,n),然后相加即可

wayne

n=3时，`(n-1)^2=4`, 只有3*4这一种基本情况。我穷举了一下，发现排除同构解，最优的只有两种已知形式：

3     0     0     1     0     3     0     1     0     0     3     1

3     0     1     0     0     3     0     1     0     0     2     2

左边的就是辗转相除法的解，右边的就是10#那种在n=3时的样子。

mathe

基本情况包括5*4, 7*4和9*4三种。
最后的9*4 也可以从基本情况中除去，因为除了10#的那种特解，其它解可由5*4的树加叶得到。
7*4可以降为4*3，因为它的解至少有（7-4+1）=4片叶子，而任意两叶皆不同蒂，因4+4>7(黑点的总权)，可见所有黑点都是叶蒂。

所以剩下只需要讨论5*4一种情况。
5*4有两种情况不论自明：一是4叶树，必是辗转相除法的结果，二是双叶树，就是一字长蛇阵，独一无二。
剩下3叶树一种情况，就是一个Y字形，由于三条臂长（边数）两两之和皆为偶数，故三臂皆偶，总和为8，只有2+2+4一解。
所以5*4恰好3解。

先去掉所有叶结点，余下图是4个黑点和若干个白点（最多三个）构成的树（黑白点不相邻）。
而它们之间的边的权全部是1，2，3之一，而且每个白点各边权之和为4，每个黑点各边权之和模41余1，于是给定图，我们通过求解同余方程就可得出各边的权，由此就可以得出5*4的解的数目。

mathe

7*4可以降为4*3的原理可以推广到 (2n-1)* n 降为 n*( n-1)。
还可以进一步推广到 (kn-r)*n 降为 (kn-n-r)*n, 其中2≤k≤(n-2), 1≤ r ≤(k-1).

只需要证明树G(E, kn-r, n)的 n 个黑点都是叶蒂。用反证法。假定至少有一个黑点不是叶蒂。
由于 m=kn-r<kn, 所以一个蒂上最多 k-1片叶子。
按假设叶蒂数最多 (n-1)个，所以叶片数≤(k-1)(n-1).
但从10#我们知道叶片数≥m-n+1=kn-r-n+1=(k-1)(n-1)+(k-r) >(k-1)(n-1)，矛盾。

比如，n=5时， 基本范围包括 16*5， 14*5, 13*5, 12*5, 11*5, 9*5, 8*5, 7*5, 6*5
分别取k=2, 3得9*5，14*5， 13*5， 可以从基本范围中除名，它们分别可以降为 5*4, 9*5(进一步降为5*4)和8*5.

mathe

(5,n)也好算，模5为1有5个解，模5为4唯一解，模5为2三个解，模5为3两解。所以（5，8）情况本质上俩不同解

mathe

n=5遗漏了多个构图。看来还是要用计算机穷举