Answer about algoritmos

Algoritmo BackTracking - Problema de la Mochila

2017-07-11 05:25:00

Antes de empezar con BackTracking es recomendable que mires el video https://www.youtube.com/watch?v=vdVpRjO7g84 hasta el minuto 8:30 para entender correctamente como funciona BackTracking y el árbol resultante.

Enunciado:
Teniendo una mochila con una capacidad de "N" y un grupo de objetos que tienen dos atributos, por un lado el peso "P" y por otro lado el precio "V" teniendo estas tres variables: Implementar un algoritmo que devuelva el conjunto de objetos que deberias meter en la mochila, para obtener el mayor beneficio con una capacidad "N"...

Leer más

Algoritmo BackTracking - Problema del Festival

2017-07-10 00:00:00

Backtracking es una manera de recorrer un arbol de posibles soluciones. Imagina que quieres cruzar un laberinto, el laberinto tiene una puerta de entrada y salida.

Estas frente a la puerta de entrada y tienes tres caminos a seguir, escoges el de la derecha y marcas con una raya en la pared antes de entrar en ese camino, caminas y te topas con otras division, nuevamente tres caminos, escoges el de la derecha y lo marcas (en la pared con una raya de tiza), te vas por el camino y te encuentras que esta cerrado..
¿Que haces? pues te devuelves (back) y vuelves a la ultima division ahora tienes solo dos caminos para escoger, escoges el de mas a la derecha y que no esta marcado, lo marcas, y avanzas, cerrado, te devuelves a la division, escoges el de mas a la derecha que no este marcado (igual queda uno) lo marcas, avanzas, cerrado, te devuelves, y.. no queda nada para escoger, todo esta marcado, te devuelves y vuelves a la primera division, y escoges el camino mas a la derecha que no este marcado...

Leer más

Algoritmo BubbleSort - Ordenamiento

2017-07-02 15:10:16

El método de la burbuja es el más utilizado por los estudiantes principiantes de computación, por su fácil comprensión y programación. Pero es preciso señalar que es probablemente el método más ineficiente O(n²) (Para eficientes tenemos el QuickSort).

El algoritmo de la burbuja puede trabajar de dos maneras diferentes.

  • Llevando los elementos más pequeños hacia la parte izquierda del arreglo.
  • Llevando los elementos más grandes hacia la parte derecha del mismo.

  • La idea básica de este algoritmo consiste en comparar pares de elementos adyacentes e intercambiarlos entre sí hasta que todos se encuentren ordenados...

    Leer más

    Algoritmo QuickSort - Ordenamiento

    2017-07-02 07:25:36

    El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare, basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

    El algoritmo trabaja de la siguiente forma:

  • Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  • Resituar los elementos de la lista de manera que a un lado queden todos los menores que él, y al otro los mayores.
  • La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
  • Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

  • Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
  • En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
  • En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²).
  • En el caso promedio, el orden es O(n·log n).

  • ...

    Leer más

    Algoritmo BackTracking - Alquiler de coche

    2017-06-18 17:36:37

    Dentro de las técnicas de diseño de algoritmos, el método de Vuelta Atrás (del inglés Backtracking) es uno de los de más ámplia utilización, en el sentido de que puede aplicarse en la resolución de un gran número de problemas, muy especialmente en aquellos de optimización.
    Antes de empezar con BackTracking es recomendable que mires el video https://www.youtube.com/watch?v=vdVpRjO7g84 hasta el minuto 8:30 para entender correctamente como funciona BackTracking y el árbol resultante...

    Leer más