Sebuah prasasti
seperti itu , Google / Yandex tidak menemukan penulisnya Ini adalah bagian kedua dari artikel "Yang jelas bagi semua orang".
Untuk pemahaman yang lebih baik tentang algoritma Z yang diuraikan di dalamnya, saya akan menambahkan di sini contoh bagus yang diberikan sebelumnya dalam diskusi / komentar.
Bayangkan bahwa tugasnya adalah membuat kurva dari fungsi T (X) tertentu pada interval nilai (yang diizinkan) tertentu. Sangat diharapkan untuk melakukan ini sedetail mungkin, tetapi Anda tidak tahu sebelumnya kapan Anda akan "digenggam oleh tangan". Anda ingin menghasilkan nilai X sehingga kapan saja saat plot kurva terputus (menghasilkan parameter X pada interval dan menghitung T (X)), grafik yang dihasilkan mencerminkan fungsi ini seakurat mungkin. Akan ada lebih banyak waktu - grafik akan lebih akurat, tetapi - selalu semaksimal mungkin saat ini untuk fungsi arbitrer .
Tentu saja, untuk fungsi yang diketahui, algoritma partisi interval dapat memperhitungkan perilakunya, tetapi di sini kita berbicara tentang pendekatan umum yang memberikan hasil yang diinginkan dengan "kerugian" minimal. Untuk casing dua dimensi, Anda dapat memberikan contoh tampilan relief / permukaan tertentu dan ingin memastikan bahwa sebanyak mungkin fitur-fiturnya telah ditampilkan.
Tugas dan objek pemodelan (dari bagian pertama) dalam kasus umum bisa sangat berbeda: ada model teoretis / fisik atau perkiraan atau tidak (kotak hitam) - akan ada nuansa dalam model bangunan di mana-mana. Tetapi kebutuhan untuk menghasilkan parameter (termasuk algoritma Z) adalah bagian yang umum dan tidak terpisahkan untuk semua orang. Ada objek (misalnya, seperti ) ketika waktu untuk memperoleh T terlalu lama (hari dan minggu), maka algoritma untuk memilih langkah baru berhenti dengan kriteria lain, bukan karena penyelesaian siklus kalkulasi utama dalam proses paralel. Tidak masuk akal untuk mengurangi lebih lanjut langkah untuk meningkatkan pencarian perkiraan berikutnya T jika peningkatan yang diharapkan jelas lebih buruk daripada kesalahan model dan / atau kesalahan pengukuran T.
Saya akan memberikan satu ilustrasi lagi tentang pembagian interval yang dapat diterima untuk kasus dua dimensi dari algoritma Z (K = 3 di bidang 64 * 64):
Titik-titik yang disorot pada gambar (9 buah.) Adalah titik awal dari tepi dan tengah interval, mereka, jika perlu, dianggap di luar algoritma Z. Anda dapat melihat bahwa arah / "jalur" horizontal dan vertikal Nilai Z tidak ada. Poin tambahan di sini mudah dihitung secara terpisah, tetapi dengan peningkatan jumlah titik di sepanjang arah / "trek" ini, representasi fungsi akan meningkat ("trek" menjadi lebih sempit) dan kebutuhan untuk melengkapi algoritme itu sendiri (diperlukan 7 baris, yang mana 4 operator di loop utama di n, lihat di bawah) atau saya tidak melihat membuat perhitungan terpisah. Selain itu, dalam kasus ini, efisiensi rata-rata algoritme menurun, dan tidak akan ada peningkatan khusus dalam representasi model (bahkan untuk n> 8, langkah dalam parameter kurang dari 1/1000, lihat tabel di bawah).
Fitur kedua dari algoritma Z adalah (untuk kasus dua dimensi) asimetri urutan penambahan titik - mereka lebih sering pada sumbu / parameter Y, gambar disejajarkan pada akhir setiap siklus dengan n.
Algoritma Z, kasus satu dimensi, dalam bahasa VBA:
Xmax =
Xmin =
Dx = (Xmax - Xmin) / 2
L = 2
Sx = 0
For n = 1 To K
Dx = Dx / 2
D = Dx
For j = 1 To L Step 2
X = Xmin + D
Cells(5, X) = "O" ' - / T(X)
X = Xmax - D
Cells(5, X) = "O"
D = D + Sx
Next j
Sx = Dx
L = L + L
Next nAlgoritma Z, huruf 2D, bahasa VBA:
Xmax = ' 65 - , GIF
Xmin = ' 1
Ymax = ' 65
Ymin = ' 1
Dx = (Xmax - Xmin) / 2
Dy = (Ymax - Ymin) / 2
L = 2
Sx = 0
Sy = 0
For n = 1 To K ' K = 3 GIF
Dx = Dx / 2
Dy = Dy / 2
Tx = Dx
For j = 1 To L Step 2
X1 = Xmin + Tx
X2 = Xmax - Tx
Ty = Dy
For i = 1 To L Step 2
Y = Ymin + Ty
Cells(Y, X1) = "O" ' - / T(Y,X)
Cells(Y, X2) = "O"
Y = Ymax - Ty
Cells(Y, X1) = "O"
Cells(Y, X2) = "O"
Ty = Ty + Sy
Next i
Tx = Tx + Sx
Next j
Sx = Dx
Sy = Dy
L = L + L
Next nBiaya komputasi:
Operasi utama yang digunakan dalam perhitungan ditunjukkan dalam tanda kurung siku (biaya pengaturan siklus tidak termasuk).
Perlu dicatat di sini bahwa operasi pembagian [÷] yang agak "berat" dalam hal ini tidak mahal, karena pembagian bilangan bulat dengan 2 adalah pergeseran satu digit. Biaya relatif dari divisi dan operasi penugasan ([=], istilah kedua) dengan cepat cenderung nol dengan meningkatnya K.
Poin total:
Biaya rata-rata:
Untuk nilai pertama K, kita akan melakukan kalkulasi menggunakan rumus ini dan mengisi tabel:
Di sini "pecahan interval" adalah langkah relatif antara titik pada akhir siklus dengan n.
Baris terakhir ("rata-rata") menunjukkan biaya relatif per poin - proporsi penambahan / pengurangan. Batasnya cenderung 0,5625 atau 1 / 1,77777 dari operasi penjumlahan.
Kembali ke pernyataan dari bagian pertama artikel , ditunjukkan di sini bahwa "algoritme yang diusulkan untuk diskusi menunjukkan biaya komputasi yang sangat rendah dan tidak menimbulkan kekurangan atau kesulitan," dan dalam kondisi gangguan komputasi yang tiba-tiba, ini juga memiliki keuntungan. Sebaiknya gunakan di semua aplikasi yang sesuai.
Saya meminta bantuan dalam distribusi dan implementasi baik dalam perangkat lunak maupun perangkat keras.