Resolvendo labirinto sem capacidade de retorno

Preciso escrever um programa que resolva o labirinto. O labirinto possui uma estrutura gráfica, onde cada nó - alguma sala e arestas - sai para outras salas:

Especificação:

• Começamos a partir de uma sala aleatória.
• O labirinto tem becos sem saída, 0 ou poucas saídas.
• Não sabemos nada sobre todo o labirinto, apenas o número da sala atual e a lista de portas.
• Quando entramos em uma nova sala, não sabemos de onde viemos (que porta da sala atual nos leva de volta à sala anterior).
• Podemos reconhecer quando chegamos à saída.
• A cada passo, passamos da sala atual para uma porta disponível a partir dela.
• Se estamos na sala 6, por exemplo, não podemos simplesmente pular para começar. É como um movimento de robô.
• Sabemos exatamente o ID da sala atual. Sabemos a identificação de cada porta na sala atual (não em todo o labirinto).
• Nós controlamos o robô.

Procurei todos os algoritmos conhecidos, mas todos eles exigem pelo menos capacidade adicional de retornar à sala anterior. De acordo com a especificação, não podemos usar algoritmos que busquem o caminho mais curto (na verdade, não preciso do mais curto), porque sabemos apenas sobre a sala atual. Não podemos usar a mão esquerda (direita) seguindo os algoritmos, porque não sabemos a direção das saídas. Provavelmente, a única solução que atende às especificações é escolher a saída aleatória em todas as salas, na esperança de que seja encontrada alguma saída de tempo ...

Alguma sugestão de como resolver esse labirinto de maneira mais inteligente?

Hmm, você sabe o número da sala real. Então você pode construir uma estrutura de dados. Acho que a lista de saídas não tem os números dos quartos anexados. Mas depois de escolher um aleatoriamente, você sabe pelo menos que existe uma conexão.

Digamos que você esteja na sala 4 e escolha uma das três saídas aleatórias. Agora o sistema informa que você está na sala 6 e tem apenas uma saída restante. Você escolhe isso e volta à sala 4. Nesse ponto, você reuniu algumas informações sobre a estrutura do labirinto. Agora você escolhe outra saída e termina na sala 5. Moe informações sobre a sala 4 (uma saída para 6, uma saída para 5)

Você pode escolher uma saída específica? Eles estão numerados, digamos, se no quarto 4 você escolhe a saída 1, sempre termina em 6? Caso contrário, você pelo menos poderá descobrir sobre possíveis rotas.

Ok, basta ler o seu comentário. Portanto, se as saídas tiverem IDs e estiverem estaticamente vinculadas a uma sala (mesmo que você não saiba qual delas para começar), basta escolher uma nova e lembrar as conexões de saída / sala e lembrar qual saída já foi tentada. Tente saídas não experimentadas até ter pesquisado cada quarto individual.

Dessa forma, é realmente simples. Após algumas etapas, você deve ter uma lista mais ou menos completa de conexões. Somente quando você entra em uma nova sala, você pode (por alguns passos) correr aleatoriamente. Porém, a cada passo, você obtém mais informações e sempre que entra em uma sala visitada anteriormente, pode tomar uma decisão mais inteligente (não testando a sala 6 do beco sem saída novamente, por exemplo, quando encontrar 4, pois ela não possui saídas não testadas).

Editar A idéia é fazer etapas aleatórias primeiro e registrar as informações que você encontra como eu descrevi (a descrição de Dan é mais concisa). Se você se encontrar em uma sala sem saídas desconhecidas, poderá usar qualquer pathfinder conhecido para encontrar o caminho mais curto para uma sala com saídas que você ainda não explorou.

Não tenho 100% de certeza, mas acho que Peter Norvig escreveu sobre um problema semelhante (O labirinto de Wumpus) em seu livro "Inteligência artificial: uma abordagem moderna". Embora, se bem me lembro, tratava-se menos de encontrar caminhos e mais de tomar decisões sobre algumas informações que o sistema poderia obter sobre as salas vizinhas.

Editar:

Não, não é apenas aleatório. Ao acompanhar as saídas já tentadas, você remove redundância desnecessária. Na verdade, você nem precisa escolher aleatoriamente.

Suponha que você comece na sala 4. Informações que você obtém: 3 saídas A, B, C Você sempre escolhe a primeira saída agora não utilizada. Então comece com A. Você termina na sala 6. Agora você se lembra de 4A => 6 (e usado) na sala 6 e obtém a informação 1 saída A. Mais uma vez, você escolhe a primeira não utilizada (e, neste caso, apenas a saída) Voltar na sala por saber 6A => 4 (e não há mais saídas na sala 6) Agora você escolhe a próxima saída B e alcança a sala 5 ...

Mais cedo ou mais tarde, você terá pesquisado todos os quartos dessa maneira. Mas em uma questão sistemática.

A única razão para o que você precisaria encontrar um caminho é quando você se encontra em uma sala onde todas as saídas já foram exploradas. Em seguida, você desejará encontrar um caminho direto para a próxima sala com saídas inexploradas para se adequar à sua pesquisa. Portanto, o truque principal é menos saber qual saída leva a qual sala (embora isso possa ser útil), mas acompanhar as saídas ainda não tentadas.

Dessa forma, por exemplo, você pode evitar correr em círculos o tempo todo, o que seria um risco para uma abordagem puramente aleatória.

No seu exemplo de labirinto, isso provavelmente não importaria muito. Mas em um grande labirinto com muitos cômodos e conexões e, talvez, cômodos circulares organizados, esse sistema garante que você encontre a saída com o menor número possível de tentativas.

(Eu acho que esse é provavelmente o mesmo sistema que o Byte56 criou nos Gamers)

Eu reconheço que você provavelmente entendeu a essência de outras respostas, mas foi uma pergunta divertida e tive vontade de escrever um pouco de código Python. Esta é a minha abordagem orientada a objetos. Recuo define o escopo.

Representação gráfica

O gráfico pode ser facilmente armazenado como uma chave, dicionário de valores em que a chave é o ID da sala e o valor é uma matriz das salas às quais ele leva.

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

Interface do agente

Primeiro, devemos pensar sobre quais informações o agente deve ser capaz de aprender com o ambiente e as operações que ele deve ser capaz de executar. Isso simplificará o pensamento sobre o algoritmo.

Nesse caso, o agente deve ser capaz de consultar o ambiente para identificar o ID da sala em que está, deve conseguir obter uma contagem das portas na sala em que está ( observe que esse não é o ID dos quartos nos quais o portas levam a! ) e ele deve poder passar por uma porta especificando um índice de porta. Qualquer outra coisa que um agente saiba precisa ser descoberta pelo próprio agente.

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

Conhecimento do agente

Quando o agente entra no mapa pela primeira vez, ele sabe apenas a quantidade de portas na sala e a identificação da sala em que está atualmente. Eu precisava criar uma estrutura que armazenasse informações que o agente havia aprendido, como quais portas não haviam sido fechadas. através de, e onde as portas levam a que é passou.

Esta classe representa as informações sobre um quarto individual. Eu escolhi armazenar as portas não visitadas como a sete as portas visitadas como a dictionary, onde a chave é o ID da porta e o valor é o ID da sala que ele leva.

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

Algoritmo do agente

• Cada vez que o agente entra em uma sala, ele procura informações no seu dicionário de conhecimento. Se não houver entradas para esta sala, ela cria uma nova RoomKnowledgee a adiciona ao seu dicionário de conhecimento.

• Ele verifica se a sala atual é a sala de destino e, se sim, retorna.

• Se houver portas nesta sala que não visitamos, passamos pela porta e armazenamos para onde ela leva. Continuamos o ciclo.

• Se não havia portas não visitadas, voltamos atrás pelas salas que visitamos para encontrar uma com portas não visitadas.

A Agentclasse herda da AgentInterfaceclasse.

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)

Funções de suporte

Eu tive que escrever uma função que encontrasse uma chave em um dicionário, devido a um valor, pois ao retornar, sabemos o ID da sala em que estamos tentando chegar, mas não qual porta usar para acessá-la.

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

Teste

Testei todas as combinações de posição inicial / final no mapa fornecido acima. Para cada combinação, imprime os quartos visitados.

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))

Notas

O retorno não é muito eficiente - na pior das hipóteses, poderia passar por todos os cômodos para chegar a um cômodo adjacente, mas o retorno é bastante raro - nos testes acima, ele retrocede apenas três vezes. Evitei colocar manipulação de exceção para manter o código conciso. Quaisquer comentários no meu Python apreciado :)

Essencialmente, você tem um gráfico direcional, onde todas as salas conectadas são conectadas por duas passagens desconhecidas - uma em qualquer direção. Digamos que você comece no nó 1, nas portas Ae Bsaia. Você não sabe o que há além de cada porta, então apenas escolhe a porta A. Você começa a sala 2, que tem portas C, De E. Agora você sabe que a porta Aleva de um cômodo 1para outro 2, mas não sabe como voltar, então escolhe aleatoriamente a porta C. Você volta para o quarto 1! Agora você sabe como chegar entre quartos 1e 2. Continue a explorar pela porta desconhecida mais próxima até encontrar a saída!

Como as salas estão sempre na mesma ordem nas listas de saída, podemos fazer um mapa rápido das salas enquanto procuramos uma saída.

Meu pseudo-código é um pouco Javaish, desculpe, eu tenho usado muito ultimamente.

Unvisited_Rooms é um hashmap contendo um ID da sala e uma lista de índices das salas não mapeadas Ou uma matriz 2D, o que funcionar.

Eu imagino que o algoritmo poderia ser algo como isto:

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)

Você precisará usar um dos localizadores de caminho de nó comuns para as salas PathTo () no "mapa". Espero que isso esteja claro o suficiente para você iniciar alguma coisa.

Não sou muito claro sobre seus requisitos, mas se o seguinte for permitido, pode ser um algoritmo simples de seguir. Provavelmente existe um bug, principalmente porque ele usa uma função recursiva. Além disso, verifica se uma porta leva à sala de onde você veio, mas eu não sei como um caminho circular de três salas lidaria; ele pode continuar girando para sempre nesses três quartos. Pode ser necessário adicionar um histórico para garantir que nenhuma sala seja verificada duas vezes. Mas lendo sua descrição, isso pode não ser permitido.

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

[Editar] Adicionado 'id' à verificação anterior e atualizado para tornar mais orientado a objetos.

A resposta curta é a primeira pesquisa profunda com retorno. Você pode fazer a amplitude primeiro, se preferir, mas o seu pequeno robô fará muito mais caminhadas para lá e para cá.

Mais concretamente, suponha que recebamos:

// 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();

Para encontrar a saída, basta:

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());
  }
}

Ligue escape()com o ID da sala inicial e ele moverá o robô para a saída (ligando moveTo()).