Определение веса ребер по списку прогулок на графике

Question

Эти вопросы касаются набора данных со списками задач, выполненных подряд, и общего времени, необходимого для их выполнения. Мне было интересно, можно ли было бы определить полезные вещи о длине задач, как они есть, или с помощью некоторой первоначальной оценки на основе соответствующих знаний предметной области. Я пришел к выводу, что теория графов могла бы стать подходом к решению этой проблемы абстрактно, и у меня есть приличное базовое понимание материала, но я не могу точно знать, нахожусь ли я на правильном пути. Кроме того, я думаю, что это довольно интересный вопрос. Итак, поехали:

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

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

3. Наконец, что если бы у вас был набор начальных догадок относительно весов, и вам нужно было уточнить их, используя данные прогулки? Повысит ли это вашу способность угадывать, и как вы сможете применить дополнительную информацию?

РЕДАКТИРОВАТЬ: Разъяснение трудностей простого линейного алгебраического подхода. Рассмотрим следующий набор прогулок:

a = 5
b = 4
b + c = 5
a + b + c = 8

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

Answer 1

Похоже на применение линейной алгебры.

У вас есть набор линейных уравнений, которые вам нужно решить.Переменные, являющиеся длинами задач (или весами ребер).

Например, если длины задач были t1, t2, t3 для 3 задач.

И вам дают

t1 + t2 = 2  (task 1 and 2 take 2 hours)

t1 + t2 + t3 = 7 (all 3 tasks take 7 hours)

t2 + t3 = 6   (tasks 2 and 3 take 6 hours)

Решение дает t1 = 1, t2 = 1, t3 = 5.

Вы можете использовать любые методы линейной алгебры (например: http://en.wikipedia.org/wiki/Gaussian_elimination) для их решения, которые сообщат вам, есть ли уникальное решение, нетрешение или бесконечное число решений (другие возможности невозможны).

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

Или, может быть, вы можете попытаться ввести некоторую «слабую» задачу в каждом цикле (то есть добавить больше переменных) и попытаться выбрать решение для нового уравненияВ тех случаях, когда слабые задачи удовлетворяют некоторым линейным ограничениям (например, 0 методов линейного программирования .

Answer 2

Я бы забыл о графиках и рассматривал бы списки задач как векторы - каждая задача представлена ​​как компонент со значением, равным ее стоимости (время выполнения в этом случае.

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

С каноническими векторами учитывайте только наличие и отсутствие задачи (всего 0 | 1 для этой итерации) и ищите миниmal diffs - одна задача diffs первой - это даст оценки для небольшого числа переменных.Продолжайте делать это рекурсивно, будьте готовы отследить и до сих пор иметь эвристическое правило для достоверности или качества оценок.Следите за хорошими «раундами», от которых вы вернулись.

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

Да, это может стоить много :-)

Answer 3

Предположим, у вас есть неограниченное количество произвольных символов для представления каждого ребра.(a, b, c, d и т. д.)

w - это список всех прогулок в форме 0, a, b, c, d, e и т. д. (0 будет объяснено позже.)

i = 1

если #w [i] ~ = 1, то

замените w [2] на ДЛИНУ w [i], минус все остальные значенияв ш.

повторить навсегда.

Пример:

0, a, b, c, d, e 50

0, a, c,б, е 20

0, с, е 10

Итак:

а - первое.Заменить все вхождения "a" на 50, -b, -c, -d, -e.

Новые данные:

50, 50

50, -b, -d, 20

0, c, e 10

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