A * Допустимая эвристика для прокатки по сетке

Ответ 1

Здесь мой алгоритм применил пример Павла сетки 300x300, начиная с (23,25) и заканчивая на (282, 199). Он находит минимальный путь и сумму (1515, что на 2 пункта меньше, чем результат Пола 1517) за 0.52 секунды. Версия с поисковыми таблицами вместо вычисления небольших разделов занимала 0.13 секунды.

Код Haskell:

import Data.List (minimumBy)
import Data.Ord (comparing)
import Control.Monad (guard)

rollDie [email protected][left,right,top,bottom,front,back] move
  | move == "U" = [left,right,front,back,bottom,top]
  | move == "D" = [left,right,back,front,top,bottom]
  | move == "L" = [top,bottom,right,left,front,back]
  | move == "R" = [bottom,top,left,right,front,back]

dieTop die = die!!2

--dieStartingOrientation = [4,3,1,6,2,5] --left,right,top,bottom,front,back

rows = 300
columns = 300

paths (startRow,startColumn) (endRow,endColumn) dieStartingOrientation = 
  solve (dieTop dieStartingOrientation,[]) [(startRow,startColumn)] dieStartingOrientation where
    leftBorder = max 0 (min startColumn endColumn)
    rightBorder = min columns (max startColumn endColumn)
    topBorder = endRow
    bottomBorder = startRow
    solve [email protected](cost,moves) ((i,j):pathTail) die =
      if (i,j) == (endRow,endColumn)
         then [(result,die)]
         else do
           ((i',j'),move) <- ((i+1,j),"U"):next
           guard (i' <= topBorder && i' >= bottomBorder && j' <= rightBorder && j' >= leftBorder)
           solve (cost + dieTop (rollDie die move),move:moves) ((i',j'):(i,j):pathTail) (rollDie die move) 
        where next | null pathTail            = [((i,j+1),"R"),((i,j-1),"L")]
                   | head pathTail == (i,j-1) = [((i,j+1),"R")]
                   | head pathTail == (i,j+1) = [((i,j-1),"L")]
                   | otherwise                = [((i,j+1),"R"),((i,j-1),"L")]

--300x300 grid starting at (23, 25) and ending at (282,199)

applicationNum = 
  let (r,c) = (282-22, 199-24)
      numRowReductions = floor (r/4) - 1
      numColumnReductions = floor (c/4) - 1
      minimalR = r - 4 * fromInteger numRowReductions
      minimalC = c - 4 * fromInteger numColumnReductions
  in (fst . fst . minimumBy (comparing fst) $ paths (1,1) (minimalR,minimalC) [4,3,1,6,2,5])
     + 14*numRowReductions + 14*numColumnReductions

applicationPath = [firstLeg] ++ secondLeg ++ thirdLeg
               ++ [((0,["R"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (2,4) die2] 
    where
      (r,c) = (282-22, 199-24) --(260,175)
      numRowReductions = floor (r/4) - 1
      numColumnReductions = floor (c/4) - 1
      minimalR = r - 4 * fromInteger numRowReductions
      minimalC = c - 4 * fromInteger numColumnReductions
      firstLeg = minimumBy (comparing fst) $ paths (1,1) (minimalR,minimalC) [4,3,1,6,2,5]
      die0 = snd firstLeg
      secondLeg = tail . foldr mfs0 [((0,["R"]),die0)] $ [1..numColumnReductions - 1]
      die1 = snd . last $ secondLeg
      thirdLeg = tail . foldr mfs1  [((0,[]),die1)] $ [1..numRowReductions - 3 * div (numColumnReductions - 1) 4 - 1]
      die2 = rollDie (snd . last $ thirdLeg) "R"
      mfs0 a b = b ++ [((0,["R"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (4,4) (rollDie (snd . last $ b) "R")]
      mfs1 a b = b ++ [((0,["U"]),[])] ++ [minimumBy (comparing fst) $ paths (1,1) (4,1) (rollDie (snd . last $ b) "U")]

Вывод:

*Main> applicationNum
1515

*Main> applicationPath
[((31,["R","R","R","R","U","U","R","U","R"]),[5,2,1,6,4,3])
,((0,["R"]),[]),((25,["R","R","R","U","U","U"]),[3,4,1,6,5,2])
,((0,["R"]),[]),((24,["R","U","R","R","U","U"]),[5,2,1,6,4,3])
................((17,["R","R","R","U"]),[5,2,1,6,4,3])]
(0.52 secs, 32093988 bytes)

Список "R" и "U" :

*Main> let listRL = concatMap (\((a,b),c) -> b) applicationPath
*Main> listRL
["R","R","R","R","U","U","R","U","R","R","R","R","R","U","U","U","R","R","U","R"
..."U","R","R","R","R","U"]

Сумма пути с использованием стартовой матрицы и списка "R" и "U" :

*Main> let sumPath path = foldr (\move (cost,die) -> (cost + dieTop (rollDie die move), rollDie die move)) (1,[4,3,1,6,2,5]) path
*Main> sumPath listRL
(1515,[5,2,1,6,4,3])

Вычисление (r,c) из (1,1) с использованием списка "R" и "U" (так как мы начинаем с (1,1,), (r,c) настраивается на (282-22, 199-24):

*Main> let rc path = foldr (\move (r,c) -> if move == "R" then (r,c+1) else (r+1,c)) (1,1) path
*Main> rc listRL 
(260,175)

Алгоритм/решение

Continuing the research below, it seems that the minimal face-sum path (MFS) 
can be reduced, mod 4, by either rows or columns like so:

MFS (1,1) (r,c) == MFS (1,1) (r-4,c) + 14, for r > 7
                == MFS (1,1) (r,c-4) + 14, for c > 7

This makes finding the number for the minimal path straightforward:

MFS (1,1) (r,c) = 
  let numRowReductions = floor (r/4) - 1
      numColumnReductions = floor (c/4) - 1
      minimalR = r - 4 * numRowReductions
      minimalC = c - 4 * numColumnReductions
  in MFS (1,1) (minimalR,minimalC) + 14*numRowReductions + 14*numColumnReductions

minimalR and minimalC are always less than eight, which means we can easily
pre-calculate the minimal-face-sums for these and use that table to quickly
output the overall solution.

Но как мы находим путь?
Из моего тестирования, похоже, это получается так:

MFS (1,1) (1,anything) = trivial
MFS (1,1) (anything,1) = trivial
MFS (1,1) (r,c), for r,c < 5 = calculate solution in your favorite way
MFS (1,1) (r,c), for either or both r,c > 4 = 
  MFS (1,1) (minimalR,minimalC) -> roll -> 
  MFS (1,1) (min 4 r-1, min 4 c-1) -> roll -> 
  ...sections must be arranged so the last one includes 
     four rotations for one axis and at least one for the other.
     keeping one row or column the same till the end seems to work.
     (For Paul example above, after the initial MFS box, I moved in 
     fours along the x-axis, rolling 4x4 boxes to the right, which 
     means the y-axis advanced in threes and then a section in fours 
     going up, until the last box of 2x4. I suspect, but haven't checked, 
     that the sections must divide at least one axis only in fours for 
     this to work)...
  MFS (1,1) (either (if r > 4 then 4 else min 2 r, 4) 
             or     (4, if c > 4 then 4 else min 2 c))
  => (r,c) is now reached

Например,

  MFS (1,1) (5,13) = MFS (1,1) (1,5) -> roll right -> 
                     MFS (1,1) (1,4) -> roll right -> MFS (1,1) (5,4)

  MFS (1,1) (2,13) = MFS (1,1) (1,5) -> roll right -> 
                     MFS (1,1) (1,4) -> roll right -> MFS (1,1) (2,4)

Свойства кубиков, наблюдаемых при эмпирическом тестировании

For target points farther than (1,1) to (2,3), for example (1,1) to (3,4)
or (1,1) to (4,6), the minimum path top-face-sum (MFS) is equal if you 
reverse the target (r,c). In other words: 

1. MFS (1,1) (r,c) == MFS (1,1) (c,r), for r,c > 2

Не только это.

2. MFS (1,1) (r,c) == MFS (1,1) (r',c'), for r,c,r',c' > 2 and r + c == r' + c'
   e.g., MFS (1,1) (4,5) == MFS (1,1) (5,4) == MFS (1,1) (3,6) == MFS (1,1) (6,3)

Но здесь было интересно:

The MFS for any target box (meaning from startPoint to endPoint) that
can be reduced to a symmetrical combination of (r,c) (r,c) or (r,c) (c,r), for 
r,c > 2, can be expressed as the sum of the MFS of the two smaller symmetrical 
parts, if the die-roll (the change in orientation) between the two parts is 
accounted for. In other words, if this is true, we can breakdown the calculation
into smaller parts, which is much much faster.

For example: 
 Target-box (1,1) to (7,6) can be expressed as: 
 (1,1) (4,3) -> roll right -> (1,1) (4,3) with a different starting orientation

 Check it, baby: 
 MFS  (1,1) (7,6) = MFS (1,1) (4,3) + MFS (1,1) (4,3) 
 (when accounting for the change in starting orientation, rolling right in 
 between)

 Eq. 2., implies that MFS (1,1) to (7,6) == MFS (1,1) (5,8)
 and MFS (1,1) (5,8) can be expressed as (1,1) (3,4) -> roll right -> (1,1) (3,4)

 Check it again: 
 MFS (1,1) (7,6) = MFS (1,1) (5,8) = MFS (1,1) (3,4) + MFS (1,1) (3,4)
 (when accounting for the change in starting orientation, rolling right in
 between)

Не только это.

The symmetrical parts can apparently be combined in any way:

3. MFS (1,1) (r,c) -> roll-right -> MFS (1,1) (r,c) equals
   MFS (1,1) (r,c) -> roll-right -> MFS (1,1) (c,r) equals
   MFS (1,1) (r,c) -> roll-up -> MFS (1,1) (r,c) equals
   MFS (1,1) (r,c) -> roll-up -> MFS (1,1) (c,r) equals
   MFS (1,1) (2*r-1, 2*c) equals
   MFS (1,1) (2*r, 2*c-1), for r,c > 2

Ответ 2

Хорошо, я добавлю свой комментарий здесь, так как он более оптимален, чем текущий голос с наибольшим голосом от @larsmans, но, я убежден, что должно быть что-то лучше (отсюда и щедрость).

Если мною умножить эвристику с константой, то она уже не допустима

Лучшее, что я могу придумать, это (manhattenDistance/3)*6 + (manhattenDistance%3), где / - целочисленное деление, а % - мода. Это работает, потому что в любых 3-х ходах без обратного отслеживания все три цифры будут уникальными, поэтому самая низкая сумма, которую мы могли бы иметь, равна 1 + 2 + 3 = 6 (% 3 просто добавляет любые дополнительные, три хода).

[Изменить] Как отмечал @GrantS в комментариях выше, моя эвристика может быть улучшена очень незначительно, добавив дополнительный 1, когда manhattenDistance%3 == 2. Это легко сделать без условного: (manhattenDistance/3)*6 + (manhattenDistance%3)*3/2

Ответ 3

Main Edit 3: Доказательство того, что оптимальная допустимая эвристика должна основываться на 3.5m

Средняя стоимость проезда по доске должна приближаться к 3.5m в течение длительного времени, где m - расстояние Манхэттена. Поэтому наилучшая допустимая эвристика должна быть 3.5m плюс или минус небольшая константа.

Причиной этого является то, что всякий раз, когда вы двигаетесь в направлении, x, скажем, с лица x1, следующий ход в том же направлении, чтобы лицо x2 должно удовлетворять x1 + x2 = 7. Это связано с тем, что любые перемещения в перпендикулярном направлении оставляют ориентацию лица x2 одинаковой. Подумайте о повороте матрицы слева направо - передняя и задняя поверхности остаются такими же, независимо от того, сколько оборотов вы делаете. И наоборот, если вы поворачиваете фронт матрицы назад, левая и правая лица остаются неизменными.

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

   6
2453
1

здесь вы можете видеть, что мы начинаем с y1=1, и как бы много раз мы не двигались в направлении x после этого, следующий шаг в направлении y должен быть y2=6, поэтому y1+y2=7. (Также в x-направлении существует простое спаривание 2+5 = 7 и 4+3 = 7).

Другим примером является

  35
 26
14

В этом примере мы начинаем с x1=1, и как бы много раз мы не двигались в направлении y после этого, следующее движение в направлении x должно быть x2=6. (Также мы видим пары 4+3=7 в направлении y, 2+5=7 в направлении x. И мы знаем, что в этом случае следующее движение в направлении x должно быть 4, а следующее движение в направлении y должно быть 1.)

Все это предполагает, что он никогда не стоит отступать, но, надеюсь, это можно считать прочитанным.

Исходное сообщение ниже просто заполняет некоторые детали того, как следует оценивать оценку 3.5m, чтобы учесть способность к ее избиению в краткосрочной перспективе.

Как примечание, поскольку я просто прокомментировал OP, поиск A * может вообще не требоваться. Необходимо иметь в виду просто выбрать путь, построенный из 4-х горизонтальных фигур и четырехстрочных вертикальных фигур, скажем, оптимальных. А затем составьте остаток с помощью поисковой или поисковой таблицы на основе ориентации и смещения x-y. (Но вопрос требует приемлемой эвристики, поэтому я оставлю свой ответ.)

Main Edit 2: суммируйте оригинальную эмпирическую работу с учетом комментариев ниже

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

Это дает наивную оценку 3.5m, где m - расстояние Манхэттена. Однако это переоценка, потому что в краткосрочной перспективе можно добиться большего, чем среднее. Хорошая гипотеза для этого заключается в том, чтобы исследовать, как мы можем избежать использования лиц большего размера, чем 3.

• Если мы начинаем с лица 1, мы можем использовать грани 2 и 3 на наших первых 2 ходах, и движение 2 будет лучше, чем 3.5m.
• Если мы начнем с лица 2, мы можем использовать грани 1 и 3 для наших первых 2 ходов, и движение 3 будет лучше, чем 3.5m.
• Если мы начинаем с лица 3, мы можем использовать грани 1 и 2 для наших первых 2 ходов, и движение 4 будет лучше, чем 3.5m.
• Если мы начинаем с лица 4,5 или 6, мы можем использовать грани 1, 2 и 3 на наших первых 3 ходах, идя 4,5 будет двигаться лучше, чем 3.5m предсказывает.

Эта гипотеза может быть подтверждена эмпирически путем простого запуска script ниже для каждой начальной возможности штампа, как было предложено BlueRaja - Danny Pflughoeft. Таким образом, простая допустимая статистика 3.5m - k, где k = max(f+1, 4.5) и f - стартовая грань. Но это немного klunky, давая отрицательные числа при малых значениях m. Легко написать программную версию, которая учитывает, есть ли у вас всего 1 или 2 или 3 шага, см. Ниже

    static double Adm(int x, int y, int face /* start face */, out int m)
    {
        double adm = 0;
        m = Math.Abs(x) + Math.Abs(y);
        if (m >= 1) {
            if (face == 1)
                adm += 2;
            else
                adm += 1;
            m--;
        }
        if (m >= 1) {
            if (face <= 2)
                adm += 3;
            else
                adm += 2;
            m--;
        }
        if (m >= 1 && face >=4) {
            // 4,5,6: we can still use a 3 without backtracking
            adm += 3;
            m--;
        }

        adm += 3.5 * m;

        return adm;
    }

Выполняя это через поисковое пространство с помощью |x|,|y| <= 100, эта функция недооценивает фактическую стоимость между 0 и 6, с медианой 0,5 или 1,5 в зависимости от начального лица.

Главное Редактировать 1: оригинальное сообщение

Моя основная мысль заключалась в том, что было бы полезно изучить данные. Поэтому я пошел в алгоритм Дейкстрычтобы увидеть, как выглядит пространство решений. То, что я нашел, поддерживает то, что уже было сказано. Некоторый фактор времени Манхэттена является подходящим, но может быть какое-то обоснование для более высокого коэффициента, чем 1,5. Это хорошо видно по форме контурной зависимости стоимости от отклонения от начальной позиции x y.

Здесь участок проволочной рамки - честно говоря, это только для глазных конфет.

Интересно, что если вы добавите еще один столбец в свои данные для расстояния manhattan (человек) и измените стоимость (v) на расстояние manhattan в R, вы получите следующее

Coefficients:
          Estimate Std. Error  t value Pr(>|t|)    
(Intercept) -0.6408087  0.0113650   -56.38   <2e-16
df$man       3.4991861  0.0001047 33421.66   <2e-16

т.е. он говорит вам, что за каждый ход, который вы делаете горизонтально или вертикально, ваша стоимость составляет 3.4991861, или v близка к 3.5. Это всего лишь среднее значение от 1 до 6, поэтому моя интуиция заключается в том, что данные говорят нам, что в среднем наиболее эффективно использовать все грани умирающего на одинаковом расстоянии. На коротких расстояниях вы можете быть более оптимальными.

Я попробовал 3.5man - k как оценку, с k = 2.5. Казалось, это нормально. Когда я вычитал фактическую стоимость из этого, я получил -0.5 как наивысшее значение.

> summary(df$est - df$v)
  Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 -6.500  -2.500  -2.000  -1.777  -1.000  -0.500 

Однако поиск A * должен работать для всех конфигураций, в том числе после начала, когда штамп не находится в исходной конфигурации, поэтому константа k не может быть такой же низкой, как 2.5. Он либо должен быть поднят, например. до 4 или быть зависимым от конфигурации матрицы, как было предложено в другом ответе.

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

Вот несколько строк файла результатов.

17, -100410

17, -99406

17, -98403

17, -97399

17, -96396

Код С#

class Die
{
    int top;
    int bottom;
    int front;
    int back;
    int left;
    int right;

    public int Top { get { return top; } }
    public int Bottom { get { return bottom; } }
    public int Front { get { return front; } }
    public int Back { get { return back; } }
    public int Left { get { return left; } }
    public int Right { get { return right; } }

    public Die(int top, int bot, int fro, int bac, int lef, int rig)
    {
        this.top = top;
        bottom = bot;
        front = fro;
        back = bac;
        left = lef;
        right = rig;
    }

    public Die RotateLeft()
    {
        return new Die(
               top: right,
               rig: bottom,
               bot: left,
               lef: top,
               fro: front,
               bac: back
            );
    }

    public Die RotateRight()
    {
        return new Die(
               rig: top,
               top: left,
               lef: bottom,
               bot: right,
               fro: front,
               bac: back
            );
    }

    public Die RotateUp()
    {
        return new Die(
                top: front,
                fro: bottom,
                bot: back,
                bac: top,
                lef: left,
                rig: right
             );
    }

    public Die RotateDown()
    {
        return new Die(
                fro: top,
                top: back,
                bac: bottom,
                bot: front,
                lef: left,
                rig: right
            );
    }
}



class DieXY

{

    public Die Die { get; set; }
    public int X { get; set; }
    public int Y { get; set; }

    public DieXY(Die die, int x, int y) { Die = die; X = x; Y = y; }

    public override int GetHashCode() { return Die.Top + Die.Bottom*6 + Die.Front*6^2 + Die.Back*6^3 + Die.Left*6^4 + Die.Right*6^5 + X*6^6 + Y*6^8; }
    public override bool Equals(object obj)
    {
        DieXY die = (DieXY)obj;
        return die != null
            && die.Die.Top == Die.Top && die.Die.Bottom == Die.Bottom
            && die.Die.Front == Die.Front && die.Die.Back == Die.Back
            && die.Die.Left == Die.Left && die.Die.Right == Die.Right 
            && die.X == X && die.Y == Y;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Dictionary<DieXY, int> dict = new Dictionary<DieXY, int>();
        int n = 100;
        int sofar = -1;
        DieXY root = new DieXY(new Die(1, 6, 2, 5, 4, 3), 0, 0);
        Queue<Tuple<DieXY, int>> queue = new Queue<Tuple<DieXY, int>>();
        queue.Enqueue(new Tuple<DieXY,int>(root,0));
        while (queue.Count > 0)
        {
            Tuple<DieXY, int> curr = queue.Dequeue();
            DieXY dieXY = curr.Item1;
            Die die = dieXY.Die;
            int x = dieXY.X;
            int y = dieXY.Y;
            if (Math.Max(x,y) > sofar)
            {
                sofar = Math.Max(x, y);
                Console.WriteLine("{0}", sofar);
            }
            int score = curr.Item2;
            if (Math.Abs(x) <= n && Math.Abs(y) <= n)
            {
                int existingScore = 0;
                if (!dict.TryGetValue(dieXY, out existingScore)
                    || score < existingScore)
                {
                    dict[dieXY] = score;
                    Die newDie = null;
                    newDie = die.RotateLeft();
                    queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x - 1, y), score + newDie.Top));
                    newDie = die.RotateRight();
                    queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x + 1, y), score + newDie.Top));
                    newDie = die.RotateUp();
                    queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x, y + 1), score + newDie.Top));
                    newDie = die.RotateDown();
                    queue.Enqueue(new Tuple<DieXY, int>(new DieXY(newDie, x, y - 1), score + newDie.Top));
                }
            }
        }

        int[,] scores = new int[2*n+1,2*n+1];
        for (int aX = 0; aX < 2 * n + 1; aX++)
            for (int aY = 0; aY < 2 * n + 1; aY++)
                scores[aX, aY] = int.MaxValue;
        foreach (KeyValuePair<DieXY, int> curr in dict)
        {
            int aX = curr.Key.X + n;
            int aY = curr.Key.Y + n;
            if (curr.Value < scores[aX, aY])
            {
                scores[aX, aY] = curr.Value;
            }
        }

        using (System.IO.StreamWriter file = new System.IO.StreamWriter("out.csv"))
        {
            file.WriteLine("x,y,v");
            for (int aX = 0; aX < 2*n+1; aX++)
            {
                int x = aX - n;
                for (int aY = 0; aY < 2 * n + 1; aY++)
                {
                    int y = aY - n;
                    file.WriteLine("{0},{1},{2}", x, y, scores[aX, aY]);
                }
            }
        }

        Console.WriteLine("Written file");
        Console.ReadKey();
    }
}

R-код ниже

library(lattice)
df = read.csv("out.csv")
df=transform(df, man=abs(x)+abs(y))

v50=df[abs(df$x)<=50 & abs(df$y)<=50,]
with(v50, wireframe(v ~ x*y))
with(v50, contourplot(v ~ x*y))

summary(lm(df$v ~ df$man))

df$est = df$man * 3.5 - 2.5
summary(df$est - df$v)

Ответ 4

Если мною умножить эвристику с константой, то она уже не допустима

Это может быть, если вы избавитесь от некоторых угловых случаев. Пусть d - расстояние Манхэттена и заметим, что у кристалла никогда не может быть 1 лицо вверх на двух последующих шагах пути. Из этого следует, что если вы еще не достигли цели:

• первый шаг стоит как минимум 1;
• если 1 находится лицом вверх, то оно не менее 2 (и то же самое верно для 6);
• остальная часть пути, по крайней мере, такая же дорогая, как серия из 1-2 чередований, которая имеет стоимость 1,5 & times; × (d - 1).

Таким образом, допустимая эвристика

if d == 0 then
    h := 0
else if die == 1 or die == 6 then
    h := 2 + 1.5 × (d - 1)
else
    h := 1 + 1.5 × (d - 1)

Ответ 5

Идея:

Если вам нужно двигаться по прямой линии, лучше всего сделать, чтобы закончить ваши движения с помощью 1 и 2, для всех остальных ходов вы не можете сделать лучше, чем 3.5*distance.

Эвристический:

С ManhattanDistance = x + y можно использовать следующую эвристику:

Heuristic = xH + yH;

где

xH = calculateStraightLineHeuristic(x)
yH = calculateStraightLineHeuristic(y)

и функция calculateStraightLineHeuristic(z) определяется следующим образом:

calculateStraightLineHeuristic(z)
    if (z = 1)
        return zH = 1
    elseif (z = 2)
        return zH = 2+1
    else
        return zH = (z-2)*3.5+2+1
end