计算机问题求解周期

问题与问题实例的定义

问题：是需要我们回答的一般性提问，通常含有若干参数，由求解问题描述，输入条件以及输出要求等要素组成。

问题实例：定义为确定问题描述参数后的一个对象。

• 一个问题可以包含若干问题实例
• 问题和问题实例的关系类似于C++语言中类和类对象的关系

正整数求和问题

任务描述：计算正整数a与b的和c
输入：正整数a、b(1<=a,b<=10000)
输出：和c。

• 问题实例1：a=1,b=1
• 问题实例2：a=1000,b=10000

棋盘迷宫问题

问题描述：在一个棋盘迷宫中，有些格子能通行(用1表示)，有些格子不能通行(用0表示)，嘉定棋盘位置(1,1)为入口，(N,N)为出口，且在棋盘中只能横向或者竖向移动。任意给定一棋盘，试问是否存在从入口到出口的路径。
输入：正整数N表示棋盘的大小，以及N*N的0-1矩阵表示每个棋盘格子的状态。
输出：1，表示存在路径；0，表示不存在。

问题求解的过程

问题求解周期：从一个问题的提出，到计算机可执行的、满足准确性和复杂性要求的程序算法的完成，可以看作是“计算机问题求解”的一个周期。问题求解周期包括问题简化，模型构建，算法设计，程序设计与测试等过程。

• 抽象：对问题形式化描述
• 建模：对问题和数据分析和建模
• 算法：设计有效的计算机算法
• 实现：用特定程序设计语言实现算法
• 验证：测试、验证与推广

计算思维：是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等蕴含计算机科学之广度的一系列思维活动。计算思维是一种普适思维方法和基本技能。

• 通过简约、嵌入、转化和仿真等方法，把一个看来困难的问题重新阐释成一个我们知道问题怎样解决的方法；
• 是一种采用抽象和分解来控制庞杂的任务或进行巨大复杂系统设计的方法，是基于关注分离的方法；
• 是利用启发式推理寻求解答，也即在不确定情况下的规划、学习和调度的思维方法；
• 是利用海量数据来加快计算，在时间和空间之间，在处理能力和存储容量之间进行折衷的思维方法；
• ...

补丁与Bug问题

错误就是人们所说的Bug，用户在试用软件时总是希望其错误越少越好，最好是没有错误的。但是推出一个没有错误的软件几乎是不可能的，所以很多软件公司都在疯狂地发放补丁(有时这种补丁甚至是收费的)。T公司就是其中之一。上个月，T公司推出了一个新的字处理阮籍，随后发放了一批补丁。最近T公司发现其发放的补丁有致命的问题，那就是一个补丁在排除某些错误时，往往会加入另一些错误，此字处理软件中只可能出现n个特定的脱误，这n个错误是由软件本身决定的。T公司目前共发放了m个补丁，对于每一个补丁，都有特定的适用环境，某个补丁只有在当前软件中包含某些错误而同时又不包含另一些错误时才可以使用，如果它被使用，它将修复某些错误而同时加入某些错误。另外，使用某个补丁都要耗一定的时间(即补丁程序的运行时间)。
????????
现在T公司的问题很简单：其字处理软件的初始版本不幸地包含了全部的n个错误，有没有可能通过使用这m个补丁(任意顺序地使用，一个补丁可使用多次)，使此字处理软件成为一个没有错误的软件。如果可能，希望找到总耗时最少的方案。

任务描述：T公司的字处理软件中可能出现n个错误的集合B={b1,b2,...,bn}中的元素，T公司目前共发放了m个补丁，记为P={p1,p2,pm}。对于每一个补丁(P_i)，假设存在错误集合(B_{i+},B_{i-})，当软件包含(B_{i+})中的所有错误，而没有包含(B_{i-})中的任何错误时，补丁(P_i)才可以被使用，否则不能使用，显然(B_{i+},B_{i-})交集为空。补丁(P_i)将修复某些错误而同时加入某些错误，设错误集合(F_{i+},F_{i-})使用过补丁(P_i)之后，(F_{i-})中的任何错误都不会在软件中出现，而软件将包含(F_{i+})中的所有错误，同样(F_{i+},F_{i-})交集为空。另外，使用每个补丁都要耗一定的时间(T_i)。
????????
现在T公司的字处理软件的初始版本不幸地包含了全部n个错误，试编写程序判断有没有可能通过使用这m个补丁(任意顺序地使用，一个补丁可使用多次)，使此字处理软件成为一个没有错误的软件。如果可能，希望找到总耗时最少的方案。
输入格式：第一行有两个正整数n和m，n表示bug总数，m表示补丁总数，1<=n<=15，1<=m<=100，接下来m行给了m个补丁的信息。每行包括一个正整数(T_i)(表示此补丁程序(P_i)的运行耗时)和两个长度为n的字符串，中间用一个空格符隔开。
????????
第一个字符串，如果第K个字符为"+"，则表示(b_k)属于(B_{i+})，若为"-"，则表示(b_k)属于(B_{i-})，若为"0"，则(b_k)既不属于(B_{i+})也不属于(B_{i-})，即软件中是否包含(b_k)不会影响补丁(P_i)是否可用。
????????
第二个字符串，如果第K个字符为"+"，则表示(b_k)属于(F_{i+})，若为"-"，则表示(b_k)属于(F_{i-})，若为"0"，则(b_k)既不属于(F_{i+})也不属于(F_{i-})，即软件中是否包含(b_k)不会因为使用补丁(P_i)而改变。
输出格式：输出一个整数，如果问题有解，输出总耗时，否则输出0。

• 构建模型：把n个bug的状态(存在和不存在)的组合用一个0-1字符串(模式串)表示，执行一个补丁基本上就是模式串的转换。模式串作为一个图的定点，补丁则是边，问题则转换为从全1模式串到全0模式串的转换。
  
• 设计最短路径算法：Dijkstra最短路径算法求解
  
• 编程实现
  
• 测试