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

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

  1. LEXAlForpostl

    LEXAlForpostl

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

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


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

    noxwell Создатель

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

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    708
    Симпатии:
    225
    Да, можно представить и как граф, в котором циклов не будет. Но вот поиск осуществляется только по матрице и аналогов алгоритма нет, необходимо понять из слов.
    Продемонстрирую работу алгоритма на примере:
    -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
    Много, много ошибок :) Вот рабочий вариант:
     
    Iwashka и LEXAlForpostl нравится это.