Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Как сделать обход всех путей графа в pl/sql(желательно без самописных функций)?

88K
05 декабря 2014 года
ShaoKahn
3 / / 05.12.2014
Добрый день, есть такая задача:

В таблице содержится информация о произвольном наборе косточек домино (левое число косточки, правое число косточки). Создать программу для определения списка “рыбных” ситуаций (т.е. ситуаций, когда остается одна или более косточек исходного набора, которые некуда положить) и количества таких ситуаций.
Например, если в таблице содержится информация о наборе из трех косточек:
левое число косточки правое число косточки
2 0
2 6
1 5
то список рыбных ситуаций:
(6,2) -> (2,0) Осталась кость (1,5)
(1,5) Остались кости (2,6) , (2,0)
Количество рыбных ситуаций: 2
Примечание: программа должна предусматривать проверку правильности заполнения таблицы.


Вот в чем собственно сам вопрос:
Я делаю эту задачу по такому алгоритму, создаю 3 индексных таблицы, в 1 записываю костяшки(отдельно право и лево) и номер вершины, во 2 записываю просто костяшки(право и лево), в 3 записываю номер костяшки из первой таблицы и посищенность(тоесть если костяшка уже использована, то записываю 1, если нет то 0). Потом начинается сам перебор, внешний цикл перебирает начальные вершины(костяшки), внутренний перебирает вершины из второго массива, если есть совпадение, то начинает сравниваться уже эта вершина со всеми остальными, если весь второй массив перебран, то возвращаемся по порядку вершины на 1 назад и ищем вершины, которые ещё не использовались, но возможны для использования(например была такая комбинация 02-26-63, а возможно ещё и 02-26-61, и нам как раз и надо найти 61) и вот тут и начинается загвоздка, ведь если есть такая ситуация где у костяшки есть 3 или более продолжения, причем одно или несколько из них использованы в предыдущей комбинации, то мне никак не дойти до последнего продолжения, тоесть до того, которое стоит самым последним во второй индексной таблице, подскажите пожалуйста, как это победить?
412
06 декабря 2014 года
grgdvo
323 / / 04.07.2007
Должны очень помочь иерархические запросы. Делать циклы - это ресурсозатратно.
412
07 декабря 2014 года
grgdvo
323 / / 04.07.2007
Стало даже интересно с задачкой. Давненько я мозги не разминал :) Прошу указать на ошибки, которые я допустил
Итак... Дано какие-то "доминошки". Пусть эти доминошки заданы в таблице DICES.

 
Код:
CREATE DICES (
ID INTEGER NOT NULL,
A INTEGER NOT NULL,
B INTEGER NOT NULL
);
Поля: ID - уникальный идентификатор, A - например левая половина доминошки, B - правая половина доминошки. Вопрос уникальности оставляем за скобками, предполагая, что в DICES заданы только уникальные доминошки.

Заполгяем таблицу, например, так

 
Код:
INSERT INTO DICES (ID, A, B) VALUES (1, 2, 6);
INSERT INTO DICES (ID, A, B) VALUES (2, 2, 0);
INSERT INTO DICES (ID, A, B) VALUES (3, 1, 5);
INSERT INTO DICES (ID, A, B) VALUES (4, 0, 1);
Чтобы перебрать все комбинации, нам понадобятся зеркальные перевертыши наших доминошек. Создадим такое представление и назовем его FULLDICES.

 
Код:
CREATE VIEW FULLDICES AS
SELECT ID, A, B FROM DICES
UNION ALL
SELECT ID, B, A FROM DICES;
Ну а теперь собственно полный перебор, когда B "предыдущей" записи равно A "текущей" записи.

 
Код:
SELECT
  FD.*,
  level
FROM
  FULLDICES FD
CONNECT BY nocycle
  PRIOR B = A AND
  PRIOR ID != ID;
Первое условие соединяет записи по иерархии следования цифр, второе условие не дает использовать одну "доминошку" два раза (ибо, например, 2-6 и 6-2 --- это одна и та же "доминошка"). Дополнительно еще nocycle, чтобы избежать повторного циклического использования записей в иерархии.

Вот результат (не знаю, как таблицу вставить)

# ID A B LEVEL
1 4 0 1 1
2 3 1 5 2
3 2 0 2 1
4 1 2 6 2
5 3 1 5 1
6 4 1 0 1
7 2 0 2 2
8 1 2 6 3
9 1 2 6 1
10 2 2 0 1
11 4 0 1 2
12 3 1 5 3
13 3 5 1 1
14 4 1 0 2
15 2 0 2 3
16 1 2 6 4
17 1 6 2 1
18 2 2 0 2
19 4 0 1 3

Вроде таков ответ. По хорошему, еще надо поработать с сортировкой этого запроса. Я его шибко не проверял, возможно при большом количестве доминошек oracle будет его сортировать так, как ему вздумается, и будет тяжело отличить одну ветку выстраивания "доминошек" от другой. Ну и вопрос производительности! Честно говоря, не хочу сейчас считать возможное количество всех комбинацией всех цепочек, но можно грузануть этим запросом сервер.
88K
07 декабря 2014 года
ShaoKahn
3 / / 05.12.2014
Это нечто очень похожее на правду, но вся беда в том, что мне надо сделать с циклами на PL/SQL. А про иерархические запросы я сразу подумал как увидел задание, но к сожалению тема задания другая)...но всё равно большое спасибо за отклик. Я могу приложить своё решение( с той ошибкой, которую никак победить не могу)

Код:
DECLARE
TYPE one_tab IS RECORD (lev INTEGER(1) , prav INTEGER(1));
TYPE one_tab2 IS RECORD (lev INTEGER(1) , prav INTEGER(1) , lev1 INTEGER(1) , prav1 INTEGER(1) , shod INTEGER(1));
TYPE one_tabplus IS RECORD (lev INTEGER(1) , prav INTEGER(1), porjadok INTEGER(2));
TYPE schet IS RECORD(nom INTEGER(2) , kol INTEGER(2));
TYPE vershini IS RECORD(ind INTEGER(2) , ind2 INTEGER(2) , shod INTEGER(2));
TYPE vershini_mat IS TABLE OF vershini INDEX BY PLS_INTEGER;
TYPE newlok IS TABLE OF one_tab2 INDEX BY PLS_INTEGER;
TYPE soot IS TABLE OF schet INDEX BY PLS_INTEGER;
TYPE cep_of IS TABLE OF one_tabplus INDEX BY PLS_INTEGER;
TYPE pos IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
TYPE cep IS TABLE OF NUMBER INDEX BY PLS_INTEGER;
TYPE tab_f IS RECORD (pod one_tab , nad one_tab , assoc integer(1));
TYPE tab_is IS TABLE OF tab_f INDEX BY PLS_INTEGER;
TYPE domin IS TABLE OF one_tab INDEX BY PLS_INTEGER;
CURSOR perv IS SELECT pravo , levo FROM domino;
CURSOR vtor IS SELECT pravo , levo FROM domino;
per domin;
vto domin;
vto1 domin;
vto2 domin;
tre domin;
matr tab_is;
nomer soot;
tab_ver vershini_mat;
num INTEGER:=0;
num2 INTEGER:=0;
num3 INTEGER:=0;
num4 INTEGER:=0;
n INTEGER:=0;
m INTEGER:=0;
f INTEGER:=0;
q INTEGER:=0;
k INTEGER:=0;
b INTEGER:=0;
a INTEGER:=0;
c INTEGER:=1;
j INTEGER:=1;
l INTEGER:=0;
s INTEGER:=0;
h INTEGER:=0;
g INTEGER:=0;
u INTEGER:=0;
d INTEGER:=0;
o INTEGER:=0;
br INTEGER:=0;
aw INTEGER:=0;
z INTEGER:=0;
z2 INTEGER:=0;
z1 INTEGER:=1;
zp INTEGER:=0;
bm INTEGER:=0;
cep1 cep;
position pos;
porad cep_of;
lop newlok;
BEGIN


porad(1).porjadok:=0;

FOR i IN perv LOOP
  num:=num+1;
  per(num).lev:=i.levo;
  per(num).prav:=i.pravo;
END LOOP;

vto:=per;
vto1:=per;

WHILE(o!=num) LOOP
o:=o+1;
nomer(o).nom:=o;
nomer(o).kol:=0;

END LOOP;

LOOP
--z1:=z1+1;
exit when g=num;
g:=g+1;
aw:=0;
LOOP
EXIT WHEN aw=num;
aw:=aw+1;
if per(g).lev = per(aw).lev OR per(g).lev = per(aw).prav OR per(g).prav = per(aw).lev OR per(g).prav = per(aw).prav THEN
lop(z1).lev:=per(g).lev;
lop(z1).prav:=per(g).prav;
lop(z1).lev1:=vto(aw).lev;
lop(z1).prav1:=vto(aw).prav;
lop(z1).shod:=1;
z1:=z1+1;
ELSE
lop(z1).lev:=per(g).lev;
lop(z1).prav:=per(g).prav;
lop(z1).lev1:=vto(aw).lev;
lop(z1).prav1:=vto(aw).prav;
lop(z1).shod:=0;
z1:=z1+1;
END IF;
END LOOP;
END LOOP;
FOR i IN 1..z1-1 LOOP
 DBMS_OUTPUT.PUT_LINE(lop(i).lev||' '||lop(i).prav||' '||lop(i).lev1||' '||lop(i).prav1||' '||lop(i).shod);

END LOOP;



















/*
    LOOP -- цикл перебора правого числа
      n:=n+1;
      nomer(n).kol:=1;
      exit when n=0;
          q:=0;
          DBMS_OUTPUT.PUT_LINE('1n='||n);
        LOOP
    --   EXIT WHEN q>num;
                   q:=q+1;
       IF q>num THEN
       DBMS_OUTPUT.PUT_LINE('zashlo');
                o:=0;
            FOR i IN 1..num   LOOP
                 
               DBMS_OUTPUT.PUT_LINE('b='||b);
               nomer(i).kol:=0;
               
                  END LOOP;
       
       
                zl:=vto(1).lev;
                 zp:=vto(1).prav;
        DBMS_OUTPUT.PUT_LINE('a='||a);
               FOR i IN 1..num LOOP
     
                  IF i!=num THEN
                       vto(i).lev := vto(i+1).lev;
                        vto(i).prav := vto(i+1).prav;
                 END IF;
                  END LOOP;
                   vto(num).lev := zl;
       vto(num).prav := zp;
                  FOR i IN 1..num LOOP
               
                  DBMS_OUTPUT.PUT_LINE(per(i).lev||per(i).prav||' '||vto(i).lev||vto(i).prav);
                       
                  END LOOP;
     
     q:=0;
     n:=b-1;
     
   
     d:=0;
     EXIT;
     
     
     
        ELSIF (per(n).lev = vto(q).lev) AND q!=n AND nomer(q).kol!=1 THEN
         
         
            DBMS_OUTPUT.PUT_LINE(per(n).prav||' '||per(n).lev ||' '||' -->  '||vto(q).lev ||' '||vto(q).prav);
      d:=d+1;
       porad(d).lev:=per(n).lev;
        porad(d).prav:=per(n).prav;
         porad(d).porjadok:=d;
         b:=n;
            n:=q;
            a:=q;
            nomer(q).kol:=1;
                      q:=0;      
                CONTINUE;  
               ELSIF (per(n).lev = vto(q).prav) AND q!=n AND nomer(q).kol!=1 THEN
                   DBMS_OUTPUT.PUT_LINE(per(n).prav||' '||per(n).lev ||' -->  '||vto(q).prav ||' '||vto(q).lev);
                  d:=d+1;
       porad(d).lev:=per(n).lev;
        porad(d).prav:=per(n).prav;
         porad(d).porjadok:=d;
         
      nomer(q).kol:=1;
           b:=n;
                 n:=q;
     a:=q;
                    q:=0;  
                   CONTINUE;
                   
                   ELSIF(per(n).prav = vto(q).prav) AND q!=n  AND nomer(q).kol!=1 THEN
                       DBMS_OUTPUT.PUT_LINE(per(n).lev||' '||per(n).prav ||' '||' -->  '||vto(q).prav ||' '||vto(q).lev);
             d:=d+1;
       porad(d).lev:=per(n).lev;
        porad(d).prav:=per(n).prav;
         porad(d).porjadok:=d;
     nomer(q).kol:=1;
      b:=n;
                    n:=q;
                 a:=q;
                    q:=0;  
                     
                       CONTINUE;
               
               
                ELSIF(per(n).prav = vto(q).lev) AND q!=n  AND nomer(q).kol!=1 THEN
                       DBMS_OUTPUT.PUT_LINE(per(n).lev||' '||per(n).prav ||' '||' --> '|| vto(q).lev||' '||vto(q).prav );
                d:=d+1;
       porad(d).lev:=per(n).lev;
        porad(d).prav:=per(n).prav;
         porad(d).porjadok:=d;
                     
       nomer(q).kol:=1;
        b:=n;
                    n:=q;
           
                 a:=q;
                 q:=0;  
                       
                       CONTINUE;
                  END IF;
             
              END LOOP;
         
           exit when n=num  ;
         
        END LOOP;
           
                */
     
















END;
412
08 декабря 2014 года
grgdvo
323 / / 04.07.2007
Уххххх....! :)) Такой объем кода!! У меня просто нет времени во всем разобраться.
Могу предложить компромис. Если нужны циклы, то мой запрос можно легко адаптировать, чтобы он строил дерево комбинаций для заданной фишки. Добавьте START WITH A=... AND B=... перед CONNECT BY. И этот SELECT оберните в цикл по всем фишкам из FULLDICES.
88K
08 декабря 2014 года
ShaoKahn
3 / / 05.12.2014
Да нагородил там реально много) самое обидное, что не работает. Я кстати ваш код тоже протестировал и он , к сожалению, тоже не срабатывает как надо(...при чуть большем количестве фишек начинается что то вроде зацикливания, то есть в одной цепочке попадаются одни и те же фишки, например 02-24-46-62-20. Я попытался сделать через запись курсора в массив и потом отделить по уровню, но к сожалению пока не нашел явного признака отличия 1ой цепочки от другой. То есть в том же самом примере у 02 уровень может быть 1 и может быть 5.
412
10 декабря 2014 года
grgdvo
323 / / 04.07.2007
Цитата:
при чуть большем количестве фишек начинается что то вроде зацикливания, то есть в одной цепочке попадаются одни и те же фишки, например 02-24-46-62-20


не должно быть такого! Фишка в DICES должна создаваться один раз, а в FULLDICES она инвертируется с сохранением ID. Потом в запросе идет проверка, чтобы PRIOR ID != ID. может быть вы создали в DICES две "как бы одинаковые" фишки??! я позже смогу проверить указанную ситуацию.

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог