Добрый вечер, дорогие форумчане! Программирую алгоритм транспортной задачи методом минимального элемента, чтобы получить первый опорный план и перейти к методу потенциалов. Столкнулся с проблемой: Никак не могу понять, почему не ищутся правильно индексы минимального элемента. Они (инлдексы0 вначале находят правильный элемент, а потом идут на (0;0), и всегда (0;0), хотя функция по их поиску работает правильно. Вот код: Код (PHP): // Матрица тарифов $c = array( array(2,5,2), array(4,1,5), array(3,6,8) ); // Запасы груза $m = array(90,400,110); // Потребности в грузе $n = array(140,300,160); function MinTarif($c,$m, $n) { $X = array(); for ($i=0; $i < count($m); $i++) { for ($j=0; $j < count($n); $j++) { $X[$i][$j]=-1; } } $k=0; $t=0; for ($i=0; $i < count($c); $i++) { for ($j=0; $j < count($c[0]); $j++) { $k = getIndexi($c); $t = getIndexj($c); $minPost = min($m[$k],$n[$t]); // Минимальная поставка в строке или столбце $X[$k][$t] = $minPost; // Загружаем поставку if($minPost == $m[$k]) { $n[$t] -= $m[$k]; $m[$k]=0; $c = ZamenaStroki($c,$k); } if($minPost == $n[$t]) { $m[$k] -= $n[$t]; $n[$t]=0; $c = ZamenaStolbca($c,$t); } } } return $X; } В функции я передаю матрицу тарифов $c, массив с запасами груза $n, и массив с потребностями $n. Результат, соответственно, я записываю в Матрицу поставок $X. Иду по матрице тарифов, ищу и запоминаю индексы минимального элемента с помощью функции getIndexi() и getIndexj() соответственно. Вот эти функции: Код (PHP): function getMin($arr) { static $res = array(); foreach ($arr as $k => $v) { if(is_array($v)) getMin($v); else{ if($v != 0) $res[] = $v; } } return !empty($res) ? min($res) : 0; } function getIndexi($ab) { $k=0; for ($i=0; $i < count($ab); $i++) { for ($j=0; $j < count($ab[0]); $j++) { if($ab[$i][$j] == getMin($ab)) $k = $i; } } return $k; } function getIndexj($ab) { $t=0; for ($i=0; $i < count($ab); $i++) { for ($j=0; $j < count($ab[0]); $j++) { if($ab[$i][$j] == getMin($ab)) $t = $j; } } return $t; } Функция getMin() возвращает минимальный элемент двумерного массива. Причем пропуская нули. То есть если в матрице есть нули, то функция работает как continue в цикле for. (P. S. я писал функцию поиска мин элемента в двумерном массиве сам, она пропускала нули, но если первый элемент матрицы был бы 0, она брала его за минимум, так как я стартовал с первого элемента, но не суть). Далее в самой MinTarif() я ищу минимальную поставку в массивах $m и $n, и записываю её в матрицу погрузок $X. После этого я проверяю, какая была поставка минимальна и, в соответствии с этим, зануляю элементы массива, а так же заменю нулями строку или столбец матрицы $c (в зависимости, чьи потребности были удовлетворены) функциями ZamenaStroki() и ZamenaStolbca() соответственно. Вот они: Код (PHP): function ZamenaStroki($c, $stroka) { for ($i=0; $i < count($c[0]); $i++) { $c[$stroka][$i] = 0; } return $c; } function ZamenaStolbca($c,$stolbec) { for ($i=0; $i < count($c); $i++) { $c[$i][$stolbec] = 0; } return $c; } Проблема вот в чем: первый элемент ищется нормально. Всё зануляется, всё работает. А дальше, индексы минимального элемента принимается (0;0), т.е. первый элемент. И всегда последующий становится первым элементом... Возможно проблема в цикле или ещё в чём-то. Если можете, подскажжите, пожалуйста. Заранее спасибо! ============================================== Кратко о методе минимального элемента в транспортной задаче: В матрице тарифов ищется минимальный элемент запоминаются его индексы $k, $t. Затем в матрицу погрузок вносится минимальный элемент из массивов запасов и потребностей min($m[$k],$n[$t]). В массиве $m[k] (или $n[$t]) этот минимальный элемент зануляется путём вычитания из него большего, а матрице тарифов вычёркивается строка (или столбец), считая, что потребности поставщика (или получателя) удовлетворены, т.е.$m[k]=0 (или $n[k]=0). И далее идёт до тех пор, пока не будут удовлетворены все потребности, т.е. массив $m и $n должны быть будут пустыми.
А почему бы не научить getMin возвращать сразу индексы, зачем столько функций городить? getMin в нынешнем варианте мне совсем не нравится, ещё и рекурсивная на кой-то хрен... Чем плоха та, что мы в прошлом посту делали? Смотрите, как красиво её можно переделать под задачу: http://phpfiddle.org/lite/code/yx2w-idjr (Здесь можно убедиться, что работает) Код (PHP): <?php $ab = array( array(5,0,0), array(0,4,0), array(0,2,0) ); function MinElem($arr) { $min = array ("value"=>$arr[0][0], "col"=>0, "row"=>0); for ($i=0; $i < count($arr); $i++) { for ($j=0; $j < count($arr[0]); $j++) { if($arr[$i][$j]==0) continue; if($min["value"]>$arr[$i][$j] || $min["value"] == 0 && $arr[$i][$j] != 0) { $min["value"] = $arr[$i][$j]; $min["col"] = $j; $min["row"] = $i; } } } return $min; } var_export(MinElem($ab)); ?> Добавлено спустя 1 минуту 41 секунду: Правда, я по привычке написал первым столбец, а вторым строку, но думаю, вы поймёте. если $min = MinElem($ab), то минимальный элемент это $ab[$min["row"]][$min["col"]] Добавлено спустя 2 минуты 29 секунд: Вот это, к сожалению, для меня китайский язык, так что что дальше вы делаете неверно, не могу сказать. Добавлено спустя 7 минут 37 секунд: А что мы должны получить на выходе? И что значит вычёркивается строка или столбец? Типа, если $m[$k] < $n[$t], то строка, а если наоборот, то столбец? Вы, кстати, не вычёркиваете, а зануляете строку или столбец. Хотя может в вашем случае это одно и тоже.
Реализовал ради интереса алгоритм. Ответ получился для ваших данных Код (Text): $X = array ( 0 => array ( 0 => 90, 1 => -1, 2 => -1, ), 1 => array ( 0 => -1, 1 => 300, 2 => 100, ), 2 => array ( 0 => 50, 1 => -1, 2 => 60, ), ) Верно? Но кажется мне, что для некоторых исходных данных алгоритм может зациклится. Если интересно, реализацию кинуть могу
Абсолютно верный ответ. Можете, пожалуйста, написать, как сделали? Добавлено спустя 19 минут 30 секунд: На выходе должна быть матрица загрузок $X. Строка или столбец вычёркивается (если решать на листочке от руки), когда удовлетворены потребности поставщиков или потребителей, т.е. ищем мин элемент в матрице тарифов, загружаем мин поставку min($m[$k], $n[$t]); в $X и если $m[$k] < $n[$t], тогда из $n[$t] вычитается $m[$k], $m[$k] становится равным нулю и значит, что удовлетворена потребность поставщика и вычеркивается (или зануляется) строка в матрице тарифов, соответствующая индексу $k, иначе если $m[$k] > $n[$t], то так же вычитается из большего меньшее вычёркивается столбец, соответствующий $t. и так до тех пор, пока массивы $m и $n не будут пустыми. Поставщики ($m) это строки, потребители ($n) это столбцы.
Код (PHP): <?php function MinElem($arr) { $min = array ("value" => $arr[0][0], "col" => 0, "row" => 0); for ($i = 0; $i < count($arr); $i++) { for ($j = 0; $j < count($arr[0]); $j++) { if ($arr[$i][$j] == 0) continue; if ($min["value"] > $arr[$i][$j] || $min["value"] == 0 && $arr[$i][$j] != 0) { $min["value"] = $arr[$i][$j]; $min["col"] = $j; $min["row"] = $i; } } } return $min; } function nullRow(&$a, $row) { for ($i = 0; $i < count($a[$row]); $i++) $a[$row][$i] = 0; } function nullCol(&$a, $col) { for ($i = 0; $i < count($a); $i++) $a[$i][$col] = 0; } function isNull($a) { foreach ($a as $v) { if ($v) return false; } return true; } // Матрица тарифов $c = array ( array (2, 5, 2), array (4, 1, 5), array (3, 6, 8) ); // ПОставка $X = array (array (-1, -1, -1), array (-1, -1, -1), array (-1, -1, -1)); // Запасы груза $m = array (90, 400, 110); // Потребности в грузе $n = array (140, 300, 160); while (!isNull($m) || !isNull($n)) { $min = MinElem($c); $k = $min["row"]; $t = $min["col"]; $mm = min($m[$k], $n[$t]); $X[$k][$t] = $mm; if ($m[$k] == $mm) { $n[$t] -= $m[$k]; $m[$k] = 0; nullRow($c, $k); } else { $m[$k] -= $n[$t]; $n[$t] = 0; nullCol($c, $t); } } var_export($X); ?> Единственное, у вас и в алгоритме не учтён один момент - а если исходные данные таковы, что матрица $c обнулится раньше, чем массивы $m и $n, что тогда? Пока он зациклится. А так сам алгоритм сделан как вы описали. Может, конечно, можно это всё оптимизировать, но пока так.
Спасибо, большое за помощь! Матрица $c не сможет обнулиться быстрее, потому что в ней должны присутствовать элементы больше нуля.Она в любом случае обнуляется только,когда обнуляется $m или $n. Спасибо большое ещё раз! Самая лёгкая часть программы сделана) Осталась самая сложная - метод потенциалов. Но без труда ничего не получится)
Аааа, понял о чём вы. Нет, такого случая не будет. Так как если вместо 90 будет 120, то сумма элементов $m будет больше суммы $n, значит транспортная задача считается открытой и её нужно привести к закрытой форме. Для этого вводится фиктивный поставщик (или потребитель), т.е. добавляется в массив с меньшей суммой та разность, которая получается при вычитании из большего. И задача снова сводится к закрытой и снова будет всё работать)) То есть сумма массивов всегда равна. И сумма элементов, которые получаются на выходе в матрице $X (кроме -1) тоже равна сумме массива $m или $n) Так что ваш алгоритм 100% рабочий! Спасибо еще раз за помощь! (ЛС).