Goal Search Algorithm

Descrizione:
L’algoritmo di ricerca Goal è l’algoritmo di ricerca del limite di una sequenza monotona crescente limitata superiormente.

1. Finalità:

Ricerca del limite di una sequenza monotona crescente limitata superiormente.

2. Esempio:

Supponiamo di voler creare una torre di 10 metri con una tolleranza di 10 millimetri, avendo un dato numero di mattoni, ciascuno di altezza differente, impilati uno sull’altro. Per costruire la torre saremo quindi obbligati ad utilizzare i mattoni seguendo un accesso Last In First Out
Supponiamo di chiamare questa pila di mattoni XdataTable:
908
906
832
454
464
522
45
229
5057
433
930
214
1
1
1
2
1
219
1
83
1
3
82
424
2
58
30
24
461
675
Tramite il lancio dello script goal_search_procedure.sql verrà restituita la seguente successione di mattoni (XdataTableTarget), con in evidenza i mattoni non utilizzati, che ci consentirà di realizzare la nostra torre.
908
906
832
454
464
522
45
229
5057
433
930
214
1
1
1
2
1
219
1
83
1
3
82
424
258
30
24
461
675

3. Esempio di preparazione dell’ambiente
   Per comodità segue lo script preparato per l’esempio precedente.

———————————
— TEST ENVIROMENT PREPARATION —
———————————
CREATE TABLE XDataTable
(
SortId NUMBER,
DataValue NUMBER
)
TABLESPACE TFTCUS04
LOGGING
NOCOMPRESS
NOCACHE
MONITORING;
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (1, 908);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (2, 906);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (3, 832);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (4, 454);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (5, 464);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (6, 522);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (7, 45);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (8, 229);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (9, 5057);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (10, 433);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (11, 930);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (12, 214);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (13, 1);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (14, 1);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (15, 1);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (16, 2);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (17, 1);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (18, 219);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (19, 1);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (20, 83);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (21, 1);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (22, 3);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (23, 82);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (24, 424);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (25, 2);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (26, 58);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (27, 30);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (28, 24);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (29, 461);
INSERT INTO XDATATABLE (SortId, DataValue) VALUES (30, 675);
CREATE TABLE XDataTableSorted
(
Row_Id NUMBER,
DataValue NUMBER,
FLAG_JUMP NUMBER,
SumDataValue NUMBER
)
TABLESPACE TFTCUS04
LOGGING
NOCOMPRESS
NOCACHE
MONITORING;
CREATE TABLE XDataTableTemp
(
Row_Id NUMBER,
DataValue NUMBER,
FLAG_JUMP NUMBER,
SumDataValue NUMBER
)
TABLESPACE TFTCUS04
LOGGING
NOCOMPRESS
NOCACHE
MONITORING;
CREATE TABLE XDataTableTarget
(
Row_Id NUMBER,
DataValue NUMBER,
SumDataValue NUMBER,
WeightDataValue NUMBER
)
TABLESPACE TFTCUS04
LOGGING
NOCOMPRESS
NOCACHE
MONITORING;
COMMIT;

4. goal_search_procedure.sql script

:
Il seguente script cerca e restituisce la successione desiderata
/*
File: goal_search_procedure.sql
Date of creation: 2014-11-07
Description: Goal search algorithm or search algorithm of the limit of a monotonically increasing sequence bounded above.
Autore:
*/
DECLARE
SumDataValueProgr NUMBER DEFAULT 0;
Tollerance NUMBER;
TargetValue NUMBER;
i NUMBER;MaxRowId NUMBER;
NoMoreData NUMBER DEFAULT 0;
BEGIN
— Variable initialization
Tollerance := 10;
TargetValue := 10000;
dbms_output.put_line(‘Tollerance: ‘|| Tollerance);
dbms_output.put_line(‘TargetValue: ‘|| TargetValue);
— Preparation of XDataTableSorted table (elaboration table) with the data of the DataTableSource table (source table)
DELETE FROM XDataTableSorted;
dbms_output.put_line(‘DELETE FROM XDataTableSorted’);
INSERT INTO XDataTableSorted (Row_Id, DataValue, FLAG_JUMP, SumDataValue)
SELECT SortId Row_Id,
DataValue,
0 AS FLAG_JUMP,
SUM (DataValue) OVER (ORDER BY SortId ASC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS SumDataValue
FROM XDataTable
WHERE 1=1
ORDER BY SortId
;
dbms_output.put_line(‘INSERT INTO XDataTableSorted’);
SELECT MAX(Row_Id) INTO MaxRowId
FROM XDataTableSorted;
dbms_output.put_line(‘MaxRowId: ‘|| MaxRowId);
— Preparation of XDataTableTarget table (results table)
DELETE FROM XDataTableTarget;
dbms_output.put_line(‘DELETE FROM XDataTableTarget’);
commit;
— Loop of search of SumDataValue value as much as possible near at TargetValue value
— CoverLoop: LOOP
<> LOOP
SELECT MIN(Row_Id) INTO i
FROM (
SELECT FLAG_JUMP, SUM(DataValue) OVER (ORDER BY Row_Id) SumDataValue, Row_Id
FROM XDataTableSorted
WHERE 1=1
AND FLAG_JUMP <> 1
) CalcSumDataValueProgr
WHERE SumDataValue > TargetValue
AND FLAG_JUMP <> 1
;
dbms_output.put_line(‘i: ‘|| i);
IF (i IS NULL) THEN
SELECT MAX(Row_Id)+1 INTO i
FROM (
SELECT FLAG_JUMP, SUM(DataValue) OVER (ORDER BY Row_Id) SumDataValue, Row_Id
FROM XDataTableSorted
WHERE 1=1
AND FLAG_JUMP <> 1
) CalcSumDataValueProgr
WHERE 1=1
AND FLAG_JUMP <> 1
;
dbms_output.put_line(‘exNull i: ‘|| i);
SELECT distinct(FLAG_JUMP) INTO NoMoreData
FROM XDataTableSorted
WHERE Row_Id > i or Row_Id = MaxRowId;
END IF;
— SET i = i – 1
i := i – 1;
dbms_output.put_line(‘i – 1: ‘|| i);
SELECT SumDataValue INTO SumDataValueProgr
FROM (
SELECT FLAG_JUMP, SUM(DataValue) OVER (ORDER BY Row_Id) SumDataValue, Row_Id
FROM XDataTableSorted
WHERE 1=1
AND FLAG_JUMP <> 1
) CalcSumDataValueProgr
WHERE Row_Id = i
;
dbms_output.put_line(‘SumDataValueProgr: ‘|| SumDataValueProgr);
— Verifies that (TargetValue > SumDataValueProgr-Tolerance) or that has arrived at the last Row_Id
IF (SumDataValueProgr > TargetValue – Tollerance) OR (i = MaxRowId) OR (NoMoreData = 1)
THEN
— Set FLAG_JUMP = 1 for all bad deal/records that satisfy the condition
UPDATE XDataTableSorted
SET FLAG_JUMP = 1, SumDataValue = 0
WHERE DataValue > ABS((TargetValue – Tollerance) – SumDataValueProgr)
AND Row_Id > i
;
dbms_output.put_line(‘UPDATE EXIT XDataTableSorted – FLAG_JUMP = 1′);
— Preparation of XDataTableTemp table (temporary support table)
DELETE FROM XDataTableTemp;
dbms_output.put_line(‘DELETE FROM XDataTableTemp’);
— Populating of the XDataTableTemp table (temporary support table)
INSERT INTO xdatatabletemp (Row_Id, DataValue, FLAG_JUMP, SumDataValue)
SELECT Row_Id,
DataValue,
FLAG_JUMP,
SUM (DataValue) OVER (ORDER BY Row_Id ASC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS SumDataValue
FROM XDataTableSorted
WHERE 1=1
and FLAG_JUMP = 0
;
dbms_output.put_line(‘INSERT INTO XDataTableTemp’);– Update sumdatavalue for all deal/records Ok (x FLAG_JUMP = 0) that satisfy the condition
UPDATE xdatatablesorted
SET sumdatavalue = (SELECT xdatatabletemp.sumdatavalue
FROM xdatatabletemp
WHERE xdatatabletemp.row_id = xdatatablesorted.row_id)
WHERE EXISTS (SELECT xdatatabletemp.sumdatavalue
FROM xdatatabletemp
WHERE xdatatabletemp.row_id = xdatatablesorted.row_id);
dbms_output.put_line(‘UPDATE XDataTableSorted – sumdatavalue x FLAG_JUMP = 0′);
— Insert the records that were identified as OK from CoverLoop into the XDataTableTarget table
INSERT INTO XDataTableTarget (Row_Id, DataValue, SumDataValue, WeightDataValue)
SELECT Row_Id
,DataValue
,SumDataValue
,1 AS WeightDataValue
FROM (
SELECT Row_Id
,DataValue
,SUM(DataValue) OVER (ORDER BY Row_Id) SumDataValue
FROM XDataTableSorted
WHERE 1=1
AND FLAG_JUMP = 0
) SDTable
;
dbms_output.put_line(‘INSERT INTO XDataTableTarget – FLAG_JUMP = 0 – ‘|| SumDataValueProgr);
— Insert the records that were identified as discarded from CoverLoop into the XDataTableTarget table
INSERT INTO XDataTableTarget (Row_Id, DataValue, SumDataValue, WeightDataValue)
SELECT Row_Id
,DataValue
,0 AS SumDataValue
,0 AS WeightDataValue
FROM (
SELECT Row_Id
,DataValue
FROM XDataTableSorted
WHERE 1=1
AND FLAG_JUMP = 1
) SDTable
;
dbms_output.put_line(‘INSERT INTO XDataTableTarget – FLAG_JUMP = 1 – ‘|| SumDataValueProgr);
commit;
— EXIT CoverLoop
EXIT CoverLoop;
ELSE
— Set FLAG_JUMP = 1 for all bad deal/records that satisfy the condition
UPDATE XDataTableSorted
SET FLAG_JUMP = 1, SumDataValue = 0
WHERE DataValue > ABS((TargetValue – Tollerance) – SumDataValueProgr)
AND Row_Id > i
;
dbms_output.put_line(‘UPDATE XDataTableSorted – FLAG_JUMP = 1′);
— Preparation of XDataTableTemp table (temporary support table)
DELETE FROM XDataTableTemp;
dbms_output.put_line(‘DELETE FROM XDataTableTemp’);
— Populating of the XDataTableTemp table (temporary support table)
INSERT INTO xdatatabletemp (Row_Id, DataValue, FLAG_JUMP, SumDataValue)
SELECT Row_Id,
DataValue,
FLAG_JUMP,
SUM (DataValue) OVER (ORDER BY Row_Id ASC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS SumDataValue
FROM XDataTableSorted
WHERE 1=1
and FLAG_JUMP = 0
;
dbms_output.put_line(‘INSERT INTO XDataTableTemp’);
— Update sumdatavalue for all deal/records Ok (x FLAG_JUMP = 0) that satisfy the condition
UPDATE xdatatablesorted
SET sumdatavalue = (SELECT xdatatabletemp.sumdatavalue
FROM xdatatabletemp
WHERE xdatatabletemp.row_id = xdatatablesorted.row_id)
WHERE EXISTS (SELECT xdatatabletemp.sumdatavalue
FROM xdatatabletemp
WHERE xdatatabletemp.row_id = xdatatablesorted.row_id);
dbms_output.put_line(‘UPDATE XDataTableSorted – sumdatavalue x FLAG_JUMP = 0′);
commit;
END IF;
END LOOP CoverLoop;
END;

5. goal_search_procedure.sql output:

— ******************************************************************************** —
/*
DBMS_OUTPUT
Tollerance: 10
TargetValue: 10000
DELETE FROM XDataTableSorted
INSERT INTO XDataTableSorted
MaxRowId: 30
DELETE FROM XDataTableTarget
i: 11
i – 1: 10
SumDataValueProgr: 9850
UPDATE XDataTableSorted – FLAG_JUMP = 1
DELETE FROM XDataTableTemp
INSERT INTO XDataTableTemp
UPDATE XDataTableSorted – sumdatavalue x FLAG_JUMP = 0
i: 23
i – 1: 22
SumDataValueProgr: 9944
UPDATE XDataTableSorted – FLAG_JUMP = 1DELETE FROM XDataTableTemp
INSERT INTO XDataTableTemp
UPDATE XDataTableSorted – sumdatavalue x FLAG_JUMP = 0
i:
exNull i: 29
i – 1: 28
SumDataValueProgr: 10000
UPDATE EXIT XDataTableSorted – FLAG_JUMP = 1
DELETE FROM XDataTableTemp
INSERT INTO XDataTableTemp
UPDATE XDataTableSorted – sumdatavalue x FLAG_JUMP = 0
INSERT INTO XDataTableTarget – FLAG_JUMP = 0 – 10000
INSERT INTO XDataTableTarget – FLAG_JUMP = 1 – 10000
*/
— ************