1. Pendahuluan
Pencarian bisa rumit atau sederhana. Ketika tidak diketahui (atau hanya diketahui sebagian) baik tujuan itu sendiri maupun cara untuk mencapainya, peluang itu penting
Tujuan dari artikel penelitian ini adalah untuk membandingkan metode menemukan target sebagai bergerak (objek kuning), dan tidak bergerak.
Metode-metode ini:
- Pencarian acak (objek merah)
- Pencarian acak dengan memori (objek biru)
- Pencarian acak dengan memori dan hierarki (objek hijau)
- Cari rute pertama (objek ungu)
- Mencari rute pendek (objek cokelat)
Pada Gambar. 1, objek-objek ini ditampilkan. Kode program sepenuhnya diposting di
github
2. Bagian utama
2.1. Kelas P - Pencarian Acak
Konstruktor menginisialisasi atribut dan variabel kelas: jendela utama, warna, koordinat y dan x, penghitung, kamus yang dikunjungi, target, kamus hierarki, kamus tetangga. Metode init_3_dict mengisi tiga kamus. Metode pertunjukan melukis sel dalam warna yang diinginkan. Metode pembaruan memperbarui objek. Metode top_show membuat jendela tingkat atas dan menunjukkan berapa banyak langkah yang diambil untuk target.
class P(): def __init__(self, root, color, node, target, maps, ban): self.root = root self.color = color self.y = node[0] self.x = node[1] P.target = target self.count = 0 self.visit = {} P.hierarchy = {} P.neighbor = {} self.init_3_dict(maps, ban)
Fungsi is_en dideklarasikan dalam metode init_3_dict, yang memeriksa bahwa koordinat tidak dilarang dan tidak melampaui peta.
def init_3_dict(self, maps, ban): def is_en(yx): if yx[0] < 0 or yx[0] > len(maps)-1: return if yx[1] < 0 or yx[1] > len(maps[0])-1: return if yx in ban: return return True
Dalam satu siklus, dalam kamus yang dikunjungi dengan kunci koordinat, tulis nilai awal nol. Dalam kamus hierarki dengan kunci yang sama, tulis nama hierarki koordinat ini. Kemudian kita mengisi kamus tetangga dengan memanggil fungsi is_en.
for y in range(len(maps)): for x in range(len(maps[0])): self.visit[(y,x)] = 0 P.hierarchy[(y,x)] = maps[y][x] n = [] if is_en((y-1,x)): n.append((y-1,x)) if is_en((y+1,x)): n.append((y+1,x)) if is_en((y,x-1)): n.append((y,x-1)) if is_en((y,x+1)): n.append((y,x+1)) P.neighbor[(y,x)] = n
Metode show mengecat sel dengan koordinat y, x dalam warna yang diinginkan.
def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=P.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1)
Metode bergerak memindahkan objek. Dalam variabel y, x kita menulis koordinat tetangga, yang dipilih secara acak dari daftar tetangga. Lalu kami menggambar ulang dengan koordinat baru.
Kami menambah penghitung. Periksa apakah tujuannya tercapai. Jika tujuannya tercapai, maka dalam variabel kelas J.disable kita menulis dengan benar. Kami memanggil metode top_show ().
def move(self): v = [] for i in P.neighbor[(self.y, self.x)]: v.append(i) y,x = random.choice(v) self.show(self.y, self.x, 'white') self.y = y self.x = x self.show(y, x, self.color) self.count +=1 if P.target == P.hierarchy[(self.y, self.x)]: J.disable = True self.top_show()
Metode pembaruan panggilan bergerak dan memperbarui setiap setengah detik.
def update(self): self.move() self.root.after(500, self.update)
Metode top_show menampilkan hasilnya.
def top_show(self): top = Toplevel() lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop()
2.2. Kelas M - Pencarian Memori Acak
Konstruktor memanggil konstruktor dari kelas induk dan meningkatkan nilai sel bidang ke mana kita akan pergi. Metode bergerak memindahkan objek. Metode pilihan mengembalikan koordinat yang dipilih oleh algoritma pencarian acak dengan memori.
Dalam metode pindah, panggil metode pilihan. Kalau tidak, karyanya mirip dengan metode orang tua.
def move(self): yx = self.choice((self.y, self.x))
Metode pilihan iterates atas koordinat tetangga dan menambahkan tupel ke daftar v. Elemen pertama dari tuple akan menjadi koordinat tetangga, yang kedua - berapa kali telah dikunjungi. Lalu kami memilah dari kecil ke besar. Kami memilah-milah semua tupel dan dalam daftar v kami hanya menyisakan yang terjadi sebanyak yang dicatat dalam tupel pertama. Pilih salah satu dari mereka secara acak.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.3. Kelas N - pencarian acak dengan memori dan hierarki.
Metode pilihan memilih tupel yang paling cocok dengan nama hierarkis target. Jika kecocokan ini sama, maka koordinat yang paling sedikit dikunjungi dipilih.
Konstruktor memanggil konstruktor dari induk dan menginisialisasi atribut kebetulan jumlah karakter yang cocok dengan nama hierarkis dengan target.
def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0
Metode pilihan dalam loop menulis nama hirarkis dari koordinat tetangga saat ini. Variabel r menyimpan jumlah kecocokan variabel ini dengan target. Jika jumlah kecocokan r lebih besar, maka kebetulan ditimpa. Dalam hal ini, tupel (koordinat, jumlah kunjungan) dari daftar v ditulis ke daftar d. Jika r sama dengan kebetulan, maka di d kita tambahkan tuple dari v.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) d = [] for l in v: c = P.hierarchy[l[0]] r = 0 for i in range(len(P.target)): if c[i] == P.target[i]: r +=1 else: break if r > self.coincidence: self.coincidence = r d = [l] if r == self.coincidence: d.append(l) if d: v = d v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.4. Kelas K - mencari rute dan mencari rute terpendek.
Konstruktor menulis koordinat akhir ke variabel akhir. Jika parameter pendeknya False, maka kami memanggil pencarian rute. Kalau tidak, kami menemukan rute terpendek.
Metode find_path menambahkan koordinat saat ini ke rute. Jika tujuan tercapai, maka kembalikan rute. Kami memilah-milah semua tetangga. Jika tidak ada tetangga di jalan, maka sebutlah diri kita secara rekursif. Dan fakta bahwa metode pengembalian ditulis ke newpath. Rute pertama yang ditemukan adalah newpath. Perbedaan antara metode find_short_path adalah bahwa jika panjang newpath lebih besar dari atau sama dengan panjang terpendek, maka terpendek ditimpa.
def find_path(self, node, end, path=[]): path = path + [node] if node == end: return path for v in P.neighbor[node]: if v not in path: newpath = self.find_path(v, end, path) if newpath: return newpath
2.5. Kelas J adalah target yang bergerak.
Objek kelas J bergerak seperti kelas P. Jika variabel kelas J.disable benar, maka objek berhenti.
2.6. Fungsi utama.
Buat jendela utama. Dalam variabel target, tulis nama hierarki target. Daftar larangan berisi koordinat sel terlarang. Dalam daftar peta, peta itu sendiri. Dalam lingkaran kita menggambar peta. Buat objek kelas. Kemudian kita memanggil fungsi pembaruan, yang memperbarui objek.
3. Kesimpulan
Lima percobaan dilakukan baik untuk target yang bergerak maupun yang tidak bergerak.
Tabel 1 menunjukkan bahwa algoritma terbaik adalah rute terpendek. Yang paling efektif kedua adalah pencarian acak dengan memori dan hierarki. Yang terburuk adalah pencarian acak.
Tabel 1. Target tetap
Dalam hal target bergerak, hasilnya berbeda. Algoritma terburuk adalah yang awalnya menghitung rute ke tujuan. Dalam tabel 2, tanda hubung menunjukkan bahwa tujuan belum tercapai. Brown ternyata lebih buruk dari Violet. Lebih buruk, karena Violet memiliki lintasan yang lebih panjang (kesempatan untuk memenuhi target bergerak lebih besar). Algoritma terbaik saat mencari target bergerak adalah pencarian acak dengan memori dan hierarki. Di tempat kedua adalah pencarian acak dengan memori.
Tabel 2. Target Bergerak
Jika tidak diketahui apakah target bergerak atau tidak, maka lebih baik menggunakan algoritma pencarian acak dengan memori dan hierarki atau hanya pencarian acak dengan memori.
4. Kesimpulan
Keacakan penting jika pencarian target terjadi di tengah ketidakpastian. Pencarian berkurang jika data disajikan secara hierarkis. Memori, tentu saja, juga berharga.