Autor Tema: Ayuda con algoritmos de busqueda  (Leído 241 veces)

edgarof

  • Mensajes: 14
    • Ver Perfil
    • Email
Ayuda con algoritmos de busqueda
« : mayo 12, 2010, 06:31:00 pm »
hola compa

Clerigo

  • Administrador
  • Mensajes: 154
  • Jr. Programmer
    • Ver Perfil
Re: Ayuda con algoritmos de busqueda
« Respuesta #1 : mayo 12, 2010, 08:19:49 pm »
De pronto lo consigue mas facil buscandolo como RECORRIDO EN PREORDEN

edgarof

  • Mensajes: 14
    • Ver Perfil
    • Email
Re: Ayuda con algoritmos de busqueda
« Respuesta #2 : mayo 12, 2010, 08:23:26 pm »
gracias clerigo ahora voy investigar si el algoritmo en profundiad funciona igual

edgarof

  • Mensajes: 14
    • Ver Perfil
    • Email
Re: Ayuda con algoritmos de busqueda
« Respuesta #3 : mayo 28, 2010, 08:29:21 am »
compañeros de ric con repecto a este tema encontramos con clerigo un codigo  muy parecido a lo que solicitamos como algoritmos de busqueda por produndiad, aca les dejo el codigo para los que quieran probarlo, este recorrido lo hace desde el tatro el camarin del carmen, hasta el teatro de la castellana

Código: [Seleccionar]
/*
 * Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
 * James Holmes McGraw-Hill/Osborne 2003
 * 
 */

//The entire depth-first search program follows:
//Find connections using a depth-first search.

import java.util.*;
import java.io.*;

//Flight information.
class FlightInfo {
  String from;

  String to;

  int distance;

  boolean skip; // used in backtracking

  FlightInfo(String f, String t, int d) {
    from = f;
    to = t;
    distance = d;
    skip = false;
  }
}

public class Depth {
  final int MAX = 100; // maximum number of connections

  // This array holds the flight information.
  FlightInfo flights[] = new FlightInfo[MAX];

  int numFlights = 0; // number of entries in flight array

  Stack btStack = new Stack(); // backtrack stack

  public static void main(String args[]) {
    String to, from;
    Depth ob = new Depth();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    ob.setup();

    try {
      System.out.print("From? ");
      from = br.readLine();
      System.out.print("To? ");
      to = br.readLine();

      ob.isflight(from, to);

      if (ob.btStack.size() != 0)
        ob.route(to);
    } catch (IOException exc) {
      System.out.println("Error on input.");
    }
  }

  //Initialize the flight database.
  void setup() {

               addFlight("Carmen", "Colon", 1);
addFlight("Libre", "Faenza", 8);
addFlight("Colon", "Candelaria", 3);
addFlight("Colon","Iberoamericano", 9);
addFlight("Iberoamericano", "Colsubsidio", 8);
addFlight("Iberoamericano", "Gaitan", 18);
addFlight("Mama", "Nacional", 17);
addFlight("Gaitan", "Colsubsidio", 18);
addFlight("Colsubsidio", "Mama", 50);
addFlight("Candelaria", "Libre", 1);
addFlight("Libre", "Torta", 2);
addFlight("Faenza", "Gaitan", 6);
addFlight("Torta", "Gaitan", 5);
addFlight("Metropol", "Colombiano", 30);
addFlight("Gaitan", "Metropol", 2);
addFlight("Colombiano", "Santafe", 3);
addFlight("Santafe", "Mama", 10);
addFlight("Nacional", "Castellana", 24);

  }

  //Put flights into the database.
  void addFlight(String from, String to, int dist) {
    if (numFlights < MAX) {
      flights[numFlights] = new FlightInfo(from, to, dist);

      numFlights++;
    } else
      System.out.println("Flight database full.\n");
  }

  // Show the route and total distance.
  void route(String to) {
    Stack rev = new Stack();
    int dist = 0;
    FlightInfo f;
    int num = btStack.size();

    // Reverse the stack to display route.
    for (int i = 0; i < num; i++)
      rev.push(btStack.pop());

    for (int i = 0; i < num; i++) {
      f = (FlightInfo) rev.pop();
      System.out.print(f.from + " to ");
      dist += f.distance;
    }

    System.out.println(to);
    System.out.println("Distance is " + dist);
  }

  /*
   * If there is a flight between from and to, return the distance of flight;
   * otherwise, return 0.
   */
  int match(String from, String to) {
    for (int i = numFlights - 1; i > -1; i--) {
      if (flights[i].from.equals(from) && flights[i].to.equals(to)
          && !flights[i].skip) {
        flights[i].skip = true; // prevent reuse
        return flights[i].distance;
      }
    }

    return 0; // not found
  }

  // Given from, find any connection.
  FlightInfo find(String from) {
    for (int i = 0; i < numFlights; i++) {
      if (flights[i].from.equals(from) && !flights[i].skip) {
        FlightInfo f = new FlightInfo(flights[i].from, flights[i].to,
            flights[i].distance);
        flights[i].skip = true; // prevent reuse

        return f;
      }
    }

    return null;
  }

  // Determine if there is a route between from and to.
  void isflight(String from, String to) {
    int dist;
    FlightInfo f;

    // See if at destination.
    dist = match(from, to);
    if (dist != 0) {
      btStack.push(new FlightInfo(from, to, dist));
      return;
    }

    // Try another connection.
    f = find(from);
    if (f != null) {
      btStack.push(new FlightInfo(from, to, f.distance));
      isflight(f.to, to);
    } else if (btStack.size() > 0) {
      // Backtrack and try another connection.
      f = (FlightInfo) btStack.pop();
      isflight(f.from, f.to);
    }
  }
}
« Última Modificación: mayo 28, 2010, 08:36:39 am por edgarof »