📖
Wiki
Back to my personal website
  • Home
  • Equipment and Devices
    • 3D Printer
    • Laser Cutter
    • Motion Capture System
    • Sensors
      • RGB-D Cameras
      • Velodyne LiDAR
      • Zed Camera
      • RealSense D435i
      • IMU
    • eGPU
    • Nvidia AGX Xavier
    • CPU Benchmark
    • Installation Checklist
  • Development
    • Linux
      • Shell
      • GDB
      • Git
      • Tmux
      • Network
      • Tricks
      • Debug FAQ
    • CMake
      • Catkin Tools
      • CMakeLists
      • CMake Variables
      • CMake Commands
      • CMake: find_package()
    • ROS
      • Gazebo
      • wstool
      • roslaunch
      • rosbag
      • multi-threaded spinner
    • ROS2
      • Convert ROS1 bag to ROS2 bag
    • C++
      • C++ 11
      • C++ Examples
      • C++ Debug
      • Factory Method
      • Timing
    • Google Tools
      • GLog
      • GFlags
      • GTest
      • Style Guide
      • Clang Format
    • PCL
      • Point Type
      • Methods
      • Architecture
      • Code Explained
    • Open3D
      • Python API
      • Registration
      • Visualization
      • Tools
    • OpenCV
      • Documentation
      • Modules
    • Other Libraries
      • Eigen
      • Ceres
      • g2o
      • GTSAM
    • Website
  • Algorithm
    • SLAM
      • K-D Tree
      • Octree
      • Bag of Words
      • Distance Measures
      • Coordinate Systems
      • LOAM
      • Iterative Closest Point
      • Generalized ICP
      • Mahalanobis Distance
    • Computer Science
      • Computational Model
      • Sorting
      • Analysis
      • Complexity Classes (P, NP)
      • Divide and Conquer
      • Greedy Algorithm
      • Dynamic Programming
      • Tree
      • Graph
    • Computer Vision
      • Camera Models
      • Distortion
      • Motion Models
      • Shutter
      • Image Sensors
      • Epipolar Geometry
      • Multiple-View Geometry
    • Datasets
      • RGB-D Datasets
      • Point Cloud Datasets
      • LiDAR SLAM Datasets
  • Math
    • Optimization
      • Convex Optimization
      • Descent Methods
    • Probability
      • Moment
      • Covariance Matrix
      • Stochastic Process
    • Topology
      • References
      • Concepts
      • Topological Spaces
      • Representation of Rotations
      • Representation of 3-sphere
    • Algebra
      • Linear Algebra
      • Matrix Factorization
      • Condition Number
      • Matrix Lie Group
    • Differential Geometry
      • Manifold
      • Submanifold
      • Quotient Manifolds
      • Tangent Space
  • Quadrotor
    • PX4 Development
    • Companion Computer
    • Drone Hardware
    • Propeller Lock
    • Debug
  • Favorites
    • Bookmarks
Powered by GitBook
On this page
  • Optimization Problem
  • Prove the Optimality
  • Example problems
  • Greedy vs. Dynamic Programming
  • Example Code: Easy Swaps to Sort 123

Was this helpful?

  1. Algorithm
  2. Computer Science

Greedy Algorithm

  • Greedy algorithms are applied to optimization algorithms only.

  • It picks always the current best solution; no backtracking.

  • Not necessarily optimal --> need to prove it.

Optimization Problem

  • find a set of items that can

    • meet some constraints, and

    • optimize some objective function

  • examples: shortest path, minimum spanning tree

  • not an optimization problem: sorting

Prove the Optimality

To prove the optimality of a greedy strategy, we need to prove the following two parts.

  • Greedy Choice

    • find the choice that is part of SOME optimal solution

    • there may exist multiple optimal solutions; no need to prove it for ANY optimal solution

  • Optimal Substructure

    • After making the first choice, the final best solution is first choice + best solution for the rest of (compatible) input

    • We can solve the same optimization problem recursively!

    • Otherwise, we find a contradiction!

Example problems

  • activity selection (pick the earliest-finish task)

  • minimum spanning tree

  • Huffman code

  • Dijkastra's shortest path

  • graph coloring

  • traveling salesman

Greedy vs. Dynamic Programming

  • Greedy: always pick the current best

  • DP: pick the best based on history

  • You can always use DP to solve Activity Selection problem, but it is much costly (since you have to try all other branches)

Example Code: Easy Swaps to Sort 123

#include <iostream>
#include <vector>
#include <algorithm>

int main(){
  int n;
  std::cin >> n; 
  std::vector<int> candies(n);
  for (int k = 0; k < n; ++k)
    std::cin >> candies[k];

  // count total number of 1s, 2s, 3s
  int sum1 = 0, sum2 = 0, sum3 = 0;
  for (int k = 0; k < n; ++k){
    if (candies[k] == 1)
      sum1++;
    else if (candies[k] == 2)
      sum2++;
    else
      sum3++;
  }

  // all 3s should be placed in the range [sum1+sum2, n-1]
  // and then leave a subproblem of 1s and 2s in the range [0, sum1+sum2-1]
  int swap = 0;
  std::vector<int> temp_queue;
  for (int k = sum1 + sum2; k < n; ++k){
    if (candies[k] != 3){
      swap++;
      temp_queue.push_back(candies[k]);
    }
  }

  // move all 1s to the front and 2s to the end
  std::sort(temp_queue.begin(), temp_queue.end());

  // in [0, sum1+sum2-1], we want to put 1s to the front and 2s to the end 
  for (int k = sum1 + sum2 - 1; k >= 0; --k){
    if (candies[k] == 3){
      candies[k] = temp_queue.back();
      temp_queue.pop_back();
    }
  }

  // finally, count how many 2s are still there in the range [0, sum1-1]
  // which is supposed to be all 1s
  for (int k = 0; k < sum1; ++k){
    if (candies[k] == 2)
      swap++;
  }

  std::cout << swap << std::endl;

  return 0;
}
PreviousDivide and ConquerNextDynamic Programming

Last updated 3 years ago

Was this helpful?