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

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

  1. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    739
    Симпатии:
    226
    Здравствуйте.
    Есть квадратный массив данных, на главной диагонали -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 (вес)
    И т.д.
    Если цепь/дерево разорвано, то значит надо новую таблицу строить.

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

    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) } }


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

    noxwell Создатель

    Регистр.:
    23 июн 2011
    Сообщения:
    13
    Симпатии:
    9
    Можешь в теории графов объяснить. Я вижу граф представленный матрицей смежности, но из условия непонятно, что в нем нужно найти.
     
    Iwashka нравится это.
  3. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    739
    Симпатии:
    226
    Да, можно представить и как граф, в котором циклов не будет. Но вот поиск осуществляется только по матрице и аналогов алгоритма нет, необходимо понять из слов.
    Продемонстрирую работу алгоритма на примере:
    -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. Находим макс. элемент во всей матрице - это 97. Индекс его 1;5 или 5;1 не принципиально. Значит первой парой у нас будет 1 и 5.
    2. Удаляем столбцы 1 и 5:
    87 11 44
    -1 94 89
    94 -1 64
    89 64 -1
    71 57 90
    3. Только в 1 и 5 строке находим максимальный элемент с учетом удаленных столбцов - 90. Его индекс 4;5 или 5;4 не принципиально. Значит 4 будет соединена с 5м элементом.
    4.Удаляем 4й столбец:
    87 11
    -1 94
    94 -1
    89 64
    71 57
    5. Осуществляем поиск максимального элемента в 1,4,5 строках - 89. Его индекс 2,4 или 4,2. Удаляем 2й столбец.
    11
    94
    -1
    64
    57
    6.Осуществляем поиск максимального элемента в 1,4,5 строках - 94. Его индекс 2,3 или 3,2. Удаляем 3й столбец.
    7. Столбцы закончились - обход завершен.

    В графах или деревьях можно представить вот так. Прошу прощения, веса представил в 100 раз меньше. Но думаю суть будет понятна.
    [​IMG]
    Получился очень легкий пример, потому как был взят из головы. Бывает что от одного родителя может быть и пять, и десять потомков.
     
    Iwashka нравится это.
  4. noxwell

    noxwell Создатель

    Регистр.:
    23 июн 2011
    Сообщения:
    13
    Симпатии:
    9
    Много, много ошибок :) Вот рабочий вариант:

    PHP:
    <?
    function 
    max_arr_2x ($arr,$is)
    {
        
    $i_max;
        
    $j_max;
        
    $max=0;
     
    var_dump ($is);
    echo (
    "<= var_dump (\$is)<br />");
            foreach (
    $is as $i)
            {
    // !!FOREACH
     
    //for ($j=0;$j<count ($arr[$i]);$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;$i<$c=count ($used);$i++)
        {
            if (
    $used[$i]==1)
            
    $result[]=$i;
        }
        return 
    $result;
    }
     
    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 (
    in_array($num,$x))
                return (array (
    $key,array_search($num,$x)));
        }
        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;
        
    var_dump($t); echo "<=\$t <br />";
        
    unset_col ($t[0]);
        
    unset_col ($t[1]);
        
    unset_col ($t[2]);
        while (
    $rows>0)
        {
            
    $t=max_arr_2x ($tbl,check_used($used));
            if (
    $id=is_X($t[0],$X))
            {
                
    $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];
                
    $used[$t[1]]=1;
            }
     
            else if (
    $id=is_X($t[1],$X))
            {
                
    $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];
                
    $used[$t[0]]=1;
            }
     
            else { echo 
    "ERROR searching ID<br />"; }
            
    unset_col ($t[0]);
            
    unset_col ($t[1]);
            
    unset_col ($t[2]);
            
    $rows--;
        }
        
    var_dump ($weight);
        echo (
    "<=var_dump (\$weight); <br />");
        
    var_dump ($X);
        echo (
    "<=var_dump (\$X); <br />");
    }
    $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();
    ?>
     
    Iwashka и LEXAlForpostl нравится это.