Saat menguji n item, bagaimana cara menutupi semua t-subset dengan sesedikit mungkin s-subset?

Masalah ini muncul dari pengujian perangkat lunak. Masalahnya agak sulit dijelaskan. Pertama saya akan memberikan contoh, kemudian mencoba untuk menggeneralisasi masalah.

Ada 10 item yang akan diuji, katakan A ke J, dan alat pengujian yang dapat menguji 3 item sekaligus. Urutan item dalam alat pengujian tidak masalah. Tentu saja, untuk pengujian menyeluruh, kami membutuhkan kombinasi item.$^{10}C_{3}$

Masalahnya lebih kompleks. Ada kondisi tambahan bahwa sekali sepasang barang telah diuji bersama, maka pasangan yang sama tidak perlu diuji lagi.

Misalnya, setelah kami melakukan tiga tes berikut:

ABC

ADE

BDF

kita tidak harus mengeksekusi:

ABD

karena pasangan A, B ditutupi oleh kasus uji pertama, A, D ditutupi oleh yang kedua, dan B, D ditutupi oleh yang ketiga.

Jadi masalahnya adalah, berapa jumlah minimum kasus uji yang perlu kita pastikan bahwa semua pasangan diuji?

Untuk menggeneralisasi, jika kita memiliki n item, s dapat diuji pada saat yang sama, dan kita perlu memastikan bahwa semua t tupel yang mungkin diuji (seperti s> t), berapa jumlah minimum kasus uji yang kita butuhkan dalam syarat n, s dan t?

Dan akhirnya, apa algoritma yang baik untuk menghasilkan kasus uji yang diperlukan?

Desain blok yang Anda inginkan (untuk menguji 3 hal sekaligus, dan mencakup semua pasangan) disebut sistem triple Steiner . Ada sistem triple Steiner dengan tiga kali lipat setiap kali mod , dan algoritma dikenal untuk membangun ini. Lihat, misalnya, pertanyaan MathOverflow ini (dengan tautan ke kode Sage yang berfungsi!). Untuk lain , Anda dapat membulatkan ke mod , dan menggunakan modifikasi sistem triple ini untuk untuk mencakup semua pasangan untuk .$\frac{1}{3} {n \choose 2}$$n \equiv 1 \mathrm{\ or\ } 3$$6$$n$$n' \equiv 1 \mathrm{\ or\ } 3$$6$$n'$$n$

Jika Anda menginginkan konstruksi terbaik untuk lain , jumlah tiga kali lipat yang diperlukan adalah yang mencakup nomor , dan diberikan oleh entri ini dalam ensiklopedia online urutan bilangan bulat. Tautan ini ke La Jolla Covering Repository yang memiliki repositori yang bagus. Ensiklopedia online urutan bilangan bulat memberikan rumus dugaan untuk ; jika rumus ini berlaku, secara intuitif itu berarti mungkin ada cara algoritmik yang baik untuk membangun penutup ini, tetapi karena rumus ini terkira, jelas bahwa tidak ada yang tahu saat ini.$n$ $C(n,3,2)$$C(n,3,2)$

Untuk angka penutup yang tinggi, penutup yang baik lebih sulit ditemukan daripada untuk , dan repositori akan memberikan solusi yang lebih baik daripada algoritma efisien yang dikenal.$C(n,3,2)$

Bentuk grafik tidak berarah di mana setiap simpul adalah sepasang item, dan di mana ada tepi antara dua simpul jika mereka berbagi item yang sama. Dengan kata lain, mana dan . Grafik memiliki simpul , dan setiap simpul memiliki insiden tepi .$G$$G=(V,E)$$V=\{\{a,b\} : a,b \in \text{Items} \land a\ne b\}$$E=\{(s,t) : s,t \in V \land |s\cap t|=1\}$${n \choose 2}$$2n-4$

Maka salah satu pendekatan akan menemukan matching maksimum di . Algoritma Edmonds dapat digunakan untuk menemukan pencocokan maksimum dalam waktu polinomial. Jika Anda beruntung, ini akan memberi Anda pencocokan sempurna, dan kemudian Anda baik. Setiap tepi dalam pencocokan berhubungan dengan kasus uji . Karena setiap titik adalah kejadian dengan satu sisi dalam pencocokan sempurna, Anda telah mencakup semua pasangan, menggunakan test case, yang berada dalam faktor optimal. Jika Anda tidak mendapatkan kecocokan yang sempurna, tambahkan beberapa test case lagi sesuai kebutuhan untuk mencapai cakupan penuh.$G$$(\{A,B\},\{B,C\}) \in E$$A B C$${n \choose 2}/2$$1.5$

Dalam kasus dan Anda harus melakukan setidaknya tes, karena ada pasangan dan setiap tes mencakup 3 pasang. Itu berarti bahwa Anda dapat melakukan hal-hal sepele dan melakukan tes , dan hanya menjadi faktor 3 lebih buruk daripada yang optimal.$s=3$$t=2$${n \choose 2}/3$${n \choose 2}$${n \choose 2}$

Jika Anda benar-benar memprogram ini, maka cara untuk mengoptimalkan ini bisa dengan terlebih dahulu memilih beberapa tes angka secara acak, dan kemudian lakukan brute force pada pasangan yang tidak tercakup oleh tes sejauh ini.

---

Untuk umum dan , ada batas yang lebih rendah dari tes . Untuk batas atas, saya mengklaim sudah cukup untuk membuat menguji.$s$$t$${n \choose t}/{s \choose t}$$C \cdot \frac{{n \choose t}}{s \choose t}\cdot {\log({n \choose t})} \leq O(t \cdot (\frac{n-t}{s-t})^t \log(n))$

Mari kita lihat apa yang terjadi, kita memilih tes secara acak. Jika Anda memilih -tuple secara acak, maka untuk tetap -tuple , kita memiliki . Karenanya, jika kita memilih tes secara acak, maka$s$$S \subseteq [n]$$t$$X \subseteq [n]$$\Pr[X \subset S] = \frac{{n-t \choose s-t}}{{n \choose s}}$$C \cdot {n \choose t} \cdot {\log({n \choose t})}$

$$\Pr[X \text{ does not belong to any of them}] = \left(1 - \frac{{n-t \choose s-t}}{{n \choose s}}\right)^{C \cdot {n \choose t} \cdot {\log({n \choose t})}} \leq \exp \left(-C \frac{{n-t \choose s-t}{n \choose t}}{{n \choose s}{s \choose t}} \cdot \log({n \choose t})\right) = \exp(-C \log{n \choose t})\leq 1/{n \choose t}.$$

Oleh karena itu, dengan ikatan terikat, setelah tes acak semua -tupel akan dibahas.$O(t \cdot (\frac{n-t}{s-t})^t \log(n))$$t$