Перебор всевозможных вариантов

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

  1. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    708
    Симпатии:
    225
    Здравствуйте.
    Есть квадратная таблица NxN.
    Шаги работы алгоритма:
    1. Находим максимальный элемент в таблице с индексами i,j.
    2. Далее удаляем столбцы i и j.
    3. Ищем максимальный элемент в строках i и j.
    4. Повторяем шаги 2 и 3, пока не удалятся все столбцы.

    Однако, может быть такой случай, когда будет несколько одинаковых максимальных значений, причем на нескольких шагах. И при таком раскладе результат может измениться. Подскажите, пожалуйста, как можно применить алгоритм, описанный выше ко всевозможным вариантам.
    Пока даже не определился в каком виде хранить данные, которые бы отражали несколько вариантов развития алгоритма.
     
    Iwashka нравится это.
  2. dandandan

    dandandan

    Регистр.:
    7 авг 2008
    Сообщения:
    975
    Симпатии:
    255
    Первое, что приходит в голову - хранить данные в массиве. Делать обход
    PHP:
    for ($a 1$a <= i$i++) {
      for (
    $b 1$b <= $j$j++) {
      echo 
    $array[$a][$b]i// тут сравниваем значение массива с максимальным значением, полученным на предыдущем шаге
      
    }
    }
    Обход делать рекурсивно, уменьшая количество строк и столбцов.

    Поиск максимального значения лучше делать методом "пузырька"
    http://ru.wikipedia.org/wiki/Сортировка_пузырьком
     
    Iwashka нравится это.
  3. PapaJoe

    PapaJoe

    Регистр.:
    4 авг 2008
    Сообщения:
    620
    Симпатии:
    311
    первый вариант: сначала найти максимальное значение(попутно увеличивая счетчик элементов, равных максимальному значению), а потом пройтись еще раз и удалить элементы, равные этому значению
    второй вариант: во время поиска максимального значения создавать массив со значениями i и j, элементы в которых равны максимальному. Если во время поиска находится элемент больше, чем максимальный, массив очищается и заполняется заново. В конце поиска пройтись по полученному массиву и удалить из первоначального строки и столбцы, записанные в новом массиве
     
    Iwashka нравится это.
  4. DrakonHaSh

    DrakonHaSh

    Регистр.:
    29 июн 2010
    Сообщения:
    358
    Симпатии:
    122
    какое-то, лично для меня, не внятное описание алгоритма, и пункт 1 и 3 вроде как одно и то же

    а результат это что ? по вашу алгоритму результат - это удаление всех столбцов. может вы имеете в виду последовательность удаления (процесс) ?
     
    Iwashka нравится это.
  5. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    708
    Симпатии:
    225
    В первом пункте мы ищем по всей таблице.
    В третьем пункте только в 2х строках.
    Спасибо, забыл указать.
    Результат это последовательность номеров удалённых столбцов.

    Здесь Вы погорячились.
    Во-первых, Ваш вариант пузырька можно оптимизировать, и кстати, в нём много ошибок. Вы то с i,j, то с a,b работаете.
    for ($a = 0,$c = count($array[0]); $a < $c; $a++) {
    for (
    $b = $a+1; $b <= $j; $b++) {


    Во-вторых, проблема не в метода поиска максимального значения.

    Самое главное: Если на каком-то этапе у нас будет возможность выбрать путь развития А либо В. Далее если мы выберем ячейку А, то может быть ещё одна спорная ситуация, где нам надо будет обработать одну из одинаковых ячеек C,D,E. Прошу заметить, что если мы пойдем черезе ячейку В, то НЕ ОБЯЗАТЕЛЬНО, что будет спорный момент с ячейками C,D,E.
     
    Iwashka нравится это.
  6. dandandan

    dandandan

    Регистр.:
    7 авг 2008
    Сообщения:
    975
    Симпатии:
    255
    Вам алгоритм надо или исходный код? Если код, то только Вы знаете как должен выглядеть конечный код.
    По алгоритму, еще раз повторю: Перебираем массив. Находим максимум. Каким-то образом (только Вы знаете как: самый первый, самый последний, рандомно, по дате своего рождения и т.д.) удаляем одну строку/столбец. Выполняем рекурсивно еще проверку...

    Если есть конкретный вопрос - спрашивайте. Кто-нибудь ответит.

    Если исходный вопрос этот?
    То неизвестно, что на выходе желаете получить. Вообще нужно будет создавать копию массива и по нему делать повторный заход поиска данных, потом еще копию и т.д... Дальше анализируем полученные данные.
     
    Iwashka нравится это.
  7. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    708
    Симпатии:
    225
    Алгоритм, который находит самое ближайшее максимальное в массиве - уже реализован.
    Однако, интересует идея, которая позволила бы выполнить алгоритм для всевозможных вариантов. В моей версии берется только 1 максимальное. Однако, если их 2,3,5... То результаты я теряю.
    Приведу пример:
    -1 5 6
    5 -1 9
    6 9 -1
    Диагональ не участвует. Верхний треугольник равен нижнему.
    В данном случае, очевидно, что начинаем с 9.
    -1 9 6
    9 -1 9
    6 9 -1
    Однако, в данном можно начать либо с одной либо со второй 9.
    Мой алгоритм начнет с [0;1] и всё успешно выполнит.
    Однако, надо ещё с [1;2] поработать, этого он не сделает.

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

    Нужен алгоритм, но за исходный код - буду безмерно благодарен.
     
    Iwashka нравится это.
  8. dino

    dino

    Регистр.:
    28 май 2009
    Сообщения:
    550
    Симпатии:
    204
    а если растаскать матрицу в одномерный массив, а затем обрабатывать обычными функциями типа array_unique(), asort(), arsort() и т.д ?
     
    Iwashka нравится это.
  9. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    708
    Симпатии:
    225
    Весь треугольник можно представить в одномерном массиве. И по формуле получать доступ, но для чего?
    Не совсем понимаю, для чего сортировка, поиск уникального.
     
    Iwashka нравится это.
  10. dino

    dino

    Регистр.:
    28 май 2009
    Сообщения:
    550
    Симпатии:
    204
    Эти функции я привел только для примера, а подразумевалось не поиск уникального, а преобразование массива содержащего одинаковые значения в массив с уникальными значениями (лишнее убирается), сортировка, для того чтоб найти максимальное/минимальное значение, ну и так далее....
    В общем измываться над массивом можно как угодно и искать в нем что угодно используя весь набор функций обработки массивов...
    P.S. А если вам все таки важно ковырять именно матрицу, то попробуйте не удалять данные, а перекладывать их с такими же ключами в новую матрицу, и когда нашли искомое значение в одной матрице - переходим к разбору новой матрицы и т.д. пока не найдете столько элементов, сколько нужно...
     
    Iwashka нравится это.