|
|
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
имеется множество параметров. каждый определяется своим уникальным именем p(i). имеется набор функций API, каждая из которых принимает некоторые параметры на входе, и возвращает набор параметров на выходе. кол-во параметров на входе и на выходе у каждой функции свое. Задача: используя набор функций, вычислить требуемый набор параметров, зная значения некоторых других параметров. При этом надо минимизировать затраты на вычисления, в простейшем случае считаем, что все функции равнозначны по стоимости, то есть надо минимизировать количество вызовов функций. В общем случае, если представить зависимости в виде орграфа, то могут быть циклы, но нет петель. связность графа также не гарантируется, но можно для простоты считать, что граф связный. Упрощенный пример: имеем множество из 6 параметров p1, p2, ..., p6, и множество из 5 "функций" F1, F2, ... , F5 (p3,p5) = F1(p1) (p3) = F2(p2) (p4) = F3(p2) (p5,p6) = F4(p3,p4) (p6) = F5(p2) 1) Известны p1 и p2. Надо вычислить p5, p6. Оптимальное решение: p5=F1(p1), p6 = F5(p2) - два вызова. 2) Известно только p1. Надо вычислить p5, p6. Оптимальное решение: p3=F2(p2), p4=F3(p2), (p5,p6) = F4(p3,p4) - три вызова Вроде бы задача на графы, но не могу свести ее к известным мне задачам. имхо, это точно не кратчайший путь, и не задача о потоке, и не остов... Но сама задача, на первый взгляд, кажется "из жизни", а значит, должны существовать соотв. алгоритмы. также есть трудности с выбором способа представления графа для его обхода. Если кто знает, в какую сторону копать, подскажите. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.04.2016, 22:15 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVA2) Известно только p1. Надо вычислить p5, p6. Оптимальное решение: p3=F2(p2), p4=F3(p2), (p5,p6) = F4(p3,p4) - три вызова сорри, опечатался. во втором примере известно только p2 2) Известно только p2. Надо вычислить p5, p6. Оптимальное решение: p3=F2(p2), p4=F3(p2), (p5,p6) = F4(p3,p4) - три вызова ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.04.2016, 22:18 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVAимхо, это точно не кратчайший путь,А по-моему, как раз поиск кратчайшего пути в графе состояний. LVAУпрощенный пример: имеем множество из 6 параметров p1, p2, ..., p6, и множество из 5 "функций" F1, F2, ... , F5 (p3,p5) = F1(p1) (p3) = F2(p2) (p4) = F3(p2) (p5,p6) = F4(p3,p4) (p6) = F5(p2) граф состоянийсостояние 1: не знаем p1, не знаем p2, не знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 2: не знаем p1, не знаем p2, не знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 3: не знаем p1, не знаем p2, не знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 4: не знаем p1, не знаем p2, не знаем p3, не знаем p4, знаем p5, знаем p6 состояние 5: не знаем p1, не знаем p2, не знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 6: не знаем p1, не знаем p2, не знаем p3, знаем p4, не знаем p5, знаем p6 состояние 7: не знаем p1, не знаем p2, не знаем p3, знаем p4, знаем p5, не знаем p6 состояние 8: не знаем p1, не знаем p2, не знаем p3, знаем p4, знаем p5, знаем p6 состояние 9: не знаем p1, не знаем p2, знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 10: не знаем p1, не знаем p2, знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 11: не знаем p1, не знаем p2, знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 12: не знаем p1, не знаем p2, знаем p3, не знаем p4, знаем p5, знаем p6 состояние 13: не знаем p1, не знаем p2, знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 14: не знаем p1, не знаем p2, знаем p3, знаем p4, не знаем p5, знаем p6 состояние 15: не знаем p1, не знаем p2, знаем p3, знаем p4, знаем p5, не знаем p6 состояние 16: не знаем p1, не знаем p2, знаем p3, знаем p4, знаем p5, знаем p6 состояние 17: не знаем p1, знаем p2, не знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 18: не знаем p1, знаем p2, не знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 19: не знаем p1, знаем p2, не знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 20: не знаем p1, знаем p2, не знаем p3, не знаем p4, знаем p5, знаем p6 состояние 21: не знаем p1, знаем p2, не знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 22: не знаем p1, знаем p2, не знаем p3, знаем p4, не знаем p5, знаем p6 состояние 23: не знаем p1, знаем p2, не знаем p3, знаем p4, знаем p5, не знаем p6 состояние 24: не знаем p1, знаем p2, не знаем p3, знаем p4, знаем p5, знаем p6 состояние 25: не знаем p1, знаем p2, знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 26: не знаем p1, знаем p2, знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 27: не знаем p1, знаем p2, знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 28: не знаем p1, знаем p2, знаем p3, не знаем p4, знаем p5, знаем p6 состояние 29: не знаем p1, знаем p2, знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 30: не знаем p1, знаем p2, знаем p3, знаем p4, не знаем p5, знаем p6 состояние 31: не знаем p1, знаем p2, знаем p3, знаем p4, знаем p5, не знаем p6 состояние 32: не знаем p1, знаем p2, знаем p3, знаем p4, знаем p5, знаем p6 состояние 33: знаем p1, не знаем p2, не знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 34: знаем p1, не знаем p2, не знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 35: знаем p1, не знаем p2, не знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 36: знаем p1, не знаем p2, не знаем p3, не знаем p4, знаем p5, знаем p6 состояние 37: знаем p1, не знаем p2, не знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 38: знаем p1, не знаем p2, не знаем p3, знаем p4, не знаем p5, знаем p6 состояние 39: знаем p1, не знаем p2, не знаем p3, знаем p4, знаем p5, не знаем p6 состояние 40: знаем p1, не знаем p2, не знаем p3, знаем p4, знаем p5, знаем p6 состояние 41: знаем p1, не знаем p2, знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 42: знаем p1, не знаем p2, знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 43: знаем p1, не знаем p2, знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 44: знаем p1, не знаем p2, знаем p3, не знаем p4, знаем p5, знаем p6 состояние 45: знаем p1, не знаем p2, знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 46: знаем p1, не знаем p2, знаем p3, знаем p4, не знаем p5, знаем p6 состояние 47: знаем p1, не знаем p2, знаем p3, знаем p4, знаем p5, не знаем p6 состояние 48: знаем p1, не знаем p2, знаем p3, знаем p4, знаем p5, знаем p6 состояние 49: знаем p1, знаем p2, не знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 50: знаем p1, знаем p2, не знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 51: знаем p1, знаем p2, не знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 52: знаем p1, знаем p2, не знаем p3, не знаем p4, знаем p5, знаем p6 состояние 53: знаем p1, знаем p2, не знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 54: знаем p1, знаем p2, не знаем p3, знаем p4, не знаем p5, знаем p6 состояние 55: знаем p1, знаем p2, не знаем p3, знаем p4, знаем p5, не знаем p6 состояние 56: знаем p1, знаем p2, не знаем p3, знаем p4, знаем p5, знаем p6 состояние 57: знаем p1, знаем p2, знаем p3, не знаем p4, не знаем p5, не знаем p6 состояние 58: знаем p1, знаем p2, знаем p3, не знаем p4, не знаем p5, знаем p6 состояние 59: знаем p1, знаем p2, знаем p3, не знаем p4, знаем p5, не знаем p6 состояние 60: знаем p1, знаем p2, знаем p3, не знаем p4, знаем p5, знаем p6 состояние 61: знаем p1, знаем p2, знаем p3, знаем p4, не знаем p5, не знаем p6 состояние 62: знаем p1, знаем p2, знаем p3, знаем p4, не знаем p5, знаем p6 состояние 63: знаем p1, знаем p2, знаем p3, знаем p4, знаем p5, не знаем p6 состояние 64: знаем p1, знаем p2, знаем p3, знаем p4, знаем p5, знаем p6 переход 1: состояние 33 → состояние 43 (F1) переход 2: состояние 34 → состояние 44 (F1) переход 3: состояние 35 → состояние 43 (F1) переход 4: состояние 36 → состояние 44 (F1) переход 5: состояние 37 → состояние 47 (F1) переход 6: состояние 38 → состояние 48 (F1) переход 7: состояние 39 → состояние 47 (F1) переход 8: состояние 40 → состояние 48 (F1) переход 9: состояние 41 → состояние 43 (F1) переход 10: состояние 42 → состояние 44 (F1) переход 11: состояние 45 → состояние 47 (F1) переход 12: состояние 46 → состояние 48 (F1) переход 13: состояние 49 → состояние 59 (F1) переход 14: состояние 50 → состояние 60 (F1) переход 15: состояние 51 → состояние 59 (F1) переход 16: состояние 52 → состояние 60 (F1) переход 17: состояние 53 → состояние 63 (F1) переход 18: состояние 54 → состояние 64 (F1) переход 19: состояние 55 → состояние 63 (F1) переход 20: состояние 56 → состояние 64 (F1) переход 21: состояние 57 → состояние 59 (F1) переход 22: состояние 58 → состояние 60 (F1) переход 23: состояние 61 → состояние 63 (F1) переход 24: состояние 62 → состояние 64 (F1) переход 25: состояние 17 → состояние 25 (F2) переход 26: состояние 18 → состояние 26 (F2) переход 27: состояние 19 → состояние 27 (F2) переход 28: состояние 20 → состояние 28 (F2) переход 29: состояние 21 → состояние 29 (F2) переход 30: состояние 22 → состояние 30 (F2) переход 31: состояние 23 → состояние 31 (F2) переход 32: состояние 24 → состояние 32 (F2) переход 33: состояние 49 → состояние 57 (F2) переход 34: состояние 50 → состояние 58 (F2) переход 35: состояние 51 → состояние 59 (F2) переход 36: состояние 52 → состояние 60 (F2) переход 37: состояние 53 → состояние 61 (F2) переход 38: состояние 54 → состояние 62 (F2) переход 39: состояние 55 → состояние 63 (F2) переход 40: состояние 56 → состояние 64 (F2) переход 41: состояние 17 → состояние 21 (F3) переход 42: состояние 18 → состояние 22 (F3) переход 43: состояние 19 → состояние 23 (F3) переход 44: состояние 20 → состояние 24 (F3) переход 45: состояние 25 → состояние 29 (F3) переход 46: состояние 26 → состояние 30 (F3) переход 47: состояние 27 → состояние 31 (F3) переход 48: состояние 28 → состояние 32 (F3) переход 49: состояние 49 → состояние 53 (F3) переход 50: состояние 50 → состояние 54 (F3) переход 51: состояние 51 → состояние 55 (F3) переход 52: состояние 52 → состояние 56 (F3) переход 53: состояние 57 → состояние 61 (F3) переход 54: состояние 58 → состояние 62 (F3) переход 55: состояние 59 → состояние 63 (F3) переход 56: состояние 60 → состояние 64 (F3) переход 57: состояние 13 → состояние 16 (F4) переход 58: состояние 14 → состояние 16 (F4) переход 59: состояние 15 → состояние 16 (F4) переход 60: состояние 29 → состояние 32 (F4) переход 61: состояние 30 → состояние 32 (F4) переход 62: состояние 31 → состояние 32 (F4) переход 63: состояние 45 → состояние 48 (F4) переход 64: состояние 46 → состояние 48 (F4) переход 65: состояние 47 → состояние 48 (F4) переход 66: состояние 61 → состояние 64 (F4) переход 67: состояние 62 → состояние 64 (F4) переход 68: состояние 63 → состояние 64 (F4) переход 69: состояние 17 → состояние 18 (F5) переход 70: состояние 19 → состояние 20 (F5) переход 71: состояние 21 → состояние 22 (F5) переход 72: состояние 23 → состояние 24 (F5) переход 73: состояние 25 → состояние 26 (F5) переход 74: состояние 27 → состояние 28 (F5) переход 75: состояние 29 → состояние 30 (F5) переход 76: состояние 31 → состояние 32 (F5) переход 77: состояние 49 → состояние 50 (F5) переход 78: состояние 51 → состояние 52 (F5) переход 79: состояние 53 → состояние 54 (F5) переход 80: состояние 55 → состояние 56 (F5) переход 81: состояние 57 → состояние 58 (F5) переход 82: состояние 59 → состояние 60 (F5) переход 83: состояние 61 → состояние 62 (F5) переход 84: состояние 63 → состояние 64 (F5) LVA1) Известны p1 и p2. Надо вычислить p5, p6.Начальное состояние -- 49 (знаем p1, знаем p2, не знаем p3, не знаем p4, не знаем p5, не знаем p6). Добавляем финальное состояние 65 «знаем p5, знаем p6», добавляем переходы нулевой стоимости: переходы в финальное состояниепереход 85: состояние 4 → состояние 65 переход 86: состояние 8 → состояние 65 переход 87: состояние 12 → состояние 65 переход 88: состояние 16 → состояние 65 переход 89: состояние 20 → состояние 65 переход 90: состояние 24 → состояние 65 переход 91: состояние 28 → состояние 65 переход 92: состояние 32 → состояние 65 переход 93: состояние 36 → состояние 65 переход 94: состояние 40 → состояние 65 переход 95: состояние 44 → состояние 65 переход 96: состояние 48 → состояние 65 переход 97: состояние 52 → состояние 65 переход 98: состояние 56 → состояние 65 переход 99: состояние 60 → состояние 65 переход 100: состояние 64 → состояние 65 LVAОптимальное решение: p5=F1(p1), p6 = F5(p2) - два вызова.Путь в графе: состояние 49, переход 13, состояние 59, переход 82, состояние 60, переход 99, состояние 65. LVA2) Известно только p2. Надо вычислить p5, p6.Начальное состояние -- 17 (не знаем p1, знаем p2, не знаем p3, не знаем p4, не знаем p5, не знаем p6). Достраиваем граф так же, как в 1). LVAОптимальное решение: p3=F2(p2), p4=F3(p2), (p5,p6) = F4(p3,p4) - три вызоваПуть в графе: состояние 17, переход 25, состояние 25, переход 45, состояние 29, переход 60, состояние 32, переход 92, состояние 65. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.04.2016, 05:04 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
Пётр Седов, блестяще! спасибо, прекрасная аналогия. на небольшом количестве параметров вполне сгодится, но дальше уже довольно дорого становится... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.04.2016, 11:34 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVA, есть ощущение, что состояния в памяти можно вообще не хранить, потому что из номера состояния легко узнать его описание, например: состояние 35: знаем p1, не знаем p2, не знаем p3, не знаем p4, знаем p5, не знаем p6 35 = 1 + 34 = 1 + 100010 2 состояние 45: знаем p1, не знаем p2, знаем p3, знаем p4, не знаем p5, не знаем p6 45 = 1 + 44 = 1 + 101100 2 Но если переходов окажется слишком много, тогда да, придётся думать над другим алгоритмом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.04.2016, 22:35 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
Пётр Седов, Да, вершины можно не хранить и граф не строить. Тогда на каждом шаге надо перебирать ВСЕ функции, которые могут изменить текущее состояние. Правда уже пройденные состояния все равно надо запоминать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 10:45 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVA, ранжирование графа называется. алгоритм прост, Можно реализовать самому. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 11:00 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVAДа, вершины можно не хранить и граф не строить. Тогда на каждом шаге надо перебирать ВСЕ функции, которые могут изменить текущее состояние.Переходы лучше хранить в памяти, это должно ускорить процесс. LVAПравда уже пройденные состояния все равно надо запоминать.Это да. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 15:02 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVAна небольшом количестве параметров вполне сгодится, но дальше уже довольно дорого становится... Если не нужно 100% минимальное кол-во переходов, а только подходящее/рабочее решение. То можно делать в два прохода: 1. Откластиризовать граф. (вроде так называется). 2. Получить граф меньшего размера, но с "укрупненными узлами". 3. При получении задания A-->B 3.1 ищем переход из точки A в точку на укрупненном графе 3.2. ищем переход из B в точку на укрупненном графе. 4. Ищем переход на укрупненном графе" 5. Искомое решение есть путь 3.1 + 4 + 3.2. Я лично сейчас так делаю + все возможные решения на укрупненном графе заранее просчитаны и сложены в табличку. Как кластеризовать, какие есть алгоритмы - не знаю. Мы свои данные руками (глазками) кластеризовали. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 15:08 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
MasterZivранжирование графа называется. алгоритм прост, Можно реализовать самому. не могли бы Вы пояснить, какой именно граф вы предлагаете ранжировать и как это позволит решить задачу ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 22:18 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
Пётр СедовПереходы лучше хранить в памяти, это должно ускорить процесс. все-все в памяти, разумеется. правда, свести к поиску точка-точка наверное все таки не получится. если, скажем, известно только p1, то p6 определить никак нельзя, в этом случае надо выдать частичное решение, то есть маршрут(ы) определения того, что смогли, в данном случае - p5. фиктивные ребра тут уже наверное не стоит добавлять, но задача все равно решается ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 22:30 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
Leonid KudryavtsevКак кластеризовать, какие есть алгоритмы - не знаю. Мы свои данные руками (глазками) кластеризовали. я Вас понял. кластеризация - самая мутная штука в данном случае. мне на данном этапе она точно не понадобится ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.04.2016, 22:31 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
LVAMasterZivранжирование графа называется. алгоритм прост, Можно реализовать самому. не могли бы Вы пояснить, какой именно граф вы предлагаете ранжировать и как это позволит решить задачу ? вершины - функции, которые нужно выехать, чтобы получить все нужные параметры. ребра - связи от одной функции к другой, когда на входе функции нужно иметь параметр с выхода другой. решение будет не всегда, Если циклы будут, решения может не быть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.04.2016, 12:01 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
Кстати, подумай про циклы. если они есть, значит выход одной функции зависит от выхода другой, которая в сад очередь зависит от выхода первой. это называется гонки, и они могут стабилизироваться только в особых вырожденных случаях, когда функция не зависит от некоторых своих входов, тех, которые рекурсивные. Погляди например на описание RS trigger. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.04.2016, 12:08 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
MasterZiv, не понимаю Вас совсем. может Вы продемонстрируете на маленьком примере, который описан в первом сообщении ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.04.2016, 23:37 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
MasterZivLVAпропущено... не могли бы Вы пояснить, какой именно граф вы предлагаете ранжировать и как это позволит решить задачу ? вершины - функции, которые нужно вызвать, чтобы получить все нужные параметры. ребра - связи от одной функции к другой, когда на входе функции нужно иметь параметр с выхода другой. решение будет не всегда, Если циклы будут, решения может не быть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.04.2016, 05:30 |
|
||
|
минимизация кол-ва вызовов
|
|||
|---|---|---|---|
|
#18+
MasterZiv, в предлагаемом Вами графе всего 5 вершин. что мы получим в результате ранжирования ? F1 - 1 F2 - 1 F3 - 1 F5 - 1 F4 - 2 и что ? мне не надо вызывать все эти функции в указанном порядке. мне нужно получить результат (p5 и p6) за минимальное кол-во вызовов. А в этом графе вообще не учитывается, какие вершины известны, а какие нет. так же как не учитывается, какие вершины нужно найти. Как ранжирование поможет найти ответ ? Напомню, что для первого примера ответом является {F1, F5), а для второго {F2, F3, F4} ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.04.2016, 22:05 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39211841&tid=1340740]: |
0ms |
get settings: |
6ms |
get forum list: |
14ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
120ms |
get topic data: |
8ms |
get forum data: |
2ms |
get page messages: |
51ms |
get tp. blocked users: |
1ms |
| others: | 216ms |
| total: | 422ms |
| 0 / 0 |
