උත්තල හල් ඇල්ගොරිතම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ජ්යාමිතික මෝර්ගන් ස්ටැන්ලි Samsung ජංගම දුරකථන

“උත්තල හල් ඇල්ගොරිතම” ගැටලුවේදී අපි කරුණු කිහිපයක් ලබා දී ඇත. එහි ඇති අනෙකුත් සියලුම ලක්ෂ්‍ය අඩංගු එම ලක්ෂ්‍ය සමඟ සෑදිය හැකි කුඩාම බහුඅවයව එහි උත්තල හල් ලෙස හැඳින්වේ.

උත්තල හල් ඇල්ගොරිතම

භාවිතා කිරීමෙන් මෙය සාක්ෂාත් කරගත හැකිය ජාවිස් ඇල්ගොරිතම.

ඇල්ගොරිතම

  1. වම් කෙළවරේ සිට 0 දක්වා ආරම්භ කරන්න.
  2. දෛශික ලක්ෂ්‍යයේ ප්‍රති result ලය
  3. ප්‍රමුඛතම වම් ලක්ෂ්‍යය සොයා ගන්නා තෙක් ලකුණු වස්තු අරාව හරහා ගමන් කරන්න
  4. ප්‍රති point ල දෛශිකයට එම ලක්ෂ්‍යය එක් කරන්න
  5. ඊළඟ කරුණ සොයා ගන්න "Q" එය අනෙක් සියලුම ලක්ෂ්‍යයන්ගෙන් වඩාත්ම ප්‍රතිවිරුද්ධ දිශාවයි
  6. ලක්ෂ්‍යයට p සකසන්න "Q" ඊළඟ ක්‍රියාවලිය සඳහා.
  7. අතරතුර එකතු කිරීම දිගටම කරගෙන යන්න "පී" වම් කෙළවරට සමාන නොවේ.

විස්තර

එබැවින් උත්තල කුහරය විසඳීම සඳහා අපගේ ප්‍රධාන අදහස වන්නේ දිශානතිය භාවිතා කිරීමයි. අපි වම් කෙළවරේ හෝ අඩුම X ඛණ්ඩාංකය සොයාගෙන ආරම්භ කරන්නෙමු. සමහර ලකුණු සමූහයක් රැස් කර ගත හැකි අපගේ සියලු ලකුණු සොයා ගන්නා තෙක් අපට එය ගත හැකිය.

කේතයේ ආරම්භයේදීම අපි එය දැනටමත් අර්ථ දක්වා ඇති පරිශීලක පන්තියේ ලක්ෂ්‍යයේ වස්තු අරාව ලකුණු පසුකර යන්නෙමු. පූර්ණ සංඛ්‍යා වල ලක්ෂ්‍ය හා දිග පිළිබඳ අපගේ තර්ක උත්තල කුහරය තුළට යවනු ලැබේ ක්රියාව, එහිදී අපි අපගේ ප්‍රතිදානය ගබඩා කිරීමට යන දෛශික නම් කරන ලද ප්‍රති result ලය ප්‍රකාශ කරමු.

දැන් වම් කෙළවරේ ලක්ෂ්‍යය 0 ට ආරම්භ කරන්න. අපි එය 0 සිට ආරම්භ කරන්නෙමු, අඩුම x ඛණ්ඩාංක ඇති ලක්ෂ්‍යය හෝ වම් කෙළවරේ ලක්ෂ්‍යය අප එය වෙනස් කිරීමට යන්නේ නම්.

දැන් සියලු කරුණු හරහා ගමන් කර අඩුම අගය සොයා ගන්න. වම් කෙළවරේ සිට ස්ථානය දක්වා ගබඩා කරන්න "පී" කරුණක් ප්‍රකාශ කරන්න

දැන්, අපි කළ යුතු පළමු දෙය ප්‍රතිදානය ලෙස පළමු කරුණ එකතු කිරීම සඳහා කළ යුතු වේලාවක් ආරම්භ කරන්න.

දැන් අපි අනෙක් සියලුම ලක්ෂ්‍යයන්ට වඩාත්ම ප්‍රතිවිරුද්ධ දිශාව සොයා ගත යුතුව ඇත, මේ සඳහා අපි දිශානතිය භාවිතා කිරීමට යන්නෙමු. අපි මේ සඳහා වෙනම ශ්‍රිතයක් සිදු කළ අතර, එය ත්‍රිත්වයේ දිශානතිය 2 ද නැද්ද යන්න පරීක්ෂා කරන්නේ එය 2 ක් දැයි සොයා ගන්නේ නම් ලක්ෂ්‍යයේ අගය යාවත්කාලීන කරන්න "Q".

මෙය තෙක් ඉදිරියට යා යුතුය "පී" වම් කෙළවරට සමාන නොවේ.

උදාහරණයක්

ලබා දී ඇති කරුණු:

{{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};

leftmost = 0;

සියළුම ලකුණු පසුකර ගිය පසු, අපගේ පළමු අඩුම x ඛණ්ඩාංකය වනු ඇත (0,3) එහි ප්‍රති store ලයක් ලෙස එය ගබඩා වේ.
දැන් එය පරීක්ෂා කිරීමට යන්නේ x, y යුගලයට බොහෝ වාමාවර්තව ඇති බැවින් එය දිශානතිය 2 ලෙස ලබා දෙන අතර ලක්ෂ්‍යයේ අගය යාවත්කාලීන කරයි "Q".
(0,0) ලෙස සොයාගත යුතු යුගලය.
දැන්, ලක්ෂ්‍යයේ අගය පිටපත් කරන්න "Q" වඩාත් ප්‍රතිවිරුද්ධ දිශාව සොයා ගැනීම සඳහා ඊළඟ ලක්ෂ්‍යයක් ලෙස p බවට.
P හි අගය වමට සමාන නොවන තුරු අපි මෙම ලූපය භාවිතා කරන්නෙමු.
අපගේ ප්‍රතිදානය වනුයේ: (0,3), (0,0), (3,0), (3,3)

ක්රියාත්මක කිරීම

උත්තල හල් ඇල්ගොරිතම සඳහා C ++ වැඩසටහන

#include <iostream>
using namespace std;
#define INF 10000

struct Point
{
        int x;
        int y;
};

int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

    if (val == 0)
        return 0;
    return (val > 0) ? 1 : 2;
}

void convexHull(Point points[], int n)
{
    if (n < 3)
        return;
    int next[n];

    for (int i = 0; i < n; i++)
        next[i] = -1;

    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;

    int p = l, q;
    do
    {
        q = (p + 1) % n;
        for (int i = 0; i < n; i++)
            if (orientation(points[p], points[i], points[q]) == 2)
                q = i;

        next[p] = q;
        p = q;
    }
    while (p != l);

    for (int i = 0; i < n; i++)
    {
        if (next[i] != -1)
            cout << "(" << points[i].x << ", " << points[i].y << ")\n";
    }
}

int main()
{
    Point points[] = { { 0, 3 }, { 2, 2 }, { 1, 1 }, { 2, 1 }, { 3, 0 },
            { 0, 0 }, { 3, 3 } };
    cout << "The points in the convex hull are: ";
    int n = sizeof(points) / sizeof(points[0]);
    convexHull(points, n);
    return 0;
}
The points in the convex hull are: (0, 3)
(3, 0)
(0, 0)
(3, 3)

උත්තල හල් ඇල්ගොරිතම සඳහා ජාවා වැඩසටහන

import java.util.*;
class Point {

  int x, y;

  Point(int x, int y) {
    this.x = x;
    this.y = y;
  }
}

class ConvexHull{

  public static int OrientationMatch(Point check1, Point check2, Point check3) {

    int val = (check2.y - check1.y) * (check3.x - check2.x) - (check2.x - check1.x) * (check3.y - check2.y);

    if (val == 0)
      return 0;

    return (val > 0) ? 1 : 2;
  }

  public static void convex_hull(Point points[], int lengths) {

    if (lengths<3) return;

    Vector<Point> result = new Vector<Point> ();

    int leftmost = 0;

    for (int i = 1; i<lengths; i++)
      if (points[i].x<points[leftmost].x)
        leftmost = i;

    int p = leftmost, pointq;

    do {

      result.add(points[p]);

      pointq = (p + 1) % lengths;

      for (int i = 0; i<lengths; i++) {
        if (OrientationMatch(points[p], points[i], points[pointq]) == 2) {
          pointq = i;
        }
      }
      p = pointq;
    }

    while (p != leftmost);

    System.out.print("The points in the convex hull are: ");
    for (Point temp: result)
      System.out.println("(" + temp.x + ", " + temp.y + ")");

  }

  public static void main(String[] args) {

    Point points[] = new Point[7];
    points[0] = new Point(0, 3);
    points[1] = new Point(2, 3);
    points[2] = new Point(1, 1);
    points[3] = new Point(2, 1);
    points[4] = new Point(3, 0);
    points[5] = new Point(0, 0);
    points[6] = new Point(3, 3);

    int lengths = points.length;
    convex_hull(points, lengths);
  }
}
The points in the convex hull are: (0, 3)
(0, 0)
(3, 0)
(3, 3)

උත්තල හල් ඇල්ගොරිතම සඳහා සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එම් * එන්) මෙහි n යනු ආදාන ලක්ෂ්‍ය ගණන වන අතර m යනු ප්‍රතිදාන ලක්ෂ්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) මෙහි n යනු ආදාන ලක්ෂ්‍ය ගණන වේ. මෙන්න අපි ඊළඟ අගය සොයා ගැනීම සඳහා N ප්‍රමාණයේ අරාවක් භාවිතා කරමු.

විමර්ශන