如何平衡这个有向图的输入到输出？
How to balance inputs to outputs of this directed graph?
我正在考虑的图表类型非常具体。我为它取了自己的名字：Iode (EYE-ode).
这是 "I/O" 和电子术语 "anode" 和 "cathode" 的游戏。
艾德
一个 Iode 从其关联的输入节点获取一些项目，并将这些项目平均分配到其关联的输出节点。
- 可能有1到N个输入节点。
- 可能有1到M个输出节点。
- 来自输入节点的边被合并，然后拆分到输出节点。
- 输出节点永远不会连接到输入节点。
- 当 Iode "ticks" 它在其关联节点上执行平衡操作。
- 每个节点每个刻度的最大输入。
- 每个节点每个刻度的最大输出。
- 每个滴答的最大总吞吐量。
这是连接方式的示意图（使用 http://pencil.evolus.vn/）：
每个方块都是一个节点。每个节点可以包含一些数字。
我对 Iode tick 的算法有困难。我想最大化吞吐量，这可能会受到多种方式的限制。
这是我对 github (https://github.com/voxelv/ioder) 的初步 python 尝试，特别是在 algorithms.py:
def iode_int_tick(iode):
# Get the amounts per input iode node
input_amount_per_iode_node = []
for iode_node in iode.input_nodes:
input_amount_per_iode_node.append(min(iode_node.amount, iode.speed['input']))
# Get the amounts per output iode node
output_amount_per_iode_node = []
for iode_node in iode.output_nodes:
output_amount_per_iode_node.append(iode.speed['output'])
# Get the maximum throughput
max_thru_speed = int(iode.speed['throughput'])
input_amount_total = sum(input_amount_per_iode_node)
output_amount_total = sum(output_amount_per_iode_node)
# Compare the maximum throughput
diff_input_thru_max = int(input_amount_total - max_thru_speed)
diff_output_thru_max = int(output_amount_total - max_thru_speed)
# Lessen the input if the maximum throughput is smaller
if diff_input_thru_max > 0:
for i in xrange(len(iode.input_nodes)):
pass # TODO: figure out this
# Lessen the output if the maximum throughput is smaller
if diff_output_thru_max > 0:
for i in xrange(len(iode.input_nodes)):
pass # TODO: figure out this
# Move the numbers from the inputs
for i, inode in enumerate(iode.input_nodes):
inode.take(input_amount_per_iode_node[i])
# Move the numbers into the outputs
for i, inode in enumerate(iode.output_nodes):
inode.give(output_amount_per_iode_node[i])
我正在尝试找出具有 # TODO 注释的 for 循环中的内容。
编辑：示例已加载到 main.py 和 config.py。
每个节点的输入限制为 5
每个节点的输出限制为5
最大吞吐量为 8
因此，将两个输入设置为 23 和 6，将两个输出设置为 4 和 0，输入节点的预期结果为 19 和 2，输出节点为 8 和 4。
运行 带有 python main.py 的代码导致以下输出：
Actual: [18, 1], [9, 5]
Expected: [19, 2], [8, 4]
更多示例：
Initial: [22, 2], [3, 20]
Actual: [17, 0], [8, 25]
Expected: [17, 0], [7, 23] or [17, 0], [6, 24]
根据处理余数的顺序，预期可能是所提到的任何一个。最大吞吐量将我们限制为 8，但每个节点的最大输入限制我们从第一个输入节点获取 5。由于第二个输入节点只有两个，所以我们只能为这个刻度提供 7 个。 7 尽可能均匀地分配到输出，3 或 4 进入第一个输出，4 或 3 进入第二个输出。
我想出了一个我的问题的类比，并且能够通过类比更好地理解它。
这就像试图用水填充冰块托盘。
按照我构建 Iode 的方式，水永远不会超过托盘的处理能力。
这是我的解决方案：
def water_into_ice_tray(water, ice_tray, **kwargs):
water_to_put = [0 for _ in xrange(len(ice_tray))]
recursion_ice_tray = [x for x in ice_tray]
# Debug depth
if 'depth' in kwargs:
print kwargs['depth'],
kwargs['depth'] += 1
# BASE_CASE: No more water
if not water > 0:
# Exit early
return water_to_put
# Get slots that have space for more water
open_slots = []
for i in xrange(len(ice_tray)):
if ice_tray[i] > 0:
open_slots.append(i)
# BASE_CASE: Not enough water to go around
if water < len(open_slots):
# Put 1 more in the first 'water' slots
for i in xrange(water):
water_to_put[open_slots[i]] += 1
# Exit early
return water_to_put
# BASE_CASE: Too much water
if water > sum(ice_tray):
raise ValueError("Too much water")
# Attempt to fill each open slot with a distributed amount
fill_amount = int(math.floor(int(water) / len(open_slots)))
leftover = int(water) % len(open_slots)
for slot_index in open_slots:
# With how much water have we overfilled this slot?
diff = fill_amount - ice_tray[slot_index]
if diff >= 0:
# We tried putting too much water into this slot
# Calculate how much to put in it
water_to_put[slot_index] += fill_amount - diff
# No more water can fit into this slot
recursion_ice_tray[slot_index] = 0
# Keep the leftover
leftover += diff
else:
# The slot could hold the water
water_to_put[slot_index] += fill_amount
# Some more water can fit into this slot
recursion_ice_tray[slot_index] = -diff
# None is leftover
# Recurse
recursion_water_to_put = water_into_ice_tray(leftover, recursion_ice_tray, **kwargs)
# Add up recursion result to this result
return map(add, water_to_put, recursion_water_to_put)
def iode_int_tick(iode):
# Calculate available amounts per input node
available_input_per_node = []
for inode in iode.input_nodes:
available_input_per_node.append(min(inode.amount, iode.speed['input']))
input_limit = sum(available_input_per_node)
# Get the throughput
throughput_limit = iode.speed['throughput']
# Calculate available space per output node
available_output_per_node = []
for inode in iode.output_nodes:
available_output_per_node.append(min(inode.max_amount - inode.amount, iode.speed['output']))
output_limit = sum(available_output_per_node)
# Decide which is the limiting factor
limiter = min(input_limit, throughput_limit, output_limit)
if limiter == input_limit:
# If the input limits, then distribute to the outputs. The throughput can handle it.
amount_to_take_per_input_node = available_input_per_node
amount_to_put_per_output_node = water_into_ice_tray(input_limit, available_output_per_node)
pass
elif limiter == throughput_limit:
# If throughput limits, then distribute the throughput amount from the inputs, to the outputs.
amount_to_take_per_input_node = water_into_ice_tray(throughput_limit, available_input_per_node)
amount_to_put_per_output_node = water_into_ice_tray(throughput_limit, available_output_per_node)
pass
elif limiter == output_limit:
# If output limits, then distribute the draw on the inputs. The throughput can handle it.
amount_to_take_per_input_node = water_into_ice_tray(output_limit, available_input_per_node)
amount_to_put_per_output_node = available_output_per_node
pass
else:
raise ValueError("Somehow the limiting factor is something other than the input, throughput, or output.")
# Do the taking
for i in xrange(len(iode.input_nodes)):
iode.input_nodes[i].take(amount_to_take_per_input_node[i])
# Do the giving
for i in xrange(len(iode.output_nodes)):
iode.output_nodes[i].give(amount_to_put_per_output_node[i])
我正在考虑的图表类型非常具体。我为它取了自己的名字：Iode (EYE-ode).
这是 "I/O" 和电子术语 "anode" 和 "cathode" 的游戏。
艾德
一个 Iode 从其关联的输入节点获取一些项目，并将这些项目平均分配到其关联的输出节点。
- 可能有1到N个输入节点。
- 可能有1到M个输出节点。
- 来自输入节点的边被合并，然后拆分到输出节点。
- 输出节点永远不会连接到输入节点。
- 当 Iode "ticks" 它在其关联节点上执行平衡操作。
- 每个节点每个刻度的最大输入。
- 每个节点每个刻度的最大输出。
- 每个滴答的最大总吞吐量。
这是连接方式的示意图（使用 http://pencil.evolus.vn/）：
每个方块都是一个节点。每个节点可以包含一些数字。
我对 Iode tick 的算法有困难。我想最大化吞吐量，这可能会受到多种方式的限制。
这是我对 github (https://github.com/voxelv/ioder) 的初步 python 尝试，特别是在 algorithms.py:
def iode_int_tick(iode):
# Get the amounts per input iode node
input_amount_per_iode_node = []
for iode_node in iode.input_nodes:
input_amount_per_iode_node.append(min(iode_node.amount, iode.speed['input']))
# Get the amounts per output iode node
output_amount_per_iode_node = []
for iode_node in iode.output_nodes:
output_amount_per_iode_node.append(iode.speed['output'])
# Get the maximum throughput
max_thru_speed = int(iode.speed['throughput'])
input_amount_total = sum(input_amount_per_iode_node)
output_amount_total = sum(output_amount_per_iode_node)
# Compare the maximum throughput
diff_input_thru_max = int(input_amount_total - max_thru_speed)
diff_output_thru_max = int(output_amount_total - max_thru_speed)
# Lessen the input if the maximum throughput is smaller
if diff_input_thru_max > 0:
for i in xrange(len(iode.input_nodes)):
pass # TODO: figure out this
# Lessen the output if the maximum throughput is smaller
if diff_output_thru_max > 0:
for i in xrange(len(iode.input_nodes)):
pass # TODO: figure out this
# Move the numbers from the inputs
for i, inode in enumerate(iode.input_nodes):
inode.take(input_amount_per_iode_node[i])
# Move the numbers into the outputs
for i, inode in enumerate(iode.output_nodes):
inode.give(output_amount_per_iode_node[i])
我正在尝试找出具有 # TODO 注释的 for 循环中的内容。
编辑：示例已加载到 main.py 和 config.py。
每个节点的输入限制为 5
每个节点的输出限制为5
最大吞吐量为 8
因此，将两个输入设置为 23 和 6，将两个输出设置为 4 和 0，输入节点的预期结果为 19 和 2，输出节点为 8 和 4。
运行 带有 python main.py 的代码导致以下输出：
Actual: [18, 1], [9, 5]
Expected: [19, 2], [8, 4]
更多示例：
Initial: [22, 2], [3, 20]
Actual: [17, 0], [8, 25]
Expected: [17, 0], [7, 23] or [17, 0], [6, 24]
根据处理余数的顺序，预期可能是所提到的任何一个。最大吞吐量将我们限制为 8，但每个节点的最大输入限制我们从第一个输入节点获取 5。由于第二个输入节点只有两个，所以我们只能为这个刻度提供 7 个。 7 尽可能均匀地分配到输出，3 或 4 进入第一个输出，4 或 3 进入第二个输出。
我想出了一个我的问题的类比，并且能够通过类比更好地理解它。
这就像试图用水填充冰块托盘。
按照我构建 Iode 的方式，水永远不会超过托盘的处理能力。
这是我的解决方案：
def water_into_ice_tray(water, ice_tray, **kwargs):
water_to_put = [0 for _ in xrange(len(ice_tray))]
recursion_ice_tray = [x for x in ice_tray]
# Debug depth
if 'depth' in kwargs:
print kwargs['depth'],
kwargs['depth'] += 1
# BASE_CASE: No more water
if not water > 0:
# Exit early
return water_to_put
# Get slots that have space for more water
open_slots = []
for i in xrange(len(ice_tray)):
if ice_tray[i] > 0:
open_slots.append(i)
# BASE_CASE: Not enough water to go around
if water < len(open_slots):
# Put 1 more in the first 'water' slots
for i in xrange(water):
water_to_put[open_slots[i]] += 1
# Exit early
return water_to_put
# BASE_CASE: Too much water
if water > sum(ice_tray):
raise ValueError("Too much water")
# Attempt to fill each open slot with a distributed amount
fill_amount = int(math.floor(int(water) / len(open_slots)))
leftover = int(water) % len(open_slots)
for slot_index in open_slots:
# With how much water have we overfilled this slot?
diff = fill_amount - ice_tray[slot_index]
if diff >= 0:
# We tried putting too much water into this slot
# Calculate how much to put in it
water_to_put[slot_index] += fill_amount - diff
# No more water can fit into this slot
recursion_ice_tray[slot_index] = 0
# Keep the leftover
leftover += diff
else:
# The slot could hold the water
water_to_put[slot_index] += fill_amount
# Some more water can fit into this slot
recursion_ice_tray[slot_index] = -diff
# None is leftover
# Recurse
recursion_water_to_put = water_into_ice_tray(leftover, recursion_ice_tray, **kwargs)
# Add up recursion result to this result
return map(add, water_to_put, recursion_water_to_put)
def iode_int_tick(iode):
# Calculate available amounts per input node
available_input_per_node = []
for inode in iode.input_nodes:
available_input_per_node.append(min(inode.amount, iode.speed['input']))
input_limit = sum(available_input_per_node)
# Get the throughput
throughput_limit = iode.speed['throughput']
# Calculate available space per output node
available_output_per_node = []
for inode in iode.output_nodes:
available_output_per_node.append(min(inode.max_amount - inode.amount, iode.speed['output']))
output_limit = sum(available_output_per_node)
# Decide which is the limiting factor
limiter = min(input_limit, throughput_limit, output_limit)
if limiter == input_limit:
# If the input limits, then distribute to the outputs. The throughput can handle it.
amount_to_take_per_input_node = available_input_per_node
amount_to_put_per_output_node = water_into_ice_tray(input_limit, available_output_per_node)
pass
elif limiter == throughput_limit:
# If throughput limits, then distribute the throughput amount from the inputs, to the outputs.
amount_to_take_per_input_node = water_into_ice_tray(throughput_limit, available_input_per_node)
amount_to_put_per_output_node = water_into_ice_tray(throughput_limit, available_output_per_node)
pass
elif limiter == output_limit:
# If output limits, then distribute the draw on the inputs. The throughput can handle it.
amount_to_take_per_input_node = water_into_ice_tray(output_limit, available_input_per_node)
amount_to_put_per_output_node = available_output_per_node
pass
else:
raise ValueError("Somehow the limiting factor is something other than the input, throughput, or output.")
# Do the taking
for i in xrange(len(iode.input_nodes)):
iode.input_nodes[i].take(amount_to_take_per_input_node[i])
# Do the giving
for i in xrange(len(iode.output_nodes)):
iode.output_nodes[i].give(amount_to_put_per_output_node[i])