Сортированные пары с наименьшим количеством изменений между каждым элементом

Question

Коллега пришел ко мне с проблемой, на которую мне удалось ответить, но я не знаю, является ли мой ответ правильным или даже хорошим ...

Он создает программу для сравнения данных в различных файлах - в данном случае таблицы Excel. У него есть список сравнений, который будет сводиться к двум файлам со ссылками на ячейки в них. Для каждого сравнения необходимо открыть файлы, выполнить сравнение, а затем закрыть файлы.

Конечно, это можно оптимизировать, если вы упорядочите сравнения так, чтобы вы могли сохранить один файл и просто изменить другой.

Так как же сортировать файлы, чтобы минимизировать количество раз, когда вам нужно закрывать и открывать файлы?

Следует отметить, что идея просто открыть все файлы неосуществима, поскольку может сравниваться более 500 различных таблиц.

Мое решение состояло в том, чтобы найти таблицу, которая встречается в большинстве сравнений, и обработать все сравнения, связанные с этим первым. Затем повторите процесс, игнорируя все сравнения, которые уже были сделаны.

Мне интересно, если при обработке этого первого пакета вы хотите сначала выполнить наименее распространенные, в конечном итоге получая наиболее часто встречающуюся таблицу, - это будет следующая таблица, которую вы обрабатываете следующей (то есть, при изменении только одного файла)

Так кто-нибудь может дать мне лучший вариант или подтвердить, что моя идея хороша (или достаточно хороша)?

Конкретный пример:

Вот пример списка сравнений с примечанием рядом с ними, показывающим, сколько файлов необходимо выгружать и загружать каждый раз. например, после сравнения fileA и fileB ему нужно только выгрузить FileB и загрузить FileC, чтобы выполнить следующее сравнение. После сравнения FileA и FileF необходимо выгрузить оба файла, чтобы загрузить FileB и FileC.

FileA   FileB   
FileA   FileC   One file change
FileA   FileD   One file change
FileA   FileE   One file change
FileA   FileF   One file change
FileB   FileC   Two file changes
FileB   FileF   One file change
FileC   FileD   Two file changes
FileC   FileE   One file change
FileD   FileF   Two file changes
FileE   FileF   One file change

Теоретически в этом примере порядок сравнений можно изменить так, чтобы на каждом шаге вам нужно было выгружать и перезагружать только один файл.

FileA   FileB   
FileA   FileD   One file change
FileA   FileE   One file change
FileA   FileF   One file change
FileA   FileC   One file change
FileB   FileC   One file change
FileC   FileD   One file change
FileC   FileE   One file change
FileE   FileF   One file change
FileB   FileF   One file change
FileD   FileF   One file change

Итак, я хочу знать, каков наилучший алгоритм сортировки пар файлов для получения минимального количества операций выгрузки / загрузки всего файла.

Я должен отметить, что не всегда будет возможно свести это к одному изменению файла каждый раз, как продемонстрировано тривиальной парой сравнений ниже:

FileA   FileB   
FileC   FileD   Two file changes

Answer 1

Вот идея:

Рассмотрим график, в котором каждый файл является узлом, а каждое требуемое сравнение - ребром.

Теперь, если вы найдете Эйлеровый путь на графике этот путь будет представлять последовательность, такую, что после каждого сравнения происходит только одна замена файла.

Если не существует никакого Эйлерова пути, то, как только вы не сможете продолжить путь, просто перейдите на какой-нибудь узел снечетное количество ребер (и если все они имеют четное число ребер, просто выберите любой узел).Этот подход, вероятно, все еще даст вам лучшие результаты, но в какой-то момент (ы) в последовательности, вам придется заменить два файла вместо одного.Я считаю, что должно быть легко доказать, что если не существует никакого Эйлерова пути, то не существует последовательности, которая заменяет только один файл на каждом шаге.