Dinamik Programlama - Dynamic Programming

Lineer Programlama - Linear Programming
Lineer programlama bir şeyin min veya max değerini bulmak için kullanılır. Min max ile de işler daha küçük parçalara ayrılarak load balancing yapılır. Linear Programlama halen geçerli bir şey. Açıklaması şöyle

Linear Programming is probably more useful than 50 years ago.

The software for solving linear programming problems has dramatically improved and more and more practical problems can be solved. Most of these practical problems are mixed integer linear programs (MILPs), but linear programming is integral to solving MILPs.

To support this statement, here a few indicators:

The airline industry heavily uses mathematical optimization for solving problems such as pairing optimization and crew scheduling. The same is true for public transport. The exitance of companies like Sabre and Optibus testifies to that.

The best way to find provenly optimal solutions to the traveling salesman problems is based on linear programming: https://www.math.uwaterloo.ca/tsp/concorde.html.

Companies that focus on mathematical optimization with linear programming at their core are thriving, for example Gurobi. Meanwhile, new competitor enter the market for mathematical optimization, specifically linear programming using the simplex algorithm, such as COPT, MindOpt, and Huawei.

Google has increased interest in linear and integer programming, including having their own linear programming solver GLOP.

Amazon is looking for people with skills in linear optimization: https://www.amazon.jobs/de/jobs/1716646/research-scientist.

Dynamic Algoritma Nedir?

Açıklaması şöyle

Dynamic programming is a technique that allows you to divide your problem into smaller subproblems and store the result of the subproblems in order to be able to use them at recurring calculations.

Dynamic Algoritma Ne Zaman Lazım

Dinamik Programlama için şu lazım.

For a problem to be solved using dp, we need overlapping subproblems.

Dynamic Algorita vs Recursion

Açıklaması şöylee

... recursion is similar to dynamic programming. One of the vital differences in a naive recursive solution is that it answers to sub-problems that may be computed multiple times.

Örnek

Elimde şöyle bir kod olsun. Bu kod recursion kullanıyor ancak verimli değil.

int fib(int n)
{
  if (n <= 1)
    return n;
  return fib(n-1) + fib(n-2);
}

Dynamic Algoritma vs Greedy Algoritma

Dinamik Algoritmalar, Greedy algoritmalara göre daha iyi sonuç verebilirler, çünkü her türlü olasılığı denerler.

Dynamic Algoritma Çözümleri

Dinamik Programlama top-down veya bottom-up olarak çözülebilir. top-down olanlar recursion kullanılır. bottom-up olanlar döngü kullanır.

Dinamik Programlama knapsack problemlerinde kullanılabilir. Tüm kombinasyonları denemek yerine, şimdiye kadar hesaplanmış değer üzerinden devam edebilmeyi sağlar.

Örnek

Örneğin aşağıdaki kod parçası dinamik programlama kullanmıyor.

def Fib(n):
  if n <= 1:
    return 1
  else:
    return Fib(n-1) + Fib(n-2)

Eğer top-down olarak çözmek isteseydik şöyle yapardık

// Note: Size is n + 1 because we store the values from 0 to n
unsigned int lookup[n + 1] = {0};
unsigned int fibonacci(unsigned int n) {
  if (n < 2) {
    return n;
  } else if (lookup[n] != 0) {
    return lookup[n];
  }
  lookup[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return lookup[n];
}

Eğer bottom-up olarak çözmek isteseydik şöyle yapardık.

unsigned int fibonacci(unsigned int n) {
  unsigned int lookup[n + 1] = {0};
  lookup[0] = 0;
  lookup[1] = 1;
  for (unsigned int i = 2; i <= n; i++) {
    lookup[i] = lookup[i - 1] + lookup[i - 2];
  }
  return lookup[i];
}

Brute Force Knapsack Algoritması
Knapsack algoritması bir torbaya belli bir kapasiteyi/ağırlığı aşmayacak ancak toplam değeri en fazla olan nesnelerin seçimi problemidir.

Kod olarak şöyle yazılır. Önce bir kapasite değeri tanımlanır.

// This is the total weight limit.
public double Capacity { get; set; }

Daha sonra bu kapasiteyi dolduracak nesnelerin atandığı bir dizi tanımlanır. Böylece kaç tane nesne alabileceğimizi biliriz.

>// This is an array with all the given items.
public Item[] Items { get; set; }

Daha sonra kodun içinde her nesneyi teker teker denediğimiz bir permüstasyon hesaplanır.

var permutations = (long)Math.Pow(2,size);

Kodun brute force olmasının sebebi her nesnenin teker teker denenmesidir.

for (int i = 0; i<permutations; i++)
{ 
    // ...
}

Nihayetinden elimizi şöyle bir kod çıkar

public Data Run(){
  int bestValue = 0;
  int bestPosition = 0;
  int size = Items.Length;

  var permutations = (long)Math.Pow(2,size);

  for (int i = 0; i<permutations; i++){
    int total = 0;
    int weight = 0;
    for (int j = 0; j<size; j++){
       //bit "not included"
       if(((i>>j)&1)!=1)
         continue;
         total += Items[j].v;
         weight += Items[j].w;
    }
    if (weight <= Capacity && total>bestValue){
      bestPosition = i;
      bestValue = total;
    }
  }
  var include = new List<Item>();
  for (int j = 0; j<size; j++){
    if (((bestPosition>>j) & 1)==1)
      include.Add(Items[j]);
  }
  return new Data { BestValue = bestValue, Include = include };

}//End of Run

Knapsack ve Job Scheduling
Bir diğer problem ise belli bir zamanda bitmesi gereken en değerli işleri bitirme algoritması. Problem şöyle çözülüyor.
1. Elimizdeki tüm işleri değerine göre azalacak şekilde sıralıyoruz.
2. Sıradan ilk işi alıyoruz.
3. Bir sonraki iş için süresine bakarak bitip bitmeyeceğini hesaplıyoruz. Eğer zaman dizisinde boşluk varsa iş bitebilir, boşluk yoksa bir sonraki işi deniyoruz.