Greedy Algorithm

Program Information

Name: Greedy Algorithm
Domain: Optimization algorithms
Functionality: Greedy Algorithm on Set Covering Problem
Input: A set of keys, $K = \{k_1,k_2,\ldots ,k_x\}$ and a set of locks, $L=\{l_1,l_2,\ldots ,l_y\}$ where $x,y>0$.For every pair $(k_m,k_n) \in (K \times L)$, we define $r(m,n)$ as a relationship between key $k_m$ and lock $l_n$ such that $r(m,n)=1$ if $k_m$ opens lock $l_n$ and $r(m,n)=0$,otherwise. Initially, the relationship $r(m,n)$ is stored in the $(m,n)^{th}$ element of matrix $M, \forall m, 1 \leq m \leq x, \forall n, 1 \leq n \leq y$. Matrix $M$ can be presented as follows: $$M=\left( \begin{array}{ccccc} r(1,1) & r(1,2) & \cdots & r(1,y) & k_1 \\ r(2,1) & r(2,2) & \cdots & r(2,y) & k_2 \\ \vdots & \vdots & \cdots & \vdots & \vdots \\ r(x,1) & r(x,2) & \cdots & r(x,y) & k_x \\ l_1 & l_2 & \cdots & l_y & \\ \end{array}\right)$$ The number of locks opened by a key k is referred as numOpenL(k). We use $M$ and $M'$ to denote a source test case and the follow-up test case respectively.To illustrate those MRs further, we reuse the KL-example with M KL as the source test case.  KL-example:Suppose there is a set of keys,$\{k_1 ,k_2 ,\cdots ,k_5 \}$, a set of locks, $\{l_1 ,l_2 ,\cdots ,l_9 \}$, and the associated input matrix $M_{KL}$ to $GA$ is as follows:  $$M_{KL}= \left( \begin{array}{cccccccccc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & k_5 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & \\ \end{array}\right)$$
Output: We also use $O$ and $O'$ to denote the output of the source and follow-up test cases, respectively and numO to denote the size (the number of elements) of $O$.

Reference

 Testing of Heuristic Methods: A Case Study of Greedy Algorithm https://doi.org/10.1007/978-3-642-22386-0%5C_19

MR Information

MR1------ Interchanging columns related to the key-lock relationship

Description: $$M'(\textrm{MR1})= \left( \begin{array}{c >{\columncolor[gray]{.9}}cc >{\columncolor[gray]{.9}}ccccccc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & k_1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & k_2 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & k_5 \\ l_1 & l_4 & l_3 & l_2 & l_5 & l_6 & l_7 & l_8 & l_9 & \\ \end{array}\right)$$
Property: interchanging columns related to $l_2$ and $l_4$ in $M_{KL}$
Source input: $M_{KL}$
Source output: $O==[k_4,k_2,k_5,k_3]$
Follow-up input: $M'$(MR1)
Follow-up output: $O'==[k_4,k_2,k_5,k_3]$
Input relation:
Output relation: $O'=O=[k_4,k_2,k_5,k_3]$
Pattern:

MR2------ Adding a useless key row

Description: $$M'(\textrm{MR2})= \left( \begin{array}{cccccccccc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & k_5 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & k_6 \\ l_1 & l_2 & l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & \\ \end{array}\right)$$
Property: adding a row corresponding to the useless key $k_6$ in $M_{KL}$
Source input: $M_{KL}$
Source output: $O==[k_4,k_2,k_5,k_3]$
Follow-up input: $M'$(MR2)
Follow-up output: $O'==[k_4,k_2,k_5,k_3]$
Input relation:
Output relation: $O'=O=[k4,k2,k5,k3]$
Pattern:

MR3------ Adding an insecure lock column

Description:  $$M'(\textrm{MR3})= \left( \begin{array}{ccccccccc>{\columncolor[gray]{.9}}cc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 &k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 &k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 &k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 &k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 &k_5 \\ l_1 & l_2 & l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & l_{10} & \\ \end{array}\right)$$
Property: adding a column corresponding to the insecure lock $l_10$ in $M_{KL}$
Source input: $M_{KL}$
Source output: $O==[k_4,k_2,k_5,k_3]$
Follow-up input: $M'$(MR3)
Follow-up output: $O'==[k_4,k_2,k_5,k_3]$
Input relation:
Output relation: $O'=O=[k4,k2,k5,k3]$
Pattern:

MR4------ Rearranging rows corresponding to the selected keys on top while preserving their order

Description: $$M(\textrm{MR4})= \left( \begin{array}{cccccccccc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & k_4 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & k_2 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & k_5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & k_1 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & \\ \end{array}\right)$$
Property: rearranging $M'$(MR4) from $M_{KL}$
Source input: $M_{KL}$
Source output: $O==[k_4,k_2,k_5,k_3]$
Follow-up input: $M'$(MR4)
Follow-up output: $O'==[k_4,k_2,k_5,k_3]$
Input relation:
Output relation: $O'=O=[k4,k2,k5,k3]$
Pattern:

MR5------ Adding a combined key of two consecutively selected keys

Description: $$M(\textbf{MR5})= \left( \begin{array}{ccccccccc >{\columncolor[gray]{.9}} c >{\columncolor[gray]{.9}}cc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 &k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 &k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 &k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 &k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 &k_5 \\ 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 &k_6 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & l_{10} & l_{11} \\ \end{array}\right)$$
Property: appending $k_6$ — a combined key of $k_2$ and $k_5$ — in $M_{KL}$ and then appending two exclusive locks to $k_4$ ($l_{10}$ and $l_{11}$)
Source input: $M_{KL}$
Source output: $O=[k4,k2,k5,k3]$
Follow-up input: $M'$(MR5)
Follow-up output: $O'=[k_4,k_6,k_3],k_6 = O'[2]$
Input relation:
Output relation: $O'-k_6 = (O-k_2)-k_5$
Pattern:

MR6------ Excluding a selected key other than the first selected key while preserving the order of the remaining selected keys

Description: $$M(\textbf{MR6})= \left( \begin{array}{cccccccccc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & k_5 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & \\ \end{array}\right)$$
Property: excluding $k_5$ of $M_{KL}$ in $O'$
Source input: $M_{KL}$
Source output: $O=[k4,k2,k5,k3]$
Follow-up input: $M'$(MR6)
Follow-up output: $O'=[k_4,k_2,k_3]$
Input relation:
Output relation: $O'=O-k_5$
Pattern:

MR7------ Deleting a selected key while preserving the order of the remaining selected keys

Description: $$M(\textbf{MR7})= \left( \begin{array}{c >{\columncolor[gray]{.7}}ccccc >{\columncolor[gray]{.7}}c >{\columncolor[gray]{0.7}}cc >{\columncolor[gray]{0.9}}c >{\columncolor[gray]{0.9}}cc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & k_5 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & l_{10} & l_{11} \\ \end{array}\right)$$
Property: deleting $k_3$ in $M_{KL}$
Source input:  $M_{KL}$
Source output: $O=[k4,k2,k5,k3]$
Follow-up input:  $M'$(MR7)
Follow-up output: $O'=[k_4,k_2,k_5]$
Input relation:
Output relation: $O'=O - k_3$
Pattern:

MR8------ Adding an exclusive lock to an unselected key

Description: $$M(\textbf{MR8})= \left( \begin{array}{ccccccccc >{\columncolor[gray]{.9}}cc} 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & k_5 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & l_{10} \\ \end{array}\right)$$
Property: adding an exclusive lock $l_{10}$ to $k_1$ — a key which is unselected in $O$
Source input: $M_{KL}$
Source output:  $O=[k4,k2,k5,k3]$
Follow-up input: $M'$(MR8)
Follow-up output: $O' = [k_1,k_2,k_3,k_5]$
Input relation:
Output relation: $k_1 \in O',k_4 \notin O'$
Pattern:

MR9------ Adding an exclusive lock to an unselected key while preserving the order of the previously selected keys

Description: $$M(\textbf{MR9})= \left( \begin{array}{ccccccccc >{\columncolor[gray]{.9}}cc} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & k_1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & k_2 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & k_3 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & k_4 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & k_5 \\ l_1 & l_2& l_3 & l_4 & l_5 & l_6 & l_7 & l_8 & l_9 & l_{10} \\ \end{array}\right)$$
Property: adding an exclusive lock $l_{10}$ to $k_1$ and resetting $k_1$
Source input: $M_{KL}$
Source output:  $O=[k4,k2,k5,k3]$
Follow-up input:  $M'$(MR9)
Follow-up output: $O'=[k_4,k_2,k_1,k_3,k_5]$
Input relation:
Output relation: $O'-k_1 = O$
Pattern:
Insert title here