Здравствуйте. Очень прошу вашей помощи, потому что заниматься описанной ниже работой вручную – совершенно непроизводительная трата времени, а срок поджимает.
Суть задания: Имеется матрица сходств, из которой необходимо сформировать итоговую таблицу, отражающую минимальный корреляционный путь. Алгоритм построения итоговой таблицы вручную такой:
1) Ищем в матрице максимум. 2) Копируем содержащую его строку второй строкой в итоговую таблицу. 3) Столбец, на который в скопированной строке приходится пустая ячейка, исключаем, он должен оставаться пустым. 4) Ячейки первой строки итоговой таблицы заполняем именем второй строки. 5) В строке 2 итоговой таблицы ищем максимум. Смотрим имя столбца матрицы, под которым этот максимум находится. 6) Ищем в матрице строку с таким же именем, копируем её в строку 4 итоговой. 7) Столбец, на которые приходится пустая ячейка, снова исключаем, он должен оставаться пустым во всех последующих строках. 8) Сравниваем строки 2 и 4. Если в 4 значение больше, оставляем без изменений, а в 3-ю копируем имя 4-й. Если нет, то в 4-ю переносим значение из 2-й, а в 3-ю – из 1-й. 9) Ищем в 4-й максимум. 10) Повторяем цикл до того, как все столбцы окажутся исключёнными.
Первый 2 строки итоговой пусть остаются ручными – главное автоматизировать дальнейшие шаги. Заранее спасибо.
Здравствуйте. Очень прошу вашей помощи, потому что заниматься описанной ниже работой вручную – совершенно непроизводительная трата времени, а срок поджимает.
Суть задания: Имеется матрица сходств, из которой необходимо сформировать итоговую таблицу, отражающую минимальный корреляционный путь. Алгоритм построения итоговой таблицы вручную такой:
1) Ищем в матрице максимум. 2) Копируем содержащую его строку второй строкой в итоговую таблицу. 3) Столбец, на который в скопированной строке приходится пустая ячейка, исключаем, он должен оставаться пустым. 4) Ячейки первой строки итоговой таблицы заполняем именем второй строки. 5) В строке 2 итоговой таблицы ищем максимум. Смотрим имя столбца матрицы, под которым этот максимум находится. 6) Ищем в матрице строку с таким же именем, копируем её в строку 4 итоговой. 7) Столбец, на которые приходится пустая ячейка, снова исключаем, он должен оставаться пустым во всех последующих строках. 8) Сравниваем строки 2 и 4. Если в 4 значение больше, оставляем без изменений, а в 3-ю копируем имя 4-й. Если нет, то в 4-ю переносим значение из 2-й, а в 3-ю – из 1-й. 9) Ищем в 4-й максимум. 10) Повторяем цикл до того, как все столбцы окажутся исключёнными.
Первый 2 строки итоговой пусть остаются ручными – главное автоматизировать дальнейшие шаги. Заранее спасибо.Narak-zempo
Не совсем понял алгоритм, может быть нужна реализация алгоритма поиска кратчайшего пути в графе (алгоритм Дейкстры, Левита или Форда-Беллмана)? http://www.excelworld.ru/forum/3-6656-1
Не совсем понял алгоритм, может быть нужна реализация алгоритма поиска кратчайшего пути в графе (алгоритм Дейкстры, Левита или Форда-Беллмана)? http://www.excelworld.ru/forum/3-6656-1MCH
Здравствуйте. Конечная цель - построение по матрице сходств графа, не содержащего циклов (дендрита), отражающего максимальный уровень сходства. В сообщении 1 описан механический ("бумажный") алгоритм построения, который я хотел попробовать реализовать в excel (т.к. в силу привычки он кажется более наглядным). К сожалению, математической сути процесса я не знаю, поэтому на Ваш вопрос ответить не могу.
Очевидно, суть задачи сводится к тому, чтобы получить пары вершин, наиболее связанных между собой, но при этом избежать появления циклических структур (в "бумажном" варианте это достигается вычёркиванием столбцов). При этом следует учесть, что в матрице значения не расстояний, а сходств, т.е. максимальное сходство соответствует минимальному расстоянию.
Здравствуйте. Конечная цель - построение по матрице сходств графа, не содержащего циклов (дендрита), отражающего максимальный уровень сходства. В сообщении 1 описан механический ("бумажный") алгоритм построения, который я хотел попробовать реализовать в excel (т.к. в силу привычки он кажется более наглядным). К сожалению, математической сути процесса я не знаю, поэтому на Ваш вопрос ответить не могу.
Очевидно, суть задачи сводится к тому, чтобы получить пары вершин, наиболее связанных между собой, но при этом избежать появления циклических структур (в "бумажном" варианте это достигается вычёркиванием столбцов). При этом следует учесть, что в матрице значения не расстояний, а сходств, т.е. максимальное сходство соответствует минимальному расстоянию.Narak-zempo
MCH, судя по всему, это "построение дендрита по матрице сходств". Там вроде ничего особо сложного (типа см.), но применительно к ситуации (надо показать процесс решения) - задачку желательно бы решать на VBA, а не формулами... Некоторые вон даже отдельные программы для этого пишут
MCH, судя по всему, это "построение дендрита по матрице сходств". Там вроде ничего особо сложного (типа см.), но применительно к ситуации (надо показать процесс решения) - задачку желательно бы решать на VBA, а не формулами... Некоторые вон даже отдельные программы для этого пишут AndreTM