Machine Translated by Google

Lihat diskusi, statistik, dan profil penulis untuk publikasi ini di: [Link]

Algoritma Backtracking Serbaguna

Artikel dalam Jurnal Komputasi Simbolik · Juli 1994

DOI: 10.1006/jsco.1994.1035 · Sumber: DBLP

SITASI BACAAN

47 6.226 orang

2 penulis:

Hilary Priestley Martin Bangsal

Universitas Oxford Universitas De Montfort

90 PUBLIKASI 9.288 SITASI 76 PUBLIKASI 1.431 SITASI

LIHAT PROFIL LIHAT PROFIL

Semua konten setelah halaman ini diunggah oleh Martin Ward pada tanggal 25 Oktober 2017.

Pengguna telah meminta peningkatan pada berkas yang diunduh.

Machine Translated by Google

Algoritma Backtracking Serbaguna

HA Priestley Anggota Parlemen

HAP@@[Link] [Link]@@[Link]
Institut Matematika Jurusan Ilmu Komputer
24/29, St. Giles, Laboratorium Sains
Oxford OX1 3LB Jalan Selatan

Durham DH1 3LE

17 Januari 2003

Abstrak

Disajikan suatu algoritma penelusuran balik dengan pemilihan urutan elemen, dan keefisienannya dibahas
baik dalam kaitannya dengan contoh standar maupun contoh mengenai peta pemeliharaan relasi yang ingin
dipecahkan dengan menggunakan algoritma tersebut.

1 Pendahuluan

Backtracking telah lama digunakan sebagai strategi untuk memecahkan masalah kombinatorial dan
telah dipelajari secara luas (Gerhart & Yelowitz (1976), Roever (1978), Walker (1960), Wells (1971)).
Dalam situasi terburuk, hal ini mungkin sangat tidak efisien, dan analisis sistematis terhadap efisiensi
sangatlah sulit. Oleh karena itu, penelusuran balik terkadang dianggap sebagai metode pilihan terakhir.
Meskipun demikian, algoritme penelusuran balik digunakan secara luas, khususnya pada masalah NP-
lengkap. Untuk membuat algoritme ini layak secara komputasi pada berbagai masalah besar, algoritme
ini biasanya disesuaikan dengan aplikasi tertentu (lihat, misalnya, pendekatan Butler dan Lam untuk
pengujian isomorfisme dalam Butler & Lam (1985) dan pendekatan Knuth dan Szwarcfiter untuk
pengurutan topologi (yaitu, memperluas urutan parsial ke urutan linier) Knuth & Szwarcfiter (1974)).
Pendekatan kami terhadap penelusuran balik didasarkan pada karya Ward tentang transformasi
program Ward (1989), Ward (1992), Ward (1994), Ward (1993). Kami memperoleh (dan sekaligus
membuktikan kebenarannya) algoritma penelusuran balik sederhana yang 'universal'. Bahkan dalam
bentuk dasar ini, algoritma kami terbukti sangat efektif untuk jenis masalah yang menjadi tujuan
perancangannya. Semua masalah ini dapat dianggap sebagai masalah yang memerlukan penghitungan,
pencatatan, atau pemrosesan lainnya, dari peta yang mempertahankan relasi dari struktur relasional
terbatas ke struktur relasional lain dengan tipe yang sama. Secara khusus, pengujian isomorfisme akan
termasuk dalam kategori ini. Priestley secara khusus memperhatikan masalah yang muncul sehubungan
dengan dualitas tipe Stone untuk berbagai aljabar yang anggotanya adalah kisi distributif dengan
struktur tambahan. Ternyata, dalam aplikasi ini, waktu berjalan algoritma sangat bergantung pada
urutan elemen data yang dicantumkan (dengan faktor beberapa ribu). Teknik yang sama yang
menghasilkan algoritma backtracking sederhana kemudian digunakan untuk mendapatkan versi
algoritma yang menggabungkan mekanisme untuk mengubah elemen. Dengan memanfaatkan ini dalam
berbagai cara, peningkatan efisiensi yang sangat besar diperoleh yang memungkinkan kami untuk
menyelesaikan berbagai perhitungan yang jika tidak demikian akan sama sekali tidak praktis. Tabel 3
dan 4 di Bagian 6.2 secara mencolok menggambarkan efek pemilihan urutan elemen yang cermat dalam satu kasus terte
Tulisan kami ditujukan kepada dua kelompok pembaca dengan (mungkin) sedikit persimpangan.
Kelompok pertama terdiri dari mereka yang tertarik pada penelusuran balik. Kelompok kedua berisi
matematikawan yang perlu memecahkan masalah, misalnya, dalam aljabar atau teori grafik, yang dapat
diterapkan pada metode kami. Untuk kepentingan pembaca tersebut, kami telah menyertakan beberapa diskusi tentang

1
Machine Translated by Google

cerita rakyat yang tidak diperlukan dalam makalah yang ditujukan hanya kepada ilmuwan komputer.

Makalah ini disusun sebagai berikut. Bagian 2, yang menggunakan teka-teki delapan ratu yang terkenal
sebagai ilustrasi, memiliki dua tujuan. Bagian ini memberikan pengantar singkat tentang backtracking bagi
mereka yang belum mengenalnya, dan juga memungkinkan kita untuk menarik perhatian pada faktor-faktor
yang memengaruhi efisiensi yang akan kita bahas nanti. Bagian 3 menyajikan fragmen Bahasa Spektrum Luas
(WSL) Ward yang kita gunakan, dan Bagian 4 berisi teori dari karya Ward tentang transformasi program yang
menjadi dasar derivasi algoritme kita. Algoritme backtracking sederhana diberikan di Bagian 5.
Bagian selanjutnya membahas penerapan algoritma ini yang menjadi dasar penulisan makalah ini.
Buku ini menyediakan latar belakang matematika untuk berbagai contoh yang telah kami uji metodenya.
Meskipun Bagian 6 cukup lengkap, buku ini ditujukan terutama untuk matematikawan dengan minat yang
sesuai. Bagian 7 membahas berbagai heuristik untuk pemilihan urutan elemen, dengan ilustrasi. Kami
menyimpulkan dengan beberapa komentar singkat yang relevan dengan pengembangan lebih lanjut: kami
membahas keadaan terkini mengenai otomatisasi lengkap proses pengembangan algoritma, dari spesifikasi
abstrak hingga implementasi dalam bahasa pemrograman yang sesuai.

Kami menekankan bahwa pemahaman tentang mesin di Bagian 4–5 tidak diperlukan oleh pengguna produk
akhir. Teori ini menjamin bahwa algoritme tersebut memenuhi spesifikasinya. Karena sifatnya yang universal,
algoritme (dengan atau tanpa pemilihan urutan elemen) dapat dengan mudah diadaptasi ke berbagai situasi
tanpa harus menggunakan teori lebih lanjut. Implementasinya mudah. Kami membahas masalah implementasi
dalam kasus khusus di Bagian 6. Kami juga menyertakan Lampiran yang memberikan implementasi C dari
algoritme backtracking sederhana. Kode sumber untuk semua algoritme dan berkas data contoh dapat diperoleh
dari penulis.

2 Teka-teki Delapan Ratu

Akan lebih mudah untuk memperkenalkan konsep backtracking melalui teka-teki sederhana, yaitu masalah
delapan ratu:

Berapa banyak cara untuk menempatkan delapan ratu pada papan catur sedemikian rupa sehingga
tidak ada ratu yang menyerang yang lain?

Dua ratu saling menyerang jika mereka berada pada baris, kolom, atau diagonal yang sama. Gambar 1 mengilustrasikan
salah satu solusinya.

Gambar 1: Satu solusi untuk teka-teki delapan ratu.

Solusi brute force untuk setiap masalah kombinatorial adalah dengan menghitung semua solusi yang
mungkin, menguji masing-masing solusi secara bergantian dan menolak solusi yang gagal memenuhi
persyaratan yang diperlukan. Dalam kasus ini, metode yang “paling brutal” menguji setiap kemungkinan
susunan delapan ratu di papan catur. Ada 64 tempat untuk ratu pertama, untuk masing-masing ratu ada 63 tempat untuk ratu ked

2
Machine Translated by Google

total 64×63×· · ·×57 = [Link].760 kasus. Jumlah ini dapat dikurangi secara substansial dengan
pengamatan bahwa setiap solusi yang valid harus berisi tepat satu ratu di setiap kolom. Jadi, kita hanya perlu
8
mempertimbangkan 8 = 16.777.216 cara menempatkan delapan ratu, satu per kolom, ke dalam delapan kolom.
Setiap susunan seperti itu dapat direpresentasikan sebagai urutan delapan angka dari 1 hingga 8, misalnya
situasi pada Gambar 1 direpresentasikan sebagai 3, 6, 4, 1, 8, 5, 7, 2.

2.1 Penelusuran Balik

Cara sederhana untuk mengurangi jumlah kasus lebih jauh kini muncul. Pertimbangkan situasi di mana dua
ratu pertama telah ditempatkan di posisi 1 dan 1, atau 1 dan 2 di dua kolom pertama.
6
Karena keduanya saling menyerang, kita tidak perlu mempertimbangkan salah satu dari 2 = 262.144 cara untuk
menempatkan enam ratu yang tersisa. Demikian pula, setelah menempatkan empat ratu pertama pada Gambar
1, hanya ada dua posisi yang valid untuk ratu kelima. Penempatan berurutan seperti itu dapat direpresentasikan
sebagai struktur pohon, seperti yang ditunjukkan pada Gambar 2 untuk teka-teki empat ratu. Empat simpul di bawah akar
ÿÿÿ ÿ
ÿÿÿ ÿ
ÿÿ ÿÿ
ÿÿÿ ÿÿÿ
ÿÿÿ ÿÿ 1
ÿÿ
2
ÿÿ ÿÿÿÿÿÿÿÿÿÿÿ 3 4
ÿ ÿÿ
ÿ ÿ ÿÿÿÿ
ÿÿÿÿÿÿ ÿÿÿÿÿÿ
ÿÿ 11 ÿ ÿ 13 14 ÿÿÿÿÿÿÿ 24
12 ÿÿ ÿÿ Tanggal 21 22 23 ÿÿ
ÿÿÿÿ ÿÿÿÿ ÿÿÿ
ÿÿÿÿÿÿ ÿÿÿÿÿÿ
ÿÿ ÿ142
ÿÿÿÿÿÿ 241
131 132 133 134 141 ÿÿ 143 144 ÿÿ 242 243 244
ÿÿÿ ÿÿÿÿ
ÿÿÿÿÿÿ

Tahun 1421 1422 1423 1424 Nomor telepon 2411 2412 2413 2414

Gambar 2: Pohon Pencarian Empat Ratu

(simpul atas) pohon mewakili empat posisi untuk ratu pertama. Di bawah setiap simpul yang valid terdapat
simpul-simpul lain yang mewakili posisi ratu berikutnya yang akan ditempatkan. Perhatikan bahwa cabang 3
dan 4 dari pohon merupakan bayangan cermin dari cabang 2 dan 1, dan dihilangkan demi singkatnya. Solusinya
adalah 2, 4, 1, 3 dan bayangan cerminnya 3, 1, 4, 2.

Prosedur ini memangkas jumlah kasus yang diperiksa (untuk teka-teki delapan ratu) menjadi total 15.720.
Untuk menghitung semua kasus ini secara sistematis, kita mulai dari akar dan bergerak ke bawah pohon,
mengambil cabang paling kiri di setiap persimpangan, tetapi jika tidak mungkin untuk bergerak ke bawah, kita
"mundur" dengan mempertimbangkan persimpangan berikutnya di tingkat sebelumnya. Ini dapat menyebabkan
penelusuran kembali lebih lanjut jika semua persimpangan di tingkat sebelumnya kini telah tercakup. Formulasi
terkomputerisasi pertama dari metode ini adalah oleh Walker pada tahun 1958 (Walker (1960)).

Dengan asumsi kita memiliki predikat valid(p) yang menguji apakah deret bilangan bulat p merupakan
susunan ratu yang valid tanpa ratu yang menyerang ratu lainnya, maka prosedur rekursif berikut akan
menyelesaikan masalah tersebut. (Notasi p + t menunjukkan deret p dengan deret singleton t ditambahkan.
Lihat Bagian 3 untuk deskripsi notasi lainnya). begin count := 0; Queens()

Di mana
proc Queens(p) ÿ jika
(p) = 8 maka hitung := hitung + 1

3
Machine Translated by Google

jika tidak untuk t := 1 sampai 8 lakukan

jika valid (p + t) maka Queens (p + t) fi od.

akhir

Ini adalah kasus khusus dari algoritma yang akan kita peroleh di Bagian 5. Juga di Bagian 5 kita mengubah algoritma
rekursif ini menjadi algoritma iteratif yang setara: count := 0; var p := ,t :=
1: while p =
ÿ t 8 do

terakhir
jika t > 8 maka t ÿÿ p; t := t + 1 jika
tidak valid(p + t) ÿ (p) = 7 maka hitung := hitung + 1; t := t + 1 jika tidak valid(p +
t) ÿ (p) < 7 maka p := p + t; t := 1 jika tidak t := t + 1 titik akhir

Program rekursif menekankan gerakan ke bawah pada pohon. Penelusuran balik (gerakan ke atas) terjadi begitu
saja ketika setiap posisi pada kolom telah dipertimbangkan. Program iteratif menekankan penelusuran balik dengan
secara eksplisit mencari ke atas dan ke bawah pohon, bekerja dari kiri ke kanan. Keempat kasus dalam loop
berhubungan dengan:

1. Bergerak ke atas, yaitu mundur;

2. Bergerak ke kanan saat solusi telah ditemukan; 3.

Bergerak ke bawah ke cabang paling kiri dari simpul saat ini, dan; 4. Bergerak

ke kanan saat susunan saat ini tidak valid.

2.2 Pemilihan Urutan Elemen

Sejauh ini kami berasumsi bahwa ratu-ratu akan ditempatkan di kolom-kolomnya dari kiri ke kanan, tetapi ini sama
sekali tidak penting. Penempatan kelompok ratu mana pun dapat dilakukan dalam urutan apa pun tanpa memengaruhi
hasil akhir; namun, urutan yang berbeda dapat mengakibatkan lebih sedikit kasus yang perlu dianalisis.
Perhatikan situasi pada Gambar 3 di mana tiga ratu pertama telah ditempatkan di tiga kolom pertama. Di sini, kita
memiliki tiga tempat untuk ratu berikutnya di kolom 4 dan 5 (ditandai dengan s), tetapi

Gambar 3: Solusi parsial

hanya satu tempat di kolom 6. Menempatkan ratu berikutnya di kolom 6 (bukan kolom 4) akan mengurangi jumlah total
kasus yang akan dipertimbangkan, tanpa memengaruhi hasilnya. Ini adalah dasar untuk berbagai heuristik “pemilihan
urutan elemen” yang dibahas di bawah ini.

Perlu dicatat bahwa untuk masalah khusus ini (dan masalah ratu N yang lebih umum
masalah), heuristik tidak memberikan banyak manfaat. Hal ini karena:

4
Machine Translated by Google

1. Ukuran keseluruhan pohon pencarian hanya bertambah sekitar 2 atau 3 kali lipat apabila urutan elemen yang
dipilih adalah acak, bukan urutan optimal (sehingga pengurangan jumlah percobaan yang besar tidaklah
memungkinkan);

2. Dengan menggunakan metode Wirth (1971), suatu solusi percobaan dapat diuji dengan sangat efisien (sehingga tidak ada
tidak banyak yang bisa diperoleh dari pengurangan kecil dalam jumlah percobaan);

3. Solusi “naif” dengan menempatkan ratu dalam urutan kiri ke kanan ternyata merupakan solusi optimal.
urutan (jika urutan elemen ditetapkan sepanjang perhitungan).

Untuk masalah yang ingin kami selesaikan, urutan elemen yang sesuai sangat penting dalam menghasilkan hasil dalam
jumlah waktu yang layak. Meskipun demikian, dengan memulai dengan permutasi acak setiap kali kami mampu
menghasilkan beberapa perbaikan dengan menggunakan heuristik yang dibahas dalam Bagian 7. Lihat Gambar 1 untuk
beberapa contoh hasil, yang masing-masing dirata-ratakan dari sepuluh permutasi awal acak yang berbeda. Metode
"pra-analisis" menganalisis pohon pencarian untuk memilih permutasi awal. Metode "pemangkasan semak" memperbarui
permutasi secara dinamis saat pencarian berlangsung. Metode "hibrida" adalah kombinasi dari sejumlah kecil pra-
analisis, diikuti oleh pemangkasan semak. Ini adalah yang paling efisien dalam hal jumlah percobaan, tetapi
membebankan overhead yang lebih tinggi daripada pra-analisis sederhana—yang paling efisien dalam hal waktu CPU.

Jumlah percobaan Waktu CPU 13 ratu 14 ratu

Metode yang digunakan 13 ratu 14 ratu 130.150.618 899.139.237 138,43 942,14
tidak ada 100.515.902 654.151.660 89.088.384 569.929.575
pra-analisis 110.61 696.29
hibrida Rp 140.000 878.52

Tabel 1: Contoh hasil dari masalah N ratu

3 Bahasa WSL
Bahasa Indonesia: Di bagian ini kami memberikan pengenalan singkat ke bahasa WSL (Bull (1990), Ward (1989), Ward
(1994)) “Bahasa Spektrum Luas”, yang digunakan dalam pekerjaan transformasi program Ward, yang mencakup
konstruksi pemrograman tingkat rendah dan spesifikasi abstrak tingkat tinggi dalam satu bahasa. Dengan bekerja
dalam satu bahasa formal, kami dapat membuktikan bahwa sebuah program mengimplementasikan spesifikasi dengan
benar, atau bahwa spesifikasi menangkap perilaku program dengan benar, melalui transformasi formal dalam bahasa
tersebut. Kami tidak harus mengembangkan transformasi antara bahasa “pemrograman” dan “spesifikasi”. Keuntungan
tambahannya adalah bahwa bagian-bagian program yang berbeda dapat diekspresikan pada tingkat abstraksi yang
berbeda, jika diperlukan.

Transformasi program merupakan operasi yang mengubah program ke dalam bentuk lain yang mempunyai perilaku
eksternal sama (ekuivalen dengan semantik denotasional yang didefinisikan secara tepat).
Karena program dan spesifikasi merupakan bagian dari bahasa yang sama, transformasi dapat digunakan untuk
menunjukkan bahwa program tertentu merupakan implementasi yang benar dari spesifikasi tertentu.
Dalam Ward (1990), Ward (1996) transformasi program digunakan untuk memperoleh berbagai algoritma yang efisien
dari spesifikasi abstrak. Dalam makalah ini kami menggunakan transformasi untuk memperoleh berbagai algoritma
backtracking yang efisien dari spesifikasi formal.

3.1 Sintaksis Ekspresi Ekspresi

meliputi nama variabel, angka, string dalam bentuk “teks...”, konstanta N, R, Q, Z, dan operator serta fungsi berikut.
Perhatikan bahwa karena WSL adalah bahasa dengan spektrum yang luas, bahasa ini tidak boleh dibatasi pada nilai
terbatas dan operasi komputasi. Berikut ini e1, e2, dst., yang mewakili ekspresi yang valid: Operator numerik: e1 + e2,
e1 ÿ e2, e1 ÿ e2, e1/e2, e
Bahasa Inggris: e2

1 dan seterusnya, dengan makna yang biasa.

5
Machine Translated by Google

a1, a2, . . . , suburutan s[i], s[i + adalah suatu barisan, maka unsur ke i ai dinotasikan s[i], s[i. . j] adalah barisan: s =
1], . . . , s[j], dimana s[i. . j] = (barisan kosong) jika i > j. Panjang barisan s dinotasikan (s), maka s[(s)] adalah unsur
terakhir dari s.

Penggabungan deret: s1 + s2 = s1[1], . . . , s1[(s1)], s2[1], . . . , s2[(s2)].

Tumpukan: Urutan juga digunakan untuk mengimplementasikan tumpukan, untuk tujuan ini kita memiliki yang berikut ÿÿ
muncul

urutan s dan variabel x: x mengeluarkan elemen dari s berarti x := s[1]; s := s[2 . . (s)] yang notasinya: Untuk
tumpukan ke variabel x. Untuk mendorong nilai ekspresi e ke tumpukan s kita gunakan: s ÿÿ e yang mewakili: s :=
dorongan
e + s.
terakhir

Antrean: Pernyataan x ÿÿ s menghapus elemen terakhir dari s dan menyimpan nilainya dalam variabel x. Ini setara dengan
x := s[(s)]; s := s[1 . . (s) ÿ 1].

Himpunan: Kita mempunyai operasi himpunan biasa ÿ (gabungan), ÿ (potongan) dan (selisih himpunan), ÿ (bagian
himpunan), ÿ (elemen), ÿ (himpunan pangkat). { x ÿ A | P(x) } adalah himpunan semua elemen dalam A yang
memenuhi predikat P. Untuk barisan s, himpunan(s) adalah himpunan elemen barisan tersebut, yaitu himpunan(s)
= { s[i] | 1 i (s) }. Ekspresi #A menunjukkan ukuran himpunan A.

3.2 Sintaksis Rumus Berikut ini

Q, Q1 , Q2 , dst. yang mewakili rumus sembarang dan e1, e2, dst. merupakan ekspresi sembarang:

Hubungan: e1 = e2, e1 = e2, e1 < e2, e1 e2, e1 > e2, e1 Bahasa Indonesia: e2;

Operator logika: ¬Q, Q1 ÿ Q2 , Q1 ÿ Q2 ;

Kuantifier: ÿv. Q, ÿv. Q.

3.3 Sintaksis Pernyataan Berikut

ini, S1, S2 dst., merupakan pernyataan, Q, B dst., merupakan rumus, x1, x2 dst., merupakan variabel, dan e1, e2 dst.
merupakan ekspresi.

Komposisi berurutan: S1; S2; S3; . . . ; Sn Pernyataan: {B}.

Pernyataan adalah pernyataan lewati sebagian, pernyataan ini dibatalkan jika kondisinya salah tetapi tidak melakukan apa
pun jika kondisinya benar.

Penugasan: x1, . . . , .Q. Ini menetapkan nilai baru

akanke
benar,
variabel
kemudian
x1,tidak
. . . ditugaskan
, xn
ada:= xx xn.
N ke1 variabel.
, . . . , Dalam
Jikarumus
ada beberapa
Q, xi mewakili
set nilai
nilai
yanglama
memenuhi
dan x mewakili
Q makanilai
satubaru.
set dipilih
Nilai baru
secara
dipilih
nondeterministik.
sehingga Q Jika

nilai yang memenuhi Q maka pernyataan tidak berakhir. Misalnya, penugasan x := x .(x = 2.x ) membagi dua x jika genap dan dibatalkan jika x ganjil. Jika deret tersebut berisi satu
Saya

variabel maka tanda kurung deret dapat dihilangkan, misalnya: x := x .(x = 2.x ).

Penugasan x := x .(y = 0) menetapkan nilai sembarangan pada x jika y = 0 pada awalnya, dan dibatalkan jika y = 0
pada awalnya: ia tidak mengubah nilai y.

Penugasan sederhana: x1, . . . , en. Ini menugaskan

bersamaan,
nilai
jadi
ekspresi ei ke xn := e1, . . . , variabel xi . Penugasan dilakukan secara
misalnya x, y := y, x menukar nilai x dan y. Penugasan tunggal x := e dapat disingkat menjadi

Contoh soal:

Pilihan deterministik: jika B maka S1 atau S2 fi. Pilihan pernyataan mana yang akan dieksekusi adalah
ditentukan oleh kondisi B.

Pilihan nondeterministik: “Perintah terjaga” dari Dijkstra (1976):

jika B1 ÿ S1
B2 ÿ S2
....
Bn ÿ Sn fi

6
Machine Translated by Google

Masing-masing "penjaga" B1, B2, . . . , Bn dievaluasi, salah satu yang benar dipilih dan pernyataan terkait dieksekusi.
Jika tidak ada penjaga yang benar maka pernyataan dibatalkan. Jika beberapa penjaga benar, maka salah satu
pernyataan terkait dipilih secara nondeterministik.
Iterasi deterministik: sementara B melakukan S od Kondisi B diuji dan S dieksekusi ulang
secara bertahap sampai B menjadi salah.

Variabel lokal yang tidak diinisialisasi: var x: S end Di sini x adalah variabel lokal yang hanya ada di dalam
pernyataan S. Pernyataan tersebut harus diinisialisasi dalam S sebelum diakses pertama kali.

Variabel lokal yang diinisialisasi: var x := t: S end Ini adalah singkatan untuk var x: x := t; S end.
Variabel lokal diinisialisasi ke nilai t. Kita dapat menggabungkan variabel yang diinisialisasi dan yang tidak
diinisialisasi dalam satu blok, misalnya: var x := t, y: S end di mana x diinisialisasi dan y tidak diinisialisasi.

Iterasi yang dihitung: untuk i := b hingga f langkah s lakukan S od setara dengan:

var i := b :

sementara jika melakukan

S; i := i + s od akhir

Perulangan dan keluar tanpa batas: Pernyataan dalam bentuk do S od, di mana S adalah pernyataan, adalah perulangan
“tak terbatas” atau “tak terbatas” yang hanya dapat diakhiri dengan eksekusi pernyataan dalam bentuk exit(n) (di
mana n adalah bilangan bulat, bukan variabel atau ekspresi) yang menyebabkan program keluar dari n perulangan
yang melingkupinya. Untuk menyederhanakan bahasa, kami melarang keluar yang meninggalkan blok atau
perulangan selain perulangan tak terbatas. Jenis struktur ini dijelaskan dalam Knuth (1974) dan baru-baru ini dalam
Taylor (1984).

3.4 Sistem Tindakan

Subbagian ini akan memperkenalkan konsep sistem tindakan sebagai serangkaian prosedur rekursif yang tidak memiliki
parameter. Program yang ditulis menggunakan label dan lompatan diterjemahkan langsung ke dalam sistem tindakan.
Namun, perlu dicatat bahwa jika akhir dari isi suatu tindakan tercapai, maka kontrol dikembalikan ke tindakan pemanggil,
atau ke pernyataan yang mengikuti sistem tindakan jika tidak ada tindakan pemanggil, daripada "beralih" ke label
berikutnya. Pengecualian untuk ini adalah tindakan khusus yang disebut tindakan penghentian, biasanya dilambangkan
dengan Z, yang ketika dipanggil mengakibatkan penghentian langsung seluruh sistem tindakan.

Tindakan adalah prosedur tanpa parameter yang bekerja pada variabel global (lih. Arsac (1982a), Arsac (1982b)).
Tindakan ditulis dalam bentuk A ÿ S. di mana A adalah variabel pernyataan (nama tindakan) dan S adalah pernyataan (isi
tindakan). Seperangkat tindakan (yang saling rekursif) disebut sistem tindakan. Terkadang mungkin ada tindakan khusus
Z, yang pelaksanaannya menyebabkan penghentian seluruh sistem tindakan meskipun ada panggilan rekursif yang belum
selesai. Kemunculan panggilan pernyataan X dalam isi tindakan mengacu pada panggilan tindakan lain.

Sistem tindakan ditulis sebagai berikut, dengan tindakan pertama yang akan dieksekusi (A1 di bawah) disebutkan di
awal: tindakan A1 :
A1 ÿ S1.

Contoh soal: A2 ÿ S2

....
An ÿ Sn. tindakan akhir

Misalnya, sistem tindakan ini setara dengan loop while saat B melakukan S od:
Tindakan A:
A ÿ jika ¬B maka panggil Z fi; S;
panggil A. endactions

Dengan sistem tindakan ini, setiap panggilan tindakan harus mengarah ke panggilan tindakan lainnya, sehingga sistem hanya dapat

7
Machine Translated by Google

diakhiri dengan memanggil aksi Z (yang menyebabkan penghentian segera). Sistem aksi semacam itu disebut reguler.

3.5 Prosedur dan Fungsi dengan Parameter

Kami menggunakan notasi berikut untuk prosedur dengan parameter: mulai

S1 di mana
proc

F(x, y) ÿ S2. akhir

di mana S1 adalah program yang berisi panggilan ke prosedur F yang memiliki parameter x dan y. Badan S2 dari prosedur
tersebut dapat berisi panggilan prosedur rekursif. Kami menggunakan notasi yang sama (dengan funct alih-alih proc) untuk
panggilan fungsi.

4 Penyempurnaan dan Transformasi Program

Bahasa WSL mencakup konstruksi spesifikasi, seperti penugasan umum, dan konstruksi pemrograman. Salah satu tujuan
dari pekerjaan transformasi program kami adalah mengembangkan program dengan menyempurnakan spesifikasi, yang
dinyatakan dalam logika orde pertama dan teori himpunan, menjadi algoritma yang efisien. Ini mirip dengan pendekatan
"kalkulus penyempurnaan" dari Hoare et al. (1987), Morgan (1994), namun, bahasa spektrum luas kami telah diperluas
untuk mencakup sistem tindakan umum dan loop dengan beberapa pintu keluar. Ekstensi ini penting untuk tujuan kedua
kami, dan yang sama pentingnya, yaitu menggunakan transformasi program untuk merekayasa balik dari program ke
spesifikasi. Dalam Ward (1993) kami menjelaskan metode kami untuk merekayasa balik formal menggunakan transformasi.

Penyempurnaan didefinisikan dalam hal semantik denotasional bahasa: semantik program S adalah fungsi yang
memetakan dari status awal ke serangkaian status akhir. Serangkaian status akhir mewakili semua kemungkinan status
keluaran program untuk status masukan yang diberikan. Menggunakan serangkaian status memungkinkan kita untuk
memodelkan program nondeterministik dan spesifikasi yang ditentukan sebagian (atau tidak lengkap). Untuk program S1
dan S2, kita katakan S1 disempurnakan oleh S2 (atau S2 adalah penyempurnaan dari S1), dan tulis S1 ÿ S2, jika S2 lebih
terdefinisi dan lebih deterministik daripada S1. Jika S1 ÿ S2 dan S2 ÿ S1 maka kita katakan S1 setara dengan S2 dan tulis
S1 ÿ S2. Dengan demikian, kesetaraan didefinisikan dalam hal perilaku "kotak hitam" eksternal dari program. Transformasi
adalah operasi yang memetakan program apa pun yang memenuhi kondisi penerapan transformasi ke program yang setara.

Lihat Ward (1989) dan Ward (1991a) untuk deskripsi semantik WSL dan metode yang digunakan untuk membuktikan
kebenaran penyempurnaan dan transformasi.

Bagian selanjutnya dari bagian ini menjelaskan transformasi yang akan kita gunakan nanti dalam derivasi
algoritma pelacakan mundur.

4.1 Memperluas pernyataan IF

Pernyataan if:
jika B maka S1 atau S2 fi; S

dapat diperluas melalui pernyataan berikut untuk memberikan:

jika B maka S1; S jika tidak S2; S fi

4.2 Memperbaiki Penugasan

Jika Q ÿ Q dan ÿx. Q ÿ ÿx. Q maka kita dapat menyempurnakan penugasan x := x .Q menjadi x := x .Q . Misalnya, jika ÿ = I ÿ
I maka x := x .x ÿ I ÿ x := x .x ÿ I .

8
Machine Translated by Google

4.3 Membagi Blok

Jika pernyataan S2 memberikan nilai baru ke x sebelum mengaksesnya maka blok: var x: S1; S2 end dapat dibagi
menjadi dua blok: var x: S1 end; var x: S2 end

4.4 Pembalikan Loop

Jika pernyataan S1 tidak mengandung jalan keluar yang dapat menyebabkan penghentian loop penutup (yaitu
dalam notasi Ward (1989) merupakan urutan yang tepat) maka loop:

melakukan S1; S2 dari

dapat dibalik menjadi:

S1; melakukan S2; S1 dari

Transformasi ini dapat digunakan dalam arah maju untuk memindahkan pengujian terminasi suatu perulangan ke
awal, sebelum mengubahnya menjadi perulangan while, atau dapat digunakan dalam arah sebaliknya untuk
menggabungkan dua salinan pernyataan S1.

4.5 Pembukaan Gulungan Lingkaran

Tiga transformasi berikutnya menyangkut berbagai bentuk pelepasan loop. Transformasi-transformasi ini
memainkan peran penting dalam pembuktian transformasi lain dan juga berguna secara umum.

Lemma 4.1 Pembukaan Loop:

selama B melakukan S od ÿ jika B maka S; selama B melakukan S od fi

Lemma 4.2 Pembukaan loop while secara selektif: Untuk setiap kondisi Q, kita memiliki:

selama B melakukan S od ÿ selama B melakukan S; jika B ÿ Q maka S fi od

Lemma 4.3 Unrolling Seluruh Loop: jika B ÿ B maka untuk setiap kondisi Q:

sementara B melakukan S od ÿ sementara B melakukan S; jika Q maka sementara B melakukan S od fi od

Untuk setiap transformasi ini ada generalisasi di mana, alih-alih memasukkan bagian yang “tidak digulung”
setelah S, bagian tersebut disalin ke dalam pemilihan posisi terminal yang sembarangan di S.

Transformasi kebalikannya, tentu saja, disebut loop rolling dan entire loop rolling.

4.6 Memperkenalkan Rekursi

Bagian ini memperkenalkan teorema penting tentang implementasi rekursif pernyataan. Bagian ini menunjukkan
bagaimana pernyataan umum dapat diubah menjadi pernyataan rekursif yang ekuivalen. Transformasi yang terlibat
dapat digunakan untuk mengimplementasikan spesifikasi rekursif sebagai prosedur rekursif, untuk memperkenalkan
rekursi ke dalam program abstrak guna mendapatkan program yang "lebih konkret" (yaitu lebih dekat dengan
implementasi bahasa pemrograman), dan untuk mengubah prosedur rekursif tertentu ke dalam bentuk yang
berbeda. Teorema ini digunakan dalam derivasi algoritma Ward (1996) dan Ward (1989), kami menggunakannya di
bawah ini pada Bagian 5.

Misalkan kita memiliki pernyataan S yang ingin kita ubah menjadi prosedur rekursif
proc F ÿ S. Hal ini dimungkinkan bilamana:

1. Pernyataan S disempurnakan oleh S[S /F] (yang menyatakan S dengan semua kemunculan F digantikan oleh
S ). Dengan kata lain, jika kita mengganti pemanggilan rekursif di S dengan salinan S maka kita memperoleh
penyempurnaan S ;

2. Kita dapat menemukan ekspresi t (disebut fungsi varian) yang nilainya dikurangi sebelum setiap kemunculan
S di S[S /F].

9
Machine Translated by Google

Ekspresi t tidak harus berupa bilangan bulat: himpunan apa pun ÿ yang memiliki tatanan yang berdasar dapat digunakan.
Untuk membuktikan bahwa nilai t direduksi, cukup dengan membuktikan bahwa jika t awalnya t0 , maka pernyataan {t ÿ t0}
dapat disisipkan sebelum setiap kemunculan S dalam S[S /F]. Teorema ini menggabungkan kedua persyaratan ini menjadi
satu kondisi:

Teorema 4.4 Jika merupakan orde parsial yang berdasar pada suatu himpunan ÿ dan t merupakan ekspresi yang memberikan
nilai dalam ÿ dan t0 merupakan variabel yang tidak muncul dalam S, maka jika untuk beberapa premis P

Misalkan P ÿ t ÿ t0 = t0 , maka P ÿ t ÿ t0 = t0.

Kemudian

P ÿ (S ÿ proc F ÿ S.)

Seringkali memungkinkan untuk memperoleh badan prosedur S yang sesuai dari pernyataan S dengan menerapkan
transformasi ke S, membaginya ke dalam kasus-kasus, dst., hingga kita memperoleh pernyataan S[S /F] yang masih

didefinisikan dalam bentuk S. Jika kita dapat menemukan fungsi varian yang sesuai untuk S[S /F] maka kita dapat
menerapkan teorema dan menyempurnakan S[S /F] untuk proc F ÿ S. yang tidak lagi didefinisikan dalam bentuk S.

Sebagai contoh kita akan mempertimbangkan fungsi faktorial yang sudah dikenal. Misalkan S = r := n!. Kita dapat
ubahlah ini (dengan mengacu pada definisi faktorial) untuk mendapatkan:

S ÿ jika n = 0 maka r := 1 jika tidak r := n.(n ÿ 1)! fi

Pisahkan penugasan: S ÿ jika

n = 0 maka r := 1 jika tidak n := n ÿ 1; r := n!; n := n + 1; r := nr fi

Jadi kita punya:

S ÿ jika n = 0 maka r := 1 jika tidak n := n ÿ 1; S ; n := n + 1; r := nr fi

Bilangan bulat positif n dikurangi sebelum salinan S menjadi (urutan Bahasa Indonesia: jadi jika kita menetapkan t menjadi n, ÿ menjadi N dan
umum pada bilangan asli), dan P menjadi benar, maka kita dapat membuktikan:

n t0 ÿ S ÿ jika n = 0 maka r := 1 jika tidak n := n ÿ 1; {n < t0}; S ; n := n + 1; r := nr fi

Jadi kita dapat menerapkan Teorema 4.4 untuk mendapatkan:

S ÿ proc X ÿ jika n = 0 maka r := 1 jika tidak n := n ÿ 1; X; n := n + 1; r := nr fi.

dan kami telah memperoleh implementasi rekursif dari faktorial.

4.7 Transformasi Rekursi menjadi Iterasi Transformasi

penghapusan rekursi tujuan umum berikut disajikan dalam Ward (1992).

Buktinya dapat ditemukan di Ward (1991b).

Misalkan kita mempunyai prosedur rekursif yang badannya adalah sistem tindakan reguler dalam bentuk berikut:

proc F(x) ÿ
tindakan A1 :
A1 ÿ S1.
. . . Ai ÿ Si.

. . . Bj ÿ Sj0; F(gj1(x)); Sj1; F(gj2(x)); . . . ; F(gjnj (x)); Sjnj . . . . tindakan akhir.

di mana Sj1, . . . , Sjnj mempertahankan nilai x dan tidak ada S yang mengandung panggilan ke F (yaitu semua panggilan ke
F tercantum secara eksplisit dalam tindakan Bj ) dan pernyataan Sj0, Sj1 . . . , Sjnjÿ1 tidak mengandung panggilan tindakan.

10
Machine Translated by Google

Total ada M +N tindakan: A1, . . . , AM, B1, . . . , BN . Perhatikan bahwa karena sistem tindakan bersifat reguler, maka tindakan
tersebut hanya dapat diakhiri dengan menjalankan panggilan Z yang akan mengakhiri pemanggilan prosedur saat ini.

Tujuannya adalah untuk menghapus rekursi dengan memperkenalkan tumpukan lokal L yang merekam operasi yang
"ditunda": Ketika panggilan rekursif diperlukan, kita "menundanya" dengan mendorong pasangan 0, e ke L (di mana e adalah
parameter yang diperlukan untuk panggilan rekursif). Eksekusi pernyataan Sjk juga harus ditunda (karena terjadi di antara
panggilan rekursif), kita merekam penundaan Sjk dengan mendorong j, k, x ke L. Di mana badan prosedur biasanya akan
berakhir (dengan memanggil Z), kita malah memanggil tindakan baru Fˆ yang mengeluarkan item teratas dari L dan
menjalankan operasi yang ditunda. Jika kita memanggil Fˆ dengan tumpukan kosong maka semua operasi yang ditunda telah
selesai dan prosedur berakhir dengan memanggil Z.

Teorema 4.5 Prosedur rekursif dalam bentuk: proc F(x) ÿ

tindakan A1 : A1
ÿ S1.

. . . Ai ÿ Si.

Misalkan , F ( gj1 (x) = F ( gj2(x)) = F( gjnj ( ...

. . . tindakan akhir.

di mana Sj1, . . . , Sjnj seperti di atas, setara dengan prosedur iteratif berikut yang menggunakan tumpukan lokal baru L dan
variabel lokal baru m:

proc F (x) ÿ var

L := Bahasa Indonesia:
M:

tindakan A1 :
A1 ÿ S1[panggil Fˆ/panggil Z].
. . . Ai ÿ Si [panggilan Fˆ/panggilan Z].
Misalkan gj1(x)j, 1, x,0, gj2 ( x), . . . ,0, gjnj ( x ), j, nj , x + L;
panggil Fˆ.
. . . Fˆ ÿ jika L = maka panggil Z, jika
muncul

tidak m, x ÿÿ L; jika m
= 0 ÿ panggil A1 . . . m =

j, k ÿ Sjk; panggil Fˆ
. . . fi fi. tindakan akhir berakhir.

Perhatikan bahwa setiap prosedur F(x) dapat direstrukturisasi ke dalam bentuk yang diperlukan; sebenarnya mungkin
ada beberapa cara berbeda untuk menyusun F(x) yang memenuhi kriteria yang diperlukan.

Pertimbangkan program faktorial rekursif yang kita turunkan di atas (Bagian 4.6): proc X ÿ
if n = 0 then r := 1 else n := n ÿ 1; X; n := n + 1; r := nr fi.

Kita dapat merestrukturkannya sebagai:

proc X ÿ
tindakan A : A
ÿ jika n = 0 maka r := 1; panggil Z jika tidak panggil B fi.
B ÿ n := n ÿ 1; X; n := n + 1; r := nr; panggil Z. tindakan akhir.

Ini adalah bentuk yang tepat untuk menerapkan Teorema 4.5. Ini
menghasilkan:
proc X ÿ var L :=M:
Bahasa Indonesia:

tindakan A :

A ÿ jika n = 0 maka r := 1; panggil Fˆ jika tidak, panggil B fi.

11
Machine Translated by Google

B ÿ n := n ÿ 1; L := 0, 1 + L; disebut Fˆ.
Fˆ ÿ jika L = maka panggil Z
muncul
yang lain m ÿÿ L;
jika m = 0 ÿ panggil A

m = 1 ÿ n := n + 1; r := tidak; panggil Fˆ fi fi.

tindakan akhir berakhir.

Perhatikan bahwa B mendorong 0 ke L, lalu memanggil Fˆ yang segera melepaskan 0 dan memanggil A. Jadi kita bisa
memanggil A secara
langsung:
proc X ÿ var L :=M:
Bahasa Indonesia:

tindakan A :

A ÿ jika n = 0 maka r := 1; panggil Fˆ jika tidak, panggil B fi.

B ÿ n := n ÿ 1; L := 1 + L; panggil A.
Fˆ ÿ jika L = maka panggil Z
muncul
yang lain m ÿÿ L;
jika m = 0 ÿ panggil A

m = 1 ÿ n := n + 1; r := tidak; panggil Fˆ fi fi.

tindakan akhir berakhir.

Sekarang kita hanya memasukkan angka satu ke L, yang perlu kita ketahui hanyalah panjangnya1 . Jadi, ubah L menjadi
variabel integer dan hapus variabel lokal m yang berlebihan: proc X ÿ var
L := 0: actions
A:

A ÿ jika n = 0 maka r := 1; panggil Fˆ jika tidak, panggil B fi.

B ÿ n := n ÿ 1; L := L + 1; panggil A.
Fˆ ÿ jika L = 0 maka panggil Z,

jika tidak L := L ÿ 1; n := n + 1; r := nr; panggil Fˆ fi.

tindakan akhir berakhir.

Sekarang tindakan A dan B tinggal menyalin n ke L, menetapkan r ke 1, menetapkan n ke 0, dan memanggil Fˆ. Tindakan Fˆ
dapat dinyatakan sebagai loop while, jadi kita punya:
proc X ÿ var
L := n: r := 1;
n := 0; while L = 0
do L := L ÿ 1; n := n + 1; r := nr od end.

Perhatikan bahwa L mencapai nol saat n mencapai nilai aslinya, jadi kita dapat menuliskan perulangan while sebagai

perulangan for: proc X ÿ r := 1; for i := 1 to n do r := ir od.

Ini adalah algoritma faktorial yang efisien, berasal dari spesifikasi yang diberikan di Bagian 4.6

4.8 Iterasi Nondeterministik

Kami memperkenalkan notasi berikut untuk iterasi nondeterministik atas elemen-elemen himpunan hingga:

untuk i ÿ I lakukan S od =DF var i, I := I :

sementara saya = ÿ melakukan

saya := saya .(saya ÿ saya ); Saya := Saya {i}; Akhir yang aneh

1Secara teknis, kita memperkenalkan variabel baru, katakanlah l, yang mencatat panjang L. Kemudian kita mengganti
referensi ke L dengan referensi yang sesuai ke l (ini dimungkinkan karena kita hanya merujuk ke panjang L). Kemudian L
menjadi redundan dan dapat dihapus. Akhirnya kita mengganti nama l menjadi L

12
Machine Translated by Google

Ini memilih elemen dari set (terbatas) I dalam urutan yang sewenang-wenang dan mengeksekusi S sekali untuk setiap
elemen.

Lemma 4.6 Jika I1 dan I2 mempartisi I (yaitu I = I1 ÿ I2 dan I1 ÿ I2 = ÿ) maka loop for disempurnakan menjadi pasangan
loop:

untuk i ÿ I melakukan S od ÿ untuk i ÿ I1 melakukan S od; untuk i ÿ I2 melakukan S od

Bukti: Pembuktiannya dilakukan dengan induksi pada ukuran himpunan (terhingga) I menggunakan transformasi 4.2,
4.3 dan 4.5.

Dengan induksi pada lemma ini kita memperoleh hasil yang lebih umum:

Lemma 4.7 Misalkan himpunan berhingga I dipartisi sebagaimana

for di atas disempurnakan menjadi loop bersarang ganda:
jÿJ Ij dimana himpunan Ij saling lepas. Maka

untuk i ÿ I lakukan S od ÿ untuk j ÿ J lakukan

untuk i ÿ Ij lakukan S od od

Bukti: Dengan induksi pada ukuran J, menggunakan lema sebelumnya.

5 Algoritma Backtracking Sederhana: Derivasi

Jenis algoritme yang kami pertimbangkan adalah algoritme yang mengharuskan kami menghitung, atau memproses,
himpunan solusi untuk suatu masalah. Solusi ini direpresentasikan sebagai urutan elemen dari beberapa domain D yang
memenuhi dua sifat: "kelengkapan" dan "validitas". Kami menggunakan Dÿ untuk menunjukkan himpunan semua urutan
elemen D yang terbatas. Setiap solusi akan dibangun dengan memperluas solusi yang tidak lengkap tetapi valid secara
berurutan hingga menjadi lengkap atau kami memiliki cara sederhana untuk menentukan bahwa tidak ada perluasan
yang valid. Spesifikasi kami dapat dinyatakan
sebagai:

SPEC =DF untuk p ÿ { x ÿ D * | V (x) ÿ C(x) } do process(p) od di mana

process adalah prosedur yang akan kita jalankan untuk setiap sekuens p yang lengkap dan valid. V (p) benar untuk
setiap p yang valid dan C(p) benar untuk setiap p yang lengkap.

Segmen awal dari suatu barisan p adalah barisan p yang sedemikian rupa sehingga ÿq ÿ Dÿ . p = p + q. Segmen awal
yang tepat p dari p adalah segmen awal yang sedemikian rupa sehingga p = p . Untuk semua segmen awal yang tepat p
dari p, kita mengasumsikan bahwa:

• Nilai yang lengkap tidak dapat diperluas lebih lanjut, yaitu C(p) ÿ (¬C(p ) ÿ ¬V (p )); dan • Setiap segmen

awal yang tepat dari nilai yang valid juga valid, yaitu V (p ) ÿ V (p).

Karena kami tertarik pada perluasan solusi yang valid, kami memperluas spesifikasi untuk memproses semua perluasan
yang valid dan lengkap dari urutan tertentu dalam urutan yang sembarangan:

SPEC(p) =DF untuk q ÿ { x ÿ D * | px ÿ V (x) ÿ C(x) } lakukan proses(q) od

di mana px =DF ÿp ÿ Dÿ . x = p + p .

Derivasi algoritma dari spesifikasi ini mengikuti tiga tahap:

1. Memperkenalkan rekursi;

2. Mengubah rekurensi menjadi iterasi; 3.

Optimasi.

5.1 Memperkenalkan Rekursi

Langkah pertama adalah mengubah spesifikasi menjadi bentuk yang sesuai untuk diterjemahkan ke prosedur rekursif
menggunakan Teorema 4.4. Kita ingin mengubah SPEC(p) menjadi pernyataan yang berisi salinan

13
Machine Translated by Google

dari SPEC(p) di mana nilai p “lebih kecil” menurut beberapa urutan yang beralasan. Pertama, kita perkenalkan pernyataan
if untuk menghilangkan kasus-kasus khusus. Kita dapat berasumsi bahwa SPEC(p) hanya dipanggil ketika V (p) bernilai
benar karena p yang tidak valid tidak dapat memiliki ekstensi yang valid. Kita tahu bahwa SPEC(p) ÿ process(p) jika C(p)
bernilai benar, jadi kita perkenalkan pernyataan if yang menguji C(P). Jika C(p) bernilai salah, maka semua nilai yang ingin
kita proses harus lebih besar dari p, jadi kita punya: SPEC(p) ÿ if C(p) then process(p)

jika tidak untuk q ÿ { p + q | q ÿ Dÿ ÿ V (p + q) ÿ C(p + q) } lakukan proses(q) od

di mana kita tahu bahwa setiap elemen himpunan yang kita ulangi akan lebih panjang dari p. Jadi kita dapat menulis
himpunan ini sebagai gabungan dari subhimpunan yang terpisah:

{p+t+q ÿ D} * Misalkan p + t + q adalah himpunan semua persamaan (p + t + q) dan (c) adalah himpunan semua persamaan (p + t + q).

tÿD

Ini berarti kita dapat menyempurnakan loop menjadi loop ganda (dengan Lemma 4.7):
SPEC(p) ÿ if
C(p) then process(p) else for
t ÿ D do for q ÿ { p + t
+ q ÿ Dÿ | V (p + t + q) ÿ C(p + t + q) } do process(q) od

Jika ¬V (p + t) maka { p + t + q ÿ Dÿ | V (p + t + q) ÿ C(p + t + q) } = ÿ dan perulangan for disempurnakan untuk melewati:

SPEC(p) ÿ jika
C(p) maka proses(p) atau
untuk t ÿ D lakukan
jika V (p + t)
maka untuk q ÿ { p + t + q ÿ Dÿ | V (p + t + q) ÿ C(p + t + q) } lakukan proses(q) od

Jadi kita punya:

SPEC(p) ÿ jika C(p) maka proses(p) atau untuk

t ÿ D lakukan jika V (p
+ t) maka SPEC(p + t) fi od

Kita tahu bahwa himpunan { p + q | q ÿ Dÿ ÿ V (p + q) ÿ C(p + q) } berhingga, sehingga ada batas atas pada panjang barisan
yang valid, katakanlah L. Jadi kita dapat menggunakan L ÿ (p) sebagai fungsi varian dan memperkenalkan rekursi
menggunakan Teorema 4.4: SPEC(p) ÿ proc
processall(p) ÿ if C(p) then process(p) else
for t ÿ D do if V (p + t) then
processall(p + t) fi od.

Kami telah mengganti nama prosedur rekursif F, yang disediakan oleh Teorema 4.4, menjadi processall dan menjadikan pa
parameter dari prosedur ini.

5.2 Penghapusan Rekursi

Bahasa Indonesia: Setelah memperkenalkan rekursi, langkah berikutnya adalah mengubah prosedur rekursif menjadi
padanan iteratif, menggunakan Teorema 4.5. Pertama, perhatikan bahwa kita dapat mengganti parameter p dengan variabel
terakhir

global karena kita dapat memulihkan nilainya dan nilai t setelah panggilan rekursif dengan melakukan t ÿÿ p. Perulangan
for nondeterministik memperkenalkan variabel lokal lain D (serta t) yang mencatat elemen-elemen D yang tersisa yang
belum diproses. Jika kita berasumsi (tanpa kehilangan keumuman) bahwa D adalah himpunan bilangan bulat dari 1 hingga
D (ukuran D), yaitu D = { i ÿ N | 1 i D }, maka kita dapat menyempurnakan perulangan for nondeterministik menjadi
perulangan deterministik yang memproses elemen-elemen

14
Machine Translated by Google

D secara berurutan. Hal ini karena nilai t memberi tahu kita elemen D mana yang belum diproses, pada kenyataannya D = { i ÿ N |
t < i D }: SPEC ÿ

var p := :
prosesall akhir
dimana

proc prosesall ÿ jika

C(p) maka proses(p) jika tidak
t := 1;
sementara t D lakukan
terakhir

jika V (p + t) maka p := p + t; prosesal; t ÿÿ p fi; t := t + 1 od.

Prosedur processall memproses semua ekstensi yang valid dari (variabel global) p dalam urutan tertentu. Spesifikasi kami “tidak
lengkap” dalam arti tidak menentukan urutan pemrosesan elemen yang valid dan lengkap. Dengan demikian, implementasi
spesifikasi bebas memilih urutan yang paling sesuai.

Tata ulang badan prosedur sebagai sistem tindakan: proc processall

ÿ actions A : A ÿ if C(p)
then process(p);

panggil Z else t := 1; panggil A1 fi.

A1 ÿ jika t D maka jika V (p + t) maka panggil B1 jika tidak

panggil A2 fi
kalau tidak sebut saja Z fi.

A2 ÿ t := t + 1; panggil A1. ÿÿ p;
terakhir

B1 ÿ p := p + t; prosesal; t panggil A2. tindakan akhir.

Ini sekarang dalam bentuk yang tepat untuk menerapkan transformasi penghapusan rekursi (Teorema 4.5).
Ada satu tindakan “tipe B” (B1) yang berisi satu panggilan rekursif. Jadi S10 = p := p + t dan ÿÿ p; panggil A2. Dengan menghapus
terakhir

rekursi, kita peroleh: S11 = t proc processall ÿ var L :=

Bahasa Indonesia:
M:
tindakan A :

A ÿ jika C(p) maka proses(p); panggil Fˆ jika tidak

t := 1; panggil A1 fi.
A1 ÿ jika t D maka jika V (p + t) maka panggil B1 jika tidak
panggil A2 fi
kalau tidak sebut saja Fˆ fi.

A2 ÿ t := t + 1; panggil A1.
B1 ÿ p := p + t; L := 0,1, 1 + L; disebut Fˆ.
Fˆ ÿ jika L = maka panggil Z
muncul
jika tidak m ÿÿ L;
jika m = 0 ÿ panggil A
terakhir

m = 1, 1 ÿ t ÿÿ p; panggil A2 fi fi. tindakan akhir berakhir.

5.3 Optimasi

Seperti pada algoritma faktorial (Bagian 4.7) kita masukkan 0 ke L dan segera memunculkannya dan memanggil A.
Jadi kita dapat menghindari push dan memanggil A secara langsung. Seperti sebelumnya, kita sekarang memiliki tumpukan
elemen identik yang dapat diimplementasikan sebagai integer. Namun, dalam kasus ini, kita dapat melakukannya dengan lebih
baik, karena panjang L sama dengan panjang p, jadi kita dapat menguji p alih-alih L dan menghapus L sepenuhnya:

15
Machine Translated by Google

proses proc semua ÿ

tindakan A :

A ÿ jika C(p) maka proses(p); panggil Fˆ jika

tidak t := 1; panggil A1 fi.
A1 ÿ jika t D maka jika V (p + t) maka panggil B1 jika tidak
panggil A2 fi
kalau tidak sebut saja Fˆ fi.

A2 ÿ t := t + 1; panggil A1.
B1 ÿ p := p + t; panggil A.
Fˆ ÿ jika p = maka panggil Z, jika
terakhir
tidak t ÿÿ p; panggil A2 fi. tindakan akhir.

Hapus sistem tindakan dan restrukturisasi:

SPESIFIKASI ÿ

var p := ,t:
lakukan jika C(p) maka proses(p);
jika p = maka keluar fi;
terakhir

t ÿÿ p; t := t + 1 jika tidak
t := 1 fi; lakukan
jika V (p + t) ÿ t D maka keluar jika tidak p = ÿ t > D
maka keluar(2) jika tidak t > D maka t ÿÿ p; t :=
terakhir
t + 1 jika tidak t := t + 1 fi od; p := p + t od akhir

Keluarkan pernyataan pertama dari loop dan ubah menjadi loop tunggal. Kita akan menganggap C() salah (karena jika
tidak, tidak ada sekuens lain yang valid) dan mendefinisikan C (t, p) =DF C(p + t), V (t, p) =DF V (p + t), process (t, p) =DF
process(p + t). var p := ,t := 1: do if V (t, p) ÿ t D then p := p + t; if C(p) then
process(p); t ÿÿ p; t :=
t + 1 else t := 1 fi;
terakhir

elsif p = ÿ t > D maka keluar elsif t > D

terakhir
maka t ÿÿ p; t := t + 1 jika tidak t := t + 1 fi
akhir

Dorong pernyataan p := p + t ke dalam pernyataan if bagian dalam: var

p := ,t := 1: do if V (t,
p) ÿ t D then if C (t, p) then process (t, p); t := t + 1 else p := p + t; t := 1 fi;

elsif p = ÿ t > D maka keluar elsif t > D

terakhir
maka t ÿÿ p; t := t + 1 jika tidak t := t + 1 fi
akhir

Terakhir, susun ulang pengujian untuk membuat loop while:

var p := ,t := 1: while p
= ÿ t D do
terakhir
jika t > D maka t ÿÿ p; t := t + 1 jika tidak
V (t, p) maka jika C (t, p) maka proses (t, p); t := t + 1 jika tidak p := p + t;
t := 1 fi
jika tidak t := t + 1 fi od akhir

16
Machine Translated by Google

Ini adalah algoritma backtracking dasar kami. Derivasi hanya menggunakan transformasi yang telah terbukti
mempertahankan semantik (Ward (1989), Ward (1991a), Ward (1992), Ward (1994)) sehingga kami dapat menjamin
bahwa algoritma ini mengimplementasikan spesifikasi SPEC dengan benar.

6 Beberapa Aplikasi
Bagian ini menguraikan masalah-masalah yang memunculkan algoritma yang disajikan dalam makalah ini. Masalah-
masalah ini menyangkut representasi konkret, melalui fungsi atau himpunan, dari struktur aljabar.
Dualitas batu untuk aljabar Boolean menyediakan prototipe untuk representasi semacam itu. Kami menguraikan latar
belakang matematika secara singkat, tetapi mulai dengan menjelaskan bentuk algoritma backtracking yang kami
butuhkan.

6.1 Peta Pelestari Hubungan

Kita diberi dua struktur relasional berhingga dengan tipe yang sama. Yaitu, kita memiliki dua himpunan berhingga X
dan Y dan dua himpunan berhingga relasi RX pada X dan RY pada Y sedemikian rupa sehingga untuk setiap relasi ÿ
di RX terdapat relasi ÿ yang bersesuaian di RY dengan aritas yang sama, dan sebaliknya. Untuk penyederhanaan
dalam subbagian ini kita akan mengasumsikan bahwa semua relasi adalah biner. Tujuannya adalah untuk menemukan
semua pemetaan ÿ : X ÿ Y yang mempertahankan semua relasi, yaitu untuk semua relasi ÿ ÿ RX, semua pasangan
elemen di X yang terkait dengan ÿ, memetakan ke elemen di Y yang terkait dengan ÿ . Secara lebih formal:

Definisi 6.1 Suatu fungsi ÿ : X ÿ Y bersifat mempertahankan relasi jika:

ÿÿ ÿ RX. ÿx, y ÿ X.(x ÿ y) ÿ (ÿ(x) ÿ ÿ(y))

Jadi kita ingin mencari ukuran himpunan:

ÿ : X ÿ Y | ÿÿ ÿ RX. ÿx, y ÿ X.(x ÿ y) ÿ (ÿ(x) ÿ ÿ(y))

Tanpa kehilangan keumuman, kita dapat menganggap X dan Y sebagai himpunan bilangan bulat: X = {1, 2, . . . , #X}
dan Y = {1, 2, . . . , #Y}. Kita dapat merepresentasikan peta parsial ÿ : {1, 2, . . . , n} ÿ Y (di mana n #X) sebagai barisan
p dengan panjang n di mana p[i] = ÿ(i). Barisan lengkap adalah barisan dengan panjang #X dan barisan yang valid
adalah barisan yang mempertahankan relasi. Jadi, kita memiliki definisi:

C(p) = DF (p) = #XV (p) =

DF ÿÿ ÿ RX. ÿx, y, 1 x, dan y (p).(x ÿ y) ÿ (p[x] ÿ p[y]))

Setiap subhimpunan dari peta pelestarian relasi (sebagian atau total) juga merupakan pelestarian relasi, sehingga
definisi ini jelas memenuhi ketentuan untuk algoritma penelusuran balik.

Algoritma iteratif sebenarnya menggunakan V (t, p) (didefinisikan sebagai V (t, p) = V (p + t) yang hanya dievaluasi
ketika V (p) bernilai benar. Ini berarti bahwa kita hanya perlu memeriksa pasangan (x, y) di mana salah satu atau
kedua x atau y sama dengan t. Jadi kita dapat menggunakan definisi:

V (t, p) =DF ÿÿ ÿ RX. ÿx, 1 x < n.(n ÿ x ÿ t ÿ p[x]) ÿ (x ÿ n ÿ p[x] ÿ t) ÿ (n ÿ n ÿ t ÿ t)

Tentukan nilai t dan p pada tabel berikut :

di mana n = (p) + 1 (jadi V (t, p) menguji apakah t adalah bayangan yang valid untuk n dalam perluasan p dari {1,
2, . . . , n ÿ 1} ke {1, 2, . . . , n}).

Untuk implementasinya kita hanya perlu mencatat ukuran X dan Y (dalam variabel SX dan SY).
Kami merepresentasikan dua set relasi menggunakan dua array integer tiga dimensi RX dan RY (kami dapat
menggunakan array boolean tetapi array integer mungkin sedikit lebih cepat diakses dan memori tidak terlalu mahal).
Integer rho merepresentasikan relasi ÿ di mana:

1 jika x ÿ y 1 jika x ÿ y
Persamaan RX[rho, x, y] = dan RY [rho, x, y] =
0 jika tidak 0 jika tidak

17
Machine Translated by Google

Pengujian pelestarian relasi diimplementasikan sebagai loop while bersarang ganda yang menyimpan hasil
dalam variabel Boolean rp. Loop berakhir segera setelah rp menjadi salah, untuk menghindari pengujian yang tidak perlu.
Variabel R mencatat jumlah relasi. Jadi, kita memiliki prosedur pengujian berikut yang menetapkan rp
menjadi benar jika V (t, p) benar, asalkan n = (p) + 1 dan V (p) benar: proc DO(t, p,
n) ÿ var np := 0: rp :=
true; rho := 1;
while rho R ÿ rp do if
RX[rho, n, n] = 1 ÿ
RY[rho,t,t] = 0 then rp := false else np := 1;
while np < n ÿ rp
do if (RX[rho,
n, np] = 1 ÿ RY[rho,t,
p[np]] = 0)
ÿ (RX[rho, np, n] = 1 ÿ RY[rho, p[np],t] = 0) maka
rp := salah fi od fi od akhir.

Perhatikan bahwa versi ini akan berulang kali mencari kumpulan elemen yang terkait dengan elemen tertentu
dalam X untuk setiap relasi. Jika relasi X cukup jarang (tidak banyak pasangan elemen yang terkait) maka
akan lebih efisien untuk merepresentasikan relasi X menggunakan dua array integer yang terkait dengan X
dan yang terkait dengan X yang merekam informasi berikut:

rel to X[rho, n, 0] = jumlah elemen x sehingga n ÿ x rel to X[rho, n,i]

= elemen ke i xi sehingga n ÿ xi rel X to[rho, n, 0] = jumlah
elemen x sehingga x ÿ n rel X to[rho, n,i] = elemen ke i xi sehingga
xi ÿ n

Bahasa Indonesia: Maka versi DO kita

yang telah diperbaiki
adalah: proc DO(p,t, n) ÿ var np := 0,
numrels := 0,i := 0:
rp := true; rho := 1; while
rho R ÿ rp do numrels := rel to
X[rho,
n, 0]; i := 1; while i numrels ÿ
rp do np := rel to X[rho,
n,i]; if np < n then if RY[rho,t, p[np]] = 0 then rp := false fi elsif np
= n then if RY[rho,t,t] = 0 then rp := false fi fi; i := i + 1 od;

jika
rp maka numrels := rel X to[rho, n, 0];
i := 1;
sementara i numrels ÿ rp do
np := rel X to[rho, n,i]; jika
np < n ÿ RY[rho, p[np],t] = 0 maka rp := false fi; i := i + 1 od
fi od akhir.

6.2 Masalah dalam Teori Dualitas

Misalkan kita diberi kelas A aljabar bertipe tetap. Asumsikan lebih lanjut bahwa A dihasilkan dari aljabar finit
P yang diberikan dengan membentuk produk, subaljabar, dan salinan isomorfik: dalam simbol, A = ISP(P).
Struktur seperti itu sering muncul sebagai model aljabar untuk logika klasik dan non-klasik, misalnya. Dalam
situasi ini, P memainkan peran "aljabar nilai kebenaran". Misalnya:

18
Machine Translated by Google

1. Misalkan P adalah kisi distributif 2 elemen 2 = ({0, 1}; ÿ, ÿ, 0, 1) (jadi 0 dan 1 diperlakukan
sebagai operasi nullary). Maka A adalah kelas D dari kisi-kisi distribusi {0, 1}.

2. Misalkan P adalah aljabar Boolean 2 elemen ({0, 1}; ÿ, ÿ, , 0, 1). Maka A adalah kelas B dari
Aljabar Boolean.

3. Dengan mengambil P sebagai ({0, a, 1}; ÿ, ÿ, ÿ, 0, 1), di mana ({0, a, 1}; ÿ, ÿ, 0, 1) adalah kisi distributif {0, 1}
dengan 0 < a < 1 dan operator negasi ÿ memenuhi ÿ0 = 1, ÿ1 = 0 dan ÿa = a, kita memperoleh kelas K dari
aljabar Kleene.

Dalam contoh-contoh ini dan contoh-contoh berbasis logika lainnya, P memiliki struktur kisi yang
mendasarinya, dengan operasi ÿ dan ÿ yang memodelkan disjungsi dan konjungsi. Untuk selanjutnya, kita akan
selalu berasumsi bahwa P memiliki reduksi kisi, karena ini menyederhanakan teori yang kita andalkan (meskipun
kita mencatat bahwa pekerjaan menarik masih menanti di kelas-kelas aljabar yang batasan ini tidak terpenuhi).
Dalam banyak kasus, terjadi bahwa A = ISP(P) bertepatan dengan varietas HSP(P), di mana H menunjukkan
pembentukan citra homomorfik. Kemudian, dengan teorema terkenal G. Birkhoff, A dapat ditentukan oleh
sekumpulan identitas. Ini terjadi untuk masing-masing D, B, dan K di atas. (Jika kuasivarietas ISP(P secara ketat
lebih kecil daripada varietas HSP(P), tidak semuanya hilang. Namun, teori representasi yang lebih rumit,
menggunakan struktur multi-sortir, kemudian diperlukan (lihat Davey & Priestley (1987)).)

Diberikan A = ISP(P), kita dapat mencari representasi konkret untuk aljabar-aljabar di A. Pertanyaan penting
lain yang harus ditangani adalah penentuan aljabar bebas FA (n) pada n generator (perhatikan bahwa aljabar-
aljabar bebas di HSP(P) selalu terletak di ISP(P), sehingga untuk soal ini cukup mempertimbangkan kelas-kelas
bentuk yang terakhir). Sebuah studi sistematis utama tentang representasi aljabar, dengan cara yang
merepresentasikan aljabar-aljabar bebas dengan cara yang sangat alami, dilakukan oleh BA Davey dan H. Werner
dalam Davey & Werner (1983). Teori mereka mencakup banyak dualitas yang terkenal (termasuk dualitas Stone
untuk B dan dualitas Priestley untuk D) dalam kerangka umum. Dalam makalah ini, struktur-struktur finitlah yang
menjadi perhatian kita. Dengan demikian, kita akan membatasi diri pada aljabar-aljabar finit di A. Hal ini
menghindarkan kita dari keharusan memperkenalkan mesin topologi yang terlibat dalam merepresentasikan
aljabar-aljabar arbitrer. Representasi yang kami perlukan bergantung pada pilihan yang tepat dari struktur
relasional Pÿ = (P; R) pada himpunan P yang mendasarinya dari P. Diberikan himpunan R dari relasi pada P, kami
memperluas setiap ÿ ÿ R titik demi titik ke pangkat P. Untuk setiap A ÿ A yang terbatas, definisikan dual dari A
sebagai D(A), di mana D(A) adalah himpunan A (A, P) dari homomorfisme-A dari A ke P, dengan struktur relasional
yang diwarisi dari Pÿ A. Kemudian, dari X = D(A) kami membentuk aljabar E(X), yang didefinisikan sebagai
Kemudian teori dalam himpunan yang mempertahankan R dengan struktur aljabar yang diwarisi dari P X.
Davey & memetakan dari X ke Pÿ , Werner (1983) (khususnya Teorema 1.18) menyiratkan bahwa kita memiliki teorema berikut.

Teorema 6.2 Asumsikan bahwa A = ISP(P) adalah kelas aljabar sedemikian rupa sehingga P adalah aljabar finit
dengan struktur kisi yang mendasarinya. Maka dimungkinkan untuk memilih R sehingga

1. A ÿ= ED(A) untuk setiap A ÿ A berhingga Dan Bahasa Indonesia:

N
2. D(FA (n)) = Pÿ n (sehingga FA (n) merupakan aljabar semua pemetaan pemelihara R dari Pÿ ( 1 n < ke Pÿ
ÿ)).
2.
Selanjutnya, R di atas dapat dipilih untuk terdiri dari hubungan biner, yang masing-masing merupakan subaljabar dari P

Bahasa Indonesia: Jika (1) dalam Teorema 6.2 berlaku, kita katakan bahwa R menghasilkan dualitas pada
(aljabar finit dalam) A. Untuk aljabar Boolean, kita ambil R = ÿ, sementara untuk D kita memperoleh dualitas
(jadi 2ÿ adalah rantai 2-elemen, Priestley dengan memilih R pada {0, 1} relasi pertidaksamaan di mana 0 < 1
Bahasa Indonesia:

yang memuat relasi tunggal sebagai himpunan terurut). Dalam contoh-contoh ini, himpunan R yang cocok
dikenali dengan melihat ke belakang, dualitas diketahui sebelum teori Davey–Werner dikembangkan. Sejak
publikasi Davey & Werner (1983), berbagai teknik (terutama metode piggyback Davey dan Werner) telah dirancang
yang membuatnya cukup mudah untuk mengidentifikasi himpunan R yang akan menghasilkan dualitas pada A.
Namun, himpunan seperti itu mungkin sering kali terlalu besar dan kompleks untuk mengarah pada dualitas yang
bisa diterapkan. Hal ini diilustrasikan secara mencolok oleh subvarietas dari varietas Bÿ dari aljabar-p distributif.
Varietas-varietas ini pertama kali dibahas oleh KB Lee Lee (1970). Ia menunjukkan bahwa subvarietas non-trivial yang tepat dari Bÿ

19
Machine Translated by Google

B0 ÿ B1 ÿ . . . (di mana B0 = B dan B1 adalah kelas yang dikenal sebagai aljabar Stone). Varietas ini dapat didefinisikan
secara ekuivalen. Atau, Teorema Produk Sublangsung Birkhoff menyiratkan bahwa mereka secara ekuivalen diberikan
*
oleh Bn = ISP(P = (2 n ÿ 1; ÿ, ÿ, kisi denganN puncak
), dimana
baru
P yang
N berdampingan, , 0, 1) menunjukkan n-atom Boolean
dan dengan operasi ÿ pseudokomplementasi yang diberikan oleh

A * = maks { c | a ÿ c = 0 } .

Untuk menghindari kasus-kasus degeneratif, maka selanjutnya kita mengasumsikan n = 3. Seperti yang ditunjukkan dalam
Davey & Priestley (1993a), dualitas diperoleh untuk Bn dengan mengambil Pÿn = (Pn; Rn), di mana himpunan Rn dari relasi terdiri dari

(i) grafik 3 endomorfisme, e, f, g dari P (ii) himpunan Tn N,

Dan
2
subaljabar dari P N
diindeks oleh partisi integer n.

Dalam (i), f dan g adalah automorfisme dan ditentukan oleh permutasi yang mereka hasilkan pada yaitu siklus (1 2 . . .
atom P N, n) dan (1 2). Dalam (ii) |Tn| tumbuh secara eksponensial dengan n, dan wajar untuk bertanya apakah
setiap subset yang tepat dari Rn masih berfungsi untuk menghasilkan dualitas. Partisi n menjadi k bagian adalah k-tuple
· · · ÿk
(ÿ1, . . . , ÿk) dari bilangan asli di mana ÿ1 ÿi = n. Dua dari relasi yang diinduksi partisi dan Tn isomorfik
dalam aku=1sebagai aljabar
tepat ketika partisi terkait memiliki jumlah bagian yang sama. Dugaan optimis tetapi masuk akal adalah bahwa dualitas
akan diperoleh dengan mereduksi Tn dengan memilih hanya satu partisi k-bagian untuk setiap k (memberikan relasi n + 3
secara total).

2
Diberikan himpunan R subaljabar dari P yang diketahui menghasilkan dualitas untuk kelas A = ISP(P), bagaimana
kita dapat menguji apakah himpunan bagian yang tepat R = R {ÿ} masih menghasilkan dualitas? Tentu saja jika himpunan
tereduksi R gagal memberikan A ÿ= ED(A) hanya untuk satu A ÿ A maka relasi ÿ tidak dapat diabaikan.
Menghilangkan relasi tidak dapat mengurangi ukuran ED(A), jadi pokok permasalahannya adalah apakah jumlah peta yang
mempertahankan R dari D(A) ke (P; R ) lebih besar daripada ukuran aljabar uji A. Kita katakan R menghasilkan dualitas
pada A jika tidak ada peta tambahan yang dapat dibolehkan.

Ketika mencoba memutuskan apakah ÿ ÿ R dapat dibuang, pilihan alami untuk aljabar uji A adalah ÿ, yang berarti
relasi ÿ dianggap sebagai aljabar (ingat bahwa setiap relasi kita adalah subaljabar dari P
2
). Di sini (akhirnya!) kita memiliki masalah komputasi: bandingkan ukuran A dengan ukuran
himpunan ED(A) dari peta yang mempertahankan R dari D(A) ke (P; R ). Versi paling awal dari algoritma penelusuran balik
kami (implementasi dalam VAX BASIC) berhasil menunjukkan bahwa tidak ada hubungan yang disebabkan oleh partisi
yang dapat dibuang dari dualitas untuk B3 (seperti yang diharapkan, karena setiap partisi 3 memiliki jumlah bagian yang
berbeda). Kasus uji kritis untuk dugaan kami muncul dengan n = 4 dan hubungan ÿ1 dan ÿ2 yang terkait dengan partisi 2
bagian (2, 2) dan (3, 1).
Di sini D(ÿ ) = D(ÿ ) memiliki 42 elemen, |P4| = 17, dan |R4| = 8. Kami berusaha menghitung jumlah
1 2
dari peta ÿ : D(ÿ ) ÿ Pÿ4 dengan mempertahankan R4{ÿi} (i = 1, 2). Perhitungan ini berhasil dilakukan pada PC, tetapi
Saya

hanya setelah pilihan urutan elemen domain yang cermat telah dibuat. Sebelum menunjukkan bagaimana urutan elemen
memengaruhi perhitungan, kami simpulkan sejarah masalah Bn .

Ternyata dengan menghilangkan ÿ1 atau ÿ2 tidak menghancurkan dualitas pada aljabar uji ÿ =ÿ2
1
(meskipun keduanya dihilangkan). Hasil negatif ini konsisten dengan dugaan bahwa hanya satu dari hubungan tersebut
yang dibutuhkan, tetapi tidak membuktikannya. Pada titik ini, pemeriksaan keluaran komputer memberikan wawasan yang
cukup untuk memungkinkan dugaan tersebut dikonfirmasi secara matematis untuk n = 4, dan selanjutnya untuk n umum.
Yang jauh lebih penting, hal ini menyebabkan Davey dan Priestley (Davey & Priestley (1993b)) membuktikan teorema yang
berikut ini merupakan kasus khusus.

Teorema 6.3 Asumsikan A seperti pada Teorema 6.2, bahwa R menghasilkan dualitas pada A (ÿ Bahasa Indonesia:

dan biarkan R = R{ÿ}

ÿ R). Maka R menghasilkan dualitas pada A jika dan hanya jika R menghasilkan dualitas pada aljabar ÿ.

Dengan demikian, pengujian redundansi relasi apa pun dalam dualitas direduksi menjadi masalah terbatas, yang
dapat dipecahkan dengan penerapan algoritma backtracking (tentu saja tergantung pada kelayakan komputasi).

20
Machine Translated by Google

Bahasa Waktu Mesin (sederhana) Waktu (ditingkatkan)

VAX BASIC VAX tidak tersedia tidak tersedia
GW BASIC 286 PC 2 jam 24 menit tidak tersedia
GW BASIC C 386 PC 49 menit tidak tersedia
(kompiler gcc) Minggu 3/50 3,9 detik Turbo 0,84 detik
PASCAL 286 PC 7 menit 30 detik 5,1 detik
Turbo PASCAL 386 PC 1 menit 52 detik C (kompiler 1,2 detik
gcc) Sparc 2 0,43 detik 0,08 detik

Tabel 2: Waktu untuk implementasi berbeda yang memecahkan masalah B4

Sekarang kita kembali ke aspek komputasi dari masalah B4 . Elemen-elemen himpunan domain
jatuh ke orbit terpisah di bawah aksi automorfisme f dan g. Juga, jika ÿ mempertahankan relasi, maka jika i dipetakan
ke ÿ(i) maka f(i) harus dipetakan ke f(ÿ(i)) dan g(i) ke g(ÿ(i))).
Pengamatan ini mengarahkan kita untuk mengurutkan domain dengan cara berikut. Kita mulai dari yang sembarangan
elemen, dilambangkan 1, dan mengambil 2 = f(1), 3 = g(1) (kecuali f(1) = g(1)). Setelah itu kita pilih sebagai
elemen berikutnya dalam urutan gambar f atau g dari elemen pertama yang tercantum yang gambarnya belum ada
telah disertakan hingga orbit 1 habis. Proses ini diulang untuk orbit yang tersisa.
Dengan demikian kita memperoleh pohon pencarian yang sangat ekonomis, dengan 17.391 simpul. Perhatikan bahwa urutan elemen
heuristik Bagian 7 sangat baik dalam menemukan rantai hubungan tersebut secara otomatis—bahkan
dimulai dari permutasi acak, mereka sejauh ini selalu berhasil menemukan permutasi yang lebih baik
daripada usaha “buatan tangan” terbaik! Misalnya, perhitungan umum untuk masalah B4 menghasilkan
pohon pencarian dengan 10.336 node.

Beberapa perbandingan waktu untuk masalah B4 untuk implementasi yang berbeda ditunjukkan pada
Tabel 2.

Versi VAX BASIC adalah yang pertama kali diimplementasikan, namun tidak pernah digunakan untuk ini
masalah yang menyebabkan waktu tidak tersedia. Implementasi pertama pada Sun 3/50 adalah
ditulis dalam perl yang merupakan bahasa interpretasi yang lebih cocok untuk pemrosesan string daripada numerik
pemrosesan. Ini memberikan pengaturan waktu yang hampir sama dengan versi GW BASIC. Beralih ke versi yang dikompilasi
bahasa, yaitu C pada Sun 3/50, menghasilkan peningkatan kecepatan yang dramatis yang mendorong kami
untuk menangani beberapa contoh yang jauh lebih besar.

Tabel 3 dan 4 mengilustrasikan pentingnya permutasi yang “baik” untuk masalah ini, Tabel 3
menunjukkan efek dari membuat perubahan kecil pada permutasi yang baik. Permutasi untuk setiap entri
dalam tabel dihasilkan dengan mengkomposisikan permutasi sebelumnya dengan permutasi bentuk
(ii + 1 . . . j) dimana i < j. Misalnya menggabungkan (1 2 3 4 5 6 7 8 9) dengan (4 5 6) menghasilkan
(1 2 3 5 6 4 7 8 9). Operasi ini kita sebut sebagai penyisipan. Tabel 3 menunjukkan efek dari urutan

Penyisipan Hasil Uji Coba Diperlukan Penyisipan Hasil Uji Coba Diperlukan
1 21 56.083 6 21 261.647 juta
2 21 196.163 7 21 527.663 orang

3 21 211.191 8 21 1.104.847 juta

4 21 228.327 9 21 4.495.633 juta
5 21 211.735 10 21 6.289.235

Tabel 3: Pengaruh penyisipan acak pada permutasi “baik” untuk masalah B4

penyisipan acak dimulai dengan permutasi yang digunakan di atas. Tabel 4 menunjukkan apa yang terjadi pada
masalah yang sama ketika permutasi acak dipilih (perhitungan tabel ini membutuhkan waktu lebih dari 1 minggu
waktu CPU pada Sparc 2). Setiap pasangan hasil adalah untuk permutasi acak yang berbeda dengan
masalah yang sama seperti di atas. Nilai “perkiraan” untuk pohon pencarian dihitung menggunakan Knuth's

21
Machine Translated by Google

Diperkirakan Sebenarnya Diperkirakan Sebenarnya

[Link] > [Link] [Link] > [Link]

190.500.933 190.764.514 [Link] > [Link]
174.773.383 174.780.145 [Link] > [Link]
[Link].643 > [Link] 740.322.532 724.756.716
868.614.966 867.753.321 259.217.324 257.759.780
[Link] > [Link] [Link] > [Link]
122.313.962 121.979.114 28.751.130 28.464.800
557.074.692 554.723.651 441.680.890 441.982.864
[Link] > [Link] [Link] > [Link]
[Link] > [Link] 16.474.273 16.314.730
[Link] [Link] [Link] > [Link]
[Link] [Link] [Link] [Link]
454.900.453 454.932.869 [Link] > [Link]

Tabel 4: Penggunaan permutasi acak pada masalah B4

metode estimasi backtracking (Knuth (1975)) dengan 1.000.000 probe, lihat Bagian 7.4 untuk detailnya.
Dengan menggunakan metode estimasi Knuth pada 487 permutasi acak dengan 1.000.000 probe masing-masing menghasilkan
ukuran pohon pencarian rata-rata [Link].638 node. Ini sesuai dengan waktu eksekusi (pada
Sparc 2) sekitar 3 tahun, sedangkan metode hybrid membutuhkan rata-rata 16 detik dan memeriksa
totalnya sekitar 800.000 node.

Untuk masalah yang lebih besar dengan tipe yang sama (menguji dualitas untuk optimalitas) dengan 153 elemen
domain, rentang 33 elemen dan 7 relasi, ukuran pohon pencarian rata-rata untuk permutasi acak
adalah sekitar 5 × 1035 yang menunjukkan waktu eksekusi 5 × 1023 tahun (sekitar 30 juta juta
kali usia alam semesta yang terlihat). Metode hibrida mengurangi ini menjadi 37.09.801 node dan 763
detik.

6.3 Aplikasi Lainnya

Dualitas Priestley memberi tahu kita bahwa kisi distributif terbatas L secara konkret direpresentasikan sebagai himpunan
dari peta pemeliharaan pesanan dari dual D(L) = D(L, 2), diurutkan berdasarkan titik, ke dalam 2 elemen
rantai 2ÿ . Lebih jauh, jika diberikan kisi distributif terbatas L dan M, terdapat bijeksi antara homomorfisme D dari L ke
M dan pemetaan pemeliharaan orde dari D(M) ke D(L). Lihat Bab 8
dari Davey & Priestley (1990) untuk penjelasan buku teks tentang teori ini, yang memungkinkan masalah tentang
kisi distributif terbatas yang akan diubah menjadi masalah tentang himpunan terurut terbatas. Pemetaan L ÿ
D(L) bertindak seperti “logaritma”: secara umum |L| tumbuh secara eksponensial dengan |D(L)|. Secara komputasional
Hal ini sangat penting: masalah yang sulit dipecahkan dalam bentuk kisi-kisi menjadi dapat diakses
setelah diterjemahkan ke dalam istilah set yang diurutkan. Algoritma peta pelestarian hubungan jelas dapat
digunakan untuk menghitung peta pemeliharaan orde dari satu himpunan terurut berhingga (P; ) ke himpunan terurut lainnya (Q; ).
Secara khusus kita dapat menemukan peta pelestarian orde dari (P; ) ke 2ÿ . Kita perhatikan bahwa berbagai
algoritma khusus telah diturunkan yang akan menangani masalah ini. Algoritma kami memiliki
kelebihannya adalah sangat mudah beradaptasi dengan berbagai situasi lainnya. Kami tidak mengklaim bahwa bahkan
bila ditingkatkan dengan heuristik di Bagian 8, hal ini tentu akan mengungguli algoritma yang dirancang untuk
masalah-masalah khusus. Pertimbangkan, misalnya, penentuan kardinalitas {0, 1}-
kisi distributif pada n generator. Elemen-elemen kisi ini dikenal sebagai peta pelestarian orde dari 2ÿ
N
ke 2ÿ ; satu bukti diberikan oleh Teorema 6.3, diterapkan dalam kasus Priestley
dualitas. Nilai |FD(n)| hanya diketahui untuk n 8 (Weidemann (1991) baru-baru ini menghitung
|FD(8)|). Algoritma kami menghitung nilai-nilai ini dengan mudah untuk n 6 tetapi dikalahkan oleh kasus n = 7,
yang tampaknya memerlukan pendekatan matematika yang lebih canggih. Bukti empiris menunjukkan
bahwa penentuan jumlah peta pemeliharaan orde dari himpunan terurut m-elemen ke dalam

22
Machine Translated by Google

6,
dan layak dalam banyak kasus untuk m 2
7,
tapi dengan kasus terburuk
2ÿ selalu layak untuk perilaku m 2
yang membuat algoritma kami tidak praktis dalam kasus tersebut.

Sekarang asumsikan, seperti pada 6.2, bahwa himpunan R relasi pada P memberikan dualitas untuk kelas aljabar A =
ISP(P). Berdasarkan Teorema 6.3, aljabar bebas FA (n) diberikan oleh pemetaan pemelihara R dari ke Pÿ ), di mana Pÿ = (P;
N
R). Baik teori maupun pengalaman memberi tahu kita bahwa untuk aljabar yang muncul dalam logika aljabar Pÿ (kelas
Bn, berbagai kelas aljabar Heyting, dsb.) normanya adalah bahwa aljabar bebas ini tumbuh sangat cepat dengan n, terlebih
2N
lagi jika |P| > 2. Misalnya, |FB(n)| = 2 dan |FK(3)| = 43, 918 sementara |FK(4)| = 160, 297, 985, 276 (Berman & Mukaidono (1984)).
Bahasa Indonesia:

Meskipun demikian kami telah berhasil menggunakan algoritma kami pada beberapa masalah semacam ini: lihat misalnya
Priestley (1992).

Algoritma peta pelestarian relasi dirancang untuk memungkinkan dualitas tertentu pada kelas aljabar A diuji untuk
keoptimalannya. Awalnya berkas data masukan disiapkan dengan kalkulasi manual yang melelahkan. Dalam aplikasi teknik
yang lebih baru (Davey & Priestley (1992), Priestley (1992)) algoritma penelusuran balik telah digunakan untuk menghasilkan
berkas data ini. Untuk melihat mengapa ini mungkin terjadi, ingatlah bahwa himpunan domain D(A) (seperti dalam 6.2) itu
sendiri adalah himpunan peta, yaitu homomorfisme-A dari A ke P. Peta tersebut hanyalah peta yang mempertahankan relasi
(tidak dalam biner umum) yang merupakan grafik operasi. Tentu saja, prosedur yang dijelaskan dalam Bagian 6.1 mudah
beradaptasi dengan relasi dari berbagai aritas. Dalam contoh yang sejauh ini dianalisis, aljabar dalam A selalu memiliki
struktur kisi distributif yang mendasarinya, sehingga mesin lengkap dualitas Priestley telah tersedia bagi kita. Hal ini
memungkinkan kita untuk bekerja bukan dengan homomorfisme tetapi dengan padanan dualnya, yang merupakan peta
pelestarian orde tertentu; ini dilakukan di seluruh Davey & Priestley (1992), Davey & Priestley (1993a), Davey & Priestley
(1993b) dan Priestley (1992). Dengan demikian, kita memperoleh manfaat dari fitur "logaritmik" dari dualitas. Lebih jauh,
dualitas sering memungkinkan kita untuk mengidentifikasi hubungan secara eksplisit dari deskripsi aljabar teoritis (ini
dilakukan, misalnya, untuk Bn dalam Davey & Priestley (1993a)). Perhitungan ini, sekali lagi, dilakukan dengan aplikasi
algoritma yang sesuai yang diberikan di Bagian 6.1. Program yang digunakan di sini merupakan bagian dari paket yang
merupakan perangkat yang sangat berharga bagi siapa pun yang menyelidiki aljabar dengan struktur kisi distributif yang
mendasarinya. Kit ini mencakup, khususnya, fasilitas untuk menemukan (dalam banyak kelas aljabar) homomorfisme,
kongruensi, subaljabar dan retraksi, dan untuk pengujian isomorfisme.

Teori dualitas untuk kisi distributif telah digunakan secara luas, sebagian karena, karena bersifat piktorial, teori ini
sangat mudah digunakan. Representasi memang ada untuk kisi sembarang yang menggeneralisasikan yang disediakan oleh
dualitas Priestley. Representasi yang diberikan oleh A. Urquhart (Urquhart (1977)) menggantikan himpunan terurut dengan
struktur dengan dua hubungan kuasi-terurut, sementara teori G. Hartung (Hartung (1992)) menggunakan formalisme analisis
konsep (diperkenalkan oleh R. Wille dalam Rival (1982), hlm. 445–470. Lihat juga Ganter, Wille & Wolff (1987) atau Bab 11
dari Davey & Priestley (1990)).
Algoritma backtracking sangat cocok untuk membuat representasi ini menjadi alat yang praktis.
Dengan bantuan paket ini, dimungkinkan untuk mengotomatiskan sepenuhnya pembuatan dualitas alami yang optimal dalam
sejumlah besar kasus, misalnya, untuk varietas aljabar Heyting tertentu (lihat Davey & Priestley (1993a)). Setiap perhitungan
tersebut memerlukan banyak subrutin yang berbeda, yang masing-masing menggunakan penelusuran balik dengan cara
yang berbeda.

7 Backtracking dengan Pemilihan Urutan Elemen

Pada Bagian 5, kami mencari urutan elemen p yang memenuhi predikat V (p) dan C(p). Algoritme backtracking mencoba
setiap kemungkinan perluasan dari urutan parsial secara bergantian. Karena pada akhirnya kami harus mencoba semua
kemungkinan perluasan, tidak masalah urutan apa yang kami pilih untuk mencobanya: semuanya harus dicoba pada
akhirnya. Jika kami mencari satu elemen, maka kami dapat menggunakan heuristik untuk mencoba perluasan yang "paling
mungkin" terlebih dahulu. Sekarang pertimbangkan kasus di mana p adalah array yang elemennya dapat diisi dalam urutan
apa pun. Masalah delapan ratu dapat dinyatakan dalam bentuk ini, seperti yang dibahas di Bagian 2.2. Dengan jenis masalah
ini, urutan pengisian elemen array dapat memiliki efek dramatis pada waktu eksekusi, seperti

23
Machine Translated by Google

diilustrasikan dalam tabel 3 dan 4. Di bagian ini kami akan membahas berbagai heuristik yang telah kami gunakan
untuk memilih urutan elemen: hal ini seringkali memungkinkan kami untuk menyelesaikan kalkulasi yang jika tidak
demikian akan sama sekali tidak mungkin dilakukan.

Kami mempertimbangkan spesifikasi yang sama seperti di Bagian 5 kecuali bahwa semua sekuens memiliki
panjang yang sama, N, dan sekuens yang valid adalah sekuens yang tidak memiliki posisi “yang tidak terisi”, yaitu
C(p) =DF ÿi, 1 i Np[i] = ÿ di mana ÿ adalah elemen baru (tidak ada di D) yang digunakan untuk merepresentasikan posisi yang tidak terisi

SPEC =DF untuk p ÿ { p ÿ D * | V (p) ÿ C(p) ÿ (p) = N } lakukan proses(p) od

Alih-alih memperluasnya untuk memproses semua ekstensi p yang valid, kita perlu memproses semua pelengkapan
p yang valid di mana urutan yang tidak lengkap adalah "array yang terisi sebagian". Misalkan p ÿ (D ÿ {ÿ}) ÿ memiliki panjang N.
Kemudian kita definisikan:

SPEC(p) =DF untuk q ÿ { q ÿ D * | pq ÿ V (q) ÿ C(q) ÿ (q) = N } lakukan proses(q) od

di mana pq berarti q adalah p dengan beberapa elemennya yang belum terisi terisi, yaitu pq =DF ÿi. 1 i N.(p[i] = ÿ ÿ
p[i] = q[i]).

Bahasa Indonesia: Dengan menggunakan permutasi ÿ : {1, 2, . . . , N} ÿ {1, 2, . . . , N} dan variabel n untuk mencatat
berapa banyak elemen p yang terisi, kita dapat menghindari perlunya elemen tambahan ÿ. Permutasi juga mencatat
urutan pengisian array. N elemen p[ÿ[1]], . . . , p[ÿ[n]] dari p terisi, dan N ÿ n elemen p[ÿ[n + 1]], . . . , p[ÿ[N]] dari p saat
ini tidak terisi. Derivasi yang mirip dengan yang ada di Bagian 5 menghasilkan algoritma berikut: var n := 0,t := 1:
while n > 0 ÿ t D do if t > D then t := p[ÿ[n]]; n := n ÿ 1; t :=
t + 1 jika tidak V (t, p,
ÿ, n) maka jika n = N maka
proses (t, p); t := t + 1 jika tidak n := n + 1; p[ÿ[n]] := t; t :=
1 fi jika tidak t := t + 1 fi akhir

Ini memberikan hasil yang sama dengan SPEC untuk setiap permutasi ÿ : {1, 2, . . . , N} ÿ {1, 2, . . . , N}. Bahkan kita
dapat mengubah elemen-elemen ÿ[d + 1] menjadi ÿ[N] kapan saja selama eksekusi program.
Pemilihan nilai yang sesuai untuk ÿ sangat penting: kami telah menggunakan dua heuristik dasar untuk
mencapainya, yang dapat digabungkan untuk membentuk metode hibrida ketiga. Ini disebut "pra-analisis" dan
"pemangkasan semak".

Dalam algoritma di bawah ini, kami mengisi array p dalam urutan yang diberikan oleh ÿ. Namun, dalam
implementasi C, kami memperbarui array rel X ke dan rel ke X setiap kali ÿ berubah (sebenarnya, mengubah pemetaan
antara bilangan bulat dan elemen X). Ini meningkatkan efisiensi dengan menghilangkan sebagian besar
akses ke ÿ.

7.1 Heuristik “Pra-Analisis”

Heuristik pra-analisis adalah metode untuk memilih permutasi ÿ yang sesuai. Heuristik ini melibatkan perluasan
berulang dari permutasi parsial yang "baik" dengan menambahkan elemen dan mencari elemen yang dapat digeser
untuk meningkatkan permutasi. "Menggeser" elemen dalam permutasi berarti menyusun ÿ dengan permutasi (i i+1 . . .
j) di mana i < j atau menyusun dengan permutasi (iiÿ1 . . . j) di mana i > j. Hal ini tampaknya memiliki peluang yang
lebih baik untuk meningkatkan permutasi daripada sekadar menukar dua elemen yang berdekatan (menyusun dengan
(ii + 1)), atau menukar dua elemen acak (menyusun dengan (ij)).

Kami menggunakan dua definisi berbeda tentang permutasi parsial yang “lebih baik”:

1. Pilih permutasi yang menghasilkan pohon pencarian backtracking yang lebih kecil (yaitu jumlah elemen yang
diperiksa oleh prosedur processall). Jika kedua pohon pencarian tersebut sama, maka pilih permutasi yang
pohon pencariannya memiliki jumlah elemen "daun" yang lebih kecil (yaitu jumlah elemen berukuran penuh
yang diperiksa oleh processall);

24
Machine Translated by Google

2. Pilih permutasi yang pohon pencariannya memiliki jumlah elemen daun lebih kecil; jika memiliki jumlah
elemen daun yang sama, pilih permutasi yang total pohon pencariannya lebih kecil.

Kami menggunakan versi algoritma backtracking dasar untuk menghitung ukuran pohon pencarian dan
jumlah elemen daun untuk permutasi parsial ÿ[mindepth . . maxdepth], di mana elemen ÿ[1 . . mindepth ÿ 1]
telah "dibekukan" (lihat di bawah). Ini segera berakhir jika jumlah percobaan yang diperlukan untuk perhitungan
melebihi batas (setiap evaluasi V (t, p, ÿ, n) adalah satu "percobaan" karena evaluasi ini mendominasi seluruh
perhitungan): proc calculate(mindepth, maxdepth, cutoff ) ÿ count := 0;
trials := 0; var n := mindepth; t := 1: while (n > 0 ÿ t D)
ÿ trials cutoff do

jika t > D maka t := p[ÿ[n]]; n := n ÿ 1; t := t + 1

jika tidak, percobaan := percobaan
+ 1; jika V (t, p, ÿ, n) maka jika n = kedalamanmaksimum
maka hitung := hitung + 1; t := t + 1 jika
tidak d := d + 1; p[ÿ[d]] := t; t := 1 fi jika
tidak t := t + 1 fi od akhir.

Kami berulang kali menguji "pergeseran" acak (di mana setidaknya satu dari i atau j harus berada dalam
permutasi parsial) untuk melihat apakah permutasi parsial dapat ditingkatkan. Setelah sejumlah percobaan
yang gagal, kami berasumsi bahwa ini adalah yang terbaik yang dapat kami lakukan untuk ukuran permutasi
parsial ini, jadi kami meningkatkan ukuran dengan menambahkan satu elemen, lalu mencoba meningkatkan permutasi yang leb
Perhatikan bahwa secara umum, permutasi "terbaik" berukuran n + 1 bukanlah perluasan sederhana dari
permutasi "terbaik" berukuran n. Kita memiliki "anggaran" yang membatasi berapa kali kita ingin mengevaluasi
fungsi V (karena ini adalah bagian algoritma yang paling mahal). Setelah anggaran ini habis, kita "membekukan"
permutasi parsial saat ini, dan mulai membangun permutasi parsial baru dengan elemen yang tersisa. Setelah
semua elemen habis, kita menyatukan permutasi parsial yang "dibekukan" untuk mendapatkan permutasi
lengkap yang digunakan untuk mencoba perhitungan penuh. Kita memiliki anggaran lain untuk perhitungan
penuh dan jika ini habis sebelum perhitungan selesai maka kita menghentikan perhitungan penuh,
menggandakan anggaran analisis dan perhitungan dan memulai lagi dari awal. Program mencetak pesan saat
berlangsung (yang dapat ditangkap dalam file log) sehingga pengguna dapat memantau kemajuannya.

Jadi rutin pra-analisis bekerja dengan meningkatkan ukuran permutasi parsial saat ini, yang disimpan
dalam ÿ[mindepth . . depth], dengan menambah depth, dan kemudian menyesuaikan permutasi untuk
meminimalkan pohon pencarian. Subrutin find good depth mencoba memasukkan masing-masing elemen
ÿ[depth + 1] ke ÿ[SX] pada posisi depth untuk menemukan yang terbaik. Ia memperbarui variabel global count
dan tries dengan jumlah simpul daun di pohon pencarian untuk ÿ[mindepth . . depth] dan jumlah total simpul
di pohon. find good insert berulang kali memilih pasangan elemen acak di ÿ (setidaknya satu di antaranya
harus berada dalam ÿ[mindepth . . depth]), memasukkan satu di tempat yang lain, dan menguji apakah ini
meningkatkan permutasi. Ia berakhir ketika kehabisan anggaran (jumlah total percobaan yang diizinkan), atau
telah mencoba maxgoes penyisipan tanpa meningkatkan permutasi parsial. Ini menetapkan variabel global
yang disisipkan ke jumlah penyisipan yang baik yang ditemukan. mindepth := 1; untuk
depth := 1 hingga
SX ÿ 1 langkah 1 lakukan lakukan
temukan elemen kedalaman yang baik (mindepth, depth, maxtrials/
10); hasil terbaik := hitung; uji coba terbaik :=
uji coba; jika uji coba terbaik maxtrials/10
lalu cetak(“ Elemen terbaik berikutnya terlampaui:”, maxtrials/10, uji
“
coba pada kedalaman:”, kedalaman,
mindepth); mindepth :=
kedalaman; untuk i := 1 hingga mindepth langkah 1 lakukan p[i] := 0 od

25
Machine Translated by Google

jika tidak keluar fi

od; anggaran := maxtrials;
printinfo(mindepth, kedalaman, percobaan terbaik, hasil terbaik);
jika kedalaman > mindepth
maka percobaan ulang := 1

lakukan anggaran := maxtrials ÿ percobaan

terbaik; temukan sisipan yang baik(mindepth, kedalaman, percobaan
terbaik, hasil terbaik); hasil terbaik := hitung;
percobaan terbaik := percobaan; printinfo(mindepth, kedalaman,
percobaan terbaik, hasil
terbaik); percobaan ulang := percobaan ulang + 1; jika percobaan ulang > maxretries ÿ sisipan selesai = 0 maka keluar fi od od

Penugasan ke p[i] saat mindepth ditingkatkan adalah untuk menunjukkan kepada rutin kalkulasi bahwa relasi yang melibatkan
elemen-elemen ini tidak harus dipertahankan. Elemen “0” dapat dianggap sebagai elemen baru, yang ditambahkan ke set B,
yang terkait dengan dirinya sendiri dan semua hal lainnya dalam setiap relasi di RY .

Prosedur printinfo mencetak laporan status tentang kemajuan perhitungan, ini termasuk
total waktu CPU yang digunakan, dan waktu CPU yang digunakan sejak laporan status terakhir.

Setelah rutinitas ini berakhir (ketika kedalaman = SX ÿ1) kami menggunakan rutinitas kalkulasi dengan anggaran total
percobaan (jumlah total percobaan yang digunakan oleh pra-analisis). Jika ini gagal karena melebihi anggarannya, maka kami
menggandakan maxtrials dan maxgoes dan menjalankan pra-analisis lagi dengan anggaran yang lebih besar ini. Ini diharapkan
akan menghasilkan permutasi yang lebih baik untuk kalkulasi penuh berikutnya, yang dalam hal apa pun akan memiliki
anggaran yang lebih besar untuk digunakan. Dengan demikian, waktu kami akan dibagi secara kasar antara pra-analisis dan
kalkulasi yang dicoba.

Perhatikan bahwa heuristik ini dapat memakan waktu hingga empat kali lebih lama dari yang diperlukan jika perhitungan
yang dicoba kehabisan anggaran "tepat sebelum" perhitungan tersebut selesai. Selain itu, tidak selalu mudah untuk melihat
dari laporan status berapa banyak waktu tambahan yang diperlukan untuk menyelesaikan perhitungan. Hasil samping yang
bermanfaat dari metode ini adalah cetakan permutasi terbaik yang ditemukan.

7.2 Heuristik “Bush Pruning” Metode praanalisis

melakukan beberapa analisis awal (selama jangka waktu tertentu) untuk mencoba dan menemukan permutasi yang sesuai.
Kemudian, metode ini mencoba melakukan kalkulasi penuh dengan permutasi tersebut. Jika kalkulasi gagal (karena kehabisan
waktu sebelum pencarian selesai), maka kami menggandakan anggaran analisis dan kalkulasi dan memulai lagi.

Sebaliknya, metode yang dijelaskan dalam bagian ini memulai perhitungan penuh dengan segera, dengan permutasi awal
yang diperbarui "saat itu juga" saat perhitungan berlangsung. Hal ini bergantung pada fakta, yang disebutkan di atas, bahwa
elemen ÿ[n + 1] hingga ÿ[N] dapat diubah-ubah setiap saat tanpa memengaruhi hasil akhir.

Metode ini disebut pemangkasan semak karena metode ini mengandalkan meminimalkan ukuran pohon kecil2 yang
terbentuk dengan menambahkan beberapa elemen ke peta parsial saat ini. Penerapan metode yang paling sederhana (yang
mencapai beberapa keberhasilan) melibatkan pemilihan elemen dengan gambar valid paling sedikit, setiap kali elemen
ditambahkan ke peta saat ini (kecuali jika peta saat ini hampir lengkap).
Tentu saja, jika ditemukan suatu unsur yang tidak mempunyai gambar yang valid, maka rangkaian parsial saat ini dapat
ditinggalkan (semak saat ini telah dipangkas seluruhnya!).

Dalam kasus umum, metode ini membagi waktunya antara mendorong maju dengan pencarian dan memangkas semak
pada posisi saat ini. Karena yang terbaik adalah memangkas sama seringnya pada semua tingkat pohon (selain dari 1/4 terakhir
dari tingkat pohon yang tidak layak dipangkas) kami menggunakan array next bush[1 . . N] untuk mencatat “waktu” saat setiap
kedalaman berikutnya harus dipangkas. “Waktu” ini adalah

2Semak adalah pohon kecil!

26
Machine Translated by Google

diukur dari segi jumlah total percobaan, yaitu evaluasi V (t, p, ÿ, n).

Algoritma ini didasarkan pada algoritma calculate dengan kode pemangkasan bush yang ditambahkan. Prosedur
find good element(n) memilih elemen untuk dimasukkan ke dalam ÿ[n] yang memiliki jumlah gambar pemelihara relasi
terkecil di Y. find bush size(n) menetapkan bush ke ukuran bush yang “cocok” untuk pemangkasan: dengan kata lain,
menambahkan elemen bush ke permutasi parsial saat ini menghasilkan pohon pencarian yang berisi sekitar bush budget/
bush goes nodes. prune bush(n, bush) kemudian menggunakan uji coba bush budget dalam upaya untuk meningkatkan
bagian permutasi antara n dan n+bush. bush trials := 0; count := 0; n := 0; t := 1; do if t D

maka jumlah percobaan := jumlah

percobaan + 1;
jika V (t, p, ÿ, n) maka jika n = SX maka hitung := hitung + 1;
t := t + 1; jika tidak p[ÿ[n]] := t; n := n + 1;
t := 1; jika n < 3N/4 ÿ jumlah percobaan > semak
berikutnya[n] maka semak
terakhir := percobaan
semak; cari ukuran
semak(n); pangkas semak(n, semak); perbarui semak berikutnya() fi fi
jika tidak t := t + 1
fi jika tidak n := n
ÿ 1; jika n = 0 maka keluar
fi; t := p[ÿ[n]] + 1 fi od
di

mana proc perbarui bush()

berikutnya ÿ untuk i := n hingga n + bush
langkah 1 lakukan bush[i] berikutnya :=total percobaan + 5(percobaan bush ÿ bush terakhir) od.

Perhatikan bahwa jika ukuran semak yang ditemukan memperluas semak ke seluruh himpunan, maka elemen p
saat ini telah dipahami sepenuhnya (semua ekstensi yang valid telah ditemukan). Jika ukuran semak yang
ditemukan atau semak yang dipangkas mencapai semak tanpa daun (tidak ada ekstensi yang valid hingga
n+semak), maka tidak akan ada ekstensi yang lengkap dan valid dari p saat ini. Dalam kedua kasus, kita dapat
langsung melompat ke langkah n := n ÿ 1, dan inilah yang dilakukan implementasi C. Implementasi C juga mencetak
laporan status reguler (setelah setiap percobaan langkah pr semak).

7.3 Metode Hibrida

Heuristik pemangkasan semak harus dimulai dengan beberapa permutasi, meskipun hanya yang acak. Metode
hibrida dimulai dengan melakukan praanalisis awal untuk menyediakan permutasi awal ini, lalu beralih ke metode
pemangkasan semak. "Bagian pertama" dari permutasi ini, hingga titik saat praanalisis pertama kali meningkatkan
mindepth, dipertahankan dari modifikasi oleh pemangkasan semak. Ini dicapai dengan menetapkan semak
berikutnya[i] untuk elemen-elemen ini ke beberapa nilai besar yang sesuai. Bagian domain ini akan memiliki
sejumlah peta parsial, kita harus menentukan semua ekstensi yang valid dari peta-peta ini. Oleh karena itu, kita
memiliki ukuran kasar kemajuan melalui perhitungan dengan melihat berapa banyak peta parsial ini yang telah
diproses sejauh ini. Ini hanya ukuran kasar karena beberapa peta parsial mungkin memiliki lebih banyak ekstensi
yang valid daripada yang lain, tetapi ini dapat memberikan beberapa indikasi kelayakan: misalnya jika program
telah dibiarkan berjalan selama akhir pekan dan telah memproses kurang dari 1% dari kumpulan peta parsial,
maka kemungkinan akan memakan waktu lebih banyak hari untuk berjalan hingga selesai.

27
Machine Translated by Google

7.4 Heuristik berdasarkan Algoritma Estimasi Knuth Dalam Knuth (1975),

Knuth menyajikan sebuah metode untuk memperkirakan ukuran pohon pencarian dari sebuah algoritma backtracking
sederhana. Metode ini didasarkan pada pembuatan sejumlah “probe” acak ke dalam pohon, memilih jalur acak pada
setiap tahap, dan menghitung total tertimbang dari biaya perhitungan yang dilakukan pada setiap node:

Persamaan kuadrat dari x1 dan x2 adalah :

Di sini c(x1, . . .) adalah biaya komputasi pada simpul p = x1, . . . (dalam kasus kami semua biaya ini sama
jadi kami tetapkan semuanya menjadi 1), d0 adalah jumlah elemen awal x sehingga deret x valid. Salah satu
elemen ini, x1, dipilih secara acak. Untuk setiap deret valid p = x1, . . . , xi, di+1 adalah jumlah elemen x yang
dapat ditambahkan ke p untuk mendapatkan deret valid.
Salah satu elemen ini, xi+1, dipilih secara acak. Prosedur berakhir saat di bernilai nol. C adalah estimasi biaya
dari pemeriksaan ini.

Knuth memberikan dua "bukti" ('setidaknya satu di antaranya harus meyakinkan') bahwa nilai yang
diharapkan dari C adalah biaya pencarian backtracking yang lengkap. Ia mengatakan bahwa metode tersebut
telah diuji pada lusinan aplikasi dan telah 'secara konsisten bekerja dengan sangat baik, bahkan pada
masalah yang dimaksudkan untuk dijadikan contoh yang buruk. Dalam hampir setiap kasus, urutan besaran
yang tepat untuk ukuran pohon ditemukan setelah sepuluh kali percobaan.' Ia membahas satu percobaan
secara terperinci (masalah "knight's tour") di mana rata-rata lebih dari 1.000 random walk menghasilkan
estimasi dalam 0,5% dari jawaban sebenarnya yaitu [Link].

Algoritme ini tampaknya menyediakan metode ideal untuk menentukan permutasi mana yang lebih baik
(dan karenanya untuk menemukan permutasi yang baik), yang, tidak seperti metode kami sebelumnya,
memperhitungkan seluruh permutasi. Sayangnya, untuk sebagian besar masalah pemetaan pelestarian relasi
kami, estimasi tersebut tampaknya kurang akurat dari yang kami harapkan: bahkan dengan rata-rata lebih
dari 100.000 probe, dan memakan waktu CPU beberapa menit pada Sparc 2, estimasi akan bervariasi dengan
faktor dua atau lebih, dengan beberapa masalah memberikan estimasi yang sangat tidak akurat.

Meskipun hasil yang mengecewakan ini, kami menerapkan algoritma pemilihan permutasi berdasarkan
metode estimasi Knuth. Algoritma menguji berbagai penyisipan potensial, menggunakan metode Knuth
untuk melihat apakah permutasi telah membaik. Begitu permutasi tampak memberikan pohon pencarian yang
layak, algoritma mencoba melakukan perhitungan. Jika ini gagal (dengan mengambil lebih dari dua kali
jumlah percobaan yang diestimasikan), kami berasumsi bahwa dengan merata-ratakan lebih banyak jalan
acak, kami akan mendapatkan estimasi yang lebih baik. Oleh karena itu, kami meningkatkan jumlah jalan
acak (misalnya 20% hingga 50% pada satu waktu) hingga estimasi lebih besar dari dua kali estimasi lama
(kami tahu bahwa ukuran pohon pencarian yang sebenarnya setidaknya sebesar ini). Kami mendefinisikan
pohon pencarian yang "layak" sebagai pohon yang diestimasikan membutuhkan waktu kurang dari
seperempat dari total jumlah percobaan yang telah kami lakukan dalam analisis sejauh ini: ini berarti bahwa
seiring pencarian permutasi yang baik membutuhkan waktu yang semakin lama, kami akan secara bertahap melonggarkan pe

Sayangnya, metode heuristik ini gagal total! Masalah utamanya adalah: 1. Terkadang terjadi

kesalahan perkiraan (bahkan dengan sejumlah besar probe)—ini menyebabkan metode ini menganggap
penyisipan acak tertentu lebih baik padahal sebenarnya mungkin lebih buruk. Jadi, metode ini
selangkah lebih jauh dari optimalitas;
2. Jumlah probe yang dibutuhkan besar sehingga hanya sedikit penyisipan yang dapat dilakukan.
teruji. Jadi hanya butuh beberapa langkah menuju optimalitas.
3. Pada masalah yang lebih besar, alih-alih menemukan permutasi yang "baik", algoritme hanya
menemukan permutasi yang hasilnya secara konsisten diremehkan oleh metode Knuth. Misalnya,
setiap perkiraan mungkin sekitar 108 hingga 109 sementara pohon sebenarnya memiliki orde besaran
lebih besar dari 109 simpul. Efeknya adalah ia terus melakukan perhitungan percobaan yang gagal dan
menyebabkan jumlah probe meningkat sedemikian rupa sehingga program secara efektif "berhenti".
Dalam satu kasus, peningkatan ukuran sampel dari 5.000 menjadi 7.500 menyebabkan perkiraan

28
Machine Translated by Google

berubah dari 107 percobaan yang cukup layak menjadi 1020 percobaan yang sama sekali tidak praktis. Algoritma tersebut kemudian
“memperbaiki” permutasi ini dengan menemukan permutasi baru yang tidak sesuai dengan metode Knuth
ukuran pohon.

Masalah-masalah ini masih ada bahkan ketika melakukan rata-rata pada sejumlah besar probe, misalnya
contoh dengan 100.000 sampel yang membutuhkan waktu CPU beberapa menit pada Sparc 2 untuk menguji satu
penyisipan. Akibatnya, metode ini telah ditinggalkan, meskipun kodenya tersedia dari
Tabel 5 membandingkan metode pemangkasan semak dengan metode berdasarkan algoritma Knuth
untuk beberapa contoh terkecil kami.

Jumlah percobaan Waktu CPU

Ukuran Masalah Knuth Hibrida Hibrida Knuth

Ukuran 42x17 28.550.038 789.604 67.119.212 533 16
Ukuran 37.248.521 49.438.402 2.722 1.048 tahun

64 × 2 65 × 2 23.438.477 2.898.059 231.928 2.223 599

Ukuran 64 × 8 tidak diketahui3 1.422.829 > 102 94
Ukuran 153 × 33 44.000 763

Tabel 5: Pemangkasan semak dibandingkan dengan metode berdasarkan algoritma estimasi Knuth. (“Permasalahan
“ukuran” mengacu pada ukuran domain dan rentang).

7.5 Batasan Praktis Metode

Setelah menguji berbagai metode pada banyak contoh peta pemeliharaan relasi dari berbagai jenis,
Kesimpulan kami adalah metode hybrid, dengan anggaran 10.000 untuk pra-analisis dan semak-semak
anggaran pemangkasan sebesar 100.000, adalah yang terbaik secara keseluruhan. Satu-satunya keterbatasan praktis dari metode ini adalah
konsekuensi yang diperlukan dari sifat umumnya: algoritma dirancang untuk memproses setiap relasi yang mempertahankan
peta secara individual, dan karena itu dibatasi oleh jumlah peta yang ditemukan, bahkan ketika
“proses” adalah hitungan sederhana. Semua contoh kami dengan hingga 109 peta berhasil, satu-satunya kegagalan kami
adalah masalah-masalah yang diketahui memiliki lebih banyak solusi (1011 atau lebih peta). Masalah-masalah seperti itu dapat
hanya dapat diselesaikan dengan menggunakan pengetahuan yang lebih mendalam tentang struktur kisi tertentu yang terlibat, dalam
untuk menghitung solusi dalam “gumpalan” besar daripada satu per satu. Misalnya, Berman dan
Mukaidono (Berman & Mukaidono (1984)) menggunakan simetri dan penggumpalan untuk menghitung |FK(n)|,
jumlah aljabar Kleene bebas pada n generator, untuk kasus n = 4. Hasil dari [Link]
berada di luar kisaran yang layak untuk algoritma tujuan umum kami. Algoritma kami berurusan dengan
n = 3 kasus hanya dalam 11 detik dan 500.000 percobaan.

Kode sumber untuk implementasi C yang dioptimalkan dari semua algoritma, bersama dengan contoh
file data dan file parameter, tersedia dari penulis. M. Ward akan tertarik untuk mendengar
dari siapa pun yang memiliki aplikasi backtracking lain yang dapat memperoleh manfaat dari pengurutan elemen
heuristik.

8 Mengotomatiskan Proses Transformasi

Teori transformasi program yang digunakan dalam makalah ini membentuk dasar dari “Maintainer's
Proyek “Asisten” (Bull (1990), Ward & Bennett (1993), Ward & Bennett (1995), Ward, Calliss &
Munro (1989)) di Universitas Durham dan Pusat Pemeliharaan Perangkat Lunak Ltd. yang bertujuan untuk
menghasilkan alat untuk membantu programmer pemeliharaan dalam memahami dan merekayasa ulang sistem besar.
Asisten Pemelihara terdiri dari editor struktur interaktif dan pencetak cantik, yang diimplementasikan di bawah X Windows,
dan mesin transformasi, yang diimplementasikan dalam LISP dan
WSL. Mesin transformasi mencakup pustaka lebih dari enam ratus transformasi yang terbukti,

3Program tidak berhenti setelah lebih dari 12 jam waktu CPU.

29
Machine Translated by Google

termasuk sebagian besar yang digunakan dalam derivasi program di atas. Setelah transformasi yang
tersisa diimplementasikan, derivasi dapat dilakukan secara interaktif: dimulai dari spesifikasi formal
dan memanggil serangkaian transformasi dan penyempurnaan yang terbukti, dengan sistem
memeriksa semua kondisi kebenaran di setiap tahap, akhirnya menerjemahkan kode WSL (yang dapat
dieksekusi) yang dihasilkan ke dalam bahasa pemrograman yang sesuai, seperti C. Satu hasil menarik
yang kami perhatikan dari pengalaman kami dengan transformasi manual adalah bahwa jenis
kesalahan (klerikal dan logis) yang dibuat dalam menurunkan algoritma cenderung menjadi jenis
kesalahan (misalnya menulis < alih-alih >) yang ditemukan oleh beberapa kasus uji pertama. Setelah
kesalahan ini diperbaiki, program selalu lulus semua kasus uji dengan sangat baik. Ini kontras dengan
bug pemrograman umum yang cenderung halus dan sangat sulit dilacak.

Referensi

Arsac, J. (1982a): Transformasi Prosedur Rekursif. Dalam: Neel, D. (ed.) Alat dan Notasi untuk Konstruksi Program.
Cambridge University Press, Cambridge, hlm. 211–265

Arsac, J. (1982b): Transformasi Program Sumber ke Sumber Sintaksis dan Manipulasi Program.
ACM 22, 1, hal. 43–54

Berman, J. & Mukaidono, M. (1984): Menghitung fungsi peralihan fuzzy dan aljabar Kleene bebas.
Komputasi. Matematika. Terapan. 10, hlm. 25–35

Bull, T. (1990): Pengantar Program Transformer WSL. Konferensi Pemeliharaan Perangkat Lunak
26–29 November 1990, San Diego

Butler, G. & Lam, CWH (1985): Algoritma Backtrack Umum untuk Masalah Isomorfisme
Objek Kombinatorial. J. Symb. Comput.

Davey, BA & Priestley, HA (1987): Dualitas piggyback umum, dengan aplikasi pada aljabar Ockham.
Jurnal Matematika Houston, 13, hlm. 151–198

Davey, BA & Priestley, HA (1990): Pengantar Kisi dan Keteraturan. Cambridge University Press,
Bahasa Inggris: Cambridge

Davey, BA & Priestley, HA (1992): Dualitas optimal untuk berbagai aljabar Heyting. pracetak Davey, BA & Priestley,

HA (1993a): Dualitas alami yang diinduksi partisi untuk berbagai aljabar pseudokompleks.
kisi distributif terdistribusi. Matematika Diskrit. 113, hlm. 41–58

Davey, BA & Priestley, HA (1993b): Dualitas alamiah yang optimal. Trans. Amer. Math. Soc. 338, hlm. 655–
677

Davey, BA & Werner, H. (1983): Dualitas dan kesetaraan untuk berbagai aljabar. Dalam: Huhn, AP & Schmidt, ET (eds.)
Kontribusi terhadap teori kisi (Szeged, 1980). (Colloq. Math. Soc. J´anos Bolyai no. 33.) North-Holland, Amsterdam, hlm.
101–275

Dijkstra, EW (1976): Disiplin Pemrograman. Prentice-Hall, Englewood Cliffs, NJ Ganter, B., Wille, R. &

Wolff, K. (eds.) (1987): Beitr¨age zur Begriffsanalyse. BI Wissenschaftsverlag,

Mannheim, Zurich ¨ h

Gerhart, SL & Yelowitz, L. (1976): Abstraksi Struktur Kontrol dari Pemrograman Backtracking
Teknik. IEEE Trans. Perangkat Lunak Bahasa Inggris. SE 2, 4, hlm.285–292

Hartung, G. (1992): Representasi topologi kisi. Algebra Universalis 29, hlm. 273–299 Hoare, CAR, Hayes, IJ,

Jifeng, HE, Morgan, CC, Roscoe, AW, Sanders, JW, Sørensen, IH, Spivey, JM & Sufrin, BA (1987): Hukum Pemrograman.
Comm. ACM 30, 8, hlm. 672–686

Knuth, DE (1974): Pemrograman Terstruktur dengan Pernyataan GOTO. Survei Komputer 6, 4, hlm. 261–
301

Knuth, DE (1975): Memperkirakan Efisiensi Algoritma Backtracking. Matematika Komputasi 29, 129,
hal. 121–136

Knuth, DE & Szwarcfiter, JL (1974): Program Terstruktur untuk Menghasilkan Semua Susunan Sortir Topologi. Proses
Inform. Surat. 2, hlm. 153–157

30
Machine Translated by Google

Lee, KB (1970): Kelas persamaan kisi pseudo-komplemen distributif. Jurnal Matematika Kanada 22,
hal. 881–891
Morgan, CC (1994): Pemrograman dari Spesifikasi. Prentice-Hall, Englewood Cliffs, NJ. Edisi Kedua Priestley, HA
(1992): Dualitas alami untuk berbagai kisi distributif dengan kuantifier. Prosiding Semester Pusat Banach ke-38
tentang Logika Aljabar dan Aplikasi Ilmu Komputer akan muncul Rival, I., (ed.) (1982): Set Terurut, Reidel,
Dordrecht Roever, WP de (1978): Tentang Backtracking
dan Titik Tetap Terbesar. Dalam: Neuhold, EJ (ed.) Deskripsi Formal
Konstruksi Pemrograman. North-Holland, Amsterdam, hlm. 621–636
Stallman, RM (1989): Menggunakan dan Memindahkan GNU CC. Free Software Foundation, Inc.
Taylor, D. (1984): Alternatif untuk Sintaksis Perulangan Arus. Pemberitahuan SIGPLAN 19, 12, hlm. 48–53
Urquhart, A. (1977): Teori representasi topologi untuk kisi. Algebra Universalis 8, hlm. 45–58 Walker, RJ
(1960): Teknik Enumeratif untuk kelas Masalah Kombinatorial. Dalam: Bellman, RE
& Hall Jr., M. (eds.) Prosiding Simposium Matematika Terapan 10: Analisis Kombinatorial. Am.
Matematika. Pergaulan, Providence RI

Ward, M. (1989): Membuktikan Penyempurnaan dan Transformasi Program. Universitas Oxford, Tesis DPhil
Ward, M. (1990): Derivasi Algoritma Penyortiran. Universitas Durham, Laporan Teknis. http: //www.
[Link]/ÿdcs0mpw/martin/papers/[Link]
Ward, M. (1991a): Spesifikasi dan Program dalam Bahasa Spektrum Luas. Diserahkan ke J. Assoc.
Komputer.
Ward, M. (1991b): Teorema Penghapusan Rekursi—Bukti dan Aplikasi. Universitas Durham, Laporan Teknis. http://
[Link]/ÿdcs0mpw/martin/papers/[Link] Ward, M. (1992): Teorema
Penghapusan Rekursi. Springer, New York Berlin Heidelberg. Prosiding Lokakarya Penyempurnaan ke-5, London,
8–11 Januari. [Link]

Ward, M. (1994): Fondasi untuk Teori Praktis Penyempurnaan dan Transformasi Program. Universitas Durham,
Laporan Teknis. [Link] Ward, M. (1993):
Mengabstraksi Spesifikasi dari Kode. J. Pemeliharaan Perangkat Lunak: Penelitian dan Praktik 5, 2, John Wiley &
Sons, hlm. 101–122. [Link] Ward, M. (1996): Derivasi
Algoritma Intensif Data melalui Transformasi Formal. Trans. Perangkat Lunak IEEE
bahasa Inggris 22, 9, hlm.665–686. [Link]
Ward, M. & Bennett, KH (1993): Sistem Transformasi Program Praktis Untuk Rekayasa Balik.
Konferensi Kerja tentang Rekayasa Balik, 21–23 Mei 1993, Baltimore MA. [Link] ÿdcs0mpw/
martin/papers/[Link]
Ward, M. & Bennett, KH (1995): Metode Formal untuk Sistem Lama. J. Pemeliharaan Perangkat Lunak: Penelitian
dan Praktik 7, 3, John Wiley & Sons, hlm. 203–219. [Link] [Link]

Ward, M., Calliss, FW & Munro, M. (1989): Asisten Pemelihara. Konferensi Pemeliharaan Perangkat Lunak 16–19
Oktober 1989, Miami Florida. http: // www. dur. ac. uk/ ÿdcs0mpw/ martin/ papers/ [Link]

Weidemann, DA (1991): Perhitungan bilangan Dedekind ke-8. Order 8, hlm. 5–6 Wells, MB
(1971): Elemen-elemen Komputasi Kombinatorial. Pergamon Press, New York

31
Machine Translated by Google

Wirth, N. (1971): Pengembangan Program melalui Penyempurnaan Bertahap. Comm. ACM 14, 4, hlm. 221–227

Lampiran: C Implementasi Algoritma Backtracking Sederhana

Lampiran ini memberikan implementasi C dari algoritma backtracking sederhana (tanpa pemilihan urutan elemen). Kode
sumber dan contoh berkas data untuk semua algoritma tersedia dari penulis.

Perhatikan bahwa “subroutine” DO (disebut relpres di bawah) disalin di tempatnya: ini untuk menghindari overhead
panggilan subroutine bagi para kompiler yang (tidak seperti kompiler GNU C gcc misalnya Stallman (1989)) tidak dapat
menangani subroutine “inline”. Versi ini menggunakan ii sebagai ganti i dan menggunakan array psi untuk urutan p. Seperti
yang dicatat di atas (Bagian 7) kami memperbarui rel ke X dan rel X ke setiap kali ÿ diubah, ini berarti bahwa p[ÿ[i]] dapat
disimpan dalam psi[i].

/****************************************************** ********************
*
* Hitung dan kembalikan jumlah peta pemelihara relasi * pada bagian domain
antara mindepth dan maxdepth inklusif.
* Mengasumsikan bahwa array rel_to_X dan rel_X_to telah disiapkan.
* Mengembalikan jumlah peta yang ditemukan.
* Mengatur uji variabel global ke jumlah panggilan relpres yang diperlukan.
* Hentikan segera jika jumlah uji coba melebihi batas.
*
******************************************************* ******************/

dobel
hitung (mindepth, maxdepth, batas) int mindepth,
maxdepth; double batas;

{
/* Hitung dan kembalikan jumlah peta pemelihara relasi:
* gunakan mindepth untuk memaksimalkan elemen domain, * akhiri segera
setelah jumlah percobaan melebihi batas
*/
hitung ganda; int
rho; daftar
pendek rp, n, t, np; daftar int ii, numrels;

percobaan = 0;
hitung = 0; n
= kedalaman
minimum;
t = 1; untuk (;;) /* perulangan kalkulasi_do1: */
{ jika (t <= SY)
{ percobaan = percobaan +
1; jika (percobaan > batas)
{ pergi ke
kalkulasi_od1; }
/* Awal subrutin relpres: * jika relpres(psi,t,n)
maka rp=1 * relpres(psi,t,n) sama dengan
psi[n]=t; relpres(psi,n) * t adalah nilai uji untuk psi[n], relpres(psi,n-1) adalah
benar */ rp = 1; for (rho = 0; rho < R; rho++) { /* menguji relasi rho: */

/* Elemen uji yang berhubungan dengan X */

numrels = rel_to_X[rho][n][0]; untuk (ii = 1; ii
<= numrels; ii++) { np = rel_to_X[rho][n][ii];
/* np adalah elt ke-i yang terkait dengan n */

32
 Machine Translated by Google

jika (np < n) { jika /* psi[np] didefinisikan: */

(RY[rho][t][psi[np]] == 0) {
rp = 0;
pergi ke calc_end_relpres;
}
} kalau tidak {
jika (np == n) { /* n berhubungan dengan dirinya sendiri */
jika (RY[rho][t][t] == 0) { /* periksa apakah t berhubungan dengan dirinya sendiri */
rp = 0;
pergi ke calc_end_relpres;
} else { /* np > n, yaitu tidak ada lagi elt yang terkait dengan n */
pergi ke calc_end_inner_1;
}
} /* fi (np == n) */
} /* temukan np < n */
} /* Akhir dari loop for bagian dalam */
kalkulasi_akhir_dalam_1:
/* Elemen uji X berhubungan dengan */
angka = rel_X_ke[rho][n][0];
untuk (ii = 1; ii <= angka; ii++) {
np = rel_X_to[rho][n][ii]; jika (np < n) { jika /* np adalah elt ke-i yang berhubungan dengan n */
(RY[rho][psi[np]][t] /* psi[np] didefinisikan: */
== 0) {
rp = 0;
pergi ke calc_end_relpres;
}
} else /* sudah diperiksa n berhubungan dengan kasus n */
{ pergi ke kalkulasi_akhir_dalam_2;
} /* temukan np < n */
} /* Akhir dari loop for bagian dalam */
kalkulasi_akhir_dalam_2:;
} /* Akhiri loop for luar, relasi berikutnya */
/* Akhir dari subrutin relpres */
kalkulasi_akhir_relpres:
jika (rp == 1) {
jika (n == kedalamanmaksimum) {
hitung++;
bahasa inggrisnya t++;

} kalau tidak {
satuan psi[n] = t;
bahasa inggris n++;

tanggal = 1;

}
} kalau tidak {
bahasa inggrisnya t++;

}
} kalau tidak { /* dari (t <= SY) */
N--;
jika (n < kedalaman minimum) {
pergi ke calc_od1;
}
t = psi[n] + 1;
} /* fi dari (t <= SY) */
}
kalkulasi_od1:
kembali (hitungan);
} /* Akhir perhitungan(kedalaman minimum, kedalaman maksimum, batas) */

33

Melihat publikasi Statistik