минимальная площадь треугольников

      Комментарии к записи минимальная площадь треугольников отключены

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 3 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #3341

    Kros11
    Участник

    Нашла готовое решение, объясните как работает и что делает каждая строка, все таки хочется разобраться (для себя). Если будет свободное время у кого нибудь, т.к. уже сдавать эту программу мне не надо, что я должна была сделать и как работает этот код. И мне кажется, что тут много лишнего.
    Задача:

    Дан набор из 3*N точек на плоскости (координаты X и Y — целые числа), причем любые три точки этого набора не лежат на одной прямой. Необходимо разбить набор на N групп точек (по три точки в группе), чтобы точки каждой группы будут являться вершинами треугольника. Задача состоит в нахождении такого разбиения на группы, чтобы суммарная площадь всех треугольников была минимальной.

    Решение:

    domains
      point=p(integer,integer)
      pl=point*
      pll=pl*
    facts
      determ sq(real)
      determ tr(pll)
    predicates
      sort(pl,pl,pl)
      insert(point,pl,pl)
      nondeterm subset(integer,pl,pl,pl)
      nondeterm razbit_treug(pl,pll,real,real)
      treug_1(pl,real,real)
      nondeterm treug(pl,pll,real)
    clauses
      sort([A|T],SL,L):- 
        insert(A,SL,SL1),
        sort(T,SL1,L).
      sort([],L,L).
    
      insert(p(H,Z),[p(X,Y)|T],[p(X,Y)|L]):- 
        H > X,!,insert(p(H,Z),T,L).
      insert(A,L,[A|L]).
    
      subset(0,L,[],L).
      subset(K,[A|L],[A|T],R):- K1=K-1,
        subset(K1,L,T,R).
      subset(K,[A|L],T,[A|R]):- 
        K > 0,subset(K,L,T,R).
    
      razbit_treug([p(X1,Y1)|L],[[p(X1,Y1),p(X2,Y2),p(X3,Y3)]|LL],S,Sq):-
        sq(Curr), 
        subset(2,L,[p(X2,Y2),p(X3,Y3)],Rest),
        S1 = S+0.5*abs((X2-X1)*(Y3-Y1)-(X3-X1)*(Y2-Y1)),
        S1 <= Curr, razbit_treug(Rest,LL,S1,Sq).
      razbit_treug([],[],Sq,Sq):- 
        sq(Curr),Sq < Curr,
        retract(sq(Curr)), assert(sq(Sq));
        sq(Sq).
    
      treug_1([p(X1,Y1),p(X2,Y2),p(X3,Y3)|L],S,Sq):-
        S1=S+0.5*abs((X2-X1)*(Y3-Y1)-(X3-X1)*(Y2-Y1)),
        treug_1(L,S1,Sq).
      treug_1([],Sq,Sq):- assert(sq(Sq)).    
    
      treug(L,LL,S):- 
        razbit_treug(L,TR,0.0,_),
        retractall(tr(_)),assert(tr(TR)),fail;
        sq(S),tr(LL).
    goal
      L=[p(2,1),p(0,5),p(3,8),p(1,1),p(2,3),p(3,2),p(4,5),p(5,4),p(9,9),p(6,7),p(7,6),p(0,9)],
      sort(L,[],L1),treug_1(L1,0.0,_),treug(L1,LL,S),
      write("Площадь = ",S,"n",LL),nl,nl.

  • #3343

    Я не особо долго думал над задачей, но в прошлый раз я предлагал построить выпуклую оболочку (возможно из этого можно как-то получить эффективную реализацию). При построении выпуклой оболочки точки сортируются по одной из координат (например по X), а затем обходятся (например слева направо).

    У вас в решении точки тоже сортируются — для этого используются методы sort и insert. Используется алгоритм сортировки вставками (по ссылке он очень подробно описан). Я не понял зачем в вашем решении сортировать точки, т.к. затем используется генерация подмножеств, т.е. перебор всех вариантов треугольников.

    Функция генерации подмножеств (subset) описана в теме «генерация перестановок на Prolog«.

    Треугольник в программе описывается в виде множества точек. Описание типа точки: point=p(integer,integer); треугольника (список точек): pl=point*; списка треугольников: pll=pl*. Я бы советовал использовать более «говорящие» имена переменных. Подробней про это можно прочитать в статье «Теория чистого кода» (с Prolog она не связана, но в ней описано как писать хороший код по мотивам книги Роберта Мартина).

    Результат работы программы накапливается в базе данных — в секции facts описано два типа записей БД — sq(real) хранит площадь, а tr(pll) — список треугольников. Для работы с БД используются предикаты retract и assert, прочитать про них подробней можно в теме «Сохранение изменений assert и retract«.

    Отсортированные точки подаются на вход функции treug_1, которая выбирает точки по три штуки, считает площадь треугольника, полученного на трех точках и прибавляет это к сумме площадей всех остальных треугольников. Когда список кончится — результат (суммарная площадь) поместится в БД (вызов assert). Обратите внимание, что функция не сработает, если число точек не кратно трем.

    Функция treug выбирает вызывает razbit_treug, которая перебирает варианты подмножеств треугольников и чтобы перебирать все варианты используется fail, запускающий механизм перебора с возвратами. Подробнее про это можно почитать в статьях «Введение в логическое программирование» и «Принципы построения Prolog-программ«.

    Функция razbit_treug создает список треугольников, каждый следующий из которых по площади больше всех предыдущих. Для этого из поданного на вход списка точек выбирается первая p(X1,Y1), из остальной части списка при помощи subset выбирается подмножество из двух других точек ([p(X2,Y2),p(X3,Y3)]). Из этих трех точек строится треугольник, к переменной S (в которой хранится сумма всех предыдущих треугольников) добавляется его площадь и результат сравнивается со значением текущего максимума из базы данных. Если новая площадь меньше предыдущей — значит треугольник, построенный по этим трем точкам не должен быть добавлен к результату. Надо понимать, что использование subset обеспечивает перебор всех возможных вариантов треугольников, которые можно построить с использованием первой точки. После этого первая точка пропускается и рекурсивно обрабатываются остальные точки. Если же площадь с новым треугольником больше предыдущего максимума — изменяется значение максимума из БД — для этого старая запись удаляется с retract и добавляется новая с assert.

Для ответа в этой теме необходимо авторизоваться.