Jumlah minimum perjalanan belanja untuk sekelompok orang untuk membeli hadiah untuk satu sama lain

10

Kami memiliki sekelompok $n$ orang. Kami diberi daftar siapa yang harus membeli hadiah untuk siapa di dalam grup. Setiap orang mungkin perlu membeli / menerima sejumlah hadiah, atau mungkin tidak sama sekali. Dalam perjalanan berbelanja, sekelompok orang bepergian bersama ke toko yang sama, dan membeli hadiah untuk siapa saja yang tidak hadir di toko. Mereka mungkin tidak membeli hadiah untuk orang lain dalam perjalanan belanja yang sama karena itu tidak akan mengejutkan. Seseorang dapat melakukan beberapa perjalanan belanja. Kami ingin meminimalkan jumlah total perjalanan belanja yang diperlukan bagi semua orang untuk membeli semua hadiah yang mereka butuhkan.

Sebagai contoh, perhatikan kasus di mana terdapat 5 orang, dan masing-masing harus membeli hadiah untuk setiap orang dalam kelompok. Biarkan orang-orang itu diberi nomor 1 hingga 5. Ini dapat dilakukan dalam 4 perjalanan belanja, seperti yang ditunjukkan:

Perjalanan 1: 1, 2, 3 berbelanja
Perjalanan 2: 1, 4, 5 berbelanja
Perjalanan 3: 2, 4 pergi berbelanja
Perjalanan 4: 3, 5 pergi berbelanja

Bagaimana saya menyelesaikan masalah ini? Jelas bahwa input dapat diwakili oleh grafik yang diarahkan, tetapi saya tidak tahu harus ke mana dari sana. Seseorang mengemukakan masalah sampul biclique , tetapi meskipun serupa, itu tidak menjawab pertanyaan ini.

Kita dapat menganggap input sebagai grafik diarahkan pada simpul, di mana ujung berarti bahwa orang harus membeli hadiah untuk orang . Tujuannya adalah untuk menemukan satu set bikli sedemikian sehingga adalah minimal dan himpunan tepi dari grafik adalah himpunan bagian dari $G$ $n$ $(u,v)$ $u$ $v$ $(S_1,T_1),\dots,(S_k,T_k)$ $k$ $E$ . Juga, dalam memperluas definisi bicliques ke grafik berarah, biclique hanya berisi tepi yang memetakan ke . Ini berbeda dari masalah tutupan biclique karena kami tidak mengharuskan setiap biclique menjadi subgraf (kami tidak memerlukan untuk setiap ). $\cup_i (S_i \times T_i)$ $(S_i,T_i)$ $S_i$ $T_i$ $G$ $S_i \times T_i \subseteq E$ $i$

Secara khusus, saya akan menerima jawaban yang:

Menunjukkan bahwa masalah ini NP-hard atau
Menyajikan algoritma waktu polinomial yang menjawab pertanyaan ini dengan tepat (tidak ada perkiraan atau batas atas)

Sebagai catatan, saya tidak melihat masalah ini di mana pun, saya hanya ingin tahu tentang keingintahuan saya sendiri.

algorithms graph-theory set-cover Riley
sumber

2

Masalah ini NP-hard . Untuk menunjukkan ini, saya akan terlebih dahulu merumuskan kembali masalah ini (optimasi) menjadi masalah keputusan. Kemudian, saya merumuskan kembali masalah itu menjadi masalah yang setara, yang darinya cukup sederhana untuk mendapatkan pengurangan dari masalah color, yang merupakan NP-hard untuk setiap . $k$ $k\geq 3$

Rumusan singkat masalah adalah sebagai berikut:

Diberikan orang dan grafik yang menyandikan hubungan 'pemberian hadiah' mereka, temukan jumlah minimum perjalanan yang diperlukan sehingga semua hadiah dapat dibeli tanpa merusak kejutan apa pun. $n$ $G$

Namun, ini adalah masalah pengoptimalan. NP kelas biasanya didefinisikan untuk masalah keputusan (di mana jawaban untuk setiap contoh adalah YA atau TIDAK). Varian keputusan ini adalah:

Mengingat orang dan grafik yang mengkodekan mereka 'pemberian hadiah' hubungan dan integer , membuat paling perjalanan yang cukup untuk membeli semua hadiah tanpa merusak kejutan? $n$ $G$ $t$ $t$

Saya mendefinisikan masalah menemukan -multicoring yang tepat $t$ dari beberapa grafik sebagai menemukan fungsi multicolor yang tepat , di mana adalah beberapa set 'warna' ( yaitu ) dan adalah himpunan daya (yaitu himpunan semua himpunan bagian $G=(V,E)$ $c:V\rightarrow \mathcal{P}(C)$ $C$ $t$ $|C|=t$ $\mathcal{P}(C)$ $C$ $C$ $(u\rightarrow v)\in E$ $c(u) \not\subseteq c(v)$

Saya mengklaim bahwa masalah belanja perjalanan setara dengan masalah memutuskan keberadaan suatu diarahkan -multicoloring $t$ dari grafik yang sama . $G$

Bukti : Jika kita memiliki diarahkan tepat -warna multi untuk , di mana kita mengubah nama warna sehingga maka pertimbangkan urutan perjalanan , di mana a vertex pergi berbelanja di perjalanan jika dan hanya jika . Kemudian, untuk setiap sisi , kami memiliki bahwa ada perjalanan sedemikian rupa sehingga dan , karena . Karena itu, perjalanan $t$ $c$ $G$ $C = \{1,\ldots, t\}$ $t$ $T_1,\ldots, T_t$ $v$ $T_i$ $i\in c(v)$ $(u\rightarrow v)\in E$ $T_i$ $u\in T_i$ $v\notin T_i$ $c(u) \not\subseteq c(v)$ $T_i$ cukup untuk membeli semua hadiah.

Jika kita memiliki urutan perjalanan , lalu buat fungsi multi-warna pada set warna sedemikian rupa sehingga . Kemudian, untuk setiap sisi , ada perjalanan sedemikian rupa sehingga dan (karena dapat membeli hadiah untuk pada beberapa perjalanan), yang berarti bahwa dan , jadi . $T_1,\ldots, T_t$ $c$ $C=\{1,\ldots, t\}$ $c(u) = \{ i \in \mathbb{N} | u \in T_i\}$ $(u\rightarrow v)\in E$ $T_i$ $u\in T_i$ $v\notin T_i$ $u$ $v$ $i\in c(u)$ $i\notin c(v)$ $c(u) \not\subseteq c(v)$ $\square$

Menemukan diarahkan tepat -multicoloring pada dasarnya adalah reformulasi aneh dari kasus spesifik -coloring. Oleh karena itu, saya dapat menunjukkan pengurangan waktu polinomial dari masalah : Diberi grafik tak berarah , pertama-tama ubah grafik ini menjadi grafik diarahkan , sehingga dan jika dan hanya jika atau ( dengan kata lain, kami mengubah tepi yang tidak terarah menjadi dua tepi yang diarahkan). $t$ $k$ $\binom{t}{\lfloor t/2 \rfloor}$ $G' = (V',E')$ $G=(V,E)$ $V=V'$ $(u\rightarrow v)\in E$ $(u,v)\in E'$ $(v,u)\in E'$

Pertimbangkan himpunan terbesar , sedemikian sehingga tidak ada , , sedemikian rupa sehingga . Himpunan semua subset dari ukuran , di mana, adalah set seperti itu. Oleh karena itu, ukuran maksimum dari subset tersebut adalah . $K\subset \mathcal{P}(C)$ $a,b\in K$ $a\neq b$ $a\subset b$ $C$ $\lfloor t/2\rfloor$ $t=|C|$ $\binom{t}{\lfloor t/2 \rfloor}$

Jika -multicoloring yang tepat ada untuk , maka ada pewarnaan yang tepat yang menggunakan tidak lebih dari elemen yang tidak sama dari (*) , jadi ini adalah -warna yang untuk . $t$ $G$ $\binom{t}{\lfloor t/2 \rfloor}$ $\mathcal{P}(C)\$ $\binom{t}{\lfloor t/2 \rfloor}$ $G'$

Jika ada untuk , maka ada himpunan , , sehingga dan tidak ada , , sehingga . Jadi, memiliki -multicoring diarahkan yang tepat . $\binom{t}{\lfloor t/2 \rfloor}$ $G'$ $K\subset \mathcal{P}(C)$ $|C|=t$ $|K| \geq \binom{t}{\lfloor t/2 \rfloor}$ $a,b\in K$ $a\neq b$ $a\subset b$ $G$ $t$

Oleh karena itu, ini adalah polinomial pengurangan waktu yang valid dari -coloring untuk masalah belanja hadir dengan perjalanan, yang berarti masalah belanja sekarang adalah NP-keras. Perhatikan bahwa masalah belanja saat ini adalah NP-complete, karena kita dapat memverifikasi dengan mudah jika daftar paling banyak perjalanan memungkinkan kita untuk membeli semua hadiah tanpa merusak kejutan. $\binom{t}{\lfloor t/2 \rfloor}$ $t$ $t$

(*): Jika beberapa multi-pewarnaan menggunakan lebih banyak set-warna daripada multi-pewarnaan multi- maksimal , kita dapat 'mengubah nama' sedemikian rupa sehingga ini adalah superset dari . tetap layak, karena tidak ada elemen dari yang berdekatan dengan elemen yang berbeda dari adalah masalah dan tidak ada set warna yang berdekatan satu sama lain di yang asli . Jadi, tanpa kehilangan keumuman, kita dapat mengasumsikan . $\mathcal{C}$ $\mathcal{C}^*$ $\mathcal{C}$ $\mathcal{C}^*$ $\mathcal C$ $\mathcal{C}^*$ $\mathcal{C}^*$ $\mathcal{C}$ $\mathcal{C}^* \subset \mathcal{C}$

Kemudian, perhatikan bahwa 'penggantian nama' ke setiap subset dari tidak merusak tepi antara node set warna , karena tidak mengandung elemen yang merupakan subset dari yang lain. Satu-satunya hal yang tersisa adalah untuk memastikan bahwa tepi antara dan tidak 'merusak' pewarnaan. $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal{C}^*$ $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal{C}^*$ $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal{C}^*$

Pertimbangkan hal berikut relasi pada warna-set di : dua warna-set dan yang terhubung jika dan hanya jika ada sepasang simpul sehingga memiliki warna-set dan warna-set dan . Relasi ini dapat diwakili oleh grafik tidak berarah . $R$ $\mathcal{C}\cup \mathcal{C}^*$ $A$ $B$ $a,b$ $a$ $A$ $b$ $B$ $(a,b)\in E$ $\mathcal G = (\mathcal{C}\cup \mathcal{C}^*, R)$

Pertama, kita dapat 'mengurangi' dengan mengganti pasangan mana pun yang tidak memiliki keunggulan dalam dengan satu set warna. Pewarnaan tetap tepat, karena mengubah dua rangkaian warna yang tidak berdekatan menjadi warna yang sama tidak menghasilkan tepi yang tidak valid. Sebagai hasilnya, kami telah mengurangi menjadi grafik yang lengkap. $\mathcal{C}\setminus \mathcal{C}^*$ $\mathcal G$ $\mathcal G$

Ini berarti bahwa jika memiliki jumlah set warna yang kurang atau sama dengan, pewarnaan yang diperlukan ada. Jika tidak, sama sekali tidak ada multi-pewarnaan yang tepat, karena adalah set 'non-subset' terbesar, jadi kami tidak dapat mewarnai klik ini. Oleh karena itu, multi-pewarnaan yang diperlukan tentu ada. $\mathcal G$ $|\mathcal{C}^*|$ $\mathcal{C}^*$

Seperti grafik lengkap tentang node adalah warna-mampu jika dan hanya jika kita memiliki setidaknya warna, kita memiliki orang dapat pergi berbelanja hadiah untuk satu sama lain di perjalanan jika dan hanya jika . Ini berarti secara khusus bahwa, jika , hanya membuat perjalanan sudah cukup. Jika ada lebih sedikit hadiah untuk dibeli, lebih banyak perjalanan tidak diperlukan, jadi ini adalah batasan umum pada setiap solusi. $n$ $K_n$ $n$ $n$ $t$ $\binom{t}{\lfloor t/2 \rfloor} \geq n$ $n\leq 12870$ $16$

Di bawah ini adalah 'jawaban' saya sebelumnya, yang memberikan algoritma heuristik yang tidak menjamin untuk mendapatkan yang optimal, tetapi dapat dihitung dalam waktu polinomial.

Cara lain untuk merumuskan masalah ini adalah dengan menemukan penutup grafik bipartit pada partisi untuk beberapa graf berarah dengan simpul , sehingga jumlah partisi (yaitu perjalanan), di sini , minimal. $C = \{(S_1,T_1), \ldots, (S_m,T_m)\}$ $(S_i,T_i)$ $G$ $n$ $m$

Pertama, beberapa pengamatan, sebagian berasal dari jawaban lain:

Strategi serakah, di mana kita memilih dengan grafik bipartit di mana jumlah tepi yang sama dengan adalah maksimal, tidak mengarah ke solusi optimal (Contoh counter yang kuat adalah grafik penuh dengan node, di mana strategi ini gagal, tidak peduli grafik bipartit maksimum mana yang dipilih.). $(S_i,T_i)$ $G$ $6$
Strategi serakah tidak optimal untuk grafik asiklik arbitrer, pertimbangkan grafik berikut: Baik untuk dan grafik bipartit menghilangkan tepi, tetapi hanya optimal. $S_i = \{3,5,6\}$ $S_i=\{1,3,6\}$ $4$ $\{3,5,6\}$
Algoritma serakah apa pun (optimal) tidak dapat memilih ukuran partisi yang dipilih daripada jumlah siklus ( ukuran apa pun ) 'dihilangkan' oleh partisi. Untuk melihat ini, perhatikan grafik dengan node, di mana ada satu siklus node dan setiap node dalam siklus memiliki tepi keluar tambahan menuju node tambahan , yang tidak memiliki tepi keluar (Lihat gambar di bawah untuk contoh di mana ). Pilihan serakah yang lebih memilih untuk memaksimalkan jumlah sisi atas siklus panjang akan mengirim semua simpul dalam siklus pada perjalanan pertama. Ini suboptimal, karena ini tidak menghilangkan tepi siklus dan hanya mengabaikan $n+2$ $n$ $2$ $2$ $A,B$ $n=4$ $n$ $A,B$ dan menghapus semua tepi dari siklus menghilangkan semua tepi menuju juga. Jadi setiap pilihan serakah yang lebih memilih ukuran partisi daripada menghapus siklus tidak optimal. $A,B$

Berdasarkan pengamatan ini, saya mengusulkan pilihan serakah berikut: Pilih sedemikian rupa, sehingga jumlah siklus bahwa perjalanan ini 'menghilangkan' dari adalah maksimal dan dalam kasus ikatan, pilih partisi dengan tumpang tindih maksimum dengan antara mereka (yaitu melihat ujung-ujungnya bukan pada siklus). $(S_i, T_i)$ $G$ $G$

Karena algoritma ini tidak berbeda dari strategi serakah 'dasar' pada grafik asiklik (menghilangkan jumlah maksimum tepi pada setiap perjalanan), algoritma serakah ini karenanya tidak optimal. Namun, intuisi untuk menghilangkan siklus masih masuk akal dan merupakan perbaikan dari strategi dasar rakus, sehingga bisa menjadi heuristik yang layak.

Kadal diskrit
sumber

1

Anda menyatakan "Jika -multicoloring ada untuk , maka pewarnaan ini menggunakan tidak lebih dari elemen yang tidak sama dari ". Pernyataan ini salah. Dalam contoh sepele dari 3 node terputus terdapat 2-multicoloring , di mana . Ini adalah 2-multicoloring yang tepat yang menggunakan lebih dari elemen yang berbeda. Apakah Anda bermaksud mengatakan "Jika -multicoloring ada untuk , maka satu pewarnaan seperti itu menggunakan tidak lebih dari

t

$t$

G

$G$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2 \rfloor}$

P (C)

$\mathcal{P}(C)$

a, b, c

$a,b,c$

v

$v$

v (a) = {1}, v (b) = {2}, v (c) = {1, 2}

$v(a)=\{1\},v(b)=\{2\},v(c)=\{1,2\}$

(\binom{2}{1}) = 2

$\binom{2}{1}=2$

t

$t$

G

$G$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2 \rfloor}$ elemen tidak sama dari "?

P (C)

$\mathcal{P}(C)$

Riley

Memang itulah yang saya maksud. Cara lain untuk melihatnya adalah bahwa jika itu adalah t-multicoloring minimal (yaitu ini tidak -beberapa warna), ia menggunakan elemen . Jelas, contoh yang Anda berikan bukanlah contoh berlawanan dengan reformulasi yang benar.

G

$G$

(t - 1)

$(t-1)$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2 \rfloor}$

Kadal diskrit

Tidak menunggu Itu tidak menggunakan persis elemen , tetapi paling banyak.

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2\rfloor}$

Kadal diskrit

Saya dapat memahami bagaimana pernyataan yang direvisi itu masuk akal secara intuitif, tetapi dapatkah Anda membuktikannya? Mungkin Anda entah bagaimana dapat menunjukkan bahwa setiap t-multicoloring dapat "ditingkatkan" sehingga semua multicolors adalah elemen dari beberapa himpunan memenuhi persyaratan ukuran, dan bahwa tidak ada sedemikian sehingga .

K

$K$

a, b \in K

$a,b\in K$

a \subset b

$a\subset b$

Riley

@Riley Saya tidak yakin apa yang Anda maksud, pernyataan mana yang Anda ingin saya uraikan? Saya telah memperbarui jawaban saya sehingga menyatakan apa yang disarankan komentar asli Anda. Sisa bukti tetap tidak terpengaruh. Sedangkan untuk hubungan masalah warna multi dan asli, ide kuncinya adalah bahwa multi-warna dapat dilihat sebagai tidak memiliki 'subset' yang berdekatan. Karena subset 'non-pairwise' terbesar dari memiliki ukuran , kita mungkin juga mempertimbangkan bahwa set sebagai set warna dan kita dapatkan masalah pewarnaan.

P (C)

$\mathcal{P}(C)$

(\binom{t}{⌊ t / 2 ⌋})

$\binom{t}{\lfloor t/2\rfloor}$

Kadal diskrit

2

Saya bisa melihat bagaimana mengurangi masalah ini menjadi Grafik Pewarnaan , yang memberi Anda alat untuk memecahkan masalah (untuk contoh kecil!), Tetapi belum bagaimana mengurangi ke arah lain (yang akan membentuk kekerasan NP).

Ide dasarnya adalah membuat grafik yang berisi titik untuk setiap pembelian , dan keunggulan antara dua pembelian yang tidak dapat terjadi pada perjalanan yang sama; kami kemudian melihat untuk mengelompokkan pembelian ke dalam jumlah kelompok sekecil mungkin ("perjalanan"), sehingga tidak ada dua pembelian dalam kelompok yang sama akan bertentangan. Khususnya, jika adalah grafik berarah asli di mana ujung menunjukkan bahwa orang yang butuhkan untuk membeli orang hadiah, kemudian buat grafik tidak terarah di mana ada simpul untuk setiap edge di dan edge (tidak ) setiap kali $G = (V, E)$ $uv$ $u$ $v$ $H = (X, Y)$ $x_{uv}$ $uv$ $G$ $x_{uv}x_{vw}$ $uv$ dan keduanya (diarahkan) tepi di (jika membeli beberapa hadiah selama perjalanan, maka tidak ada yang bisa membeli hadiah selama perjalanan itu sama). Pewarnaan simpul adalah partisi dari pembelian yang diperlukan (simpul dalam ) menjadi perjalanan (warna) yang tidak bertentangan (berbagi keunggulan), dan pewarnaan simpul ukuran minimum membutuhkan perjalanan sesedikit mungkin. $vw$ $G$ $v$ $w$ $v$ $H$ $H$

Dimungkinkan untuk pergi ke arah lain (mengurangi Pewarnaan Grafik, atau masalah NP-hard lainnya, untuk masalah Anda, dan dengan demikian membangun kekerasan NP-nya), dengan mengadaptasi pengurangan dari 3SAT ke Grafik Pewarnaan (seperti, misalnya, dirinci pada hal. 10 dari catatan Jeff Erickson ), tetapi saya belum mencoba ini sendiri.

j_random_hacker
sumber

Jawaban ini brilian; hanya apa yang saya cari. Dalam menganalisis kompleksitas waktu dari algoritma ini, terdapat paling banyak simpul (hadiah) dan . Ketika saya mencari sebuah algoritma pewarnaan grafik yang saya temukan adalah untuk grafik dengan simpul. Apakah ada algoritma yang lebih efisien dalam hal ini karena ada batas atas polinomial pada jumlah tepi?

n^{2} - n

$n^2-n$

\frac{(2 n - 3) (n^{2} - n)}{2}

$\frac{(2n-3)(n^2-n)}{2}$

O (2^{n} n)

$O(2^nn)$

n

$n$

Riley

1

@Riley Mungkin tidak, menentukan -colourability, untuk grafik dengan derajat maksimum sudah NP-hard. Lihat [catatan kuliah] ini (www-sop.inria.fr/members/Frederic.Havet/Cours/coloration.pdf) untuk pengurangan dari 3-SAT ke grafik dengan derajat maksimum 3.

k

$k$

k \geq 3

$k\geq 3$

3

$3$

Kadal diskrit

@ Kadal diskret: Di mana dalam catatan kuliah mereka memberikan pengurangan seperti itu?

Mengapa jawaban ini diterima? Itu tidak menunjukkan NP-hardness atau algoritma 'paling optimal' atau bahkan algoritma yang efisien, sejauh yang saya bisa lihat.

Kadal diskrit

1

@ Discretelizard Oke. Saya tidak berpikir bahwa pertanyaan tersirat saya sedang mencari algoritma waktu P, terutama mengingat kemungkinan bahwa masalah ini NP-keras. Tetapi saya dapat membuat poin itu lebih eksplisit dalam pertanyaan awal. Saya akan menghapus tanda pada jawaban ini sebagai benar, dan menambahkan 100 poin hadiah (ternyata yang kedua harus 100 jika pada pertanyaan yang sama, tapi saya bersedia menawarkannya karena itu hanya poin internet imajiner, bukan? :)) lagi kepada siapa saja yang dapat menunjukkan masalah ini NP-hard, ATAU menemukan algoritma waktu polinomial yang menyelesaikannya.

Riley

0

Ini adalah masalah di mana saya akan sangat khawatir jika bos saya meminta saya untuk mengimplementasikan algoritma yang dijamin untuk menemukan solusi optimal dalam waktu yang wajar.

Untuk menemukan solusi yang belum tentu optimal: Mengingat sekumpulan orang dan hadiah untuk dibeli, kita dapat menghitung berapa banyak hadiah yang dapat dibeli oleh sekelompok orang dalam perjalanan berbelanja. Jadi mulailah dengan grup kosong (yang dapat membeli 0 hadiah). Untuk setiap orang yang tidak berada dalam grup, tentukan berapa banyak hadiah yang dapat dibeli jika orang itu ditambahkan ke grup. Jika ada orang yang dapat kita tambahkan tanpa mengurangi jumlah hadiah, pilih secara acak salah satu dari mereka yang menambah jumlah hadiah yang dibeli dengan jumlah maksimum, sampai menambahkan siapa pun akan mengurangi jumlah hadiah yang dibeli. Kemudian lakukan perjalanan belanja itu dan mulai dari awal sampai semua hadiah dibeli.

Saya ulangi beberapa kali, memilih orang yang berbeda "secara acak" dalam kasus yang menemukan solusi yang lebih baik.

Dalam contoh, lima orang harus membeli hadiah untuk satu sama lain, ini menemukan solusi dalam empat perjalanan, yang optimal; jika kami tidak menambahkan orang ke perjalanan yang membuat jumlah hadiah tidak berubah tanpa memperbaikinya, kami akan melakukan lima perjalanan. Dan 6 orang membutuhkan 5 perjalanan.

gnasher729
sumber

Jadi dengan kata lain, Anda dengan rakus memilih perjalanan belanja sesuai dengan berapa banyak hadiah yang akan dibeli. Bisakah Anda membuktikan bahwa prosedur ini menghasilkan jumlah minimum yang mungkin dari perjalanan belanja? Jika ya, Anda mengerjakan contoh 6 orang secara tidak benar. 6 orang hanya membutuhkan 4 perjalanan belanja: .

{{1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}}

$\{\{1,2,3\},\{1,4,5\},\{2,4,6\},\{3,5,6\}\}$

Riley

Sama sekali tidak ada bukti. Algoritma serakah + membuat pilihan acak yang berbeda akan meningkatkan peluang Anda sedikit tetapi tidak akan melakukan 4 perjalanan.

gnasher729

Saya telah menguji klaim bahwa masalahnya serakah, dan gagal. Bahkan jika Anda menguji setiap kemungkinan perjalanan belanja daripada menambahkan orang satu per satu, Anda masih mendapatkan 5 perjalanan: . Pendekatan rakus ingin perjalanan belanja kedua untuk membeli 9 hadiah, tetapi dalam solusi yang optimal perjalanan belanja kedua membeli 8 hadiah (dengan asumsi itu berjalan dalam urutan yang tercantum di atas).

{{1, 2, 3}, {4, 5, 6}, {1, 4}, {2, 5}, {3, 6}}

$\{\{1,2,3\},\{4,5,6\},\{1,4\},\{2,5\},\{3,6\}\}$

Riley

Bahkan, pendekatan serakah bahkan tidak menyelesaikan kasus 5 orang dalam 4 perjalanan belanja baik: .

{{1, 2}, {3, 4}, {5}, {1, 3}, {2, 4}}

$\{\{1,2\},\{3,4\},\{5\},\{1,3\},\{2,4\}\}$

Riley

-1

Asumsikan bahwa Anda memesan orang berdasarkan dari siapa mereka menerima (orang tua), dan kepada siapa mereka memberikan (anak). Karena setiap orang memberikan satu hadiah dan menerima satu hadiah, fungsi orangtua-anak adalah satu-ke-satu.

Anda tidak pernah ingin memasukkan orang tua dan anak ke dalam kelompok yang sama. Anda mulai dengan acak orang dan ketertiban semua orang sesuai, sehingga , dll Anda menempatkan semua menjadi satu kelompok, dan semua ke kelompok lain. Untuk orang terakhir , jadi Anda tidak ingin orang ini berada di grup yang sama dengan . Jika adalah genap, itu bukan masalah. Selain itu, Anda memerlukan satu grup tambahan, yang dapat berupa dengan sendirinya, dalam kasus yang paling sederhana. $p_1$ $child(p_1)=p_2$ $p_{odd}$ $p_{even}$ $p_n=parent(p_1)$ $p_1$ $n$ $p_n$

Algoritma ini mengasumsikan semua orang terhubung. Tapi itu tidak perlu terjadi. Jika ada beberapa siklus terputus, dengan kata lain, jika pada titik tertentu, mana , maka Anda menyelesaikan lingkaran itu dan mulai dengan yang baru, mengikuti algoritma yang sama. Selama Anda tidak menggabungkan peluang dan bahkan dari siklus yang sama, Anda dapat menggabungkan siklus terputus. $p_k=parent(p_1)$ $k!=n$

Algoritma ini berakhir dengan paling banyak 2 putaran (untuk genap ) dan 3 putaran (untuk ganjil ). $n$ $n$

ilke444
sumber

Tampaknya pendekatan ini hanya menyelesaikan masalah untuk kasus di mana setiap orang memberikan satu hadiah dan menerima satu hadiah, yaitu, di mana grafik adalah permutasi. Saya tidak yakin bahwa pertanyaan itu dimaksudkan hanya untuk menanyakan tentang kasus khusus itu - mari kita lihat apa yang OP katakan tentang itu.

DW

Itu benar, solusi saya adalah untuk sub-kasus dari masalah di mana .

\forall i, f a n_i n (v_{i}) = f a n_o u t (v_{i}) = 1

$\forall i, fan\_in(v_i)=fan\_out(v_i)=1$

ilke444

Ya, saya tidak meminta permutasi secara khusus. Silakan lihat pertanyaan yang diperbarui di mana saya mengklarifikasi beberapa hal.

Riley

Jumlah minimum perjalanan belanja untuk sekelompok orang untuk membeli hadiah untuk satu sama lain

Jawaban: