有关边长的有向无环图的均匀分布

Question

问题

我有一组事件，其中一些事件相互连接，并且这些连接定义了顺序。事件必须按照定义的顺序进行。连接可能包含连接事件之间距离的最小和/或最大需求。让距离以天为单位。

我使用有向无环图来表示我的模型。

我需要按照给定的天数对这些事件进行排序，同时遵守定义的顺序和最小/最大要求。分布应该趋于平均。这些事件应该平均分布在给定的距离上。

你能提出哪些方法或算法来解决这个问题？我尝试过拓扑排序或约束排序等方法，但几乎没有结果。

例子

我们有一组事件a、b、c，具有以下连接：a -> b，b -> c，a -> c

给定的分配天数为7天。

a. 没有任何连接距离的要求。

那么最佳解法将是

1  2  3  4  5  6  7
a        b        c

b.要求事件(a, b)之间的时间距离在[1, 2]天范围内。

那么最佳解决方案将是

1  2  3  4  5  6  7
a     b           c

c. 当事件（a，b）之间的时间间隔为[1,2]天，事件（a，c）之间的时间间隔小于等于4天时，最佳解决方案为

然后最好的解决方案是

1  2  3  4  5  6  7
a     b     c      

要求：事件 (a, b) 之间的时间间隔为 [1,2] 天，(a, c) 之间的时间间隔为 ≤4 天，(b, c) 之间的时间间隔为 ≥3 天。

那么最佳解决方案是：

1  2  3  4  5  6  7
a  b        c      

编辑： 一天中可能会有多个事件：

1. 如果事件数量大于分配天数。
2. 如果我们有最大值 = 0 的要求。

如果我们有几个合适的解决方案，那么最好的解决方案是当前事件和其相邻事件之间的距离大致相同。我们希望事件之间的距离为 (分配天数 / 事件数量)，其中分配天数 > 事件数量。 如果我们有几个合适的解决方案具有相同距离，则最佳的解决方案是左移的解决方案。

以下是连接事件的示例

---

- Alyona

---

感谢您的编辑。图片很漂亮，但并不是非常有用。使用图片作为输入是很困难的。不如将事件、边缘和所需间距作为文本发布，以便代码可以读取。例如："a b 1 2\na c 0 4\nb c 3 0\n" - ravenspoint

Answer 1

Find R = all events that have no in edges
LOOP while R contains one or more event
   SELECT N from R with the largest number of out edges
   IF first time through
      Place N on day 1
   ELSE
      Place N in middle of largest gap between events
   LOOP M over descendants of N in required order
      Place M as far from other events as possible, within M's allowed range

- ravenspoint

Answer 2

方法。

使用约束库生成满足事件约束条件的所有事件顺序，不考虑 (不)均匀性，然后迭代地找到具有最小不均匀性的受约束解决方案。

什么是均匀性？

如果不均匀性是通过查看计算出的所有天数和事件天数之间的差异，并返回最大值减去最小值的天数差异来定义的，则需要澄清您的回答：

1  2  3  4  5  6  7
a  b        c      

这句话的意思是它的数值相对于日期偏向于左侧。

更好的回答可能是：

1  2  3  4  5  6  7
   a  b        c      

将“一次向右移动”后，从第七天到任何事件日的拉伸程度减少了。

如果您认为上述内容是等价的，那么您需要更好地定义“均匀性”-也许是在事件天数的范围内的均匀性？

最新消息！作者已编辑“均匀性”，现在描述更加清晰。

代码

如果您只需按回车键即可运行示例，则源已设置好。

# -*- coding: utf-8 -*-
"""
Even distribution of directed acyclic graph with respect to edge length
https://dev59.com/0MPra4cB1Zd3GeqPs_MT

Created on Sat Mar 26 08:53:19 2022

@author: paddy
"""

# https://pypi.org/project/python-constraint/
from constraint import Problem
from itertools import product


#%% Inputs
days = input("Days: int = ")
try:
    days = int(days.strip())
except:
    days = 7
print(f"Using {days=}")
events = input("events: space_separated = ")
events = events.strip().split()
if not events:
    events = list("abc")
print(f"Using {events=}")

constraint_funcs = []
while True:
    constr = input("constraint: string_expression (. to end) = ").strip()
    if not constr:
        constraint_funcs = ["1 <= (b - a) <=2",
                            "(c - a) <= 4",
                            "(c - b) >= 3"]
        break
    if constr == '.':
        break
    constraint_funcs.append(constr)
print(f"\nUsing {constraint_funcs=}")


#%% Constraint Setup
print()
problem = Problem()

problem.addVariables(events, range(1, days+1))
for constr in constraint_funcs:
    constr_events = sorted( set(events) & set(compile(constr, '<input>',
                                              mode='eval').co_names))
    expr = f"lambda {', '.join(constr_events)}: {constr}"
    print(f"  Add Constraint {expr!r}, On {constr_events}")
    func = eval(expr)
    problem.addConstraint(func, constr_events)

#%% Solution optimisation for "evenness"
print()

def unevenness(event_days: list[int], all_days: int):
    "(Max - min diff between ordered events, leftmost event)"
    maxdiff, mindiff =  -1, all_days + 1
    for event, next_event in zip(event_days, event_days[1:]):
        diff = next_event - event
        maxdiff = max(maxdiff, diff)
        mindiff = min(mindiff, diff)
    return maxdiff - mindiff, event_days[0]

def printit(solution, all_days):
    drange = range(1, all_days+1)
    # print(solution)
    print('  '.join(str(i)[0] for i in drange))
    for event, day in sorted(solution.items(), key=lambda kv: kv[::-1]):
        print('   ' * (day - 1) + event )
    print()

current_best = None, 9e99
for ans in problem.getSolutionIter():
    unev = unevenness(sorted(ans.values()), days)
    if current_best[0] is None or unev < current_best[1]:
        current_best = ans, unev
        print("Best so far:")
        printit(ans, days)

不均匀函数已更新。更好的函数可能是最小化连续事件之间天数的标准偏差，但对于这个示例，这个函数可行。

输出

使用您的约束条件进行样本运行，但事件名称更长。

Days: int = 7
Using days=7

events: space_separated = arch belt card
Using events=['arch', 'belt', 'card']

constraint: string_expression (. to end) = 1 <= (belt - arch) <= 2

constraint: string_expression (. to end) = (card - arch) <= 4

constraint: string_expression (. to end) = (card - belt) >= 3

constraint: string_expression (. to end) = .

Using constraint_funcs=['1 <= (belt - arch) <= 2', '(card - arch) <= 4', '(card - belt) >= 3']

  Add Constraint 'lambda arch, belt: 1 <= (belt - arch) <= 2', On ['arch', 'belt']
  Add Constraint 'lambda arch, card: (card - arch) <= 4', On ['arch', 'card']
  Add Constraint 'lambda belt, card: (card - belt) >= 3', On ['belt', 'card']

Best so far:
1  2  3  4  5  6  7
      arch
         belt
                  card

Best so far:
1  2  3  4  5  6  7
   arch
      belt
               card

Best so far:
1  2  3  4  5  6  7
arch
   belt
            card

注意：事件名称的第一个字母与日期列对齐。 unevenness函数返回元组的第二个项目是最早（最左侧）事件发生的日期。如果事件的分布相等，则在最小化时倾向于更靠左的解决方案。

- Paddy3118