Problemas

proPROBLEMAS SOBRE HEURÍSTICAS

1.- Un grupo de montañeros decide subir a la cima de una montaña pero al consultar el plano se encuentran con muchas posibilidades (croquis). Para trazar la ruta aseguir anotan las altitudes de los distintos puntos marcados en el croquis. También conocen las distancias entre los distintos puntos del croquis. Desean llegar a la cima caminando lo menos posible.a) Deciden utilizar un algoritmo que les asegure conseguir ese objetivo. ¿Qué algoritmo propones y por qué? b) Definir heurística admisible y heurística monótona. c) La heurística h(n)=Altitud en lacima – Altitud en el nodo n, ¿será admisible? ¿y monótona? Demostrar tu respuesta.

2.- Como es bien conocido, el problema del viajante de comercio consiste en encontrar una ruta mínima que pase porun grupo de ciudades, de manera que cada ciudad se visite una sola vez, salvo la última ciudad que ha de ser la de partida. Considerar este problema, una formulación de espacio de estados que defineel estado como la secuencia de ciudades recorridas, y las siguientes funciones heurísticas: h1: (nº ciudades por visitar) h2: (nº ciudades por visitar) x (distancia mínima entre cada dos ciudades porvisitar incluyendo la última visitada) h3: (nº ciudades por visitar) x (distancia máxima entre cada dos ciudades por visitar incluyendo la última visitada) Sabiendo que la distancia mínima entre dosciudades es superior a la unidad, responder razonadamente a las siguientes cuestiones: a) ¿Son admisibles? (Definir heurística admisible) b) ¿Son monótonas? (Definir heurística monótona) c) ¿Se puedeafirmar que alguna de las funciones esté más informada que otra?

3.- Para el siguiente problema diseñar una heurística admisible (definir heurística admisible) y justificar su admisibilidad. Elproblema involucra los números de dos dígitos de 10 a 99. Hay dos acciones legales: se puede sumar 1 a cualquier dígito excepto 9 y se puede restar 1 de cualquier dígito excepto 0 (por ejemplo, 10 puede...