Algoritma yang efisien untuk masalah visibilitas vertikal

Saat memikirkan satu masalah, saya menyadari bahwa saya perlu membuat algoritma yang efisien untuk menyelesaikan tugas berikut:

Masalahnya: kita diberi kotak persegi dua dimensi dari sisi $n$ yang sisi-sisinya sejajar dengan sumbu. Kita bisa melihatnya dari atas. Namun, ada juga $m$ segmen horisontal. Setiap segmen memiliki bilangan bulat $y$ koordinat ( $0 \le y \le n$ ) dan $x$ koordinat ( $0 \le x_1 < x_2 \le n$ ) dan menghubungkan titik $(x_1,y)$ dan $(x_2,y)$ (lihat gambar di bawah).

Kami ingin tahu, untuk setiap segmen unit di bagian atas kotak, seberapa dalam kita dapat melihat secara vertikal di dalam kotak jika kita melihat melalui segmen ini.

$x \in \{0,\dots,n-1\}$ $\max_{i:\ [x,x+1]\subseteq[x_{1,i},x_{2,i}]} y_i$

Contoh: diberikan dan segmen yang terletak seperti pada gambar di bawah ini, hasilnya adalah . Lihatlah seberapa dalam cahaya bisa masuk ke dalam kotak. $n=9$ $m=7$ $(5, 5, 5, 3, 8, 3, 7, 8, 7)$

Tujuh segmen; bagian yang diarsir menunjukkan wilayah yang dapat dijangkau oleh cahaya

Untungnya bagi kita, baik $n$ dan $m$ adalah cukup kecil dan kita dapat melakukan perhitungan off-line.

Algoritma termudah yang menyelesaikan masalah ini adalah brute-force: untuk setiap segmen melintasi seluruh array dan memperbaruinya jika perlu. Namun, itu memberi kita tidak terlalu mengesankan . $O(mn)$

Peningkatan yang bagus adalah dengan menggunakan pohon segmen yang mampu memaksimalkan nilai pada segmen selama kueri dan membaca nilai akhir. Saya tidak akan menjelaskan lebih lanjut, tetapi kita melihat bahwa kompleksitas waktu adalah . $O((m+n) \log n)$

Namun, saya menghasilkan algoritma yang lebih cepat:

Garis besar:

Urutkan segmen dalam urutan menurun koordinat (waktu linier menggunakan variasi jenis penghitungan). Sekarang perhatikan bahwa jika setiap segmen -unit telah dicakup oleh segmen mana pun sebelumnya, tidak ada segmen berikut yang dapat mengikat berkas cahaya melalui segmen -unit ini lagi. Kemudian kita akan melakukan sapuan garis dari atas ke bawah kotak. $y$ $x$ $x$
Sekarang mari kita perkenalkan beberapa definisi: segmen -unit adalah segmen horizontal imajiner pada sapuan yang koordinatnya bilangan bulat dan panjangnya adalah 1. Setiap segmen selama proses sapuan mungkin tidak ditandai (yaitu, berkas cahaya yang berasal dari bagian atas kotak dapat mencapai segmen ini) atau ditandai (huruf besar). Pertimbangkan segmen -unit dengan , selalu tanpa tanda. Mari kita juga memperkenalkan set . Setiap set akan berisi seluruh urutan segmen -unit bertanda yang ditandai (jika ada) dengan tanda berikut yang tidak ditandai $x$ $x$ $x$ $x_1=n$ $x_2=n+1$ $S_0=\{0\}, S_1=\{1\}, \dots, S_n=\{n\}$ $x$ segmen.
Kami membutuhkan struktur data yang dapat beroperasi pada segmen ini dan menetapkan secara efisien. Kami akan menggunakan struktur find-union yang diperluas oleh bidang yang memegang indeks segmen -unit maksimum (indeks segmen yang tidak ditandai ). $x$
Sekarang kita dapat menangani segmen dengan efisien. Katakanlah kita sekarang mempertimbangkan segmen -th agar (menyebutnya "query"), yang dimulai di dan berakhir di . Kita perlu menemukan semua segmen -unit tak bertanda yang terdapat di dalam segmen ke- (ini persis segmen di mana berkas cahaya akan berakhir dengan caranya). Kami akan melakukan yang berikut: pertama, kami menemukan segmen tanpa tanda pertama di dalam kueri ( Temukan perwakilan dari set yang berisi dan dapatkan indeks maksimum dari set ini, yang merupakan segmen tanpa tanda menurut definisi ). Maka indeks ini $i$ $x_1$ $x_2$ $x$ $i$ $x_1$ $x$ ada di dalam kueri, tambahkan ke hasil (hasil untuk segmen ini adalah ) dan tandai indeks ini ( Kumpulan Union berisi dan ). Kemudian ulangi prosedur ini sampai kami menemukan semua segmen yang tidak ditandai , yaitu, selanjutnya Cari kueri memberi kami indeks . $y$ $x$ $x+1$ $x \ge x_2$

Perhatikan bahwa setiap operasi pencarian-serikat kerja akan dilakukan hanya dalam dua kasus: apakah kita mulai mempertimbangkan segmen (yang dapat terjadi kali) atau kami baru saja menandai segmen unit (ini bisa terjadi kali). Dengan demikian kompleksitas keseluruhan adalah ( adalah fungsi Ackermann terbalik ). Jika ada sesuatu yang tidak jelas, saya bisa menguraikan lebih lanjut tentang ini. Mungkin saya akan dapat menambahkan beberapa gambar jika saya punya waktu. $m$ $x$ $n$ $O((n+m)\alpha(n))$ $\alpha$

Sekarang saya mencapai "tembok". Saya tidak dapat menghasilkan algoritma linier, meskipun sepertinya harus ada satu. Jadi, saya punya dua pertanyaan:

Apakah ada algoritma linear-waktu (yaitu, ) memecahkan masalah visibilitas segmen horizontal? $O(n+m)$
Jika tidak, apa buktinya bahwa masalah visibilitas adalah ? $\omega(n+m)$

algorithms data-structures time-complexity computational-geometry mnbvmar
sumber

Seberapa cepat Anda mengurutkan segmen m Anda ?

babou

@ Bobou, pertanyaannya menentukan jenis penghitungan, yang seperti pertanyaannya, berjalan dalam waktu linier ("waktu linier menggunakan variasi jenis penghitungan").

Apakah Anda mencoba menyapu dari kiri ke kanan? Yang Anda butuhkan adalah mengurutkan pada

dan

baik dalam langkah

dan

untuk berjalan ke kanan. Jadi total

x 1

$x1$

x 2

$x2$

O (m)

$O(m)$

O (m)

$O(m)$

O (m)

$O(m)$

invalid_id

@invalid_id Ya, saya sudah mencoba. Namun, dalam hal ini garis sapuan harus bereaksi dengan tepat ketika memenuhi awal segmen (dengan kata lain, tambahkan angka yang sama dengan

koordinat segmen ke multiset), memenuhi akhir segmen (menghapus kejadian

-coordinate) dan output segmen aktif tertinggi (output nilai maksimum dalam multiset). Saya belum pernah mendengar adanya struktur data yang memungkinkan kami melakukan ini dalam waktu (diamortisasi) konstan.

y

$y$

y

$y$

mnbvmar

@ mnbvmar mungkin saran bodoh, tapi bagaimana dengan array ukuran

, Anda menyapu dan menghentikan setiap sel

. Untuk sel evry Anda tahu maks

dan Anda bisa memasukkannya dalam matriks, selanjutnya Anda dapat melacak maksimum keseluruhan dengan variabel.

n

$n$

O (n)

$O(n)$

y

$y$

invalid_id

Jawaban:

Pertama semacam baik dan koordinat garis di dua array terpisah dan . $x1$ $x2$ $A$ $B$ $O(m)$
Kami juga mempertahankan ukuran array bit tambahan untuk melacak segmen aktif. $n$
Mulai menyapu dari kiri ke kanan:
untuk $(i=0,i<n,i++)$
{
..Jika dengan nilai $\exists x1=i$ $y$ $c$ $O(1)$
.. {
.... temukan ( ) $\max$
.... toko ( ) $\max$ $O(1)$
..}
..Jika dengan nilai $\exists x2=i$ $y$ $c$ $O(1)$
.. {
.... temukan ( ) $\max$
.... toko ( ) $\max$ $O(1)$
..}
}

find ( ) dapat diimplementasikan menggunakan array bit dengan bit. Sekarang setiap kali kita menghapus atau menambahkan elemen ke kita dapat memperbarui integer ini dengan menetapkan bit masing-masing menjadi benar atau salah. Sekarang Anda memiliki dua opsi tergantung pada bahasa pemrograman yang digunakan dan asumsi relatif kecil yaitu lebih kecil dari yang setidaknya 64 bit atau jumlah tetap dari bilangan bulat ini: $\max$ $n$ $L$ $n$ $long long int$

Dapatkan bit paling signifikan dalam waktu konstan didukung oleh beberapa perangkat keras dan gcc.
Dengan mengonversi ke integer Anda akan mendapatkan nilai maksimum (tidak secara langsung tetapi Anda dapat menurunkannya). $L$ $O(1)$

Saya tahu ini adalah hack karena mengasumsikan nilai maksimum untuk dan karenanya dapat dilihat sebagai konstanta kemudian ... $n$ $n$

invalid_id
sumber

Seperti yang saya lihat, dengan asumsi Anda sudah mendapatkan prosesor x86 64-bit, Anda hanya dapat menangani

. Bagaimana jika

ada dalam urutan jutaan?

n \leq 64

$n \le 64$

n

$n$

mnbvmar

Maka Anda akan membutuhkan lebih banyak bilangan bulat. Dengan dua bilangan bulat, Anda dapat menangani

hingga 128, dll. Jadi langkah penemuan maksimum

tersembunyi dalam jumlah bilangan bulat yang diperlukan, yang mungkin masih Anda optimalkan jika

kecil. Anda menyebutkan dalam pertanyaan Anda bahwa

relatif kecil jadi saya kira itu tidak dalam urutan jutaan. Ngomong-ngomong int panjang panjang selalu setidaknya 64 bit menurut definisi bahkan pada prosesor 32-bit.

n

$n$

O (m)

$O(m)$

m

$m$

n

$n$

invalid_id

Tentu saja itu benar, standar C ++ mendefinisikan long long intsebagai setidaknya tipe integer 64-bit. Namun, bukankah jika

besar dan kita menyatakan ukuran kata sebagai

(biasanya

), maka masing - masing akan mengambil

n

$n$

w

$w$

w = 64

$w=64$ find

waktu? Maka kita akan berakhir dengan total

O (\frac{n}{w})

$O\left(\frac{n}{w}\right)$

O (\frac{m n}{w})

$O\left(\frac{mn}{w}\right)$

mnbvmar

Ya, sayangnya untuk nilai besar dari

itulah masalahnya. Jadi sekarang saya bertanya-tanya seberapa besar

akan dalam kasus Anda dan apakah itu dibatasi. Jika memang dalam urutan jutaan hack-around ini tidak akan berfungsi lagi, tetapi jika

untuk nilai

rendah itu akan cepat dan praktis

. Jadi pilihan algoritma terbaik, seperti biasa, bergantung pada input. Misalnya untuk jenis penyisipan

biasanya lebih cepat daripada menggabungkan jenis, bahkan dengan waktu berjalan

dibandingkan dengan

n

$n$

n

$n$

c \cdot w \geq n

$c\cdot w\geq n$

c

$c$

O (n + m)

$O(n+m)$

n \leq 100

$n\leq 100$

O (n^{2})

$O(n^2)$

O (n \log n)

$O(n \log n)$

invalid_id

Saya bingung dengan pilihan format. Anda tahu Anda bisa mengeset kode di sini, kan?

Raphael

Saya tidak memiliki algoritma linier, tetapi yang ini tampaknya O (m log m).

Urutkan segmen berdasarkan koordinat pertama dan tinggi. Ini berarti bahwa (x1, l1) selalu datang sebelumnya (x2, l2) setiap kali x1 <x2. Juga, (x1, l1) pada ketinggian y1 datang sebelum (x1, l2) pada ketinggian y2 setiap kali y1> y2.

Untuk setiap subset dengan koordinat pertama yang sama, kami melakukan hal berikut. Biarkan segmen pertama menjadi (x1, L). Untuk semua segmen lain dalam subset: Jika segmen lebih panjang dari yang pertama, kemudian ubah dari (x1, xt) menjadi (L, xt) dan tambahkan ke subset L-dalam urutan yang tepat. Kalau tidak jatuhkan. Akhirnya, jika subset berikutnya memiliki koordinat pertama kurang dari L, maka bagi (x1, L) menjadi (x1, x2) dan (x2, L). Tambahkan (x2, L) ke subset berikutnya dalam urutan yang benar. Kita bisa melakukan ini karena segmen pertama dalam subset lebih tinggi dan mencakup rentang dari (x1, L). Segmen baru ini mungkin yang mencakup (L, x2), tetapi kita tidak akan tahu itu sampai kita melihat subset yang memiliki koordinat pertama L.

Setelah kami menjalankan semua subset, kami akan memiliki seperangkat segmen yang tidak tumpang tindih. Untuk menentukan nilai Y untuk X yang diberikan, kita hanya perlu menjalankan segmen yang tersisa.

Jadi apa kerumitannya di sini: Jenisnya adalah O (m log m). Looping melalui subset adalah O (m). Pencarian juga O (m).

Jadi sepertinya algoritma ini tidak bergantung pada n.

Tidak Ada Yang Tertentu
sumber