Рубрики

Задача выбора активности | Жадный Алго-1

Жадность — это алгоритмическая парадигма, которая строит решение по частям, всегда выбирая следующую часть, которая предлагает наиболее очевидную и непосредственную выгоду. Жадные алгоритмы используются для задач оптимизации. Задача оптимизации может быть решена с помощью Greedy, если задача имеет следующее свойство: на каждом этапе мы можем сделать выбор, который выглядит лучше всего в данный момент, и мы получим оптимальное решение полной задачи .
Если алгоритм Жадности может решить проблему, то он, как правило, становится лучшим способом решения этой проблемы, поскольку алгоритмы Жадности в целом более эффективны, чем другие методы, такие как динамическое программирование. Но жадные алгоритмы не всегда могут быть применены. Например, проблема дробного ранца (см. Это ) может быть решена с помощью Greedy, но 0-1 ранца не может быть решена с помощью Greedy.

Ниже приведены некоторые стандартные алгоритмы, которые являются жадными алгоритмами.
1) Минимальное остовное дерево Крускала (MST) . В алгоритме Крускала мы создаем MST, выбирая ребра один за другим. Жадный выбор — выбрать наименьшее ребро веса, которое не вызывает цикл в MST, построенном до сих пор.
2) Минимальное остовное дерево Прима : В алгоритме Прима мы также создаем MST, выбирая ребра один за другим. Мы поддерживаем два набора: набор вершин, уже включенных в MST, и набор вершин, еще не включенных. Жадный выбор заключается в выборе наименьшего веса, который соединяет два набора.
3) Кратчайший путь Дейкстры. Алгоритм Дейкстры очень похож на алгоритм Прима. Дерево кратчайших путей построено по краям. Мы поддерживаем два набора: набор вершин, уже включенных в дерево, и набор вершин, еще не включенных. Жадный выбор — выбрать ребро, которое соединяет два набора и находится на пути наименьшего веса от источника к набору, который содержит еще не включенные вершины.
4) Кодирование Хаффмана. Кодирование Хаффмана — это метод сжатия без потерь. Он назначает битовые коды переменной длины различным символам. Жадный выбор заключается в назначении кода наименьшей длины для наиболее часто встречающегося символа.

Жадные алгоритмы иногда также используются для получения аппроксимации для сложных задач оптимизации. Например, проблема коммивояжера — проблема NP-Hard. Жадный выбор для этой проблемы — выбрать ближайший не посещаемый город из текущего города на каждом шагу. Эти решения не всегда дают наилучшее оптимальное решение, но могут использоваться для получения приблизительно оптимального решения.

Давайте рассмотрим проблему выбора активности в качестве нашего первого примера алгоритмов Greedy. Ниже приводится постановка проблемы.
Вам дано n действий с их временем начала и окончания. Выберите максимальное количество действий, которые могут быть выполнены одним человеком, предполагая, что человек может работать только над одним действием за один раз.
Пример:

Example 1 : Consider the following 3 activities sorted by
by finish time.
     start[]  =  {10, 12, 20};
     finish[] =  {20, 25, 30};
A person can perform at most two activities. The 
maximum set of activities that can be executed 
is {0, 2} [ These are indexes in start[] and 
finish[] ]

Example 2 : Consider the following 6 activities 
sorted by by finish time.
     start[]  =  {1, 3, 0, 5, 8, 5};
     finish[] =  {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The 
maximum set of activities that can be executed 
is {0, 1, 3, 4} [ These are indexes in start[] and 
finish[] ]

Жадный выбор состоит в том, чтобы всегда выбирать следующее действие, время окончания которого меньше всего среди оставшихся действий, и время начала больше или равно времени окончания ранее выбранного действия. Мы можем отсортировать действия по времени их окончания, чтобы всегда рассматривать следующую деятельность как минимальное время окончания.

1) Сортировка действий по времени их окончания
2) Выберите первое действие из отсортированного массива и распечатайте его.
3) Выполните следующие действия для оставшихся действий в отсортированном массиве.
…… .a) Если время начала этого действия больше или равно времени окончания ранее выбранного действия, выберите это действие и распечатайте его.

В следующей реализации C предполагается, что действия уже отсортированы по времени их окончания.

C ++

// C ++ программа для задачи выбора активности.
// Следующая реализация предполагает, что действия
// уже отсортированы по времени окончания
#include<stdio.h>

  
// Печатает максимальный набор действий, которые могут быть выполнены одним
// человек, по одному за раз.
// n -> Общее количество действий
// s [] -> Массив, содержащий время начала всех действий
// f [] -> Массив, содержащий время окончания всех действий

void printMaxActivities(int s[], int f[], int n)

{

    int i, j;

  

    printf ("Following activities are selected n");

  

    // Первое действие всегда выбирается

    i = 0;

    printf("%d ", i);

  

    // Рассмотрим остальные мероприятия

    for (j = 1; j < n; j++)

    {

      // Если время начала действия больше или

      // равно времени окончания ранее выбранного

      // активность, затем выберите ее

      if (s[j] >= f[i])

      {

          printf ("%d ", j);

          i = j;

      }

    }

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    int s[] =  {1, 3, 0, 5, 8, 5};

    int f[] =  {2, 4, 6, 7, 9, 9};

    int n = sizeof(s)/sizeof(s[0]);

    printMaxActivities(s, f, n);

    return 0;

}

Джава

// Следующая реализация предполагает, что действия
// уже отсортированы по времени окончания

import java.util.*;

import java.lang.*;

import java.io.*;

  

class ActivitySelection

{

    // Печатает максимальный набор действий, которые могут быть выполнены одним

    // человек, по одному за раз.

    // n -> Общее количество действий

    // s [] -> Массив, содержащий время начала всех действий

    // f [] -> Массив, содержащий время окончания всех действий

    public static void printMaxActivities(int s[], int f[], int n)

    {

    int i, j;

       

    System.out.print("Following activities are selected : n");

       

    // Первое действие всегда выбирается

    i = 0;

    System.out.print(i+" ");

       

    // Рассмотрим остальные мероприятия

    for (j = 1; j < n; j++)

    {

         // Если время начала действия больше или

         // равно времени окончания ранее выбранного

         // активность, затем выберите ее

         if (s[j] >= f[i])

         {

              System.out.print(j+" ");

              i = j;

          }

     }

    }

       

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String[] args)

    {

    int s[] =  {1, 3, 0, 5, 8, 5};

    int f[] =  {2, 4, 6, 7, 9, 9};

    int n = s.length;

         

    printMaxActivities(s, f, n);

    }

      
}

C #

// Следующая реализация предполагает
// что действия уже отсортированы
// по времени их окончания

using System;

  

class GFG

{
// Печатает максимальный набор действий
// это может быть сделано одним
// человек, по одному за раз.
// n -> Общее количество действий
// s [] -> Массив, содержащий начало
// время всех действий
// f [] -> Массив, содержащий финиш
// время всех действий

public static void printMaxActivities(int[] s, 

                                      int[] f, int n)

{

int i, j;

  

Console.Write("Following activities are selected : ");

  
// Первое действие всегда выбирается
i = 0;

Console.Write(i + " ");

  
// Рассмотрим остальные мероприятия

for (j = 1; j < n; j++)

{

    // Если время начала действия больше или

    // равно времени окончания ранее выбранного

    // активность, затем выберите ее

    if (s[j] >= f[i])

    {

        Console.Write(j + " ");

        i = j;

    }

}
}

  
// Код драйвера

public static void Main()

{

    int[] s = {1, 3, 0, 5, 8, 5};

    int[] f = {2, 4, 6, 7, 9, 9};

    int n = s.Length;

          

    printMaxActivities(s, f, n);

}
}

  
// Этот код добавлен
// ChitraNayal

питон

«» «Следующая реализация предполагает, что деятельность
уже отсортированы по времени их окончания "" "

  
"" "Печатает максимальный набор действий, которые могут быть выполнены
один человек, по одному "" "
# n -> Общее количество действий
# s [] -> Массив, содержащий время начала всех действий
# f [] -> Массив, содержащий время окончания всех действий

  

def printMaxActivities(s , f ):

    n = len(f)

    print "The following activities are selected"

  

    # Первое действие всегда выбрано

    i = 0

    print i,

  

    # Рассмотрим остальные мероприятия

    for j in xrange(n):

  

        # Если время начала этого действия больше

        # или равно времени окончания ранее

        # выбранное занятие, затем выберите его

        if s[j] >= f[i]:

            print j,

            i = j

  
# Программа драйвера для проверки вышеуказанной функции

s = [1 , 3 , 0 , 5 , 8 , 5]

f = [2 , 4 , 6 , 7 , 9 , 9]

printMaxActivities(s , f)

  
# Этот код предоставлен Nikhil Kumar Singh

PHP

<?php
// PHP-программа для задачи выбора активности.
// Следующая реализация предполагает, что
// действия уже отсортированы по
// до их окончания

  
// Печатает максимальный набор действий
// это может быть сделано одним
// человек, по одному за раз.
// n -> Общее количество действий
// s [] -> Массив, содержащий начало
// время всех действий
// f [] -> Массив, содержащий финиш
// время всех действий

function printMaxActivities($s, $f, $n)

{

  

    echo "Following activities are selected " . "\n";

  

    // Первое действие всегда выбирается

    $i = 0;

    echo $i . " ";

  

    // Рассмотрим остальные мероприятия

    for ($j = 1; $j < $n; $j++)

    {

          

    // Если время начала этого действия больше

    // чем или равно времени окончания

    // ранее выбранный вид деятельности, затем выберите его

    if ($s[$j] >= $f[$i])

    {

        echo $j . " ";

        $i = $j;

    }

    }

}

  
// Код драйвера

$s = array(1, 3, 0, 5, 8, 5);

$f = array(2, 4, 6, 7, 9, 9);

$n = sizeof($s);

printMaxActivities($s, $f, $n);

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

Following activities are selected
0 1 3 4

Как работает Greedy Choice для действий, отсортированных по времени окончания?
Пусть заданный набор действий будет S = {1, 2, 3, ..n}, а действия будут отсортированы по времени окончания. Жадный выбор — всегда выбирать занятие 1. Почему занятие 1 всегда предлагает одно из оптимальных решений. Мы можем доказать это, показав, что если существует другое решение B с первой активностью, отличной от 1, то существует также решение A того же размера с активностью 1 в качестве первой активности. Пусть первая активность, выбранная с помощью B, будет k, тогда всегда существует A = {B — {k}} U {1}. (Обратите внимание, что операции в B независимы и k имеет наименьшее время окончания среди всех. Поскольку k не является 1, конец (k)> = конец (1)).

Как реализовать, когда данные виды деятельности не отсортированы?
Мы создаем структуру / класс для деятельности. Мы сортируем все действия по времени окончания (см. Сортировку в C ++ STL ). После сортировки действий мы применяем тот же алгоритм, что и выше.

Ниже изображение является иллюстрацией вышеупомянутого подхода:

Ниже приведена реализация вышеуказанного подхода:

// C ++ программа для задачи выбора активности
// когда входные действия не могут быть отсортированы.
#include <bits/stdc++.h>

using namespace std;

  
// Работа имеет время начала, время окончания и прибыль.

struct Activitiy

{

    int start, finish;

};

  
// служебная функция, используемая для сортировки
// действия в соответствии с временем окончания

bool activityCompare(Activitiy s1, Activitiy s2)

{

    return (s1.finish < s2.finish);

}

  
// Возвращает количество максимального набора действий, которые могут
// быть сделано одним человеком, по одному за раз.

void printMaxActivities(Activitiy arr[], int n)

{

    // Сортировка заданий по времени окончания

    sort(arr, arr+n, activityCompare);

  

    cout << "Following activities are selected n";

  

    // Первое действие всегда выбирается

    int i = 0;

    cout << "(" << arr[i].start << ", " << arr[i].finish << "), ";

  

    // Рассмотрим остальные мероприятия

    for (int j = 1; j < n; j++)

    {

      // Если время начала действия больше или

      // равно времени окончания ранее выбранного

      // активность, затем выберите ее

      if (arr[j].start >= arr[i].finish)

      {

          cout << "(" << arr[j].start << ", "

              << arr[j].finish << "), ";

          i = j;

      }

    }

}

  
// Драйвер программы

int main()

{

    Activitiy arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6},

                                       {5, 7}, {8, 9}};

    int n = sizeof(arr)/sizeof(arr[0]);

    printMaxActivities(arr, n);

    return 0;

}

Выход:

Following activities are selected 
(1, 2), (3, 4), (5, 7), (8, 9), 

Сложность времени: требуется время O (n log n), если входные действия не могут быть отсортированы. Требуется O (n) время, когда задано, что входные действия всегда сортируются.

Используя STL, мы можем решить это следующим образом:

// C ++ программа для задачи выбора активности
// когда входные действия не могут быть отсортированы.
#include <bits/stdc++.h>

using namespace std;

  

void SelectActivities(vector<int>s,vector<int>f){

// Вектор для хранения результатов.

    vector<pair<int,int>>ans;

  
// Очередь с минимальным приоритетом для сортировки действий в порядке возрастания времени окончания (f [i]).

  

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>p;

  

    for(int i=0;i<s.size();i++){

        // помещаем элементы в приоритетную очередь, где клавиша f [i]

        p.push(make_pair(f[i],s[i]));

    }

  

    auto it = p.top();

    int start = it.second;

    int end = it.first;

    p.pop();

    ans.push_back(make_pair(start,end));

  

    while(!p.empty()){

        auto itr = p.top();

        p.pop();

        if(itr.second >= end){

            start = itr.second;

            end = itr.first;

            ans.push_back(make_pair(start,end));

        }

    }

    cout << "Following Activities should be selected. " << endl << endl;

  

    for(auto itr=ans.begin();itr!=ans.end();itr++){

        cout << "Activity started at: " << (*itr).first << " and ends at  " << (*itr).second << endl;

    }

}

  
// Драйвер программы

int main()

{

    vector<int>s = {1, 3, 0, 5, 8, 5};

    vector<int>f = {2, 4, 6, 7, 9, 9};

    SelectActivities(s,f);

  

    return 0;

}

Ссылки:
Введение в алгоритмы Томаса Х. Кормена, Чарльза Э. Лизерсона, Рональда Л. Ривеста, Клиффорда Стейна
http://en.wikipedia.org/wiki/Greedy_algorithm

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Задача выбора активности | Жадный Алго-1

0.00 (0%) 0 votes