Hal-hal yang Seandainya Saya Ketahui Sebelum Mengembangkan Autorouter
(blog.autorouting.com)- Pengalaman mengembangkan autorouter PCB open source untuk tscircuit selama sekitar 1 tahun menunjukkan bahwa desain yang mengurangi masalah pencarian seperti A*, visualisasi, pembagian ruang, dan caching adalah inti dari performa
- Fokus optimasi ada pada mengurangi jumlah iterasi, bukan pada bahasa atau kecepatan satu iterasi; bahkan JavaScript bisa lebih cepat daripada implementasi tingkat rendah jika algoritmenya lebih cerdas dan dapat di-cache
- Dalam pencarian spasial, Spatial Hash Index bisa lebih sederhana dan cepat daripada tree serbaguna seperti QuadTree, tetapi pemilihan ukuran sel yang salah menimbulkan biaya tetap tinggi di setiap query
- Pipeline autorouter yang kompleks harus memvisualisasikan input dan output per tahap serta memeriksa proses iteratif lewat animasi; fungsi rekursif dan pendekatan Monte Carlo kurang menguntungkan untuk debugging, optimasi, dan determinisme
- A* dapat mengorbankan sebagian optimalitas dengan Greedy Multiplier pada Weighted A* untuk meningkatkan kecepatan secara besar, dan setiap tahap harus menurunkan probabilitas kegagalan agar tahap berikutnya lebih mudah diselesaikan
Menjadikan A* sebagai alat pencarian dasar
- A* bukan algoritme khusus untuk grid 2D, melainkan algoritme dasar yang dapat digunakan untuk berbagai bentuk pencarian berbasis informasi (informed search)
- BFS menjelajahi semua node tetangga, sedangkan A* memprioritaskan node yang lebih dekat ke tujuan
- Karena menggunakan metrik jarak di luar graf, ini termasuk pencarian berbasis informasi
- Algoritme rekursif mirip dengan depth-first search (DFS), dan loop yang menjelajah tanpa mengurutkan kandidat atau tetangga mirip dengan BFS
- Mengubah kode berbentuk BFS atau DFS yang sudah ada menjadi A* sering kali menghasilkan peningkatan performa besar
- Pada autorouter, beberapa tingkat A* digunakan untuk menemukan hyperparameter yang sesuai dengan masalah
- Menjalankan setiap konfigurasi autorouter sebagai kandidat
- Mengalokasikan lebih banyak iterasi pada konfigurasi yang mulai berhasil melakukan routing dengan biaya yang baik
- Ini adalah bentuk meta-A* yang memakai biaya jarak dan biaya iterasi sebagai penalti
Algoritme lebih penting daripada bahasa
- tscircuit autorouter ditulis dalam JavaScript, dan dalam diskusi performa, bahasa sering menjadi hal pertama yang disorot
- Optimasi algoritme terbagi menjadi dua sumbu besar
- Mengurangi jumlah iterasi yang diperlukan agar algoritme menjadi lebih cerdas
- Meningkatkan kecepatan eksekusi tiap iterasi
- Jika terlalu fokus pada peningkatan kecepatan satu iterasi, hasilnya bisa hanya menjalankan pendekatan yang salah dengan cepat
- Misalnya, mengubah semuanya menjadi grid untuk pemeriksaan overlap bisa menjadi lambat terlepas dari bahasanya
- Algoritme cerdas dalam JavaScript bisa lebih cepat daripada algoritme sederhana dalam assembly yang dioptimalkan di level rendah
- Sebaiknya 95% waktu pengembangan dihabiskan untuk mengurangi jumlah iterasi, dan bahasa yang cepat membawa kita ke algoritme paling cerdas dan paling dapat di-cache adalah pilihan yang baik
Spatial Hash Index bisa lebih baik daripada tree
- Dalam optimasi ruang multidimensi, QuadTree sering muncul, tetapi struktur data tree serbaguna bisa lambat
- QuadTree dikenal sebagai struktur data yang mengurangi pencarian objek terdekat di ruang 2D/3D dari
O(N)menjadiO(log(N)), tetapi tree bukan representasi berbasis informasi atas data - Spatial Hash Index meng-hash lokasi objek, bukan objek itu sendiri, lalu menyimpannya dalam sel atau bucket berisi objek-objek yang berdekatan
- Pendekatan ini menerapkan akses berbasis hash yang cepat seperti HashSet dan HashMap pada data spasial
- Alasan spatial hash kurang populer adalah karena harus memilih ukuran sel yang sesuai
- Jika ukuran sel dikalibrasi dengan buruk, setiap query menimbulkan biaya tetap yang tinggi
- Dalam praktiknya, memilih ukuran sel yang masuk akal dianggap tidak sesulit itu
Pembagian ruang dan caching mengubah performa
- Papan sirkuit seperti bagian dalam iPhone bisa memiliki kira-kira 10.000–20.000 trace, dan bahkan dengan alat EDA kelas atas, satu tim bisa membutuhkan berbulan-bulan untuk melakukan routing
- Ide sederhana yang penting dalam masalah autorouting adalah bahwa sesuatu yang sudah diroute pernah diroute sebelumnya
- Developer game memanggang mesh pencarian sebelumnya, dan LLM mengompresi internet menjadi bobot untuk pencarian
- Autorouter generasi berikutnya dapat membagi masalah secara spasial dan memanfaatkan cache besar berisi solusi yang sudah pernah diselesaikan
- Jika 99% masalah autorouting sudah diselesaikan sebelumnya di cache, kecepatan algoritme itu sendiri menjadi kurang penting
- Saat ini banyak algoritme belum cukup berfokus pada penggunaan ulang cache dan pembagian ruang
- Biaya penyimpanan dan caching tampaknya turun lebih cepat daripada peningkatan kecepatan komputasi, sehingga memakai cache 1GB untuk membuat autorouter 50% lebih cepat dianggap bukan masalah besar
Melihat masalah secara langsung dengan visualisasi dan profiling
- Prinsip pentingnya adalah: tanpa visualisasi atas masalah, kita tidak bisa menyelesaikannya
- Debugging sulit dilakukan jika hanya melihat angka, dan membuat visualisasi untuk setiap submasalah kecil membuat masalah jauh lebih cepat dipahami
- Dalam pengembangan autorouter, pemecahan masalah sering kali dimulai dari visualisasi
- Subalgoritme untuk menemukan jalur 45 derajat juga divisualisasikan, dan ini digunakan pada Path Simplification Phase, yang hampir merupakan tahap terakhir autorouter
- Alat profiling JavaScript menunjukkan total waktu yang dihabiskan di setiap baris kode dalam milidetik
- Cukup jalankan JavaScript di browser dan buka tab Performance
- Flame chart dan fitur penggunaan memori juga tersedia
- Video singkat terkait: youtube short
Menghindari rekursi dan Monte Carlo
- Fungsi rekursif sebaiknya dihindari dalam kode yang berorientasi performa
- Hampir selalu berjalan secara sinkron sehingga sulit dihentikan di tengah untuk animasi
- Secara inheren merupakan DFS dan sulit diubah menjadi A*
- Jumlah iterasi tidak mudah dilacak
- Dalam fungsi rekursif, mutabilitas terasa tidak alami, padahal mutabilitas bisa penting untuk performa
- Implementasi berbasis iterasi bisa lebih cepat karena dapat mempertahankan himpunan
visitedNodesdan memeriksa node sebelum menjelajah - Algoritme Monte Carlo mendekati solusi lewat keacakan, tetapi karena tidak deterministik, sulit di-debug dan dianggap hampir tidak pernah optimal dibanding heuristik
- Ketika kita tahu cara mengevaluasi kandidat tetapi tidak tahu cara mencapai solusi, pendekatan Monte Carlo dapat membantu mendapatkan intuisi
- Begitu ada sesuatu yang mirip fungsi biaya, sebaiknya gunakan pendekatan yang lebih baik daripada teknik acak seperti Monte Carlo atau Simulated Annealing
- Jika sensitif terhadap local minima, hyperparameter atau fungsi biaya yang lebih kompleks bisa dipertimbangkan
- Seperti desainer PCB tidak menggambar garis secara acak di atas papan sirkuit, dalam domain ini diyakini ada heuristik yang lebih baik untuk ditemukan
Menempatkan algoritme perantara dalam sistem koordinat yang sama
- Autorouter saat ini adalah pipeline yang terdiri dari 13 tahap dan sekitar 20 subalgoritme
- Jumlah iterasi diukur dalam pekerjaan seperti keputusan pembagian ruang atau penyederhanaan jalur pada batas area yang di-autoroute secara independen
- Memvisualisasikan input dan output tiap tahap secara bertumpuk membantu memahami konteks masalah yang sedang diselesaikan
- Masalah pada tahap downstream, terutama tahap high density routing, sering kali dapat diselesaikan dengan memperbaiki output tahap sebelumnya
- Saat membuat subalgoritme, ada godaan untuk memisahkan masalah ke bentuk paling sederhana dan menormalisasi koordinat di sekitar
(0, 0) - Normalisasi atau transformasi kompleks dapat mempersulit melihat dengan cepat dampak hasil tahap awal terhadap tahap berikutnya
- Menjaga ruang koordinat tetap konsisten sepanjang siklus hidup algoritme lebih menguntungkan
- Melihat setiap tahap secara berurutan dan melakukan zoom membantu menemukan tahap yang menjadi penyebab Design Rule Check gagal
Animasi iterasi dan menghindari grid
- Karena mengurangi jumlah iterasi itu penting, melihat iterasi algoritme sebagai animasi membantu memahami secara intuitif pencarian yang terbuang
- Animasi sangat membantu terutama saat menyesuaikan Greedy Multiplier
- Kasus ketika satu trace sederhana seharusnya gagal tetapi tidak segera gagal dan terus mencoba menyelesaikan ke arah luar tanpa henti sulit diketahui tanpa animasi
- Ada dua cara utama untuk menentukan apakah dua trace A dan B overlap
- Melihat tiap segmen A dan B lalu memeriksa perpotongan
- Menandai grid tempat B berada, lalu memeriksa apakah ada B pada grid yang dilalui A
- Pendekatan grid dapat dengan mudah menjadi 1000 kali lebih lambat
- Dengan matematika vektor yang cepat, dot product untuk menentukan perpotongan dua segmen bisa lebih cepat daripada akses memori untuk memeriksa satu sel grid
- Secara ketat, untuk menjamin clearance yang sesuai, perlu memakai perhitungan jarak antarsegmen; ini sedikit lebih kompleks daripada perpotongan, tetapi tidak jauh berbeda
Probabilitas kegagalan dan Weighted A*
- Pada tahap pembagian ruang, probabilitas kegagalan penyelesaian di setiap tahap dapat diukur sebagai indikator awal
- Unravel Autorouter melacak probabilitas kegagalan setiap Capacity Node pada tiap tahap utama pipeline
- Setiap tahap berfokus menurunkan probabilitas kegagalan melalui rekonstruksi node tetangga atau rerouting
- Probabilitas kegagalan benar-benar dapat diukur, dan jika algoritme berubah, prediksinya juga bisa ditingkatkan
- Setiap tahap dapat bekerja ke arah yang menurunkan kemungkinan kegagalan pada tahap berikutnya
- Lebih baik memprioritaskan kemungkinan untuk diselesaikan daripada memasukkan terlalu banyak batasan sekaligus
- Setelah papan berhasil diselesaikan, sering kali lebih mudah menangani solusi yang sudah ada daripada menghasilkan solusi optimal sejak awal
Menukar kecepatan dan optimalitas dengan Greedy Multiplier
- A* dasar menjamin solusi optimal, tetapi jika kecepatan lebih diutamakan,
f(n)dapat sedikit diubah untuk memakai Weighted A* - A* biasa:
f(n) = g(n) + h(n) - Weighted A*:
f(n) = g(n) + w * h(n) - Weighted A* memecahkan masalah secara lebih greedy dan umumnya bekerja jauh lebih cepat
- Pendekatan ini berperan sebagai Greedy Multiplier yang sangat meningkatkan performa A* dengan mengorbankan sebagian optimalitas
- Weighted A* dan varian A* lainnya dapat dilihat lebih lanjut di weighted A* and other A* variants here
- Developer game menangani banyak masalah yang mirip dengan developer autorouting, sehingga saat mencari riset terkait, makalah pengembangan game dapat dijadikan rujukan
Autorouter yang akan dirilis
- Autorouter untuk tscircuit semakin mendekati rilis
- Hasil pekerjaan ini akan tersedia sebagai open source berlisensi MIT
- Memecahkan autorouting dapat membuka inovasi dunia fisik secara besar-besaran, dan dianggap sebagai komponen kunci yang memungkinkan “vibe-building” untuk produk elektronik
- Akun terkait: follow me on twitter.
1 komentar
Komentar Hacker News
Secara umum saya cenderung tidak percaya pada autorouter, begitu juga alat AI yang masuk ke bidang ini, tetapi sulit menyangkal bahwa ada peluang besar untuk membuat sebagian layout dengan cepat di eCAD
Saya rasa saya akan lebih banyak memakai alat co-creation daripada alat yang sepenuhnya otomatis. Pada tahap awal desain, penempatan komponen sering kali belum final, dan penempatan sangat memengaruhi routing. Saya tidak melihat di halaman itu apakah penempatan dimasukkan ke dalam algoritme. Saat ini saya sudah memakai alat seperti push-and-shove atau kadang autocompletion
Pasarnya kecil, alatnya terfragmentasi, pemain lamanya adalah perusahaan besar yang lamban, dan penggunanya adalah para penggemar yang sangat rewel. Saya tidak akan melepas KiCad sampai mati. Saya tidak punya pendapat besar soal fakta bahwa autorouter ini ditulis dalam JavaScript, tetapi saya penasaran apakah rencananya akan menempel ke vendor CAD atau ekosistem alat open source, atau justru mencoba menarik orang ke ekosistem baru lagi
Jika ramah cache, memindahkan komponen dan mencoba layout lain akan jauh lebih cepat. JavaScript sekarang cukup portabel, bahkan dengan runtime kecil seperti QuickJS atau Proffor, dan saya rasa bisa dijalankan secara lokal sambil membangun cache besar secara langsung
Lock-in dan fragmentasi ekosistem di EDA adalah hal yang perlu dikhawatirkan semua orang, tetapi tscircuit dan autorouter ini adalah teknologi dengan lisensi permisif MIT, jadi dalam EDA yang jarang terjadi ini, keduanya bisa dibuat saling beroperasi dengan semua pihak
Setelah footprint, penempatan, constraint, dan net yang dirutekan manual dikunci, iterasi bisa dilakukan sangat cepat
Sejak Cadence mengakuisisi SPECCTRA pada 1990-an, autorouter PCB cukup stagnan, jadi menyenangkan melihat ada yang kembali menggarap bidang ini. Seingat saya, orang-orang yang membuat SPECCTRA pindah ke VLSI dan tidak kembali, dan tampaknya reputasi serta uang memang ada di sana. Mungkin dulu ini sempat menjadi ladang ranjau paten, dan mungkin sekarang pun masih begitu
Penempatan otomatis dulu pun merupakan masalah yang sepenuhnya sulit ditangani, dan sekarang pun tampaknya masih begitu, tetapi pendekatan AI generatif mungkin cocok. Penempatan komponen awal berbasis AI generatif yang bagus bisa mengurangi total waktu. Masalah terbesarnya adalah meyakinkan orang-orang keras kepala bahwa meski tidak sempurna, hasilnya bisa cukup baik
Upaya untuk membuat schematic sebagai kode agak membingungkan bagi saya. Sebagai format backend, semoga saja berhasil, dan khususnya kemajuan seperti di pihak jitx—mengenkode aturan desain setingkat app note dan datasheet ke dalam model komponen—terlihat bagus. Membaca semua datasheet sampai tingkat yang diperlukan untuk desain komersial jauh lebih banyak pekerjaannya daripada yang terlihat, begitu pula mengajari engineer junior untuk menguasai proses itu, jadi otomatisasi akan bermanfaat
Namun pendekatan-pendekatan itu tampaknya berakar pada gagasan bahwa schematic adalah input data untuk layout, semacam source code. Schematic juga merupakan dokumen desain dengan bahasa visual yang berevolusi dengan cermat, yang seharusnya dapat diakses bahkan oleh orang yang tidak memasang suite EDA. Orang-orang yang belajar dengan menguraikan schematic bergaya Adafruit/Sparkfun/Shenzhen yang meminimalkan wiring eksplisit mungkin tidak terlalu memahami nilai schematic yang baik
Hal lain adalah kecenderungan untuk terlalu mengandalkan analogi dan mencoba membuat desain tingkat PCB menjadi seperti desain VLSI. Saya tidak menganggapnya sepenuhnya mustahil. Jika DRC dan alat verifikasi membaik, desain tingkat komponen juga bisa menjadi lebih mirip VLSI. Namun keterikatan antara desain, EDA/CAM/simulasi, verifikasi, produsen, assembler, vendor komponen, serta lembaga regulasi dan sertifikasi terlalu longgar, sehingga jika satu sudut saja dari semua ini bisa dilakukan dengan benar, itu sudah merupakan pencapaian besar
Saat ini alurnya adalah mengerjakan desain UHF dengan kontrol impedansi bersama alat simulasi yang spesifik domain. Jadi trace penting dirutekan manual terlebih dahulu, dibuat island pole, lalu terakhir koneksi daya ditangani
Layout KiCad sedikit lebih baik daripada tidak ada, tetapi mencoba menjadikannya satu lagi alat simulasi yang setengah matang terlihat konyol
Yaitu dukungan database dan fitur outjob. Selebihnya lebih merupakan soal adopsi dan bagaimana pengguna memanfaatkan fitur ini, dan database biasanya lebih banyak disertai birokrasi internal untuk penataan data
Dari sudut pandang workflow yang mempercepat layout, saya rasa KiCad juga sudah sampai batas tertentu bergerak ke arah itu. Misalnya ada fitur “trace autocomplete” yang masuk sekitar versi 7.0. Kalau tidak salah shortcut-nya F di pcbnew, dan fitur itu memasang trace untuk track yang sedang ditempatkan. Jika dipakai bersama shortcut E untuk “routing dari sisi lain track”, produktivitas meningkat besar saat bekerja di antara dua grid ballout yang berbeda
Di versi 9, bus atau beberapa track bisa di-drag, sehingga alur ini bisa makin cepat
Jujur saja, jika bisa mencapai penempatan yang memuaskan dan bisa memberi constraint posisi routing ke autorouter, saya rasa sebagian besar desain dapat diserahkan ke autorouter. Misalnya tahun lalu saya mengerjakan board yang memakai NXP iMX8MP dan eMMC; ballout di sekitar prosesor sangat cocok dengan ballout eMMC, jadi tinggal menyelaraskan chip dan menggambar jalurnya. Seandainya autorouter tahu cukup dengan mempertahankan data bus di layer paling atas, pekerjaan 10 menit itu akan selesai dalam beberapa detik
Ada masalah kriteria keberhasilan yang dialami proyek-proyek autorouter. Tampaknya mereka menganggap harus bisa menangani semua hal di board agar bisa disebut “selesai”, tetapi sebagai electrical engineer praktis, bukan itu yang saya inginkan. Saya ingin autorouter yang bekerja bersama saya pada potongan-potongan kecil desain satu per satu, memberi waktu untuk meninjau, lalu lanjut ke potongan berikutnya
Jika constraint hingga lintas layer juga bisa diberikan, itu akan sangat kuat. Misalnya, “pertahankan semua net bernama D0-7 di layer 1 dan 3, cocokkan panjangnya agar saling berada dalam 5mm, dan jadikan D0 sebagai acuan panjang.” Jika ini bisa dilakukan, berarti length tuning DRAM sudah terpecahkan, dan desain dengan kompleksitas yang jauh lebih luas menjadi mungkin bahkan bagi pengguna umum
Kalau ada waktu, saya ingin menunjukkan demo tentang apa maksudnya
Pada poin 8, terlalu cepat menyingkirkan metode Monte Carlo adalah kesalahan besar
Inti Monte Carlo adalah kita bisa menukar akurasi dengan kecepatan. Semakin lama algoritme dijalankan, semakin akurat hasilnya
Yang lebih menarik, kebalikannya juga sering bisa dimanfaatkan. Kita bisa memperoleh hasil yang sangat tidak akurat dengan sangat cepat. Alih-alih menelusuri semua rute, misalnya hanya menelusuri satu rute yang dipilih secara acak
Pendekatan ini bersinar saat dimasukkan ke loop bersarang paling dalam dari algoritme. Misalnya, untuk melatih jaringan saraf yang belajar autorouting, loop luar memperbarui parameter jaringan saraf, sedangkan loop dalam menghitung rute yang melewati graf
Dengan Monte Carlo, jika tidak ada bias, loop dalam yang mengendalikan akurasi ini bisa dikurangi menjadi satu iterasi. Varians akan membesar sehingga loop luar melambat, tetapi machine learning “secara teori” tetap bisa belajar
Karena itu, kita bisa membuat kebijakan yang secara intuitif memilih keputusan yang benar, seperti dalam catur atau Go. Dalam varian pencarian pohon Monte Carlo seperti AlphaGo Zero, AlphaChess Zero, dan AlphaRouter Zero, bahkan tanpa bagian pencarian, cache raksasa yang dikodekan dalam parameter jaringan saraf dapat, setelah dilatih, menghitung rute estimasi terbaik dalam satu kali lintasan jaringan saraf, yaitu dalam waktu konstan. Konstanta ini dapat dengan mudah ditukar antara memori dan kecepatan dengan menambah parameter atau melatih lebih lama
MC adalah algoritme yang memberi pijakan pada realitas. Memang lambat, tetapi hampir selalu sangat sederhana untuk diimplementasikan, dan bisa diandalkan untuk mengecek ulang dengan keyakinan sangat tinggi bahwa kita tidak melenceng ke tempat yang benar-benar keliru
Ini pembahasan yang sangat bagus tentang autorouting, tetapi agak menyakitkan ketika di bagian akhir ditutup dengan “bagian kunci yang memungkinkan vibe-building produk elektronik”
Routing itu sendiri mudah. Yang membuatnya rumit adalah saat kita harus membongkar sesuatu yang sudah terpasang untuk memasukkan jalur baru, lalu ledakan kombinatorial menerjang
Saya rindu autorouter yang dulu ada di KiCad. Fitur itu dihapus karena alasan hak kekayaan intelektual yang agak samar, karena pembuatnya pernah bekerja di perusahaan autorouting. Kepada pengguna yang meminta agar fitur itu dimasukkan kembali, ada respons semacam “lelaki sejati tidak memakai autorouter”
https://forum.kicad.info/t/autorouting-and-autoplacement/185...
Saya berharap autorouter ini dan alat-alat lain yang menyusul dapat memungkinkan orang merilis produk elektronik pertama mereka tanpa banyak peta jalan atau pendidikan formal
Tentu saja autorouter yang baik juga harus berguna bagi para ahli, jadi saya berharap bagian itu juga terbantu
Namun sebagai salah satu orang lama yang rewel dan tidak terlalu ingin melihat KiCad mencurahkan tenaga pada autorouter, autorouting PCB selalu menjadi sumber masalah dan tidak bekerja dengan benar
Alasannya bisa dilihat dari autorouter VLSI. Autorouter VLSI juga dulu bermasalah dan tidak bekerja dengan benar. Lalu VLSI memiliki sangat banyak layer, sampai bisa mengalokasikan layer terpisah untuk routing vertikal, layer untuk routing horizontal, layer untuk daya, dan masih punya beberapa layer tambahan untuk koneksi vertikal global, koneksi horizontal global, serta daya global
Masalah mendasar autorouting PCB adalah PCB punya jauh lebih banyak rintangan dibanding chip VLSI. Pertama, komponen itu sendiri adalah rintangan sekaligus bottleneck. Kedua, via PCB hampir selalu memblokir semua layer papan, sedangkan via VLSI hanya memblokir dua layer yang dihubungkannya. Ketiga, via PCB biasanya lebih besar daripada lebar logam routing. Keempat, jumlah layer yang dipakai pada PCB jauh lebih sedikit daripada VLSI. Yang umum adalah 4 layer, dan dari situ yang benar-benar dipakai untuk routing umum hanya 2; karena biaya, 2 layer juga banyak dipakai dan lebih sulit diautoroute, sementara 6 layer sangat sedikit
Akibatnya, autorouting PCB adalah pekerjaan yang jauh lebih kompleks daripada autorouting VLSI
Bagus bahwa tulisan tersebut secara khusus menekankan pentingnya visualisasi dan efek cache
Namun ada beberapa hal yang mengganjal. Pernyataan bahwa “algoritma rekursif adalah pencarian depth-first, sedangkan loop yang menelusuri kandidat atau tetangga tanpa mengurutkannya adalah pencarian breadth-first” tampaknya keliru atau kehilangan intuisi. DFS dan BFS sama-sama bisa ditulis dengan loop maupun rekursi; perbedaan sebenarnya adalah apakah kandidat berikutnya diambil dari bagian atas atau bawah stack, yakni apakah memakai stack (FILO) atau queue (FIFO)
Pernyataan bahwa A* adalah fondasi terbaik untuk semua pencarian berbasis informasi juga perlu konteks. A* berguna untuk pencarian jalur ketika ada konsep “jarak” yang mudah dihitung menuju tujuan dan kueri pada graf yang sama hanya dijalankan beberapa kali. Jika berencana menjalankan banyak kueri pada graf yang hampir statis seperti jaringan jalan, algoritma prapemrosesan seperti contraction hierarchy bisa lebih baik. Jika masalahnya berupa optimisasi tanpa tujuan yang sudah ditentukan, seperti traveling salesman problem, heuristik pencarian lokal lain seperti 2-opt bisa lebih baik
“BFS menelusuri semua node yang bersebelahan, sedangkan A* memprioritaskan node yang lebih dekat ke tujuan” memang salah satu perbedaan, tetapi perbedaan yang lebih besar adalah bahwa A* adalah algoritma dinamis. Karena itu ia bisa berhenti lebih awal saat yakin telah menemukan jalur terpendek. BFS bisa saja belum yakin sampai menelusuri seluruh graf, dan grafnya bisa sangat besar
Di sebagian besar bahasa, cara itu lebih mudah diekspresikan daripada membayangkan stack eksternal. Jadi ketika melihat rekursi dalam kode nyata, kemungkinan besar itu lebih dekat ke DFS, tetapi itu bukan aturan yang ketat
BFS memakai queue FIFO, DFS memakai stack LIFO, dan A* biasanya memakai priority queue yang diimplementasikan dengan heap
Itu salah satu invariant dasar yang membuat BFS menghasilkan jawaban yang benar, sehingga ia bisa berhenti lebih awal setelah semua tujuan tercapai
Perbedaan antara A* dan BFS adalah BFS mencari jalur terpendek dari satu titik awal ke semua titik dalam graf, bukan hanya jalur terpendek antara dua titik. A* adalah kompromi yang mempercepat kueri individual dengan menjawab pertanyaan yang lebih lemah
Jika struktur masalah memungkinkan, mengganti ribuan pemanggilan A* dengan satu pemanggilan BFS atau Dijkstra saja sudah bisa memberi peningkatan kecepatan besar. Perbedaan penting lainnya adalah BFS hanya bekerja pada graf yang semua panjang edge-nya sama, sedangkan A* mendukung panjang edge yang berbeda-beda. Keduanya tidak bisa saling menggantikan, sama seperti mencari elemen minimum dalam list bukan pengganti mengurutkan list
Pernyataan seperti “quadtree dan semua struktur data tree serbaguna sangat lambat”, “tree bukan representasi yang memuat informasi tentang data”, dan “setiap kali memakai tree, kita memakai algoritma O(log N) yang lebih rumit alih-alih algoritma hash O(~1)” cukup salah arah
Pendekatan hashing baik-baik saja ketika titik-titik tersebar merata dan kueri hanya dilakukan pada area yang dekat dengan partisi tetap yang dipilih. Jika tidak, O(1) itu bisa runtuh menjadi O(n)
Saat distribusi data tidak diketahui, tree adalah representasi yang memuat informasi
Algoritma acak juga mirip. Apa yang akan dilakukan jika ruang pencarian terdiri dari triliunan atau lebih item maupun kemungkinan? Jika tidak ada heuristik juga? Dalam situasi ketika brute force tidak bisa dipakai dan algoritma cerdas pun tidak tersedia, algoritma acak menjadi penyelamat
Mungkin tidak diperlukan untuk aplikasi spesifik ini, tetapi sebaiknya hindari klaim umum yang terlalu mutlak
Lebih seriusnya, algoritma berbasis tree cenderung dilebih-lebihkan, dan orang tampaknya terlalu terpaku pada perilaku Big-O sampai lupa bahwa faktor konstanta tetap sangat penting bahkan pada ratusan ribu elemen. Hal seperti locality data juga sama. Kadang-kadang sekadar menyapu dengan pemindaian sekuensial lebih cepat daripada melakukan pembukuan untuk struktur yang lebih kompleks
Secara keseluruhan, lebih baik membungkus operasi dalam wrapper kecil, membuat implementasi yang mudah terlebih dahulu, lalu menilai berdasarkan pengukuran
Dalam kasus terburuk, kita harus menulis ulang seluruh program agar sesuai dengan struktur lain demi performa yang lebih baik, tetapi berdasarkan pengalaman, ketika menulis ulang file dari awal, biasanya ada cukup banyak peningkatan gratis yang ikut terbawa
Saya masih belum menemukan cara yang memuaskan untuk menyimpan titik 2D atau 3D dan mengueri titik di sekitarnya. kD tree bagus, tetapi saya ingin menambahkan titik seiring proses berjalan, bukan membangun struktur berdasarkan kumpulan yang sudah tetap
Hampir semuanya sejalan dengan heuristic pengembangan game saya. Saya juga paham mengapa JavaScript dipilih
Saat ini saya sedang membuat framework modding game yang bekerja dengan ekspresi-S ala Lisp, dan saya jadi sadar bahwa optimasi untuk mengurangi waktu iterasi kreatif itu yang paling penting
Hal-hal seperti A* dan algoritma Lee semuanya keren. Tidak membuat visualisasi untuk flood fill jenis apa pun rasanya hampir seperti kejahatan. Itu benar-benar membuang terlalu banyak dopamin
Membaca tulisan ini membuat saya penasaran apakah teknik-teknik yang belum saya baca tetapi berada di sekitar pengembangan game juga berguna untuk masalah seperti ini. Saya yakin saya bukan orang pertama yang berpikir router boids akan cukup menarik. Secara lebih serius, signed distance field berbasis jump flooding sepertinya bisa memberi banyak kekuatan
Khususnya bagian tentang spatial hashing sesuai dengan pengalaman saya. Selama hampir 20 tahun, saya jarang melihat struktur tree sepadan dengan waktu yang dihabiskan. Ada satu pengecualian: editor teks bergaya Lovecraft yang saya buat cukup banyak memakai trie untuk pemrosesan reaktif. Itu cara yang baik untuk menjadikan 45.000 kata sebagai mesin status terkompresi untuk pemrosesan event
Dulu saya pernah menulis tentang autorouter pola rekursif; ruang solusinya kecil, jadi relatif mudah diprediksi dengan algoritma machine learning yang ada. Masih ada banyak area menarik yang belum dieksplorasi dalam autorouting
Saya belum tahu tentang jump flooding. Sebagai tambahan untuk orang lain, itu adalah algoritma untuk mengaproksimasi distance field secara paralel dengan cepat. Jelas bisa menarik, terima kasih sudah memberi tahu
Tree juga cocok dengan algoritma rekursif, dan penulis mengatakan ada alasan memilih algoritma iteratif dibanding rekursif, jadi saran-saran ini saling terkait
Secara luas, pembedaan “rekursif” dan “non-rekursif” agak artifisial. Pertanyaan sebenarnya adalah “apakah algoritma yang sudah disusun sebelumnya dengan aturan ketat mengambil alih kontrol alur, atau saya yang mengambilnya”. Jika sangat peduli pada performa, jawabannya seharusnya saya yang mengambil alih; dan ketika status eksekusi diabstraksikan ke dalam stack yang disediakan lingkungan runtime sehingga sulit diubah secara aneh saat runtime, itu mulai menjadi penghalang
Pernyataan “95% fokus harus dipakai untuk mengurangi jumlah iterasi. Jadi bahasa tidak penting” memang ada benarnya, tetapi jika setelah membuat algoritma yang hebat dan berkinerja baik dalam bahasa interpreted/abstrak/lambat yang playful dan ekspresif performa tetap penting, Anda bisa menulis ulang hal yang sama dalam bahasa low-level yang berkinerja baik, lalu menulis assembly spesifik arsitektur bila perlu
Ada alasan mengapa numpy, pandas, OpenCV, TensorFlow tidak ditulis dalam Python murni. Python berperan memberi instruksi pada pekerjaan yang diimplementasikan dengan C++/assembly/CUDA dan sebagainya yang berkinerja tinggi
Betapapun bangganya seseorang karena telah menjelajahi ruang masalah, menemukan algoritma efisien, lalu menuliskannya di blog, jika bersikeras hanya menulisnya dalam Python atau JavaScript murni, sulit untuk menjadi library komputasi numerik yang populer
Tulisan ini memang menarik, tetapi jika insight algoritmik penulis membuat encoder HEVC JavaScript murni turun dari 1 hari per frame menjadi 3 jam, saya rasa sulit untuk menarik kesimpulan yang sama
Saya melihat banyak kata kunci yang saya ingat dari masa kuliah. Saya berharap ada kesempatan memakai algoritma terkenal dan keren
Kenyataannya, saya hanya membuat komponen UI dan REST API untuk menampilkan hasil Elasticsearch. Semua hal menarik terkubur di dalam black box
Dalam pengembangan game ada banyak algoritma yang tidak bisa dihindari, jadi jika ingin membuat algoritma, coba buat sesuatu seperti tower defense; Anda akan banyak berurusan dengan algoritma klasik
Setidaknya, menurut saya gelar ilmu komputer saat ini harus dipecah. Bagian matematika yang keren harus menjadi gelar tersendiri, dan mungkin bisa digabung dengan gelar baru terkait AI. Teori database dan jaringan juga harus menjadi gelar tersendiri, begitu pula assembly low-level. Cara kerja komponen elektronik, gerbang NAND, aljabar Boolean, dan semacamnya lebih tepat dipindahkan ke teknik elektro
Orang yang paling dibutuhkan pasar, yaitu mereka yang bisa memproduksi aplikasi CRUD, jika memang harus dipaksakan membutuhkan pengetahuan akademis, sebaiknya dibuatkan gelar tersendiri atau dipindahkan ke pendidikan vokasi
Pada saat yang sama, gatekeeping dalam syarat rekrutmen juga harus ditangani lewat hukum. Perusahaan seharusnya tidak boleh mensyaratkan gelar yang nyaris tidak berkaitan dengan pekerjaan sebenarnya. Saat ini, anak-anak dibuat membuang beberapa tahun hidup mereka dan menanggung utang puluhan hingga ratusan ribu dolar, semata-mata agar perusahaan lebih mudah menyaring orang
Saya tidak menangani langsung masalah ruang 2D/3D, tetapi pelajaran terbesar adalah nilai visualisasi
Manusia sangat hebat dalam memahami dan menganalisis gambar. Satu hal lagi adalah ide untuk terlebih dahulu memahami bentuk masalah dengan metode probabilistik atau brute force, lalu memilih metode yang lebih baik sesuai dengan itu, bukan hanya berdasarkan pemahaman teoretis murni
Pernyataan “bahasa implementasi tidak penting” mungkin benar di bidang ini, tetapi jika diterapkan pada rekayasa perangkat lunak secara umum, menurut saya asumsi bahwa pilihan bahasa tidak memengaruhi kecepatan dan jumlah iterasi yang dibutuhkan sangat keliru
Jika tahapnya adalah mengendalikan suku eksponensial atau polinomial, perbedaan antara Rust atau assembly hard-coded dengan JavaScript atau VisualBasic bisa menjadi cukup tidak berarti