Inteligencia artificial
Páginas: 2 (460 palabras)
Publicado: 6 de diciembre de 2013
Recorrido por Anchura.
Recorrido desde Vértice por anchura desde vértice D ={D, B, C, H, R, A, T }.
Recorrido por Profundidad.
Grafo Dirigido, por lo tanto necesitamos buscar laruta que incluya más nodos.
En este tipo de grafos se asume en algunos casos que el recorrido esta sujeto a los supuestos de peso y orden alfabético.
El problema del agente viajero
Unvendedor tiene que visitar n + 1 ciudades, cada una exactamente una vez. La distancia entre cada par de ciudades viene dada por dij (en general dij 6= dji). El problema es encontrar el recorrido (tour)que comienza y termina en la misma ciudad y minimiza la distancia total recorrida (¿suena fácil?).
Algunas heurísticas para el PAV:
Las heurísticas a ser discutidas se pueden clasificar en dostipos: Las que construyen recorridos y las que los mejoran. Comenzamos con las primeras.
La idea se puede resumir así:
1. Encontrar un sub-recorrido inicial (basta que tenga dos ciudades pero puede serde más).
2. Seleccionar una ciudad a ser añadida al sub-recorrido, usando alguna regla de selección.
3. Insertar el nodo correspondiente en el sub-recorrido, basándose en un criterio de inserción.4. Si se tiene un recorrido, parar. Caso contrario ir a 2.
Las distintas reglas de selección y criterios de inserción dan lugar a diferentes heurísticas. Veamos una de ellas: La heurística deinserción más barata.
Se comienza con un sub-recorrido T con dos ciudades i1 e i2, tales que
es decir, el sub-recorrido más corto entre dos ciudades. Luego se busca el costo mínimo de inserción en elsub-recorrido:
y se selecciona un nodo k∗ con ese costo. Luego se inserta el nodo entre las ciudades involucradas en el cálculo de ck∗. Finalmente se repite este proceso (con los sub-recorridos quese van generando) hasta construir un recorrido
Ejemplo de la heurística de inserción más barata
Consideremos el PAV dado por la siguiente matriz de distancias:
En primer...
Recorrido por Anchura.
Recorrido desde Vértice por anchura desde vértice D ={D, B, C, H, R, A, T }.
Recorrido por Profundidad.
Grafo Dirigido, por lo tanto necesitamos buscar laruta que incluya más nodos.
En este tipo de grafos se asume en algunos casos que el recorrido esta sujeto a los supuestos de peso y orden alfabético.
El problema del agente viajero
Unvendedor tiene que visitar n + 1 ciudades, cada una exactamente una vez. La distancia entre cada par de ciudades viene dada por dij (en general dij 6= dji). El problema es encontrar el recorrido (tour)que comienza y termina en la misma ciudad y minimiza la distancia total recorrida (¿suena fácil?).
Algunas heurísticas para el PAV:
Las heurísticas a ser discutidas se pueden clasificar en dostipos: Las que construyen recorridos y las que los mejoran. Comenzamos con las primeras.
La idea se puede resumir así:
1. Encontrar un sub-recorrido inicial (basta que tenga dos ciudades pero puede serde más).
2. Seleccionar una ciudad a ser añadida al sub-recorrido, usando alguna regla de selección.
3. Insertar el nodo correspondiente en el sub-recorrido, basándose en un criterio de inserción.4. Si se tiene un recorrido, parar. Caso contrario ir a 2.
Las distintas reglas de selección y criterios de inserción dan lugar a diferentes heurísticas. Veamos una de ellas: La heurística deinserción más barata.
Se comienza con un sub-recorrido T con dos ciudades i1 e i2, tales que
es decir, el sub-recorrido más corto entre dos ciudades. Luego se busca el costo mínimo de inserción en elsub-recorrido:
y se selecciona un nodo k∗ con ese costo. Luego se inserta el nodo entre las ciudades involucradas en el cálculo de ck∗. Finalmente se repite este proceso (con los sub-recorridos quese van generando) hasta construir un recorrido
Ejemplo de la heurística de inserción más barata
Consideremos el PAV dado por la siguiente matriz de distancias:
En primer...
Leer documento completo
Regístrate para leer el documento completo.