Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Конструкции данных, PHP. Часть вторая

Anna | 31.05.2014 | нет комментариев

Продолжаю совмещать славное с пригодным и переводить. Сегодня речь зайдет о кучах (heaps) и графах. Как обыкновенно, материал скорее подойдет новичкам — огромная часть информации, если не каждая, теснее где-то так либо напротив освещалась.

В конце прошлой статьи затрагивались деревья, следственно начнем с кучи, от того что между кучей и деревьями есть всеобщие корни. После этого перейдем к графам и реализуем алгорифм Дейкстры.


Куча — особая, деревоподобная конструкция, у которой есть одно качество — всякий родительский узел неизменно огромнее либо равен своим потомкам. Таким образом, при выполнении данного данные, корневой элемент кучи неизменно будет максимальным. Данный вариант называют максимальной (полной) кучей либо maxheap. Куча, где корневой элемент минимален, а всякий родительский узел поменьше либо равен своим потомкам — минимальная куча либо minheap.

Двоичную кучу (maxheap) дозволено представить таким образом:

image

Она является двоичной потому, что всякий родитель имеет два потомка.
Стоит подметить, что кучи хоть и реализуются как бинарные деревья, но у них нет такого представления как упорядочивание и нет определенного порядка для обхода. Куча — вариант табличной конструкции, следственно к ней применимы следующие базовые операции:

  1. create – сделать пустую кучу.
  2. isEmpty – определить, пуста ли куча либо нет.
  3. insert – добавить элемент в кучу.
  4. extract – извлечь и удалить элемент (корень, вершину) из кучи.

От того что операции приобретения и удаления элементов совмещены в одной операции извлечения, то для начала ее и разглядим.

Правило для удаления элемента из кучи состоит в том, что удалять дозволено только корневой элемент. Возможен, мы удалили корневой элемент из примера выше (100). Позже удаления мы останемся с двумя раздельными кучами и нам необходимо как-то пересобрать все это в одну отдельную кучу. Легче каждого это сделать перемещением последнего узла в корень, впрочем в таком случае такая куча не будет подходить по основному условию. Такая куча именуется semiheap:

image

Сейчас нужно сделать из полукучи типичную кучу. Одно из допустимых решений этой задачи — спускать новейший корень вниз, заодно сопоставляя корневой элемент с его потомками и меняя его местами с максимальным потомком. Таким образом, мы вернем в корень наивысший элемент, при этом опустив наименьший максимально вниз.

Мы можем реализовать maxheap как массив. Узел в бинарном дереве не может иметь больше 2-х потомков, следственно для всякого числа узлов n бинарная куча будет иметь 2n 1 узел.

Реализуем кучу дальнейшим образом:

<?php
class BinaryHeap
{
    protected $heap;

    public function __construct() {
        $this->heap  = array();
    }

    public function isEmpty() {
        return empty($this->heap);
    }

    public function count() {
        // возвращаем размер кучи
        return count($this->heap) - 1;
    }

    public function extract() {
        if ($this->isEmpty()) {
            throw new RunTimeException('Куча пуста!');
        }

        // извлечем 1-й элемент из кучи и присвоим его как корень
        $root = array_shift($this->heap);

        if (!$this->isEmpty()) {
            // переместим конечный элемент кучи на ее вершину
            // Дабы избавиться от 2-х поделенных между собой ветвей
            $last = array_pop($this->heap);
            array_unshift($this->heap, $last);

            // превратим полукучу в кучу
            $this->adjust(0);
        }

        return $root;
    }

    public function compare($item1, $item2) {
        if ($item1 === $item2) {
            return 0;
        }
        // обратное сопоставление даст нам minheap
        return ($item1 > $item2 ? 1 : -1);
    }

    protected function isLeaf($node) {
        // тут неизменно будет 2n   1 узел в "подкуче"
        return ((2 * $node)   1) > $this->count();
    }

    protected function adjust($root) {
        // спускаемся как дозволено ниже
        if (!$this->isLeaf($root)) {
            $left  = (2 * $root)   1; // левый потомок
            $right = (2 * $root)   2; // правый потомок

            $h = $this->heap;
            // если корень поменьше своих потомков
            if (
              (isset($h[$left]) &&
                $this->compare($h[$root], $h[$left]) < 0)
              || (isset($h[$right]) &&
                $this->compare($h[$root], $h[$right]) < 0)
            ) {
                // находим старшего потомка
                if (isset($h[$left]) && isset($h[$right])) {
                  $j = ($this->compare($h[$left], $h[$right]) >= 0)
                      ? $left : $right;
                }
                else if (isset($h[$left])) {
                  $j = $left; // левый потомок
                }
                else {
                  $j = $right; // правый потомк
                }

                // меняем местами с корнем
                list($this->heap[$root], $this->heap[$j]) = 
                  array($this->heap[$j], $this->heap[$root]);

                // рекурсивно перебираем кучу касательно
                // нового корневого узла $j
                $this->adjust($j);
            }
        }
    }
}

Вставка же напротив, полная противоположность извлечению: мы вставляем элемент вниз кучи и поднимаем ее до тех пор, пока это допустимо и выполняется основное условие. Так как мы знаем, что полное бинарное дерево содержит n/2 1 узел, мы можем обходить кучу применяя легкой бинарный поиск.

public function insert($item) {
    // вставим новые элементы в конец кучи
    $this->heap[] = $item;

    // определим им правильное место
    $place = $this->count();
    $parent = floor($place / 2);
    // пока не на вершине и огромнее родителя
    while (
      $place > 0 && $this->compare(
        $this->heap[$place], $this->heap[$parent]) >= 0
    ) {
        // меняем местами
        list($this->heap[$place], $this->heap[$parent]) =
            array($this->heap[$parent], $this->heap[$place]);
        $place = $parent;
        $parent = floor($place / 2);
    }
}

Посмотрим что у нас получилось и испробуем вставить несколько значений в кучу:

<?php
$heap = new BinaryHeap();
$heap->insert(19);
$heap->insert(36);
$heap->insert(54);
$heap->insert(100);
$heap->insert(17);
$heap->insert(3);
$heap->insert(25);
$heap->insert(1);
$heap->insert(67);
$heap->insert(2);
$heap->insert(7);

Если мы испробуем вывести все это, то получим следующее:

Array
(
    [0] => 100
    [1] => 67
    [2] => 54
    [3] => 36
    [4] => 19
    [5] => 7
    [6] => 25
    [7] => 1
    [8] => 17
    [9] => 2
    [10] => 3
)

Как видно, порядок не соблюден и вообще это несколько другое, что мы ждали. Впрочем если мы будем по-очереди извлекать элементы из кучи, то все будет типично:

<?php
while (!$heap->isEmpty()) {
    echo $heap->extract() . "n";
}
100
67
54
36
25
19
17
7
3
2
1
SplMaxHeap и SplMinHeap

К счастью, для нас теснее есть готовые реализации SplHeap, SplMaxHeap и SplMinHeap. Все что нам необходимо сделать это только унаследовать их и переопределить способ сопоставления, скажем так:

<?php
class MyHeap extends SplMaxHeap
{
    public function compare($item1, $item2) {
        return (int) $item1 - $item2;
    }
}

Данный способ исполнит всякое сопоставление 2-х узлов и в случае SplMaxHeap он возвращает правильное число если $item1 огромнее $item2, 0 если они равны друг другу и негативное, если $item2 огромнее $item1. Если мы наследуем SplMinHeap, то он вернет позитивное число, если $item1 поменьше $item2.

Не рекомендуется помещать в кучу несколько идентичных элементов, посколько их позицию будет сложно определить

SplPriorityQueue — приоритетная очередь

Приоритетная очередь это особый отвлеченный тип данных, тот, что ведет себя как очередь, но реализуется как куча. В отношении SplPriorityQueue это будет maxheap. Приоритетная очередь имеет достаточно много реальных использований, скажем, система тикетов либо справочная служба.

Как и в случае SplHeap, необходимо лишь унаследовать SplPriorityQueue и переопределить способ сопоставления:

<?php
class PriQueue extends SplPriorityQueue
{
    public function compare($p1, $p2) {
        if ($p1 === $p2) return 0;
        // в порядке возрастания приоритета, меньшее значение
        // обозначает больший приоритет
        return ($p1 < $p2) ? 1 : -1;
   }
}

Основное различие в SplPriorityQueue заключается в том, что при вставке, помимо значения элемента, ожидается еще и приоритет данного элемента. Операция вставки использует приоритет, Дабы просеивать кучу, базируясь на итоге, тот, что возвращает ваш компаратор.

Проверим работу приоритетной очереди, в качестве чисел зададим приоритет:

<?php
$pq = new PriQueue();
$pq->insert('A', 4);
$pq->insert('B', 3);
$pq->insert('C', 5);
$pq->insert('D', 8);
$pq->insert('E', 2);
$pq->insert('F', 7);
$pq->insert('G', 1);
$pq->insert('H', 6);
$pq->insert('I', 0);

while ($pq->valid()) {
    print_r($pq->current());
    echo "n";
    $pq->next();
}

Что в результате выдаст нам следующее:

I
G
E
B
A
C
H
F
D 

В данном случае наши элементы идут в порядке убывания приоритета — от самого высокого к самому низкому (меньшее значение — больший приоритет). Дозволено поменять порядок выдачи элементов легко изменив способ сопоставления, Дабы тот возвращал позитивное число, если $p1 огромнее чем $p2.

По-умолчанию, извлекается только значение элемента. Если необходимо получать только значения приоритета, либо же значения и их приоритет, необходимо установить соответствующий флаг извлечения:

<?php
// извлечь только приоритет
$pq->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);

// значение и приоритет (возвратит ассоциативный массив
// для всякого элемента)
$pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
Графы

За графами стоит достаточно много реальных использований — оптимизация сетей, маршрутизация либо же обзор общественных сетей. Google PageRank, рекомендации от Amazon — вот некоторые примеры их применения. В этой части статьи я испробую объяснить две задачи, в которых они применяются — задачи поиска короткого пути и наименьшее число остановок.

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

  • 3. До тех пор пока очередь не пуста:
    • 3a. извлекаем нынешний узел
    • 3b. если нынешний узел является желанным — останавливаемся
    • 3c. напротив добавляеем в очередь всякий непосещенный соседний узел и помечаем его как посещенный

Но как мы узнаем какие узлы соседние либо непосещенные не прибегая к обходу графа? Это подводит нас к вопросу о том, как графы могут быть смоделированы.

Представление графа

Обыкновенно, графы представляются двумя методами — таблица либо матрица, где описаны соседние узлы.
Вот как это выглядит для первого примера:

imageimage

В матрице, на пересечении узлов ставится «1», если узлы являются соседями.

Список комфортен в том случае, если огромная часть вершин не имеют связей между собой, матрица же обеспечивает больше стремительный поиск. В конце концов вид представления графа зависит от того, какие операции с графом будут производиться. Мы воспользуемся списком.

<?php
$graph = array(
  'A' => array('B', 'F'),
  'B' => array('A', 'D', 'E'),
  'C' => array('F'),
  'D' => array('B', 'E'),
  'E' => array('B', 'D', 'F'),
  'F' => array('A', 'E', 'C'),
);

И напишем наш поиск в ширину:

<?php
class Graph
{
  protected $graph;
  protected $visited = array();

  public function __construct($graph) {
    $this->graph = $graph;
  }

  // обнаружим минимальное число прыжков (связей) между 2 узлами

  public function breadthFirstSearch($origin, $destination) {
    // пометим все узлы как непосещенные
    foreach ($this->graph as $vertex => $adj) {
      $this->visited[$vertex] = false;
    }

    // пустая очередь
    $q = new SplQueue();

    // добавим исходную вершину в очередь и пометим ее как посещенную
    $q->enqueue($origin);
    $this->visited[$origin] = true;

    // это требуется для записи обратного пути от всякого узла
    $path = array();
    $path[$origin] = new SplDoublyLinkedList();
    $path[$origin]->setIteratorMode(
      SplDoublyLinkedList::IT_MODE_FIFO|SplDoublyLinkedList::IT_MODE_KEEP
    );

    $path[$origin]->push($origin);

    $found = false;
    // пока очередь не пуста и путь не обнаружен
    while (!$q->isEmpty() && $q->bottom() != $destination) {
      $t = $q->dequeue();

      if (!empty($this->graph[$t])) {
        // для всякого соседнего узла
        foreach ($this->graph[$t] as $vertex) {
          if (!$this->visited[$vertex]) {
            // если все еще не посещен, то добавим в очередь и подметим
            $q->enqueue($vertex);
            $this->visited[$vertex] = true;
            // добавим узел к нынешнему пути
            $path[$vertex] = clone $path[$t];
            $path[$vertex]->push($vertex);
          }
        }
      }
    }

    if (isset($path[$destination])) {
      echo "из $origin в $destination за ", 
        count($path[$destination]) - 1,
        " прыжков";
      $sep = '';
      foreach ($path[$destination] as $vertex) {
        echo $sep, $vertex;
        $sep = '->';
      }
      echo "n";
    }
    else {
      echo "Нет пути из $origin в $destinationn";
    }
  }
}

Запустив данный пример мы получим следующее:

Взглянуть на граф еще раз

image
<?php
$g = new Graph($graph);

// минимальное число шагов из D в C
$g->breadthFirstSearch('D', 'C');
// итог:
// из D в C за 3 шага
// D->E->F->C

// минимальное число шагов из B в F
$g->breadthFirstSearch('B', 'F');
// итог:
// из B в F за 2 шага
// B->A->F

// минимальное число шагов из A в C
$g->breadthFirstSearch('A', 'C');
// итог:
// из A в C за 2 шага
// A->F->C

// минимальное число шагов из A в G
$g->breadthFirstSearch('A', 'G');
// итог:
// Пути из A в G нет

Если бы мы применяли стек взамен очереди, то обход стал бы в глубину.

Поиск оптимального пути

Иная распространенная задача это поиск оптимального пути между двумя всякими узлами. Чуть прежде я теснее говорил про построение маршрута в GoogleMaps как пример решения этой задачи. Как вариант, данную задачу дозволено применить к маршрутизации, управлению дорожным трафиком и так дальше.

Один из известных алгорифмов, направленных на решение данной задачи был придуман в 1959 году 29-летним ученым по имени Эдсгер Вибе Дейкстра. Узнать подробнее про алгорифм дозволено в википедии либо посмотреть на него в програпосте от splitface. В всеобщих же чертах, решение Дейкстры сводится к проверке всякой связи между всеми допустимыми парами узлов, начиная от стартового узла, и поддерживая обновленным комплект узлов с кратчайшей дистанцией, пока целевой узел не будет достигнут, если это допустимо.

Есть несколько методов реализации данного решения, а также их дополнения. Некоторые из них улучшали эффективность, а другие лишь указывали на недочеты решения Дейкстры, от того что оно работает только с позитивно взвешенными графами — такими, где нет негативных весов у связей.

Для примера возьмем дальнейший позитивный граф и предположим его через список, где укажем связи узлов между собой:

image

<?php
$graph = array(
  'A' => array('B' => 3, 'D' => 3, 'F' => 6),
  'B' => array('A' => 3, 'D' => 1, 'E' => 3),
  'C' => array('E' => 2, 'F' => 3),
  'D' => array('A' => 3, 'B' => 1, 'E' => 1, 'F' => 2),
  'E' => array('B' => 3, 'C' => 2, 'D' => 1, 'F' => 5),
  'F' => array('A' => 6, 'C' => 3, 'D' => 2, 'E' => 5),
);

Реализуем алгорифм с применением приоритетной очереди для создания списка всех «неоптимизированных» узлов:

<?php
class Dijkstra
{
  protected $graph;

  public function __construct($graph) {
    $this->graph = $graph;
  }

  public function shortestPath($source, $target) {
    // массив кратчайших путей к всякому узлу
    $d = array();
    // массив "предшественников" для всякого узла
    $pi = array();
    // очередь всех неоптимизированных узлов
    $Q = new SplPriorityQueue();

    foreach ($this->graph as $v => $adj) {
      $d[$v] = INF; // устанавливаем первоначальные расстояния как бесконечность
      $pi[$v] = null; // никаких узлов позади нет
      foreach ($adj as $w => $cost) {
        // воспользуемся ценой связи как приоритетом
        $Q->insert($w, $cost);
      }
    }

    // исходная дистанция на стартовом узле - 0
    $d[$source] = 0;

    while (!$Q->isEmpty()) {
      // извлечем минимальную цену
      $u = $Q->extract();
      if (!empty($this->graph[$u])) {
        // пройдемся по каждому соседним узлам
        foreach ($this->graph[$u] as $v => $cost) {
          // установим новую длину пути для соседнего узла
          $alt = $d[$u]   $cost;
          // если он оказался короче
          if ($alt < $d[$v]) {
            $d[$v] = $alt; // update minimum length to vertex установим как минимальное расстояние до этого узла
            $pi[$v] = $u;  // добавим соседа как предыдущий этому узла
          }
        }
      }
    }

    // сейчас мы можем обнаружить наименьший путь
    // применяя обратный проход
    $S = new SplStack(); // кратчайший путь как стек
    $u = $target;
    $dist = 0;
    // проход от целевого узла до стартового
    while (isset($pi[$u]) && $pi[$u]) {
      $S->push($u);
      $dist  = $this->graph[$u][$pi[$u]]; // добавим дистанцию для предшествующих
      $u = $pi[$u];
    }

    // стек будет пустой, если нет пути назад
    if ($S->isEmpty()) {
      echo "Нет пути из $source в $targetn";
    }
    else {
      // добавим стартовый узел и покажем каждый путь 
      // в обратном (LIFO) порядке
      $S->push($source);
      echo "$dist:";
      $sep = '';
      foreach ($S as $v) {
        echo $sep, $v;
        $sep = '->';
      }
      echo "n";
    }
  }
}

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

<?php
$g = new Dijkstra($graph);

$g->shortestPath('D', 'C');  // 3:D->E->C
$g->shortestPath('C', 'A');  // 6:C->E->D->A
$g->shortestPath('B', 'F');  // 3:B->D->F
$g->shortestPath('F', 'A');  // 5:F->D->A 
$g->shortestPath('A', 'G');  // Нет пути из A в G

Все. На этом, судя по каждому, статьи от Ignatius Teo по конструкциям закончились. Благодарствую всех прочитавших, не ждал, что первую часть так много человек разместит в избранное, правда все мы знаем что избранное редко когда читается и все посты остаются там навечно :)

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB