Saya mencoba untuk menentukan algoritma efisien waktu terbaik untuk menyelesaikan tugas yang dijelaskan di bawah ini.
Saya memiliki satu set catatan. Untuk kumpulan rekaman ini saya memiliki data koneksi yang menunjukkan bagaimana pasangan rekaman dari kumpulan ini terhubung satu sama lain. Ini pada dasarnya mewakili grafik yang tidak diarahkan, dengan catatan menjadi simpul dan data koneksi sebagai tepinya.
Semua catatan dalam set memiliki informasi koneksi (yaitu tidak ada catatan yatim piatu yang ada; setiap catatan dalam set terhubung ke satu atau lebih catatan lain dalam set).
Saya ingin memilih dua rekaman dari set dan dapat menunjukkan semua jalur sederhana antara rekaman yang dipilih. Yang saya maksud dengan "jalur sederhana" adalah jalur yang tidak memiliki rekaman berulang dalam jalur (yaitu jalur terbatas saja).
Catatan: Dua record yang dipilih akan selalu berbeda (yaitu simpul awal dan akhir tidak akan pernah sama; tidak ada siklus).
Sebagai contoh:
Jika saya memiliki catatan berikut: A, B, C, D, E dan yang berikut ini mewakili koneksi: (A, B), (A, C), (B, A), (B, D), (B, E), (B, F), (C, A), (C, E), (C, F), (D, B), (E, C), (E, F), (F, B), (F, C), (F, E) [di mana (A, B) berarti record A terhubung ke record B]
Jika saya memilih B sebagai rekaman awal saya dan E sebagai rekaman akhir saya, saya ingin menemukan semua jalur sederhana melalui koneksi rekaman yang akan menghubungkan rekaman B ke rekaman E.
Semua jalur yang menghubungkan B ke E: B-> E B-> F-> E B-> F-> C-> E B-> A-> C-> E B-> A-> C-> F-> E
Ini adalah contoh, dalam praktiknya saya mungkin memiliki set yang berisi ratusan ribu rekaman.
sumber
Jawaban:
Tampaknya hal ini dapat dilakukan dengan penelusuran grafik yang paling dalam. Pencarian kedalaman-pertama akan menemukan semua jalur non-siklus antara dua node. Algoritme ini harus sangat cepat dan berskala ke grafik besar (Struktur data grafik jarang sehingga hanya menggunakan memori sebanyak yang diperlukan).
Saya perhatikan bahwa grafik yang Anda tentukan di atas hanya memiliki satu sisi yang terarah (B, E). Apakah ini salah ketik atau benar-benar grafik berarah? Solusi ini berhasil. Maaf saya tidak bisa melakukannya di C, saya agak lemah di daerah itu. Saya berharap Anda dapat menerjemahkan kode Java ini tanpa terlalu banyak masalah.
Graph.java:
Search.java:
Keluaran Program:
sumber
Kamus Algoritme dan Struktur Data National Institute of Standards and Technology (NIST) online mencantumkan masalah ini sebagai " semua jalur sederhana" dan merekomendasikan penelusuran mendalam-pertama . CLRS memasok algoritme yang relevan.
Teknik pintar menggunakan Petri Nets ditemukan di sini
sumber
Ini adalah pseudocode yang saya buat. Ini bukan dialek pseudocode tertentu, tetapi harus cukup sederhana untuk diikuti.
Ada yang ingin memisahkan ini.
[p] adalah daftar simpul yang mewakili jalur saat ini.
[x] adalah daftar jalur yang memenuhi kriteria
[s] adalah puncak sumber
[d] adalah puncak tujuan
[c] adalah simpul saat ini (argumen ke rutin PathFind)
Asumsikan ada cara yang efisien untuk mencari simpul yang berdekatan (baris 6).
sumber
Karena implementasi DFS non-rekursif yang ada yang diberikan dalam jawaban ini tampaknya rusak, izinkan saya memberikan yang benar-benar berfungsi.
Saya telah menulis ini dengan Python, karena saya merasa cukup mudah dibaca dan tidak berantakan oleh detail implementasi (dan karena memiliki
yield
kata kunci yang berguna untuk mengimplementasikan generator ), tetapi seharusnya cukup mudah untuk di-port ke bahasa lain.Kode ini mempertahankan dua tumpukan paralel: satu berisi node sebelumnya di jalur saat ini, dan satu lagi berisi indeks tetangga saat ini untuk setiap node dalam tumpukan node (sehingga kita dapat melanjutkan iterasi melalui tetangga node saat kita memunculkannya kembali tumpukan). Saya bisa saja menggunakan satu tumpukan (node, indeks) pasangan dengan sama baiknya, tetapi saya pikir metode dua tumpukan akan lebih mudah dibaca, dan mungkin lebih mudah diimplementasikan untuk pengguna bahasa lain.
Kode ini juga menggunakan
visited
set terpisah , yang selalu berisi node saat ini dan node apa pun di stack, agar saya dapat memeriksa secara efisien apakah node sudah menjadi bagian dari jalur saat ini. Jika bahasa Anda kebetulan memiliki struktur data "kumpulan berurutan" yang menyediakan operasi push / pop mirip tumpukan yang efisien dan kueri keanggotaan yang efisien, Anda dapat menggunakannya untuk tumpukan node dan membuangvisited
kumpulan terpisah .Alternatifnya, jika Anda menggunakan kelas / struktur kustom yang bisa berubah untuk node Anda, Anda bisa menyimpan bendera boolean di setiap node untuk menunjukkan apakah itu telah dikunjungi sebagai bagian dari jalur pencarian saat ini. Tentu saja, metode ini tidak akan membiarkan Anda menjalankan dua pencarian pada grafik yang sama secara paralel, jika Anda karena suatu alasan ingin melakukannya.
Berikut beberapa kode uji yang menunjukkan cara kerja fungsi yang diberikan di atas:
Menjalankan kode ini pada grafik contoh yang diberikan menghasilkan keluaran sebagai berikut:
Perhatikan bahwa, meskipun grafik contoh ini tidak diarahkan (semua tepinya mengarah ke dua arah), algoritme juga berfungsi untuk grafik berarah sembarang. Misalnya, menghapus
C -> B
tepi (dengan menghapusB
dari daftar tetanggaC
) menghasilkan keluaran yang sama kecuali untuk jalur ketiga (A -> C -> B -> D
), yang tidak lagi memungkinkan.Ps. Sangat mudah untuk membuat grafik dimana algoritma pencarian sederhana seperti ini (dan algoritma lainnya yang diberikan dalam utas ini) berkinerja sangat buruk.
Misalnya, pertimbangkan tugas untuk menemukan semua jalur dari A ke B pada grafik yang tidak diarahkan di mana node awal A memiliki dua tetangga: node target B (yang tidak memiliki tetangga selain A) dan node C yang merupakan bagian dari sebuah klik dari n +1 node, seperti ini:
Sangat mudah untuk melihat bahwa satu-satunya jalur antara A dan B adalah jalur langsung, tetapi DFS naif yang dimulai dari node A akan membuang waktu O ( n !) Dengan sia-sia untuk menjelajahi jalur dalam klik, meskipun jelas (bagi manusia) bahwa tak satu pun dari jalur itu yang mungkin mengarah ke B.
Seseorang juga dapat membangun DAG dengan properti serupa, misalnya dengan memiliki simpul awal A menghubungkan simpul target B dan ke dua simpul lain C 1 dan C 2 , keduanya terhubung ke simpul D 1 dan D 2 , keduanya terhubung ke E 1 dan E 2 , dan seterusnya. Untuk n lapisan node yang diatur seperti ini, pencarian naif untuk semua jalur dari A ke B akan menghabiskan O (2 n ) untuk memeriksa semua kemungkinan jalan buntu sebelum menyerah.
Tentu saja, menambahkan tepi ke node target B dari salah satu node dalam klik (selain C), atau dari lapisan terakhir DAG, akan membuat sejumlah besar kemungkinan jalur secara eksponensial dari A ke B, dan Algoritma pencarian lokal murni tidak dapat benar-benar memberi tahu sebelumnya apakah ia akan menemukan keunggulan seperti itu atau tidak. Jadi, dalam arti tertentu, sensitivitas keluaran yang buruk dari penelusuran naif tersebut disebabkan oleh kurangnya kesadaran mereka tentang struktur global grafik.
Meskipun ada berbagai metode preprocessing (seperti menghilangkan node daun secara berulang, mencari pemisah simpul simpul tunggal, dll.) Yang dapat digunakan untuk menghindari beberapa "jalan buntu waktu eksponensial" ini, saya tidak tahu ada yang umum trik preprocessing yang bisa menghilangkannya dalam semua kasus. Solusi umum adalah memeriksa di setiap langkah pencarian apakah node target masih dapat dijangkau (menggunakan sub-pencarian), dan mundur lebih awal jika tidak - tapi sayangnya, itu akan sangat memperlambat pencarian (paling buruk , sebanding dengan ukuran grafik) untuk banyak grafik yang tidak mengandung jalan buntu patologis tersebut.
sumber
for path in find_simple_paths(graph, "A", "D"): print(" -> ".join(path))
,print
tanda kurung tidak ada.Ini adalah versi rekursif yang secara logis terlihat lebih baik dibandingkan dengan lantai dua.
Keluaran Program
sumber
Solusi dalam kode C. Ini didasarkan pada DFS yang menggunakan memori minimum.
sumber
Ini mungkin terlambat, tapi berikut adalah versi C # algoritma DFS yang sama di Java dari Casey untuk melintasi semua jalur antara dua node menggunakan tumpukan. Keterbacaan lebih baik dengan rekursif seperti biasa.
sumber
neighbours.Reverse()
? Apakah ituList<T>.Reverse
?Saya telah memecahkan masalah yang mirip dengan ini baru-baru ini, alih-alih semua solusi, saya hanya tertarik pada yang terpendek.
Saya menggunakan pencarian berulang 'luas pertama' yang menggunakan antrian status 'yang masing-masing memegang catatan yang berisi titik saat ini pada grafik dan jalur yang diambil untuk sampai ke sana.
Anda mulai dengan satu catatan dalam antrian, yang memiliki simpul awal dan jalur kosong.
Setiap iterasi melalui kode mengambil item dari kepala daftar, dan memeriksa untuk melihat apakah itu solusinya (node tiba di adalah yang Anda inginkan, jika ya, kita selesai), jika tidak, itu membangun yang baru antrian item dengan node yang terhubung ke node saat ini, dan jalur yang diubah yang didasarkan pada jalur node sebelumnya, dengan lompatan baru terpasang di bagian akhir.
Sekarang, Anda dapat menggunakan sesuatu yang serupa, tetapi ketika Anda menemukan solusi, alih-alih berhenti, tambahkan solusi itu ke 'daftar yang ditemukan' dan lanjutkan.
Anda perlu melacak daftar node yang dikunjungi, sehingga Anda tidak pernah mundur pada diri Anda sendiri, jika tidak, Anda memiliki loop tak terbatas.
jika Anda ingin sedikit lebih pseudocode posting komentar atau sesuatu, dan saya akan menjelaskan.
sumber
Saya pikir Anda harus menjelaskan masalah Anda yang sebenarnya di balik ini. Saya mengatakan ini karena Anda meminta sesuatu yang efisien waktu, namun jawaban yang ditetapkan untuk masalah tersebut tampaknya tumbuh secara eksponensial!
Oleh karena itu saya tidak akan mengharapkan algoritma yang lebih baik daripada sesuatu yang eksponensial.
Saya akan melakukan backtracking dan menelusuri seluruh grafik. Untuk menghindari siklus, simpan semua node yang dikunjungi di sepanjang jalan. Saat Anda kembali, hapus tanda pada node.
Menggunakan rekursi:
Atau apakah itu salah?
edit: Oh, dan saya lupa: Anda harus menghilangkan panggilan rekursif dengan memanfaatkan tumpukan node itu
sumber
Prinsip dasarnya adalah Anda tidak perlu khawatir tentang grafik. Ini adalah masalah standar yang dikenal sebagai masalah konektivitas dinamis. Ada jenis metode berikut dari mana Anda dapat mencapai node terhubung atau tidak:
Berikut adalah Kode C yang saya coba dengan kompleksitas waktu minimum O (log * n) Itu berarti untuk 65536 daftar edge, membutuhkan 4 pencarian dan untuk 2 ^ 65536, membutuhkan 5 pencarian. Saya membagikan implementasi saya dari algoritme: Kursus Algoritma dari universitas Princeton
TIP: Anda dapat menemukan solusi Java dari tautan yang dibagikan di atas dengan penjelasan yang tepat.
sumber
find_paths [s, t, d, k]
Pertanyaan ini sudah tua dan sudah terjawab. Namun, tidak ada yang mungkin menunjukkan algoritme yang lebih fleksibel untuk mencapai hal yang sama. Jadi saya akan melempar topi saya ke dalam ring.
Saya pribadi menemukan algoritme dalam bentuk yang
find_paths[s, t, d, k]
berguna, di mana:Menggunakan bentuk infinity untuk
d
dank
akan memberi Anda semua path§.§ jelas jika Anda menggunakan grafik terarah dan Anda ingin semua jalur tidak terarah di antaranya
s
dant
Anda harus menjalankan ini dengan dua cara:Fungsi Pembantu
Saya pribadi suka rekursi, meskipun kadang-kadang bisa sulit, pertama-tama mari kita tentukan fungsi pembantu kita:
Fungsi utama
Dengan itu, fungsi intinya sepele:
Pertama, mari perhatikan beberapa hal:
[]
adalah daftar yang tidak diinisialisasi, ganti ini dengan yang setara untuk bahasa pemrograman pilihan Andapaths_found
dilewati referensi . Jelas bahwa fungsi rekursi tidak mengembalikan apa pun. Tangani ini dengan benar.graph
mengasumsikan beberapa bentukhashed
struktur. Ada banyak cara untuk mengimplementasikan grafik. Either way,graph[vertex]
memberi Anda daftar simpul yang berdekatan di a diarahkan grafik - menyesuaikan sesuai.sumber
Inilah pemikiran di luar kepala saya:
sumber
Sejauh yang saya tahu, solusi yang diberikan oleh Ryan Fox ( 58343 , Christian ( 58444 ), dan diri Anda sendiri ( 58461 ) adalah yang terbaik. Saya tidak percaya bahwa penjelajahan luas pertama membantu dalam kasus ini, karena Anda akan melakukannya tidak mendapatkan semua jalan. misalnya, dengan tepi
(A,B)
,(A,C)
,(B,C)
,(B,D)
dan(C,D)
Anda akan mendapatkan jalanABD
danACD
, tapi tidakABCD
.sumber
Saya menemukan cara untuk menghitung semua jalur termasuk yang tak terbatas yang berisi loop.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Menemukan Jalur & Siklus Atom
Apa yang ingin kami lakukan adalah menemukan semua jalur yang memungkinkan dari titik A ke titik B. Karena ada siklus yang terlibat, Anda tidak bisa hanya melalui dan menghitung semuanya. Sebaliknya, Anda harus menemukan jalur atom yang tidak berulang dan siklus terkecil yang mungkin (Anda tidak ingin siklus Anda berulang).
Definisi pertama yang saya ambil dari jalur atom adalah jalur yang tidak melalui simpul yang sama dua kali. Namun, saya menemukan bahwa tidak mengambil semua kemungkinan. Setelah beberapa refleksi, saya menemukan bahwa node tidak penting, bagaimanapun tepinya! Jadi jalur atom adalah jalur yang tidak melewati sisi yang sama dua kali.
Definisi ini berguna, ini juga berfungsi untuk siklus: siklus atom titik A adalah jalur atom yang bergerak dari titik A dan berakhir ke titik A.
Penerapan
Untuk mendapatkan semua jalur mulai dari titik A, kita akan melintasi grafik secara rekursif dari titik A. Saat melalui anak, kita akan membuat tautan anak -> induk untuk mengetahui semua sisi yang kita miliki. sudah menyeberang. Sebelum kita pergi ke anak itu, kita harus melintasi daftar tertaut itu dan memastikan tepi yang ditentukan belum dilalui.
Saat kita sampai di titik tujuan, kita bisa menyimpan jalur yang kita temukan.
Terjadi masalah saat Anda ingin membebaskan daftar tertaut. Ini pada dasarnya adalah pohon yang dirantai dalam urutan terbalik. Solusinya adalah dengan menautkan ganda daftar itu dan ketika semua jalur atom telah ditemukan, bebaskan pohon dari titik awal.
Tetapi solusi cerdas adalah dengan menggunakan referensi penghitungan (terinspirasi dari Pengumpulan Sampah). Setiap kali Anda menambahkan tautan ke induk, Anda menambahkan satu ke hitungan referensinya. Kemudian, ketika Anda tiba di ujung jalan, Anda mundur dan bebas sementara jumlah referensi sama dengan 1. Jika lebih tinggi, Anda cukup menghapus satu dan berhenti.
Mencari siklus atom A sama dengan mencari jalur atom dari A ke A. Namun ada beberapa optimasi yang bisa kita lakukan. Pertama, ketika kita tiba di titik tujuan, kita ingin menyimpan jalur hanya jika jumlah biaya sisi negatif: kita hanya ingin melalui siklus penyerapan.
Seperti yang Anda lihat sebelumnya, seluruh grafik sedang dilintasi saat mencari jalur atom. Sebagai gantinya, kita dapat membatasi area pencarian ke komponen yang sangat terhubung yang mengandung A. Menemukan komponen-komponen ini memerlukan lintasan grafik yang sederhana dengan algoritma Tarjan.
Menggabungkan Jalur dan Siklus Atom
Pada titik ini, kita memiliki semua jalur atom yang bergerak dari A ke B dan semua siklus atom dari setiap node, diserahkan kepada kita untuk mengatur semuanya untuk mendapatkan jalur terpendek. Mulai sekarang kita akan mempelajari bagaimana menemukan kombinasi terbaik dari siklus atom di jalur atom.
sumber
Seperti yang dijelaskan dengan cakap oleh beberapa poster lain, masalah singkatnya adalah penggunaan algoritma pencarian kedalaman pertama untuk secara rekursif mencari grafik untuk semua kombinasi jalur antara node akhir yang berkomunikasi.
Algoritme itu sendiri dimulai dengan simpul awal yang Anda berikan, memeriksa semua tautan keluarnya dan berkembang dengan memperluas simpul anak pertama dari pohon pencarian yang muncul, mencari secara progresif lebih dalam dan lebih dalam sampai simpul target ditemukan, atau sampai ia menemukan sebuah simpul yang tidak memiliki anak.
Pencarian kemudian menelusuri kembali, kembali ke simpul terbaru yang belum selesai dijelajahi.
Saya membuat blog tentang topik ini baru-baru ini, memposting contoh implementasi C ++ dalam prosesnya.
sumber
Menambah jawaban Casey Watson, berikut adalah implementasi Java lainnya. Memulai node yang dikunjungi dengan node awal.
sumber