专栏名称: 算法爱好者
算法是程序员的内功!伯乐在线旗下账号「算法爱好者」专注分享算法相关文章、工具资源和算法题,帮程序员修炼内功。
今天看啥  ›  专栏  ›  算法爱好者

NP 完全性理论与近似算法

算法爱好者  · 公众号  · 算法  · 2018-06-13 22:59
(点击上方公众号,可快速关注)来源:独酌逸醉www.cnblogs.com/chinazhangjie/archive/2010/12/06/1898070.html一、图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一个计算步可实现下面3个操作之一或全部。改变有限状态控制器中的状态。清除当前读写头下的方格中原有带符号并写上新的带符号。独立地将任何一个或所有读写头,向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。k带图灵机可形式化地描述为一个7元组(Q,T,I,δ,b,q0,qf),其中: Q是有限个状态的集合。T是有限个带符号的集合。I是输入符号的集合。b是唯一的空白符,b∈T-I。q0是初始状态。      qf是终止(或接受)状态。δ是移动函数。它是从Q×Tk的某一子集映射到Q×(T ………………………………

原文地址:访问原文地址
快照地址: 访问文章快照