STACK Tumpukan
Setelah array, mungkin yang paling penting adalah struktur data stack. Struktur stack membatasi secara dramatis bagaimana elemen-elemen yang dimasukkan, diambil, dan dihapus: baru-baru ini dimasukkan elemen yang paling dalam stack adalah satu-satunya yang dapat diambil atau dihapus harus. (Jadi, jika Anda ingin mengambil elemen dimasukkan sebuah lama, Anda pertama menghapus semua elemen yang disisipkan setelah yang diinginkan disebut.) Ini strategi penghapusan dan pengambilan kadang-kadang, `` terakhir, keluar pertama.''
Sebuah contoh kehidupan nyata yang baik dari stack adalah tumpukan piring makan malam yang Anda temui ketika Anda makan di kafetaria lokal: Bila Anda menghapus piring dari tumpukan, Anda mengambil piring di atas tiang persis. Tapi ini piring yang ditambahkan (dimasukkan ``'') yang terakhir ke tumpukan oleh mesin cuci piring. Jika Anda ingin piring di bagian bawah tumpukan, Anda harus menghapus semua piring di atasnya untuk mencapainya. Lain, sedih, contoh stack slogan, `` terakhir menyewa, pertama dipecat,''yang biasanya digunakan ketika perusahaan mengurangi tenaga kerja tersebut.
Banyak algoritma komputer bekerja paling baik dengan tumpukan --- tumpukan digunakan untuk
- mengingat sebagian tugas selesai, dan
- kehancuran (mundur dari) tindakan.
Contoh 1. dijelaskan dalam bagian berikutnya, di mana mengelompokkan sub ekspresi dari sebuah ekspresi aritmatika diingat untuk perhitungan nanti. Contoh lain disajikan dalam kuliah mendatang, di mana kita melihat bagaimana Java Virtual Machine menggunakan stack untuk mengingat semua program metode yang telah dipanggil tetapi belum selesai.
Contoh 2. adalah''`` undo tombol pada editor teks yang paling, yang memungkinkan seseorang membatalkan kesalahan mengetik, atau bagian belakang''`` tombol di browser web, yang memungkinkan seorang pengguna mundur ke halaman web sebelumnya. Contoh lain adalah algoritma pencarian, yang mencari labirin dan menyimpan sejarah bergerak dalam tumpukanJika algoritma membuat bergerak (buruk) palsu, memindahkan dapat dibatalkan oleh mengambil posisi sebelumnya dari stack.
Contoh: evaluasi ekspresi aritmatika
Kita mulai dengan contoh yang terkenal yang menggunakan stack untuk mengingat komputasi tugas yang telah selesai sebagian: Mengevaluasi sebuah ekspresi aritmatika ditulis dalam notasi postfix (`` Lukasiewicz''notasi).
Postfix adalah bebas cara penulisan tanda kurung ekspresi aritmatika, dimana satu tempat simbol operator setelah operator dua operan. Sebagai contoh, penambahan 3-2 ini ditulis 3 2 +, dan perbanyakan hasilnya dengan 4 ditulis 3 2 + 4 *. Hebatnya, kurung tidak pernah diperlukan. Contoh seperti
((3 + 2) * 4) / (5 - 1) ((3 + 2) * 4) / (5 - 1)
ditulis
3 2 + 4 * 5 1 - / 3 2 + 4 * 5 1 - /
Untuk melihat mengapa kurung tidak diperlukan, mari kita menghitung secara manual ekspresi:
3 2 + 4 * 5 1 - / 3 2 + 4 * 5 1 - /
=> 5 4 * 5 1 - / => 5 4 * 5 1 - /
=> 20 5 1 - / => 20 5 1 - /
=> 20 4 / => 20 4 /
=> 5 => 5
Kita melihat bahwa operator mengevaluasi dengan dua operan yang segera mendahului itu. Hal ini menjelaskan mengapa operator divisi ditulis terakhir dalam ekspresi asli, karena pembagian dilakukan hanya setelah semua mengelompokkan sub ekspresi lainnya dievaluasi.
aritmatika Postfix lebih dari sebuah keanehan yang menarik --- ini adalah format standar untuk penulisan ekspresi aritmatika yang harus dijalankan oleh CPU. Ingatlah bahwa logika-unit CPU bekerja dengan aritmatika register CPU untuk melakukan aritmatika. CPU tidak bisa menghitung hasil dari ekspresi, ((3 + 2) * 4) / (5 - 1), tetapi dapat menghitung hasil 3 2 + 4 * 5 1 - /, karena operan dan operator sekarang disusun dalam urutan yang benar untuk memuat angka ke dalam register dan melakukan operasiBerikut adalah kode perakitan urutan yang memberitahu CPU bagaimana untuk menghitung ekspresi postfix:
loadconst R1 3 // load Register 1 with constant 3 loadconst R1 3 / / ambil Pendaftaran 1 dengan 3 konstan
loadconst R2 2 // load Register 2 with constant 2 loadconst R2 2 / / load Daftar 2 dengan 2 konstan
add R2 R1 // add Register 1 to Register 2 menambahkan R2 R1 / / menambahkan Pendaftaran 1 untuk Mendaftar 2
loadconst R1 4 // etc. loadconst R1 4 / / dll
multiply R2 R1 kalikan R2 R1
loadconst R1 5 loadconst R1 5
loadconst R3 1 loadconst R3 1
subtract R1 R3 kurangi R3 R1
divide R2 R1 membagi R2 R1
nama register itu, R1, R2, R3, agak mengganggu --- pemberitahuan pola tersembunyi dalam petunjuk (menghapus nama register):
loadconst 3 loadconst 3
loadconst 2 loadconst 2
add menambahkan
loadconst 4 loadconst 4
multiply berkembang biak
loadconst 5 loadconst 5
loadconst 1 loadconst 1
subtract mengurangi
divide membagi
Memang, versi sederhana dari kode assembly ini disebut stack kode atau kode byte, dan itu sebenarnya format kode tertanam dalam file kelas. Dibangun oleh compiler Java.
menerjemahkan program Java menjadi notasi posfix
Karena format postfix sangat ideal untuk perhitungan dengan CPU, compiler Java tidak hanya memeriksa tata bahasa program Java Anda, juga diterjemahkan ke dalam format program postfix --- bahkan tugas, conditional, dan loop ulang ke dalam format postfix. If you write a program like this: Jika Anda menulis sebuah program seperti ini:
... ...
x = x + 1; x = x + 1;
if ( x > 2 ) if (x> 2)
{ y = 2 * ( x - 3 ); } {Y = 2 * (x - 3);}
... ...
Java compiler menghasilkan-ulang versi postfix:
... ...
x 1 + =x ; x 1 + = x;
x 2 > if x 2> jika
2 x 3 - * =y ; 2 x 3 - * = y;
... ...
... ...
load x beban x
loadconst 1 loadconst 1
add menambahkan
storeinto x storeinto x
load x beban x
loadconst 2 loadconst 2
greaterthan greaterthan
test_and_jump_if_false_to LabelA test_and_jump_if_false_to LabelA
loadconst 2 loadconst 2
load x beban x
loadconst 3 loadconst 3
subtract mengurangi
multiply berkembang biak
storeinto y storeinto y
LabelA: ... LabelA: ...
Contoh meninggalkan kita dengan dua pertanyaan mendasar:
- Bagaimana Java Virtual Machine mengeksekusi kode byte?
- Bagaimana compiler Java mengkonversi program Java ke format postfix (kode byte)?
Both questions are answered with the assistance of the stack data structure. Kedua pertanyaan dijawab dengan bantuan struktur data stack.
Java Virtual Machine menggunakan stack
Sebuah stack adalah struktur data yang ideal untuk mengevaluasi sebuah ekspresi aritmatika ditulis dalam notasi postfix.
Ingat lagi bahwa versi postfix dari ((3 + 2) * 4) / (5 - 1) adalah
3 2 + 4 * 5 1 - /
Gambar 2 mengilustrasikan bagaimana kita bisa menggunakan stack untuk menghitung hasil ekspresi ini --- tumpukan memegang hasil mengelompokkan sub ekspresi yang sedang menunggu perhitungan lebih lanjut.
Dalam Gambar di bawah, tumpukan digambar seakan setumpuk piring makan malam --- tumbuh vertikal. menyusut Ekspresi aritmatika horizontal seperti yang dibaca dan dihitung.
GAMBAR 2: Evaluasi ekspresi postfix dengan struktur data stack ========
Stack Ekspresi
| | | |
--- 3 2 + 4 * 5 1 - /
(Kosong)
| 3 | 2 + 4 * 5 1 - /
---
| 2 |
| 3 | + 4 * 5 1 - /
---
| 5 | 4 * 5 1 - /
---
| 4 | | 4 |
| 5 | * 5 1 - / | 5 | * 5 1 - /
--- ---
| 20| 5 1 - / | 20 | 5 1 - /
--- ---
| 5 | | 5 |
| 20| 1 - / | 20 | 1 - /
--- ---
| 1 |
| 5 |
| 20 | - /
---
| 4 |
| 20 | /
---
| 5 | (selesai)
---
ENDFIGURE ================================================= ==============
Simbol dari ekspresi input dibaca, satu per satu; angka dimasukkan ke atas''`` dari stack, dan operator mengambil angka atas dua dari tumpukan, melakukan operasi, dan masukkan hasil ke stack.
Ini sederhana dan mekanis, dan mudah untuk menulis algoritma komputer yang melakukan langkah-langkah:
dimulai dengan stack kosong dan input stream.
sementara ada masukan lebih untuk membaca, lakukan:
membaca simbol masukan berikutnya;
jika suatu angka,
kemudian dorong ke dalam stack;
jika operator
kemudian pop dua angka dari stack;
melakukan operasi pada angka;
push the result; push hasilnya;
akhir sementara;
/ / Jawaban ekspresi sedang menunggu untuk Anda dalam tumpukan:
pop jawaban;
Indeed, the algorithm sketched above forms the heart of the Java Virtual Machine , which ``reads'' and ``executes'' your Java program. Memang, algoritma membuat sketsa di atas merupakan inti dari Java Virtual Machine, yang berbunyi `` ``''dan''mengeksekusi program Java Anda.
Ingat bahwa Java Virtual Machine (JVM) itu sendiri merupakan program komputer, yang bertugas untuk membaca kode byte dan lakukan petunjuk. Seperti yang kita lihat pada bagian sebelumnya, kedua pernyataan Jawa serta ekspresi yang diterjemahkan oleh compiler Java ke dalam byte kode. The JVM membaca kode byte instruksi, dan menggunakan stack, sama seperti yang kita gunakan pada contoh aritmatika, untuk menghitung hasil ekspresi aritmatikaStack yang kadang-kadang disebut nilai-sementara tumpukan, karena subresults ekspresi aritmatika adalah ``''sementara dan hasil akhir adalah muncul dan disimpan ke dalam sel storage variabel.
The algorithm for the JVM looks something like this: Algoritma untuk JVM terlihat seperti ini:
dimulai dengan stack kosong dan kode byte.
sementara ada kode byte lebih untuk membaca, lakukan:
membaca instruksi byte-kode berikut;
jika n loadconst,kemudian dorong n ke stack; jika beban x,
kemudian mencari nilai x dalam penyimpanan dan mendorongnya ke dalam stack;
jika operator kemudian pop dua angka dari stack melakukan operasi pada angka;
push hasilnya;
jika toko x,
kemudian pop angka dan menyimpannya dalam sel x di penyimpanan;
jika label bagi test_and_jump_
maka pop stack dan melihat apakah nilai salah (0);
if jika sudah, reset instruksi JVM's counter untuk membuat label... dll ...
akhir sementara;
Jadi, CPU mengeksekusi JVM, yang membaca dan mengeksekusi kode byte. It all works well because of a stack! Itu semua bekerja dengan baik karena stack!
Menulis seseorang sendiri tumpukan
Tabel 3 menentukan metode satu kebutuhan untuk stack.
TABEL 3: spesifikasi dari sebuah stack ========================================
| Stack Tumpukan | koleksi benda-benda seperti yang baru-baru ini dimasukkan objek paling adalah satu-satunya yang dapat diambil atau dihapus. |
| push(Object v) | menyisipkan v ``''ke dalam stack |
| pop(): Object | menghapus dari tumpukan yang baru dimasukkan unsur paling (dari yang terkandung dalam struktur) dan mengembalikannya elemen. Jika stack tidak, pengecualian dilemparkan |
| atas (): Object | mengambil yang baru dimasukkan unsur paling (dari yang terkandung dalam struktur) dan mengembalikannya. Objek adalah tidak dihapus dari tumpukan elemen. Jika stack tidak, pengecualian dilemparkan |
| isEmpty(): boolean | kembali apakah tumpukan memegang setiap elemen |
ENDTABLE=============================================================
Nama, push, pop, dan top tradisional; isEmpty adalah panjang tumpukan's ``''operasi.
Sebuah stack dapat diimplementasikan dalam berbagai cara, kita mulai dengan Gambar 4, yang menggunakan sebuah array, s, untuk mengumpulkan tumpukan's elemen. Sebuah variabel tambahan, atas, digunakan untuk mengingat elemen array yang berisi objek yang paling baru dimasukkan.
GAMBAR 4: array berbasis implementasi stack ============================
/ ** Model Stack0 setumpuk struktur data * /
public class Stack0 public class Stack0
{ private int INITIAL_SIZE = 5; {Private int INITIAL_SIZE 5 =;
private int top; / / berapa banyak elemen dalam stack
private Object[] s; // the stack Obyek pribadi [] s; / / tumpukan
Invariants: elemen pada stack adalah s [top-1] s [top-2] ... s[0] s [0]
/ / Atas selalu dalam jangkauan 0 .. s.length-1 s.length-1
/ ** Konstruktor Stack0 menciptakan stack. */ * /
publik Stack0 ()
{S = Obyek baru [INITIAL_SIZE];
top = 0;
} }
/ ** Push menyisipkan elemen baru ke dalam stack
* @ param - elemen yang akan ditambahkan * /
public void push(Object ob) public void push (Object ob)
{If (top == s.length)
{/ / Array penuh --- membuat yang baru untuk memegang benda lebih:
Object [] temp = Obyek baru [s.length * 2];
for (int 0 = j; j = atas;! j = j +1)
{Temp [j] = s [j];} / / elemen copy ke temp
s = temp; / / s set ke alamat terus temp
} }
s[top] = ob; s [top] = ob;
top = top + 1; atas = top + 1;
} }
/ ** Menghilangkan pop paling baru ditambahkan unsur
* @ Return elemen dihapus dari stack
* @ Pengecualian RuntimeException jika stack kosong * /
Obyek publik pop ()
{If (top == 0)
{Melemparkan RuntimeException baru ("error Stack: stack kosong");}
atas = top - 1;
kembali s [top];
} }
/ ** Atas mengembalikan identitas dari elemen yang paling baru ditambahkan
* @ Return elemen
* @ Pengecualian RuntimeException jika stack kosong * /
Obyek publik atas ()
{ if ( top == 0 ) {If (top == 0)
{Melemparkan RuntimeException baru ("error Stack: stack kosong");}
kembali s [top - 1];
} }
/ ** Menyatakan isEmpty apakah stack memiliki 0 elemen.
* @ Return apakah stack tidak memiliki elemen * /
public boolean isEmpty ()
{Return (top == 0);}
} }
ENDFIGURE ================================================= ===========
Jika kita membuat stack, operan, dari Gambar 4 untuk melakukan perhitungan pada Gambar 2, konfigurasi kedelapan pada Gambar yang akan terlihat seperti ini di penyimpanan komputer:
----
operan Stack0 == | a1 |
----
a1: Stack0
-------------- ---
| Int INITIAL_SIZE == | 5 |
| --- ---
| Int top == | 3 |
| ------- | -------
| Obyek] [s == | a2 |
| ----
| ...
a2: Objek [5]
--------------
| 0 1 2 3 4
| -----------------------------
| | A7 | a8 | a9 | null | null |
| -----------------------------
a7 : Integer a8: Integer a9: Integer --------------- -------------- -------------- | (holds 20) | (holds 5) | (holds 1) |
array memegang alamat dari tiga objek Integer, dan atas ingat bahwa tumpukan menyelenggarakan tiga objek. (Review bagian, Objek kelas `` dan Wrapper,''dalam Bab 9 untuk mempelajari mengapa bilangan bulat, 20, 5, dan 1, harus tertanam menjadi objek Integer sebelum mereka dimasukkan ke dalam stack.)
Langkah berikutnya dalam Gambar 2 menghilangkan dua benda dari stack (menggunakan pop dua kali), apakah pengurangan, dan menyisipkan 4 (menggunakan push). Konfigurasi yang dihasilkan terlihat seperti ini:
----
operan Stack0 == | a1 |
----
a1: Stack0
-------------- ---
| Int INITIAL_SIZE == | 5 |
| --- ---
| Int top == | 2 |
| -------
| Obyek] [s == | a2 |
| ----
| ...
a2: Objek [5]
--------------
| 0 1 2 3 4
| -----------------------------
| | A7 | A10 | a9 | null | null |
| -----------------------------
a7 : Integer a8 : Integer a9 : Integer a10 : Integer --------------- -------------- -------------- --------------
| (holds 20) | (holds 5) | (holds 1) | (holds 4) |
Karena nilai atas benar menandai puncak stack, tidak perlu menghapus nilai dalam elemen 2 dari array --- nilai ini tidak akan pernah lagi digunakan dan akan ditimpa jika push dijalankan berikutnya.
The Java Compiler Menggunakan Stack
Sebuah stack adalah struktur data kunci untuk menerjemahkan program ke format postfix (dan kemudian, ke dalam kode byte).
Untuk tetap sederhana, berpikir tentang bagaimana kita bisa menerjemahkan ekspresi aritmatika infix, seperti ((3 + 2) * 4) / (5 - 1), menjadi 3 2 + 4 * 5 1 - ini / waktu., Tumpukan memegang simbol operator (bukan operan); algoritma berjalan seperti ini:
dimulai dengan stack kosong dan input stream.
sementara ada masukan lagi, lakukan:
membaca simbol masukan berikutnya;
jika suatu angka,
kemudian cetak ke FILESTREAM output;
jika operator,
kemudian dorong ke dalam stack;
jika sebuah '(',
kemudian membuangnya;
jika sebuah ')', / / menandai akhir dari sebuah ekspresi!
kemudian pop operator dari stack dan mencetaknya
akhir sementara;
Sebagai latihan, gunakan algoritma untuk menerjemahkan ((3 + 2) * 4) / (5 - 1).
Anda dapat melihat dari algoritma yang tanda kurung (terutama yang kanan) memainkan peran penting dalam mengarahkan tumpukan muncul dan terjemahan ---. Ini adalah bukan kecelakaan tumpukan digunakan untuk menerjemahkan disebut braket bahasa-begitu, dan keduanya aritmatika dan Jawa adalah contoh dari bahasa braket.
Ini bukan sebuah kecelakaan yang membuat Anda menyisipkan Java semua membosankan {dan} simbol dan seperti tanda baca, dan kata kunci seperti kelas dan sementara bentuk. Ini adalah tanda kurung yang menggunakan Java compiler Jawa membongkar program dan membangunnya kembali postfix di!
Sebagai latihan, Anda harus mencoba untuk memodifikasi algoritma di atas sehingga bisa menerjemahkan bahasa Jawa-bayi dari aritmatika, tugas, dan-sementara loop ke dalam format postfix. Jika Anda dapat melakukan ini, Anda sangat dekat dengan Jawa menulis sendiri compiler anda.
Exhaustive Cari
Tumpukan juga digunakan untuk mengingat jalan yang satu perjalanan ketika salah satu pencarian ``''melalui jaringan, grafik, atau pohon'a', 'b', 'c' and 'd' . Berikut ini adalah contoh sederhana: Katakanlah bahwa Anda harus daftar semua surat permutasi-kata empat huruf, 'a', 'b', 'c' dan 'd'. Untuk memikirkan solusi sistematis, Anda mungkin menggambar pohon ``,''jalur yang menunjukkan pilihan untuk huruf pertama kata, huruf kedua, dan seterusnya. Sebuah sketsa pohon muncul pada Gambar 5.
GAMBAR 5: cari pohon untuk permutasi dari "abcd "===========================
"" (String kosong)
/ / \ \ / / \ \
Pertama surat: abcd
/ | \ / | \ / | \ /|\ / | \ / | \ / | \ / | \
/ | \ / | \ / | \ / | \
Kedua surat: bcdacd ... ... ...
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
/ \ / \ / \ / \ / \ / \
Ketiga surat: cdbdbc ... ... ... ... ...
| | | | | | | | | | | |
(Surat Terakhir:) dcdbcb ... ... ... ... ...
ENDFIGURE ================================================= =============
Seperti pohon kadang-kadang disebut pohon pencarian, dan jalur melalui pohon disebut ruang pencarian. (Pikirkan tentang sebuah game petualangan di mana Anda harus membuka pintu, a, b, c, dan d, dan urutan di mana Anda membuka pintu mempengaruhi hasil pertandingan. Cara paling cerdas untuk komputer untuk bermain permainan ini adalah untuk mempelajari semua urutan yang mungkin bergerak sebelum membuat langkah pertama. komputer akan menghasilkan pohon pencarian terlihat di atas.)
Untuk mencari''`` pohon untuk semua huruf permutasi empat, Anda mengikuti jalur dari atas pohon (akar) untuk titik akhir nya (itu daun).
Di bagian atas pohon, Anda pilih salah satu dari empat jalan untuk mencapai pertama huruf kata; mengatakan bahwa Anda memilih jalur paling kiri, memilih saja. Ini akan memberikan Anda mungkin tiga jalur untuk kedua surat, dan sebagainya, pada. Dari untuk menghasilkan semua permuations, Anda harus melintasi semua jalan dari pohon. Traversal dari semua jalur hanya dilakukan dengan setumpuk --- sebagai salah satu jalan yang dilalui, tumpukan mengingat jalur yang harus dieksplorasi kemudian.
Gambar 6 menggambarkan proses traversal, di mana tumpukan ditarik pada sisinya, atas''`` yang diposisikan ke kanan.
GAMBAR 6: traversal pohon yang menghasilkan permutasi =====================
Isi Stack Pohon traveral langkah
-------------- ------------------------ -------------- ------------------------
"" Mulailah dengan setumpuk yang memegang string kosong.
(Kosong) Pop stack. the Menetapkan nilai muncul, "", mewakili
posisi di bagian atas pohon. Next, Selanjutnya,
memperpanjang string, "", dengan a, b, c, d, dan mendorong
menghasilkan empat string:
"d" "c" "b" "a" "D" "c" "b" "a"
Pop stack. Nilai "a" mewakili posisi-in
"D" "c" "b" pohon. Memperpanjang "a" dengan b, c, d, dan mendorong:
"D" "c" "b" "ad" "ac" "ab"
Pop stack, memperpanjang "ab" oleh c dan d, dan mendorong:
"D" "c" "b" "ad" "ac" "abd" abc "
Pop stack, dan memperpanjang "abc" oleh d push, dan:
"D" "c" "b" "ad" "ac" "abd" abcd "
Pop stack. Nilai muncul, "abcd", adalah selesai
string, sehingga output.
"D" "c" "b" "ad" "ac" "abd"
Pop stack, dan memperpanjang "abd" oleh c, dan mendorong:
"D" "c" "b" "ad" "ac" "abdc"
Pop stack. Nilai muncul, "abdc", adalah selesai
string, sehingga output.
"D" "c" "b" "ad"
Pop stack, memperpanjang "ac" oleh b dan d, dan mendorong:
"D" "c" "b" "ad" "ACD" "ACB" dll
ENDFIGURE ================================================= ============
Gambar ini menunjukkan bahwa pencarian melintasi jalan pohon dari kiri-ke-kanan, benar-benar ke titik akhir (`` daun''). Bentuk traversal disebut telusur pertama kedalaman karena turun ke kedalaman `` ''pohon secepat mungkin. A stack secara alami mendukung telusur pertama kedalaman.
Cari pohon seperti yang pada Gambar 5 yang digunakan untuk mewakili pilihan bergerak mungkin dalam permainan komputer, sebuah pemutar `` komputer'', katakanlah, tic-tac-toe (noughts dan salib), bisa menggunakan seperti pohon untuk sistematis mengeksplorasi semua urutan bergerak dan menghitung semua hasil yang mungkin. Tumpukan membantu player mengingat urutan yang bergerak tetap untuk dianalisis.
Lain-contoh yang dikenal pencarian, yang disebut masalah perjalanan salesman ``,''menemukan jalan terpendek dari sebuah kota mulai kota tujuan pada peta jalan, jalan antar kota adalah sebagai sebuah pohon, dan setumpuk membantu suatu program menghitung total jarak yang ditempuh di setiap jalur dari kota mulai kota berikutnya ke berikutnya, dll, ke tujuan.
Sedikit pemikiran akan meyakinkan anda bahwa pohon pencarian itu sendiri tidak perlu dibangun ketika pemrograman solusi untuk masalah salesman keliling: Sebuah tabel yang berisi daftar kota-kota berdekatan dan jarak antara mereka akan cukup untuk membangun stack. (Hal ini juga berlaku untuk contoh permutasi, mana huruf dalam string dapat dilihat pada tempat pohon pencarian.)
Tidak ada komentar:
Posting Komentar