Memecahkan labirin tanpa kemampuan kembali

Saya perlu menulis sebuah program yang akan menyelesaikan masalah labirin. Labirin memiliki struktur grafik, di mana setiap node - beberapa ruang, dan tepi - keluar ke kamar lain:

Spesifikasi:

• Kami mulai dari ruang acak.
• Labirin memiliki jalan buntu, 0 atau beberapa jalan keluar.
• Kami tidak tahu apa-apa tentang semua labirin, hanya jumlah kamar saat ini dan daftar pintu dari sana.
• Ketika kita memasuki kamar baru, kita tidak tahu dari mana kita berasal (pintu apa dari kamar saat ini membawa kita kembali ke kamar sebelumnya).
• Kita bisa mengenali kapan kita mencapai pintu keluar.
• Setiap langkah kami pindah dari kamar saat ini ke beberapa pintu yang tersedia darinya.
• Jika kita berada di kamar 6 misalnya, kita tidak bisa langsung memulai. Ini seperti gerakan robot.
• Kami tahu persis ID kamar saat ini. Kami tahu ID setiap pintu di kamar saat ini (tidak di semua labirin).
• Kami mengendalikan robot.

Saya melihat semua algoritma yang dikenal, tetapi semuanya membutuhkan setidaknya kemampuan tambahan untuk kembali ke ruangan sebelumnya. Menurut spesifikasi kami tidak dapat menggunakan algoritma apa pun yang mencari jalur terpendek (sebenarnya, saya tidak perlu jalur terpendek), karena kami hanya tahu tentang ruang saat ini. Kami tidak dapat menggunakan algoritme yang mengikuti Tangan Kanan (Kanan), karena tidak tahu arah keluar. Mungkin, satu-satunya solusi yang memenuhi spesifikasi adalah memilih keluar acak di setiap kamar dengan harapan bahwa beberapa waktu keluar akan ditemukan ...

Adakah saran bagaimana mengatasi labirin seperti itu dengan cara yang lebih pintar?

Hmm, kamu tahu nomor kamar yang sebenarnya. Jadi Anda bisa membangun struktur data. Saya kira daftar pintu keluar tidak memiliki nomor kamar yang terlampir. Tetapi setelah memilih satu secara acak, Anda tahu setidaknya, bahwa ada koneksi.

Katakanlah Anda berada di kamar 4 dan pilih satu dari tiga pintu keluar acak. Sekarang sistem memberi tahu Anda, Anda berada di kamar 6 dan hanya memiliki satu pintu keluar yang tersisa. Anda memilih itu dan kembali ke kamar 4. Pada titik ini Anda telah mengumpulkan beberapa informasi tentang struktur labirin. Anda sekarang memilih jalan keluar lain dan berakhir di kamar 5. Informasi Moe tentang kamar 4 (satu pintu keluar ke 6, satu pintu keluar ke 5)

Bisakah Anda memilih jalan keluar tertentu? apakah mereka bernomor, katakanlah jika di kamar 4 Anda memilih pintu keluar Anda selalu berakhir dengan 6? Kalau tidak, Anda setidaknya bisa mencari tahu tentang rute yang memungkinkan.

Ok, baca saja komentar Anda. Jadi jika pintu keluar memiliki ID dan mereka secara statis terhubung ke sebuah ruangan (bahkan jika Anda tidak tahu yang mana untuk memulai), Anda hanya memilih yang baru dan ingat koneksi keluar / ruang dan ingat pintu keluar mana yang sudah dicoba. Coba keluar yang belum dicoba sampai Anda telah mencari setiap kamar.

Dengan cara itu sebenarnya sederhana. Setelah beberapa langkah, Anda harus memiliki daftar koneksi yang kurang lebih lengkap. Hanya ketika Anda memasuki ruangan baru Anda dapat (untuk beberapa langkah) berkeliling secara acak. Tetapi dengan setiap langkah Anda mendapatkan info lebih lanjut dan setiap kali Anda memasuki ruangan yang dikunjungi sebelumnya, Anda dapat membuat keputusan yang lebih cerdas (tidak menguji buntu kamar 6 lagi misalnya ketika Anda menemukan kembali ke 4, karena tidak memiliki pintu keluar yang belum diuji).

Sunting Idenya adalah membuat langkah acak terlebih dahulu dan mencatat informasi yang Anda temukan seperti yang saya jelaskan (deskripsi Dan lebih ringkas). Jika Anda menemukan diri Anda di sebuah ruangan tanpa pintu keluar yang tidak diketahui, Anda dapat menggunakan pathfinder yang dikenal untuk menemukan cara terpendek ke sebuah ruangan yang memiliki pintu keluar yang belum Anda jelajahi.

Tidak 100% yakin, tapi saya pikir Peter Norvig menulis tentang masalah yang sama (Labirin Wumpus) dalam bukunya "Kecerdasan Buatan: Pendekatan Modern". Meskipun jika saya ingat benar, itu bukan tentang mencari jalan dan lebih banyak tentang pengambilan keputusan tentang beberapa informasi yang bisa didapat sistem tentang kamar tetangga.

Edit:

Tidak, ini tidak hanya acak. Dengan melacak keluar sudah mencoba Anda menghapus redundansi yang tidak perlu. Sebenarnya Anda bahkan tidak perlu memilih secara acak.

Asumsikan Anda mulai di kamar 4. Info yang Anda dapatkan: 3 pintu keluar A, B, C Anda selalu memilih yang pertama dengan pintu keluar yang sekarang tidak digunakan. Jadi mulailah dengan A. Anda berakhir di kamar 6. Sekarang Anda ingat 4A => 6 (dan digunakan) di kamar 6 Anda mendapatkan info 1 keluar A. Sekali lagi Anda memilih yang pertama tidak digunakan (dan dalam hal ini hanya keluar) Kembali ke kamar untuk mengetahui 6A => 4 (dan tidak ada jalan keluar lebih lanjut di kamar 6) Sekarang Anda memilih pintu keluar B berikutnya dan mencapai kamar 5 ...

Cepat atau lambat Anda akan mencari semua kamar dengan cara itu. Namun dalam masalah yang sistematis.

Satu-satunya alasan untuk apa yang Anda perlukan untuk menemukan jalan adalah, ketika Anda menemukan diri Anda di sebuah ruangan di mana semua pintu keluar sudah dieksplorasi. Maka Anda akan ingin menemukan jalan langsung ke kamar sebelah dengan pintu keluar yang belum dijelajahi untuk pergi sendiri dengan pencarian Anda. Jadi trik utamanya adalah untuk tidak tahu jalan keluar mana yang mengarah ke ruangan mana (meskipun ini mungkin bisa membantu) tetapi untuk melacak jalan keluar yang belum dicoba.

Dengan cara ini misalnya Anda dapat menghindari berjalan dalam lingkaran sepanjang waktu, apa yang akan menjadi risiko untuk pendekatan yang murni acak.

Dalam contoh Anda labirin, ini kemungkinan besar tidak masalah. Tetapi dalam labirin besar dengan banyak kamar dan koneksi dan mungkin kamar yang diatur rumit, sistem ini menjamin bahwa Anda akan menemukan jalan keluar dengan uji coba sesedikit mungkin.

(Saya pikir itu mungkin sistem yang sama dengan Byte56 muncul di Gamer)

Saya menyadari bahwa Anda mungkin mendapatkan inti dari jawaban lain, tapi itu adalah pertanyaan yang menyenangkan dan saya merasa ingin melakukan sedikit pengkodean Python. Ini adalah pendekatan berorientasi objek saya. Lekukan mendefinisikan ruang lingkup.

Representasi Grafik

Grafik dapat dengan mudah disimpan sebagai kunci, kamus nilai di mana kuncinya adalah id kamar, dan nilainya adalah array dari kamar-kamar yang dipimpinnya.

map = {
1:[5, 2],
2:[1, 3, 5],
3:[2, 4],
4:[3, 5, 6],
5:[2, 4, 1],
6:[4]
}

Antarmuka Agen

Pertama-tama kita harus memikirkan informasi apa yang harus dapat dipelajari oleh agen dari lingkungan, dan operasi yang harus dapat dilakukannya. Ini akan mempermudah berpikir tentang algoritma.

Dalam hal ini agen harus dapat menanyakan lingkungan untuk id dari ruangan itu, itu harus bisa mendapatkan hitungan pintu di ruangan itu ( perhatikan ini bukan id dari kamar yang pintu mengarah ke! ) dan dia harus bisa bergerak melalui pintu dengan menentukan indeks pintu. Hal lain yang diketahui agen harus dipecahkan oleh agen itu sendiri.

class AgentInterface(object):
    def __init__(self, map, starting_room):
        self.map = map
        self.current_room = starting_room

    def get_door_count(self):
        return len(self.map[self.current_room])

    def go_through_door(self, door):
        result = self.current_room = self.map[self.current_room][door]
        return result

Pengetahuan Agen

Ketika agen pertama kali memasuki peta itu hanya tahu jumlah pintu di ruangan itu, dan id ruangan itu saat ini. Saya perlu membuat struktur yang akan menyimpan informasi yang telah dipelajari agen tersebut seperti pintu mana yang belum melalui, dan di mana pintu mengarah ke yang telah dilaluinya.

Kelas ini mewakili informasi tentang satu kamar. Saya memilih untuk menyimpan pintu yang belum dikunjungi sebagai setdan pintu yang dikunjungi sebagai dictionary, di mana kuncinya adalah id pintu dan nilainya adalah id ruangan yang dipimpinnya.

class RoomKnowledge(object):
    def __init__(self, unvisited_door_count):
        self.unvisited_doors = set(range(unvisited_door_count))
        self.visited_doors = {}

Algoritma agen

• Setiap kali agen memasuki ruangan, ia mencari kamus pengetahuannya untuk mendapatkan informasi tentang ruangan itu. Jika tidak ada entri untuk ruangan ini maka ia membuat yang baru RoomKnowledgedan menambahkan ini ke kamus pengetahuannya.

• Ia memeriksa untuk melihat apakah ruang saat ini adalah ruang target, jika demikian maka ia kembali.

• Jika ada pintu di ruangan ini yang belum kita kunjungi, kita pergi melalui pintu dan menyimpannya. Kami kemudian melanjutkan loop.

• Jika tidak ada pintu yang belum dikunjungi, kami menelusuri ruangan yang telah kami kunjungi untuk menemukan satu dengan pintu yang belum dikunjungi.

The Agentmewarisi kelas dari AgentInterfacekelas.

class Agent(AgentInterface):

    def find_exit(self, exit_room_id):
        knowledge = { }
        room_history = [] # For display purposes only
        history_stack = [] # Used when we need to backtrack if we've visited all the doors in the room
        while True:
            room_knowledge = knowledge.setdefault(self.current_room, RoomKnowledge(self.get_door_count()))
            room_history.append(self.current_room)

            if self.current_room==exit_room_id:
                return room_history

            if len(room_knowledge.unvisited_doors)==0:
                # I have destination room id. I need door id:
                door = find_key(room_knowledge.visited_doors, history_stack.pop())
                self.go_through_door(door)
            else:   
                history_stack.append(self.current_room)
                # Enter the first unopened door:
                opened_door = room_knowledge.unvisited_doors.pop()
                room_knowledge.visited_doors[opened_door]=self.go_through_door(opened_door)

Fungsi pendukung

Saya harus menulis fungsi yang akan menemukan kunci dalam kamus yang diberi nilai, karena ketika menelusuri kembali kita tahu id ruangan yang sedang kita coba buka, tetapi tidak ke pintu mana yang harus digunakan untuk mendapatkannya.

def find_key(dictionary, value):
    for key in dictionary:
        if dictionary[key]==value:
            return key

Pengujian

Saya menguji semua kombinasi posisi awal / akhir di peta yang diberikan di atas. Untuk setiap kombinasi, akan dicetak ruang yang dikunjungi.

for start in range(1, 7):
    for exit in range(1, 7):
        print("start room: %d target room: %d"%(start,exit))
        james_bond = Agent(map, start)
        print(james_bond.find_exit(exit))

Catatan

Pelacakan mundur tidak terlalu efisien - dalam skenario kasus terburuk dapat melewati setiap ruangan untuk mencapai ruang yang berdekatan, tetapi penelusuran mundur cukup jarang - dalam tes di atas hanya mundur sebanyak tiga kali. Saya telah menghindari menempatkan penanganan pengecualian agar kode tetap ringkas. Setiap komentar tentang Python saya dihargai :)

Pada dasarnya, Anda memiliki grafik arah, di mana setiap kamar terhubung dihubungkan oleh dua bagian yang tidak diketahui - satu di kedua arah. Katakanlah Anda mulai dalam simpul 1, dan pintu Adan Bmemimpin. Anda tidak tahu apa yang ada di balik setiap pintu, jadi Anda hanya memilih pintu A. Anda mendapatkan ke kamar 2, yang memiliki pintu C, Ddan E. Anda sekarang tahu bahwa pintu Amengarah dari kamar 1ke kamar 2, tetapi Anda tidak tahu cara kembali, sehingga Anda memilih pintu secara acak C. Anda kembali ke kamar 1! Sekarang Anda tahu bagaimana untuk mendapatkan antara kamar 1dan 2. Terus jelajahi melalui pintu terdekat yang tidak dikenal sampai Anda menemukan pintu keluar!

Karena kamar selalu dalam urutan yang sama dalam daftar keluar, kita dapat membuat peta cepat kamar sambil mencari jalan keluar.

Kode pseudo saya agak Javaish, maaf, saya sudah sering menggunakannya akhir-akhir ini.

Unvisited_Rooms adalah hashmap yang memegang ID kamar, dan daftar indeks kamar yang belum dipetakan Atau array 2d, apa pun yang berfungsi.

Saya membayangkan algoritme bisa seperti ini:

Unvisited_Rooms.add(currentRoom.ID, currentRoom.exits) //add the starting room exits
while(Unvisited_Rooms.Keys.Count > 0 && currentRoom != end) //keep going while there are unmapped exits and we're not at the end
    Room1 = currentRoom
    ExitID = Room1.get_first_unmapped_Room() //returns the index of the first unmapped room
    if(ExitID == -1) //this room didn't have any more unmapped rooms, it's totally mapped
        PathTo(Get_Next_Room_With_Unmapped_Exits) //we need to go to a room with unmapped exits
        continue //we need to start over once we're there, so we don't create false links
    GoToExit(ExitID) //goes to the room, setting current room to the room on the other side
    Room1.Exits[exitID].connection = currentRoom.ID //maps the connection for later path finding
    Unvisited_Rooms[Room1.ID].remove(exitID) //removes the index so we don't worry about it
    if(Unvisited_Rooms[Room1.ID].size < 1) //checks if all the rooms exits have been accounted for
        Unvisited_Rooms.remove(Room1.ID)  //removes the room if it's exits are all mapped
    Unvisited_Rooms.add(currentRoom.ID, currentRoom.unvisited_exits) //adds more exits to the list

If(currentRoom != end && Unvisited_Rooms.Keys.Count < 1)
   print(No exit found!)
else
   print(exit is roomID: currentRoom.ID)

Anda harus menggunakan salah satu pencari jalur simpul umum untuk ruang PathTo () di "peta" Mudah-mudahan itu cukup jelas untuk membantu Anda memulai sesuatu.

Saya tidak terlalu jelas tentang kebutuhan Anda, tetapi jika hal berikut diizinkan, mungkin sederhana untuk mengikuti algoritma. Mungkin ada bug di sana, terutama karena ia menggunakan fungsi rekursif. Juga, ia memeriksa apakah sebuah pintu mengarah ke ruangan tempat Anda berasal, tetapi saya tidak tahu bagaimana sebuah jalan melingkar tiga kamar akan menangani, mungkin saja terus berputar selamanya di tiga kamar itu. Anda mungkin harus menambahkan riwayat untuk memastikan tidak ada kamar yang diperiksa dua kali. Tetapi dengan membaca deskripsi Anda itu mungkin tidak diizinkan.

solved = FALSE

SearchRoom(rooms[0], rooms[0])    // Start at room 1 (or any room)
IF solved THEN
  // solvable
ELSE
  // unsolvable
ENDIF
END

// Recursive function, should run until it searches every room or finds the exit
FUNCTION SearchRoom: curRoom, prevRoom
  // Is this room the 'exit' room
  IF curRoom.IsExit() THEN
    solved = TRUE
    RETURN
  ENDIF

  // Deadend?  (skip starting room)
  IF (curRoom.id <> prevRoom.id) AND (curRoom.doors <= 1) THEN RETURN

  // Search each room the current room leads to
  FOREACH door IN curRoom
    // Skip the room we just came from
    IF door.id <> prevRoom.id THEN
      SearchRoom(door, curRoom)
    ENDIF
    IF solved THEN EXIT LOOP
  NEXT

  RETURN
ENDFUNCTION

[Sunting] Menambahkan 'id' ke pemeriksaan sebelumnya, dan diperbarui untuk membuat lebih banyak objek berorientasi.

Jawaban singkatnya adalah pencarian mendalam-pertama dengan backtracking. Anda dapat melakukan luasnya terlebih dahulu jika Anda mau, tetapi robot kecil Anda akan melakukan lebih banyak bolak-balik saat itu.

Lebih konkret, anggap kita diberikan:

// Moves to the given room, which must have a door between
// it and the current room.
moveTo(room);

// Returns the list of room ids directly reachable from
// the current room.
getDoors();

// Returns true if this room is the exit.
isExit();

Untuk menemukan pintu keluar, kita hanya perlu:

void escape(int startingRoom) {
  Stack<int> path = new Stack<int>();
  path.push(startingRoom);
  escape(path);
}

boolean escape(Stack<int> path) {
  for (int door : getDoors()) {
    // Stop if we've escaped.
    if (isExit()) return true;

    // Don't walk in circles.
    if (path.contains(door)) continue;

    moveTo(door);
    path.push(door);
    if (escape(path)) return true;

    // If we got here, the door didn't lead to an exit. Backtrack.
    path.pop();
    moveTo(path.peek());
  }
}

Panggil escape()dengan ID dari ruang mulai dan itu akan memindahkan robot ke pintu keluar (dengan memanggil moveTo()).