Goal Search Algorithm

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

  1. Finalità:
  2. Ricerca del limite di una sequenza monotona crescente limitata superiormente.

  3. Esempio:
  4. 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

  5. Esempio di preparazione dell’ambiente
    Per comodità segue lo script preparato per l’esempio precedente.
  6. ———————————
    — 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;

  7. goal_search_procedure.sql script
  8. :
    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;

  9. goal_search_procedure.sql output:
  10. — ******************************************************************************** —
    /*
    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
    */
    — ************

Potrebbero interessarti anche...