Вопрос Нестандартный поиск

Тема в разделе "PHP", создана пользователем AlexeyForpost, 18 мар 2012.

  1. AlexeyForpost

    AlexeyForpost Member

    Регистр.:
    15 июл 2009
    Сообщения:
    540
    Симпатии:
    0
    Здравствуйте.

    Есть квадратный массив данных, на главной диагонали -1, симметричен относительной главной диагонали, т.е. верхний и нижний треугольники данных равны. Например:

    -1 87 11 44 97

    87 -1 94 89 71

    11 94 -1 64 57

    44 89 64 -1 90

    97 71 57 90 -1

    Поиск элементов осуществляется по следующему алгоритму:

    1. Находим максимальный элемент, запоминаем его индексы i,j.

    2. Удаляем i,j столбцы.

    3. В i,j строке осуществляем поиск следующего максимального элемента.

    4. Удаляем столбец равный новой найденной координате (одна из координат известна, вторая новая).

    5. Затем повторяем поиск во всех строках, участвовавших до этого в поиск плюс новая координата из предыдущего шага.

    Повторяем 4,5 шаги пока не закончатся столбы.

    В итоге получится цепочка связей, которую можно представить в виде дерева, либо в виде цепочек.

    Причем если вес связи больше 70, то необходимо её "разорвать".

    В итоге, ответ должен быть в виде таблицы:

    3(индекс строки или столбца без разницы в исходном массиве) - 6(индекс строки или столбца без разницы в исходном массиве) = 11 (вес)

    И т.д.

    Если цепь/дерево разорвано, то значит надо новую таблицу строить.

    Написал скрипт для этого дела:

    [hide=25]
    PHP:
    <?

    function 
    max_arr_2x ($arr,$is)

    {

        
    $i_max;

        
    $j_max;

        
    $max=0;

     

    var_dump ($is);

            foreach (
    $is as $i)

            {

    // !!FOREACH

           

    //for ($j=0,$c_j = count ($arr[$i]);$j<$c_j;$j++)

    foreach ($arr[$i] as $j=>$v2)

                {

                    if (
    $arr[$i][$j]>$max)

                    {

                        
    $max $arr[$i][$j];

                        
    $i_max $i;

                        
    $j_max $j;

                    }

                }

            }

     

        return (array(
    $i_max,$j_max,$max));

    }

    function 
    check_used ($used)

    {

     

        for (
    $i=0,$c=count ($used);$i<c;$i++)

        {

            if (
    $used[i]==1)

            
    $result[]=$i

        }

    }

    function 
    unset_col ($j)

    {

        global 
    $tbl;

        for (
    $i=0,$c=count($tbl);$i<$c;$i++)

        unset(
    $tbl[$i][$j]);

     

    }

    function 
    is_X ($num,$X)

    {

        foreach (
    $X as $key => $x)

        {

            if (
    $t=array_search($num,$x))

            return (array (
    $key,$t));

        } 

        return (
    false);

    }

    function 
    path ()

    {

        global 
    $tbl;

        
    $rows count ($tbl)-1;

        for (
    $i=0;$i<=$rows;$i++)

        {

            
    $is[]=$i;

            
    $used[]=0;

        }

        
    $t=max_arr_2x ($tbl,$is);

        
    $weight[0][0][0][1][0]=$t[2];

        
    $X[0][0]=$t[0];

        
    $X[1][0]=$t[1];

        
    $used[$t[0]]=1;

        
    $used[$t[1]]=1;

        
    unset_col ($t[0]);

        
    unset_col ($t[1]);

        while (
    $rows>0)

        {

            
    $t=max_arr_2x ($tbl,check_used($used));

            if (
    $id=is_X($t[0]))

            {

                
    $weight[0][$id[0]][$id[1]][$id[0]+1][]=$t[2];

                
    $X[$id[0]+1][count($weight[0][$id[0]][$id[1]][$id[0]+1])-1]=$t[1];

            }

         

            else if (
    $id=is_X($t[1]))

            {

                
    $weight[0][$id[0]][$id[1]][$id[0]+1][]=$t[2];

                
    $X[$id[0]+1][count($weight[0][$id[0]][$id[1]][$id[0]+1])-1]=$t[0];

            }

         

            else { echo 
    "ERROR searching ID"; }

         

         

        
    $rows--;     

        }

        
    var_dump ($weight);

        
    var_dump ($X);

    }

    $tbl = array (array(-1,0.87,0.11,0.44,0.97),array(0.87,-1,0.94,0.89,0.71),array(0.11,0.94,-1,0.64,0.57),array(0.44,0.89,0.64,-1,0.90),array(0.97,0.71,0.57,0.90,-1));

    path();

    ?>
    Ошибки:

    array(5) { [0]=> int(0) [1]=> int(1) [2]=> int(2) [3]=> int(3) [4]=> int(4) } NULL

    Warning: Invalid argument supplied for foreach() in script.php on line 9

    Warning: Missing argument 2 for is_X(), called in script.php on line 77 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    Warning: Missing argument 2 for is_X(), called in script.php on line 83 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    ERROR searching IDNULL

    Warning: Invalid argument supplied for foreach() in script.php on line 9

    Warning: Missing argument 2 for is_X(), called in script.php on line 77 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    Warning: Missing argument 2 for is_X(), called in script.php on line 83 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    ERROR searching IDNULL

    Warning: Invalid argument supplied for foreach() in script.php on line 9

    Warning: Missing argument 2 for is_X(), called in script.php on line 77 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    Warning: Missing argument 2 for is_X(), called in script.php on line 83 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    ERROR searching IDNULL

    Warning: Invalid argument supplied for foreach() in script.php on line 9

    Warning: Missing argument 2 for is_X(), called in script.php on line 77 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    Warning: Missing argument 2 for is_X(), called in script.php on line 83 and defined in script.php on line 47

    Warning: Invalid argument supplied for foreach() in script.php on line 49

    ERROR searching IDarray(1) { [0]=> array(1) { [0]=> array(1) { [0]=> array(1) { [1]=> array(1) { [0]=> float(0.97) } } } } } array(2) { [0]=> array(1) { [0]=> int(0) } [1]=> array(1) { [0]=> int(4) } }

    [/hide]

    Честно говоря, с первой ошибки не понимаю в чем дело. Помогите, пожалуйста, разобраться. Буду признателен за помощь.
     

Поделиться этой страницей