Efisiensi proses berurutan

Question

Saya tidak yakin apakah ini lebih merupakan pertanyaan pemrograman atau matematika. Harap beri tahu saya forum yang tepat untuk menanyakan hal ini, jika bukan yang ini.

Saya memiliki proses berurutan sebagai berikut:

1. Ada $n$ koin tersebar dalam kotak persegi $100 \times 100$ poin.
2. Ada $m$ agen di lokasi pusat, yaitu titik $(50,50)$.
3. Agen ini dapat melakukan jalan acak di grid, memindahkan satu titik grid dalam satu langkah. Dalam satu langkah, semua agen bergerak satu langkah dari posisi mereka saat ini.
4. Agen seharusnya menemukan koin itu. Setelah agen menemukan koin, langkah waktunya dicatat. Kemudian, agen melanjutkan untuk pindah ke lokasi pusat di sepanjang jalur terpendek dari titik di mana koin ditemukan. Sekali lagi, dalam satu langkah waktu, agen hanya dapat memindahkan satu titik grid, sementara agen lain mungkin masih mencari koin lain.
5. Setelah agen dengan koin mencapai lokasi pusat, koin tersebut ditinggalkan dan agen mulai mencari koin lain lagi.
6. Proses berhenti ketika sejumlah langkah waktu tertentu selesai, terlepas dari apakah semua koin telah ditemukan.

Dalam proses umum, saya memiliki kendali atas distribusi koin, apakah semua agen keluar sekaligus atau pada langkah waktu tertentu, dan apakah mereka dapat berinteraksi satu sama lain untuk mengurangi penjelajahan area yang sama lagi. Akhirnya, saya ingin mengetahui seberapa cepat koin ditemukan oleh agen. Saya mencari cara untuk mengukur efisiensi menemukan koin ini dalam kasus umum$n$ koin dan $m$agen. Artinya, jika saya ingin membandingkan 10 agen yang menemukan 100 koin dengan 5 agen yang menemukan 50 koin, jumlah ini seharusnya dapat memberi tahu saya dalam hal ini agen lebih efisien dalam menemukan koin. Saya dapat memplot persentase koin yang ditemukan dari waktu ke waktu, dan ini biasanya kurva-S, tetapi ketika parameter saya meningkat, saya pikir akan lebih baik jika saya memiliki nilai tunggal untuk dibandingkan daripada garis plot.

Menurut saya, menurut saya tiga parameter yang akan berperan dalam menentukan efisiensi ini adalah jarak koin dari pusat, waktu langkah yang diambil agen untuk menemukan koin mulai dari pusat, dan jumlah total agen. di area mencari koin. Tapi saya tidak yakin apa cara yang baik untuk menghubungkan mereka bersama.

Answer 1

Jawaban Parsial

Kami memiliki grafik kisi $G$ dengan simpul yang teridentifikasi sebagai simpul pusat, $c$.

Membiarkan $$N=V \space \text{\\} \space \{c\},$$ yaitu, $N$ adalah kumpulan node dari $G$ tidak termasuk $c$.

Membiarkan $$S = \{ p_n | p_n \text{is the shortest path between } c, n \in N \}$$

Jika kita membatasi masalah dengan menyebutkan jumlah agen $k$ yang akan diterapkan ditentukan di $t = 0$ dan tetap konstan selama simulasi, kita dapat memilih $$k = |S|$$

Ini menetapkan satu agen ke setiap jalur terpendek $p_n$ dan kami dapat menegaskan bahwa tidak ada perselisihan antara agen yang harus kami modelkan.

Membiarkan $d_{n,0}, d_{n,1}, \dots, d_{n,j}$ menjadi jarak yang diurutkan dari koin dari $c$ untuk jalan $p_n$ yaitu, $d_{n,j} < d_{n,j+1}$.

Pertimbangkan jalannya $(c,x)$ dan $(c,y)$. Kami dapat memiliki dua agen di jalur ini dan mereka dapat mengumpulkan koin di$x, y$masing-masing. Siapa yang mendapat prioritas saat kembali ke$c$? Jawabannya adalah, tidak masalah karena keduanya memiliki jarak yang sama$c$.

Oleh karena itu, kami akan menganggap konvensi tanpa kehilangan keumuman bahwa agen di jalur yang lebih pendek akan memiliki prioritas. Ini membantu kami menyederhanakan perhitungan kami.

Membiarkan $m_n$ menjadi jumlah koin di jalan $p_n$. Membiarkan$c_n$ menjadi jumlah koin yang dikumpulkan di jalan $p_n$.

$c_n$ dibatasi oleh

$$\sum_{k=1}^{m_n} 2d_{n, k} \le t$$

Jumlah total koin yang dikumpulkan diberikan oleh

$$C = \sum_{i=1}^{n} c_i$$

Membiarkan $M$jadilah jumlah agen. Kemudian produktivitas rata-rata agen diberikan oleh

$$C \over M$$

Membiarkan $C_{total}$menjadi jumlah total koin. Efisiensi$(\eta)$ penyebaran dalam hal koin yang dikumpulkan akan

$$\eta = {C \over C_{total} } \times 100 \text{%}$$

Prolog: Ini menjadi sangat rumit jika Anda mengizinkan lebih banyak agen daripada jumlah jalur terpendek ke koin karena Anda kemudian perlu membuat model kapan agen tersebut dapat memasuki lapangan, berapa banyak yang dapat memasuki lapangan dan bagaimana mereka berkoordinasi dengan agen utama di jalur terpendek tanpa menyebabkan perselisihan.

Secara teori, setelah jalur terpendek dibersihkan dari semua koin (ini akan terjadi jika $c_k < t$ untuk apapun $k$), semua jalur yang terhubung dengan edge dapat menggunakannya untuk mengantre agen yang sedang menunggu. Begitu salah satu agen itu melihat koin dari kejauhan$x$ darinya terletak di jalur terpendek yang terhubung $p_m$ dan koin berada pada jarak $d_{n,r}$ dan tidak ada koin lain antara koin itu dan $c$ dan agen utama bergerak menuju $c$, agen yang menunggu dapat bergerak untuk mengambil koin itu.

Pada gambar di atas, $r$ adalah agen yang bergerak menuju $c$dengan koin yang terkumpul. Node biru muda adalah agen yang menunggu. Agen$a$ bisa bergerak untuk mengumpulkan koin $j$ dan ikuti $r$.

Ini akan membantu meningkatkan efisiensi. Kita dapat menggunakan jalur terpendek dari agen yang menunggu ke koin dan mengirimkan agen ke koin itu. Namun, ini menjadi rumit dengan sangat cepat dan saya tidak yakin dengan cara sederhana untuk menghitung jumlah koin yang dikumpulkan.