如何将枚举算法应用到问题中？
How to apply an enumeration algorithm into a problem?
我是 Whosebug 的新手，我想知道是否有合适的 method/algorithm 来解决我的示例问题，以便生成符合问题某些条件的所需解决方案。这是我的 json 文件（example1.json），您可以从这里找到：https://gitlab.com/Schrodinger168/practice/-/blob/master/example1.json
我将解释 csv 文件和我想要生成的内容如下：
对于资源有例如Ressources_X，X这里可以是从 1 到 9 的值。所有 Ressource_X 都有它们的 min 和 max 值需要注意的是，对于所有 Ressources_X.
季节有冬天、夏天、是...并且每个数字对应于那些季节指的是天例如冬季定义从第1天到第13天，其他季节表示相同。
对于干预措施：是否必须计划任务。有Intervention_X，相应的工作量包含他们必须使用的Ressources_X。 Delta 是 Intervention_X 的持续时间，例如我们可以在 Intervention_625[=86 中看到=] 作为 Delta 列表中的第一个值（第 1 天）是 1.0 这意味着如果 Intervention_625 从第 1 天开始，它需要在同一天（第 1 天）结束，因为第 1 天的 Delta 值为 1.0 等等......每个 Intervention_X 有自己的 tmax 例如 Intervention_625 有 tmax 等于 17 这意味着它可以在我们希望生成的第 1 天和第 17 天之间开始，另一个 tmax的其他Intervention_X意思相同
对于排除有一些例外，例如：
"E141["Intervention_315","Intervention_456","summer"]表示Intervention_315和Intervention_456不能在夏季同一天开始（夏季可以不同天开始），其他意思相同。
T这里是总时长T = 17表示整个作品的时长是17天
我想要生成的解决方案是干预的名称和每个干预的开始日期 (tx,ty..) 例如：
Intervention_X 发送
Intervention_Y ty
依此类推...直到所有干预都被使用，因为它们只会使用一次。
解决方案将确保它遵守每天使用资源（最小值、最大值）的条件、排除 ，并且完成日期最多可以是 T + 1。
如果需要，这是我的代码，用于访问我的 json 文件的每个节点和值：
class access_json:
def __init__(self):
self._resources = dict()
self._seasons = dict()
self._interventions = dict()
self._exclusions = dict()
self._NRESOURCES = 0
self._NINTERVENTIONS = 0
self._list_resources = list()
self._list_interventions = list()
self._T = 0
def loadjson(self, fpath: str):
js = dict()
with open(fpath, 'r') as f:
js = json.load(f)
self._resources = js["Resources"]
self._NRESOURCES = len(self._resources)
self._list_resources = list(self._resources.keys())
self._seasons = js["Seasons"]
self._interventions = js["Interventions"]
self._NINTERVENTIONS = len(self._interventions)
self._list_interventions = list(self._interventions.keys())
self._exclusions = js["Exclusions"]
self._T = js["T"]
为了解决问题，我尝试每天使用排列来交换和替换那些干预措施，但这样做似乎很长，而且没有生成解决方案。任何有关代码的帮助，以及有关如何应用该算法解决此问题的建议，我们将不胜感激。先谢谢你！
这可以使用 backtracking algorithm 快速解决。特别是，使用规定的数据可以在毫秒内解决。
代码
def overlap(x, y):
'''
Checks if two time segments overlap
'''
a, b = x
c, d = y
return a <= d and b >= c
def allocate(data, ans = None):
'''
Intervention schedule allocation based upon backtracking
'''
if ans is None:
ans = {}
if len(ans) == len(data["Interventions"]):
# handled all the interventions
yield ans
# Check next intervention
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# will add items not in ans
# last day intervention can be run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
str_day = str(day)
# different days intervention could be run
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# must finish within last day
# Check that there are sufficient resources
resource_usage = {}
missing_resources = False
for resource_name, v in intervention["workload"].items():
if not str_day in v:
missing_resources = True
break
#raise Exception(f'{intervention_name} resources {k} missing day {str_day}')
usage_key = (resource_name, day) # pair: (resource name, day) as key
resource_usage[usage_key] = v[str_day][str_day]
if missing_resources:
continue # one resource has no resources for a day
# Resources needed by items in list for this day
for ans_name, ans_response in ans.items():
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
# An intervention in answer overlaps with current intervention
for resource_name, v_resource in ans_response["Resources"].items():
for overlap_day in range(day, day+int(delta)):
# Get resource usage for each day of overlap
usage_key = (resource_name, overlap_day)
if not usage_key in resource_usage:
resource_usage[usage_key] = 0
resource_usage[usage_key] += v_resource
# Check resource less than max
resources = data["Resources"]
for usage_key, value in resource_usage.items():
resource_name, overlap_day = usage_key # values from tuple
if value > resources[resource_name]["max"][day-1]: # max value for resoure for this day
break
else:
# Resource didn't exceed max
# Check on Exclusion
winter = data["Seasons"]['winter']
summer = data["Seasons"]['summer']
isa = data["Seasons"]['is']
if str_day in winter:
season = "winter"
elif str_day in summer:
season = "summer"
elif str_day in isa:
season = "is"
else:
season = ""
exclusions = data["Exclusions"]
bExclude = False
for k, v_lst in exclusions.items():
if season in v_lst and intervention_name in v_lst:
for intervention_k, ans_response in ans.items():
if intervention_k in v_lst:
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
bExclude = True
break
if bExclude:
break
if not bExclude:
# Resources used
response = {"Day": day, "Delta": intervention["Delta"][day-1]}
resources = {k:v[str_day][str_day] for k, v in intervention["workload"].items()}
response['Resources'] = resources
ans[intervention_name] = response
yield from allocate(data, ans)
# Remove last entry so we can try next iteration
del ans[intervention_name]
用法
使用发布的数据集
# Loading data from local file
with open('resource_allocation/example1.json', 'r') as f:
data = json.load(f)
# Get first solution using from allocate generator
answer = next(allocate(data), None)
if answer:
for name, intervention in answer.items():
print(f'Intervention {name}')
print(f'\tStart {intervention["Day"]}, Duration: {intervention["Delta"]}')
resources = intervention["Resources"]
for k, v in resources.items():
print(f'\tResource: {k} Usage: {v}')
print()
输出
Intervention Intervention_625
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_4 Usage: 0.14
Resource: Ressources_7 Usage: 0.14
Resource: Ressources_8 Usage: 0.056
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_31
Start 1, Duration: 2.0
Resource: Ressources_3 Usage: 0.86
Resource: Ressources_4 Usage: 0.86
Resource: Ressources_9 Usage: 0.086
Intervention Intervention_40
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.29
Resource: Ressources_7 Usage: 0.29
Resource: Ressources_9 Usage: 0.029
Intervention Intervention_224
Start 1, Duration: 1.0
Resource: Ressources_1 Usage: 0.71
Resource: Ressources_9 Usage: 0.071
Intervention Intervention_702
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.43
Resource: Ressources_9 Usage: 0.043
Intervention Intervention_19
Start 1, Duration: 2.0
Resource: Ressources_4 Usage: 0.86
Resource: Ressources_8 Usage: 0.344
Resource: Ressources_9 Usage: 0.086
Intervention Intervention_672
Start 1, Duration: 1.0
Resource: Ressources_3 Usage: 0.43
Resource: Ressources_9 Usage: 0.043
Intervention Intervention_579
Start 1, Duration: 1.0
Resource: Ressources_8 Usage: 0.028
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_627
Start 1, Duration: 2.0
Resource: Ressources_2 Usage: 0.86
Resource: Ressources_7 Usage: 0.86
Resource: Ressources_8 Usage: 0.344
Resource: Ressources_9 Usage: 0.086
Intervention Intervention_456
Start 1, Duration: 1.0
Resource: Ressources_4 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_90
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_315
Start 2, Duration: 1.0
Resource: Ressources_4 Usage: 0.14
Resource: Ressources_6 Usage: 0.14
Resource: Ressources_7 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_356
Start 1, Duration: 1.0
Resource: Ressources_7 Usage: 0.57
Resource: Ressources_9 Usage: 0.057
Intervention Intervention_535
Start 1, Duration: 1.0
Resource: Ressources_3 Usage: 0.29
Resource: Ressources_7 Usage: 0.29
Resource: Ressources_9 Usage: 0.029
Intervention Intervention_595
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_592
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_8 Usage: 0.056
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_536
Start 1, Duration: 1.0
Resource: Ressources_3 Usage: 0.14
Resource: Ressources_7 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_150
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_6 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
说明
伪代码
def allocate(data, ans = None):
# initize answer if not initialized
if ans is None:
ans = {} # dictionary of interventions with name, day and resources used
# Base case (check if solution found)
if len(ans) == len(data["Interventions"]):
yield ans # let me know if you're not familiar with generators
# Try remaining interventions (i.e. ones not in answer ans)
# Loop over all interventions
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# This intervention not in answer ans
# Found out what day to run the intervention
# last day to run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
# Range of days to try running the intervention
# make sure intervention finishes before last day
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# Check if intervention satisfies constraints if we add it on this day
# 1--check sufficient resources
# logic for checking if suffient resources
# set sufficient_resources to True if sufficient, False otherwise
if sufficient_resources:
# 2--check if intervention compatible with others in list
# i.e. can run on same day as others in ans
# set compatible to True if not excluded by others in list, False otherwise
if compatible:
# add intervention to ans for this day with the resources it uses on this day
# we call this response
# Add intervention for this day
ans[intervention_name] = response
# now recursive try other interventions
# This recursives tries other interventions
# by now successively trying the next intervention which is not in ans on a compatibl day
yield from allocate(data, and)
del ans[intervention_name] # remove last entry
伪代码--non-generator函数（但只求第一个解）
def allocate(data, ans = None):
# initize answer if not initialized
if ans is None:
ans = {} # dictionary of interventions with name, day and resources used
# Base case (check if solution found)
if len(ans) == len(data["Interventions"]):
return True # let me know if you're not familiar with generators
# Try remaining interventions (i.e. ones not in answer ans)
# Loop over all interventions
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# This intervention not in answer ans
# Found out what day to run the intervention
# last day to run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
# Range of days to try running the intervention
# make sure intervention finishes before last day
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# Check if intervention satisfies constraints if we add it on this day
# 1--check sufficient resources
# logic for checking if suffient resources
# set sufficient_resources to True if sufficient, False otherwise
if sufficient_resources:
# 2--check if intervention compatible with others in list
# i.e. can run on same day as others in ans
# set compatible to True if not excluded by others in list, False otherwise
if compatible:
# add intervention to ans for this day with the resources it uses on this day
# we call this response
# Add intervention for this day
ans[intervention_name] = response
# now recursive try other interventions
# This recursives tries other interventions
# by now successively trying the next intervention which is not in ans on a compatibl day
if allocate(data, ans):
# Path forward found a solution
return True
else:
# Backtrack--this day won't work
# remove intervention since won't work for this day
del ans[intervention_name]
Non-Generator版本
def overlap(x, y):
'''
Checks if two time segments overlap
'''
a, b = x
c, d = y
return a <= d and b >= c
def allocate2(data, ans = None):
'''
Intervention schedule allocation based upon backtracking
'''
if ans is None:
ans = {}
if len(ans) == len(data["Interventions"]):
# handled all the interventions
return ans
# Check next intervention
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# will add items not in ans
# last day intervention can be run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
str_day = str(day)
# different days intervention could be run
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# must finish within last day
# Check that there are sufficient resources
resource_usage = {}
missing_resources = False
for resource_name, v in intervention["workload"].items():
if not str_day in v:
missing_resources = True
break
#raise Exception(f'{intervention_name} resources {k} missing day {str_day}')
usage_key = (resource_name, day) # pair: (resource name, day) as key
resource_usage[usage_key] = v[str_day][str_day]
if missing_resources:
continue # one resource has no resources for a day
# Resources needed by items in list for this day
for ans_name, ans_response in ans.items():
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
# An intervention in answer overlaps with current intervention
for resource_name, v_resource in ans_response["Resources"].items():
for overlap_day in range(day, day+int(delta)):
# Get resource usage for each day of overlap
usage_key = (resource_name, overlap_day)
if not usage_key in resource_usage:
resource_usage[usage_key] = 0
resource_usage[usage_key] += v_resource
# Check resource less than max
resources = data["Resources"]
for usage_key, value in resource_usage.items():
resource_name, overlap_day = usage_key # values from tuple
if value > resources[resource_name]["max"][day-1]: # max value for resoure for this day
break
else:
# Resource didn't exceed max
# Check on Exclusion
winter = data["Seasons"]['winter']
summer = data["Seasons"]['summer']
isa = data["Seasons"]['is']
if str_day in winter:
season = "winter"
elif str_day in summer:
season = "summer"
elif str_day in isa:
season = "is"
else:
season = ""
exclusions = data["Exclusions"]
bExclude = False
for k, v_lst in exclusions.items():
if season in v_lst and intervention_name in v_lst:
for intervention_k, ans_response in ans.items():
if intervention_k in v_lst:
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
bExclude = True
break
if bExclude:
break
if not bExclude:
# Resources used
response = {"Day": day, "Delta": intervention["Delta"][day-1]}
resources = {k:v[str_day][str_day] for k, v in intervention["workload"].items()}
response['Resources'] = resources
ans[intervention_name] = response
result = allocate2(data, ans)
if result:
# was able to find an answer going forward using intervention
# on this day,so return the result
return result
# Remove last entry so we can try next iteration
del ans[intervention_name]
用法
answer = allocate2(data)
我是 Whosebug 的新手，我想知道是否有合适的 method/algorithm 来解决我的示例问题，以便生成符合问题某些条件的所需解决方案。这是我的 json 文件（example1.json），您可以从这里找到：https://gitlab.com/Schrodinger168/practice/-/blob/master/example1.json
我将解释 csv 文件和我想要生成的内容如下：
对于资源有例如Ressources_X，X这里可以是从 1 到 9 的值。所有 Ressource_X 都有它们的 min 和 max 值需要注意的是，对于所有 Ressources_X.
季节有冬天、夏天、是...并且每个数字对应于那些季节指的是天例如冬季定义从第1天到第13天，其他季节表示相同。
对于干预措施：是否必须计划任务。有Intervention_X，相应的工作量包含他们必须使用的Ressources_X。 Delta 是 Intervention_X 的持续时间，例如我们可以在 Intervention_625[=86 中看到=] 作为 Delta 列表中的第一个值（第 1 天）是 1.0 这意味着如果 Intervention_625 从第 1 天开始，它需要在同一天（第 1 天）结束，因为第 1 天的 Delta 值为 1.0 等等......每个 Intervention_X 有自己的 tmax 例如 Intervention_625 有 tmax 等于 17 这意味着它可以在我们希望生成的第 1 天和第 17 天之间开始，另一个 tmax的其他Intervention_X意思相同
对于排除有一些例外，例如：
"E141["Intervention_315","Intervention_456","summer"]表示Intervention_315和Intervention_456不能在夏季同一天开始（夏季可以不同天开始），其他意思相同。
T这里是总时长T = 17表示整个作品的时长是17天
我想要生成的解决方案是干预的名称和每个干预的开始日期 (tx,ty..) 例如：
Intervention_X 发送
Intervention_Y ty
依此类推...直到所有干预都被使用，因为它们只会使用一次。
解决方案将确保它遵守每天使用资源（最小值、最大值）的条件、排除 ，并且完成日期最多可以是 T + 1。
如果需要，这是我的代码，用于访问我的 json 文件的每个节点和值：
class access_json:
def __init__(self):
self._resources = dict()
self._seasons = dict()
self._interventions = dict()
self._exclusions = dict()
self._NRESOURCES = 0
self._NINTERVENTIONS = 0
self._list_resources = list()
self._list_interventions = list()
self._T = 0
def loadjson(self, fpath: str):
js = dict()
with open(fpath, 'r') as f:
js = json.load(f)
self._resources = js["Resources"]
self._NRESOURCES = len(self._resources)
self._list_resources = list(self._resources.keys())
self._seasons = js["Seasons"]
self._interventions = js["Interventions"]
self._NINTERVENTIONS = len(self._interventions)
self._list_interventions = list(self._interventions.keys())
self._exclusions = js["Exclusions"]
self._T = js["T"]
为了解决问题，我尝试每天使用排列来交换和替换那些干预措施，但这样做似乎很长，而且没有生成解决方案。任何有关代码的帮助，以及有关如何应用该算法解决此问题的建议，我们将不胜感激。先谢谢你！
这可以使用 backtracking algorithm 快速解决。特别是，使用规定的数据可以在毫秒内解决。
代码
def overlap(x, y):
'''
Checks if two time segments overlap
'''
a, b = x
c, d = y
return a <= d and b >= c
def allocate(data, ans = None):
'''
Intervention schedule allocation based upon backtracking
'''
if ans is None:
ans = {}
if len(ans) == len(data["Interventions"]):
# handled all the interventions
yield ans
# Check next intervention
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# will add items not in ans
# last day intervention can be run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
str_day = str(day)
# different days intervention could be run
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# must finish within last day
# Check that there are sufficient resources
resource_usage = {}
missing_resources = False
for resource_name, v in intervention["workload"].items():
if not str_day in v:
missing_resources = True
break
#raise Exception(f'{intervention_name} resources {k} missing day {str_day}')
usage_key = (resource_name, day) # pair: (resource name, day) as key
resource_usage[usage_key] = v[str_day][str_day]
if missing_resources:
continue # one resource has no resources for a day
# Resources needed by items in list for this day
for ans_name, ans_response in ans.items():
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
# An intervention in answer overlaps with current intervention
for resource_name, v_resource in ans_response["Resources"].items():
for overlap_day in range(day, day+int(delta)):
# Get resource usage for each day of overlap
usage_key = (resource_name, overlap_day)
if not usage_key in resource_usage:
resource_usage[usage_key] = 0
resource_usage[usage_key] += v_resource
# Check resource less than max
resources = data["Resources"]
for usage_key, value in resource_usage.items():
resource_name, overlap_day = usage_key # values from tuple
if value > resources[resource_name]["max"][day-1]: # max value for resoure for this day
break
else:
# Resource didn't exceed max
# Check on Exclusion
winter = data["Seasons"]['winter']
summer = data["Seasons"]['summer']
isa = data["Seasons"]['is']
if str_day in winter:
season = "winter"
elif str_day in summer:
season = "summer"
elif str_day in isa:
season = "is"
else:
season = ""
exclusions = data["Exclusions"]
bExclude = False
for k, v_lst in exclusions.items():
if season in v_lst and intervention_name in v_lst:
for intervention_k, ans_response in ans.items():
if intervention_k in v_lst:
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
bExclude = True
break
if bExclude:
break
if not bExclude:
# Resources used
response = {"Day": day, "Delta": intervention["Delta"][day-1]}
resources = {k:v[str_day][str_day] for k, v in intervention["workload"].items()}
response['Resources'] = resources
ans[intervention_name] = response
yield from allocate(data, ans)
# Remove last entry so we can try next iteration
del ans[intervention_name]
用法
使用发布的数据集
# Loading data from local file
with open('resource_allocation/example1.json', 'r') as f:
data = json.load(f)
# Get first solution using from allocate generator
answer = next(allocate(data), None)
if answer:
for name, intervention in answer.items():
print(f'Intervention {name}')
print(f'\tStart {intervention["Day"]}, Duration: {intervention["Delta"]}')
resources = intervention["Resources"]
for k, v in resources.items():
print(f'\tResource: {k} Usage: {v}')
print()
输出
Intervention Intervention_625
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_4 Usage: 0.14
Resource: Ressources_7 Usage: 0.14
Resource: Ressources_8 Usage: 0.056
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_31
Start 1, Duration: 2.0
Resource: Ressources_3 Usage: 0.86
Resource: Ressources_4 Usage: 0.86
Resource: Ressources_9 Usage: 0.086
Intervention Intervention_40
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.29
Resource: Ressources_7 Usage: 0.29
Resource: Ressources_9 Usage: 0.029
Intervention Intervention_224
Start 1, Duration: 1.0
Resource: Ressources_1 Usage: 0.71
Resource: Ressources_9 Usage: 0.071
Intervention Intervention_702
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.43
Resource: Ressources_9 Usage: 0.043
Intervention Intervention_19
Start 1, Duration: 2.0
Resource: Ressources_4 Usage: 0.86
Resource: Ressources_8 Usage: 0.344
Resource: Ressources_9 Usage: 0.086
Intervention Intervention_672
Start 1, Duration: 1.0
Resource: Ressources_3 Usage: 0.43
Resource: Ressources_9 Usage: 0.043
Intervention Intervention_579
Start 1, Duration: 1.0
Resource: Ressources_8 Usage: 0.028
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_627
Start 1, Duration: 2.0
Resource: Ressources_2 Usage: 0.86
Resource: Ressources_7 Usage: 0.86
Resource: Ressources_8 Usage: 0.344
Resource: Ressources_9 Usage: 0.086
Intervention Intervention_456
Start 1, Duration: 1.0
Resource: Ressources_4 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_90
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_315
Start 2, Duration: 1.0
Resource: Ressources_4 Usage: 0.14
Resource: Ressources_6 Usage: 0.14
Resource: Ressources_7 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_356
Start 1, Duration: 1.0
Resource: Ressources_7 Usage: 0.57
Resource: Ressources_9 Usage: 0.057
Intervention Intervention_535
Start 1, Duration: 1.0
Resource: Ressources_3 Usage: 0.29
Resource: Ressources_7 Usage: 0.29
Resource: Ressources_9 Usage: 0.029
Intervention Intervention_595
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_592
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_8 Usage: 0.056
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_536
Start 1, Duration: 1.0
Resource: Ressources_3 Usage: 0.14
Resource: Ressources_7 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
Intervention Intervention_150
Start 1, Duration: 1.0
Resource: Ressources_2 Usage: 0.14
Resource: Ressources_6 Usage: 0.14
Resource: Ressources_9 Usage: 0.014
说明
伪代码
def allocate(data, ans = None):
# initize answer if not initialized
if ans is None:
ans = {} # dictionary of interventions with name, day and resources used
# Base case (check if solution found)
if len(ans) == len(data["Interventions"]):
yield ans # let me know if you're not familiar with generators
# Try remaining interventions (i.e. ones not in answer ans)
# Loop over all interventions
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# This intervention not in answer ans
# Found out what day to run the intervention
# last day to run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
# Range of days to try running the intervention
# make sure intervention finishes before last day
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# Check if intervention satisfies constraints if we add it on this day
# 1--check sufficient resources
# logic for checking if suffient resources
# set sufficient_resources to True if sufficient, False otherwise
if sufficient_resources:
# 2--check if intervention compatible with others in list
# i.e. can run on same day as others in ans
# set compatible to True if not excluded by others in list, False otherwise
if compatible:
# add intervention to ans for this day with the resources it uses on this day
# we call this response
# Add intervention for this day
ans[intervention_name] = response
# now recursive try other interventions
# This recursives tries other interventions
# by now successively trying the next intervention which is not in ans on a compatibl day
yield from allocate(data, and)
del ans[intervention_name] # remove last entry
伪代码--non-generator函数（但只求第一个解）
def allocate(data, ans = None):
# initize answer if not initialized
if ans is None:
ans = {} # dictionary of interventions with name, day and resources used
# Base case (check if solution found)
if len(ans) == len(data["Interventions"]):
return True # let me know if you're not familiar with generators
# Try remaining interventions (i.e. ones not in answer ans)
# Loop over all interventions
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# This intervention not in answer ans
# Found out what day to run the intervention
# last day to run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
# Range of days to try running the intervention
# make sure intervention finishes before last day
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# Check if intervention satisfies constraints if we add it on this day
# 1--check sufficient resources
# logic for checking if suffient resources
# set sufficient_resources to True if sufficient, False otherwise
if sufficient_resources:
# 2--check if intervention compatible with others in list
# i.e. can run on same day as others in ans
# set compatible to True if not excluded by others in list, False otherwise
if compatible:
# add intervention to ans for this day with the resources it uses on this day
# we call this response
# Add intervention for this day
ans[intervention_name] = response
# now recursive try other interventions
# This recursives tries other interventions
# by now successively trying the next intervention which is not in ans on a compatibl day
if allocate(data, ans):
# Path forward found a solution
return True
else:
# Backtrack--this day won't work
# remove intervention since won't work for this day
del ans[intervention_name]
Non-Generator版本
def overlap(x, y):
'''
Checks if two time segments overlap
'''
a, b = x
c, d = y
return a <= d and b >= c
def allocate2(data, ans = None):
'''
Intervention schedule allocation based upon backtracking
'''
if ans is None:
ans = {}
if len(ans) == len(data["Interventions"]):
# handled all the interventions
return ans
# Check next intervention
for intervention_name, intervention in data["Interventions"].items():
if intervention_name not in ans:
# will add items not in ans
# last day intervention can be run
last_day = min(data["T"], int(intervention["tmax"]))
for day in range(1, last_day+1):
str_day = str(day)
# different days intervention could be run
delta = intervention["Delta"][day-1] # number of days it takes to run
if day + delta <= last_day + 1:
# must finish within last day
# Check that there are sufficient resources
resource_usage = {}
missing_resources = False
for resource_name, v in intervention["workload"].items():
if not str_day in v:
missing_resources = True
break
#raise Exception(f'{intervention_name} resources {k} missing day {str_day}')
usage_key = (resource_name, day) # pair: (resource name, day) as key
resource_usage[usage_key] = v[str_day][str_day]
if missing_resources:
continue # one resource has no resources for a day
# Resources needed by items in list for this day
for ans_name, ans_response in ans.items():
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
# An intervention in answer overlaps with current intervention
for resource_name, v_resource in ans_response["Resources"].items():
for overlap_day in range(day, day+int(delta)):
# Get resource usage for each day of overlap
usage_key = (resource_name, overlap_day)
if not usage_key in resource_usage:
resource_usage[usage_key] = 0
resource_usage[usage_key] += v_resource
# Check resource less than max
resources = data["Resources"]
for usage_key, value in resource_usage.items():
resource_name, overlap_day = usage_key # values from tuple
if value > resources[resource_name]["max"][day-1]: # max value for resoure for this day
break
else:
# Resource didn't exceed max
# Check on Exclusion
winter = data["Seasons"]['winter']
summer = data["Seasons"]['summer']
isa = data["Seasons"]['is']
if str_day in winter:
season = "winter"
elif str_day in summer:
season = "summer"
elif str_day in isa:
season = "is"
else:
season = ""
exclusions = data["Exclusions"]
bExclude = False
for k, v_lst in exclusions.items():
if season in v_lst and intervention_name in v_lst:
for intervention_k, ans_response in ans.items():
if intervention_k in v_lst:
ans_day = ans_response["Day"]
ans_delta = ans_response["Delta"]
if overlap([day, day+delta-1], [ans_day, ans_day+ans_delta-1]):
bExclude = True
break
if bExclude:
break
if not bExclude:
# Resources used
response = {"Day": day, "Delta": intervention["Delta"][day-1]}
resources = {k:v[str_day][str_day] for k, v in intervention["workload"].items()}
response['Resources'] = resources
ans[intervention_name] = response
result = allocate2(data, ans)
if result:
# was able to find an answer going forward using intervention
# on this day,so return the result
return result
# Remove last entry so we can try next iteration
del ans[intervention_name]
用法
answer = allocate2(data)